Какую оптимизацию выполняет компилятор для моего метода обращения строк с классическим обменом?
Справочная информация
Я прочитал этот вопрос о том, как перевернуть строку как можно быстрее. Я обнаружил, что один из ответов сравнивал разные методы. В одном из них они просто запускают цикл, меняя элементы с позиции i с одним в положении string.Length-1-i но они используют известный хитрый обмен через XOR. Мне было интересно, как быстрее изменить строку, используя своп через XOR, по сравнению с тем же методом, использующим классический своп через временную переменную. Удивительно, но я получаю улучшение почти на 50% по сравнению с XOR.
Вопрос
Компилятор делает что-то волшебное за кулисами, почему я получаю этот результат?
Модифицированный код с бенчмарками
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ContestLibrary
{
public class Problem
{
delegate string StringDelegate(string s);
static void Benchmark(string description, StringDelegate d, int times, string text)
{
Stopwatch sw = new Stopwatch();
sw.Start();
for (int j = 0; j < times; j++)
{
d(text);
}
sw.Stop();
Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
}
public static string ReverseXor(string s)
{
char[] charArray = s.ToCharArray();
int len = s.Length - 1;
for (int i = 0; i < len; i++, len--)
{
charArray[i] ^= charArray[len];
charArray[len] ^= charArray[i];
charArray[i] ^= charArray[len];
}
return new string(charArray);
}
public static string ReverseClassic(string s)
{
char[] charArray = s.ToCharArray();
int len = s.Length-1;
for (int i = 0; i < len; i++, len--)
{
char temp = charArray[len];
charArray[len] = charArray[i];
charArray[i] = temp;
}
return new string(charArray);
}
public static string StringOfLength(int length)
{
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++)
{
sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
}
return sb.ToString();
}
static void Main(string[] args)
{
int[] lengths = new int[] {1,10,100,1000, 10000, 100000};
foreach (int l in lengths)
{
int iterations = 10000;
string text = StringOfLength(l);
Benchmark(String.Format("Classic (Length: {0})", l), ReverseClassic, iterations, text);
Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);
Console.WriteLine();
}
Console.Read();
}
}
}
3 ответа
Причина очень проста, давайте проверим, сколько операций в IL-коде имеет каждая функция. Но сначала давайте посмотрим на реальную разницу во времени обеих функций. Вы сказали, что функция XOR почти на 50% медленнее, чем другие, когда я запускаю код в режиме отладки, у меня есть такие результаты, но вы должны запустить код в режиме выпуска, чтобы полностью позволить оптимизатору выполнять свою работу:). В режиме выпуска функции XOR работают почти в 3 раза медленнее.
Изображения имеют IL-код части внутри цикла for, то есть единственной части, которая изменяется.
Первое изображение - это функция с переменной temp
Второе изображение - функция с XOR
Как вы можете видеть, разница в количестве инструкций огромна, 14 против 34. 3-кратная разница во времени происходит от некоторых операций, таких как conv.u2, которые немного дороги.
Я согласен с Гарольдом. Обмен XOR не быстрее, чем использование временной переменной.
Я думаю, что миф о перестановке XOR восходит к тем дням, когда выделение памяти для новых переменных было трудоемкой работой.
Первоначально я думал, что есть вероятность, что это может быть связано с типом, и, возможно, с использованием XOR swap в int массивы дали бы лучшие результаты, чем на char массивы, так что я построил на вашем тесте один для int массивы просто в текст - получается те же результаты (более или менее) для int Обмен XOR происходит медленнее, чем использование временной переменной.
Обновить:
Как написал Damien_The_Unbeliever в своем комментарии к вашему вопросу, ответ Р. Мартиньо Фернандеса на вопрос, с которым вы связались, на самом деле является единственным ответом на первой странице, который правильно меняет строку, даже с языками, отличными от английского.
На самом деле, основываясь на этом ответе и одном из его комментариев, я написал метод расширения для правильного обращения строки.
На моем родном языке (иврите) у нас есть все виды точек и символов для указания гласных и простой реверс массива (или IEnumerable) делает это неправильно, как во французском примере.
Это значительно медленнее, чем обычная реализация на основе свопа (и примерно в 10 раз медленнее, чем своп на основе XOR), но я вряд ли думаю, что это будет проблемой, так как реверсирование строки - это не то, что вы делаете очень часто, и реверсирование многих строк в тугие петли еще меньше.
Протестировано на основе вашего метода бенчмарка, реверсирование 10000 строк длиной 10000 с помощью этого метода заняло примерно 13,5 секунд.
Если кто-нибудь когда-нибудь напишет программу, которая на самом деле должна делать так много реверсов для таких длинных строк, я был бы очень удивлен.
Итак, вот моя международная реализация безопасной обратной строки, я надеюсь, что кто-то выиграет от этого:
public static string Reverse(this string source)
{
if (string.IsNullOrEmpty(source))
{
return source;
}
var info = new StringInfo(source);
var sb = new StringBuilder();
for (int i = info.LengthInTextElements - 1; i > -1; i--)
{
sb.Append(info.SubstringByTextElements(i, 1));
}
return sb.ToString();
}
Вы можете проверить ниже код с Array.Reverse, Это будет более эффективным, чем другие подходы, которые вы упомянули, Array.Reverseизначально кодируется, и его очень просто поддерживать и понимать.
public static string ReverseArray(string text)
{
if (text == null) return null;
char[] array = text.ToCharArray();
Array.Reverse(array);
return new String(array);
}
Ниже приведен полный код для демонстрации,
строка делегата StringDelegate(строка s);
static void Benchmark(string description, StringDelegate d, int times, string text)
{
Stopwatch sw = new Stopwatch();
sw.Start();
for (int j = 0; j < times; j++)
{
d(text);
}
sw.Stop();
Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
}
public static string ReverseArray(string text)
{
if (text == null) return null;
// this was posted by petebob as well
char[] array = text.ToCharArray();
Array.Reverse(array);
return new String(array);
}
public static string ReverseXor(string s)
{
char[] charArray = s.ToCharArray();
int len = s.Length - 1;
for (int i = 0; i < len; i++, len--)
{
charArray[i] ^= charArray[len];
charArray[len] ^= charArray[i];
charArray[i] ^= charArray[len];
}
return new string(charArray);
}
public static string ReverseClassic(string s)
{
char[] charArray = s.ToCharArray();
int len = s.Length-1;
for (int i = 0; i < len; i++, len--)
{
char temp = charArray[len];
charArray[len] = charArray[i];
charArray[i] = temp;
}
return new string(charArray);
}
public static string StringOfLength(int length)
{
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++)
{
sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
}
return sb.ToString();
}
static void Main(string[] args)
{
int[] lengths = new int[] { 1, 10, 100, 1000, 10000, 100000 };
foreach (int l in lengths)
{
int iterations = 10000;
string text = StringOfLength(l);
Benchmark(String.Format("Classic (Length: {0})", l), ReverseClassic, iterations, text);
Benchmark(String.Format("Array (Length: {0})", l), ReverseArray, iterations, text);
Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);
Console.WriteLine();
}
Console.Read();
}
Примечание: я исправил твой код, чтобы поменять строку, она была неверно изменена как твое сообщение