5 способов сравнить два байтовых массива. Сравнительное тестирование

секундомерВ результате профилирования моей софтины я сделал вывод о необходимости оптимизации функции сравнения буферов.
Т.к. CLR не предоставляет стандартного способа сравнить два куска памяти, то функция была написан на скорую руку самостоятельно (лишь бы работало).
Погуглив по фразе «Best Way to Compare Byte Arrays in .Net», я пришёл в замешательство: в абсолютном большинстве случаев люди предлагали использовать либо LINQ, либо Enumerable.SequenceEqual(), что практически одно и тоже. Даже на StackOverflow это был самый популярный ответ. Т.е. катастрофически популярно заблуждение вида:

«Compiler\run-time environment will optimize your loop so you don't need to worry about performance.» Отсюда.

Именно оно впервые навело меня на мысль написать этот пост.
Я провёл сравнительное тестирование пяти способов сравнения буферов, доступных из C#, и на основании результатов тестирования дал рекомендации в выборе способа.
Кроме того, я декомпилировал некоторые функции, и проанализировал код, генерируемый JIT-компилятором для конфигурации x86, а так же сравнил машинный код, генерируемый JIT-компилятором, с машинным кодом функции CRT аналогичного назначения.


Предыстория


Написав очередную утилиту и добившись её работоспособности, я запустил профайлер и увидел, что огромный процент времени занимает сравнение массивов байтов.
Функция CompareByteArrays() лежала на критическом пути, и с этим надо было что-то делать.
Алгоритмическогоко решения проблемы производительности я не видел: алгоритмы подбирались заранее, и никаких идей о том, как уменьшить итоговую сложность, у меня не возникло.
Результаты поиска во всемируной паутине не очень порадовали: сравнения скорости методов были, но как были получены эти цифры, на каких данных и в каких услових никто написать не удосужился.
У меня были свои предположения на тему того, кто и в каких условиях окажется быстрее. Я решил проверить.
Результаты получились интересными, так что мысль о посте сюда окончательно созрела.

Что и чем я тестировал


Главное


Код компилировался и запускался на машине с Windows 7 x64 со всеми последними обновлениями для .Net 4.0 Client Profile, т.е. с настройками Microsoft Visual Studion 2010 по умолчанию, и только для конфигурации x86, т.е. это 32-битный код. Во-первых, потому что большая часть кода, с которой я сталкиваюсь, написана для 32-битных систем. Во-вторых, я считаю, что для .Net крайне важна производительность именно в этой конфигурации. В частности, потому, что огромный объём уже существующих компонентов написан для 32-бит, и переписывать их никто не будет, а с ними нужно взаимодействовать, т.е. они определят конфигурацию конечного приложения. Во-вторых, крайне малому числу приложений действительно нужно 64 бита – необходимая разрядность определяется в первую очередь требованиями к памяти и целевой платформой. Современные 64-разрядные x86-совместимые процессоры аппаратно поддерживают 32-битные задачи [1][2]. Логично, что Windows x64 эту возможность использует, исполняя 32-битный код напрямую [3]. Компиляция изначально 32-битного приложения в 64 бита умножает необходимую для него память и снижает его производительность, потому что опции компилятора размер TLB процессора не меняют, кэш первого уровня — тоже, а размер указателя удваивают, что в свою очередь ещё и необходимую границу выравнивания данных изменяет [4].

Размеры данных


В моей изначальной задаче требовалось сравнивать байтовые массивы размером 16 байт и размерами от 1 до 4*1024 байт. 16 байт — размер MD5, 4 Kb — размер стандартной страницы памяти в Windows, поэтому он был выбран для буфера ввода-вывода.
Однако тестировал сравнение я на блоках от 1 байта до 1/2 мегабайта, по той простой причине, что хэши бывают размером не только 16 байт, но и 4, и даже 2 байта (CRC16, CRС32), а страницы памяти не только по 4 килобайта, но и 2 МБ[2] и даже 4 МБ. Результаты, показанные на блоках 1/2 MB, оказались достаточны, чтобы делать вывод о работе с блоками больших размеров, к тому же моё время не безгранично (в процессе тестирования компьютер лучше не трогать, чтобы не отнимать время у описываемого процесса).

Исходя из результатов первых прогонов, я счёл достаточным сравнение методов на 25 различных размерах тестовых данных. Для этого я построил цикл тестирования таким образом, чтобы первый тестовый набор состоял из массивов размером 1 байт, а на каждом следующем шаге размер тестовых массивов умножался на одинаковый множитель.

Параметры задавались константами в коде:
        private const int CountArrays = 128; //Количество сравниваемых тестовых наборов
        private const int StartArraySize = 1; //Стартовый размер тестового набора
        private const int MaxArraySize = 512 * 1024; //Максимальный размер тестового набора
        private const int StepsCount = 25; //Количество шагов

        private const int MeasurementsCount = 10; //Количество измерений


Основной цикл тестирования выглядел вот так:
         double sizeMultiplier = 1;
         DoInvestigationStep(sizeMultiplier);

         const int MaxMultiplier = MaxArraySize / StartArraySize;
         var stepMmltiplier = Math.Pow( MaxMultiplier, 1 / (double)StepsCount );
         for (var step = 1; step <= StepsCount; step++)
         {
            sizeMultiplier = Math.Pow(stepMmltiplier, (double) step);
            DoInvestigationStep(sizeMultiplier);
         }


Размер массива на каждом шаге вычислялся вот так:
         var arraySize = (int) (StartArraySize * p_SizeMultiplier);


Протестированные методы



Использование интерфейса System.Collections.IStructuralEquatable


Это относительно новый для C# способ, он появился только в .NET 4, поэтому он представлял для меня особый интерес: любопытно было, насколько он всё-таки медленный.
      private static bool ByteArrayCompareWithIStructuralEquatable(byte[] p_BytesLeft, byte[] p_BytesRight)
      {
         IStructuralEquatable eqa1 = p_BytesLeft;
         return eqa1.Equals(p_BytesRight, StructuralComparisons.StructuralEqualityComparer);
      }


LINQ, а точнее Enumerable.SequenceEqual()


Это один из самых простых методов, самый простой для реализации. Кроме того, это самый популярный метод.
      private static bool ByteArrayCompareWithSequenceEqual(byte[] p_BytesLeft, byte[] p_BytesRight)
      {
         return p_BytesLeft.SequenceEqual(p_BytesRight);
      }


PInvoke, для CRT функции memcmp()


Теоретически, это должен быть самый быстрый способ, но выяснилось, что это не всегда так: накладные расходы на взаимодействие с платформой съедают довольно большое время, и этот метод в некоторых случаях теряет свою привлекательность.
Здесь я привожу его в тмо виде, в котором нашёл его на SO. Именно в таком виде я его и тестировал.
На PInvoke.net он выглядит несколько иначе.
      [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
      private static extern int memcmp(byte[] p_BytesLeft, byte[] p_BytesRight, long p_Count);

      private static bool ByteArrayCompareWithPInvoke(byte[] p_BytesLeft, byte[] p_BytesRight)
      {
         // Validate buffers are the same length.
         // This also ensures that the count does not exceed the length of either buffer.  
         return p_BytesLeft.Length == p_BytesRight.Length
                    && memcmp(p_BytesLeft, p_BytesRight, p_BytesLeft.Length) == 0;
      }


В лоб. Т.е. прямое сравнение байтов в цикле for(;;)


Это самый очевидный способ сравнить два массива, именно поэтому он представляет интерес.
Изначально метод казался не слишком быстрым, но оказалось, что для многих ситуаций он вполне приемлем.

Кстати, одна из вариаций этого метода сравнения была использована в статье от самих Производителей СLR, притом именно в том котексте, в котором она понадобилась мне.
Видимо, пользователи их доканали такими вопросами.
      private static bool ByteArrayCompareWithSimplest(byte[] p_BytesLeft, byte[] p_BytesRight)
      {
         if (p_BytesLeft.Length != p_BytesRight.Length)
            return false;

         var length = p_BytesLeft.Length;

         for (int i = 0; i < length; i++)
         {
            if (p_BytesLeft[i] != p_BytesRight[i])
               return false;
         }

         return true;
      }


Оптимизированный unsafe-метод от Хафора Стефансона


Автор метода утверждает, что этот оптимизированный метод делает сравнение блоками размером 64 бита для возможно большей части массива, рассчитывая на то, что начало массива выравнено по границе QWORD. Он также будет работать, если нет QWORD-выравнивания, но с меньшей скоростью.
Однако, в 32 битной среде сравнения блоками в 64 бита можно добиться только с помощью ассемблера: регистры общего назначения 32 битные, а компилятор при генерации машинного кода, использует именно их.
Так что, как этот метод дейсвтительно будет работать, зависит от того как он будет скомпилирован. В моём случае — точно не 64 бита.
      // Copyright (c) 2008-2013 Hafthor Stefansson
      // Distributed under the MIT/X11 software license
      // Ref: http://www.opensource.org/licenses/mit-license.php.
      private static unsafe bool UnsafeCompare(byte[] a1, byte[] a2)
      {
         if (a1 == null || a2 == null || a1.Length != a2.Length)
            return false;
         fixed (byte* p1 = a1, p2 = a2)
         {
            byte* x1 = p1, x2 = p2;
            int l = a1.Length;
            for (int i = 0; i < l / 8; i++, x1 += 8, x2 += 8)
               if (*((long*) x1) != *((long*) x2))
                  return false;
            if ((l & 4) != 0)
            {
               if (*((int*) x1) != *((int*) x2)) return false;
               x1 += 4;
               x2 += 4;
            }
            if ((l & 2) != 0)
            {
               if (*((short*) x1) != *((short*) x2)) return false;
               x1 += 2;
               x2 += 2;
            }
            if ((l & 1) != 0)
               if (*((byte*) x1) != *((byte*) x2))
                  return false;
            return true;
         }
      }


Методика тестирования


Тестовый набор


Чтобы максимально приблизить условия тестирования к боевым и исключить «застревание» тестовых данных в кэше процессора (максимально работать именно с памятью), было решено сгенерировать множество тестовых массивов и сравнивать их друг с другом, т.е. каждый массив с каждым.

В качестве тестового набора был выбран «зубчатый» массив (в оригинальной документации — «Jagged Array»). Было несколько альтернатив, например, List<byte[]> и LinkedList<byte[]>, но альтернативы не устроили временем доступа к элементу, хотя и массив в .NET здесь не блещет: CLR в любом случае проверяет индекс на выход за границы массива, даже если это массив с нулевой базой.

Тестовые данные генерировались таким образом, чтобы отличались все массивы, а отличающийся элемент массива находился ровно посередине.
Генерация тестовых данных
      private static void PrepareTestData(int p_ArraySize)
      {
         for (int i = 0; i < CountArrays; i++)
         {
            var byteArray = new byte[p_ArraySize];
            byteArray[p_ArraySize / 2] = (byte) (i & 0x000000ff);

            s_arrays[i] = byteArray;
         }
      }



Выполнение сравнений


Так как все массивы предполагалось сравнивать со всеми, то общий вид метода, время исполнения которого измерялось, представляет собой два вложенных цикла по всем массивам набора, а внутри них вызывается испытуемый метод. Суть происходящего можно выразить кодом:
         for (int i = 0; i < CountArrays; i++)
            for (int j = 0; j < CountArrays; j++)
               Compare( s_arrays[i], s_arrays[j] );

Однако тут есть одно «но»: если никак не использовать результат «вычислений», то CLR имеет полное право само «вычисление» не производить. Я с этим сталкивался раньше, когда экспериментировал с C++. При включенной оптимизации «-O3» было весьма проблематично что-либо измерить, т.к. время раз за разом получалось нулевым. Поэтому такой сценарий было решено исключить с самого начала, так что результат работы функции сравнения «аккумулировался» и возвращался, а на самом верхнем уровне анализировался.
Сравнение без игнорирования результата
         var result = true;
         for (int i = 0; i < CountArrays; i++)
            for (int j = 0; j < CountArrays; j++)
            {
               var tmp = Compare( s_arrays[i], s_arrays[j] );

               result = result && tmp;
            }
         return result;


Анализ результата сравнения
         var stubLocalVar = p_СomparisonMethod();
         if (stubLocalVar)
            throw new InvalidOperationException();



Поскольку методов сравнений 5, а вышеописанный шаблон общий, то кажется логичным определить общий, «шаблонный» метод, и передать метод сравнения в него. Таким образом:
Неправильный метод вызова функций
      private static bool CompareArraysWithExternalMethod(Func<byte[], byte[], bool> p_Method)
      {
         var result = true;
         for (int i = 0; i < CountArrays; i++)
            for (int j = 0; j < CountArrays; j++)
            {
               var tmp = p_Method( s_arrays[i], s_arrays[j] );

               result = result && tmp;
            }
         return result;
      }


Такой способ, безусловно, исключает копирование/вставку и уменьшает вероятность ошибки, но в то же время создаёт излишнюю косвенность вызова и исключает встраивание метода (inlining), что, в свою очередь, приводит к потере точности измерений, особенно учитывая, что вызовов много. Именно поэтому мне пришлось создать пять практически одинаковых методов:
      private static bool CompareArraysWithUnsafeMethod();
      private static bool CompareArraysWithSimplestMethod();
      private static bool CompareArraysWithSequenceEqualMethod();
      private static bool CompareArraysWithPInvokeMethod();
      private static bool CompareArraysWithIStructuralEquatableMethod();

Однако уровнем выше я уже мог применить шаблонный метод.

Из приведённого ниже кода видно, что функция MeasureComparisonTime(), в которой измеряется время выполнения метода сравнения, принимает в качестве параметра делегат типа Func. Именно его время выполнения и измеряется.

Функции, производящие измерение метода
      private static long GetMinimalMesuredValue(int p_MeasurementNumber, long p_PreviousValue,
                                                 long p_MeasuredValue)
      {
         var result = p_MeasurementNumber == 0
                            ? p_MeasuredValue
                            : Math.Min(p_PreviousValue, p_MeasuredValue);
         return result;
      }

      private static long MeasureComparisonTime(Func<bool> p_Method, long p_PreviousTime,
                                                int p_MeasurementNumber)
      {
         GC.Collect();
         GC.Collect();

         s_stopwatch.Start();
         var stubLocalVar = p_Method();
         s_stopwatch.Stop();

         if (stubLocalVar)
            throw new InvalidOperationException();

         var result = GetMinimalMesuredValue(p_MeasurementNumber, p_PreviousTime, s_stopwatch.ElapsedTicks);
         s_stopwatch.Reset();

         return result;
      }



Методика измерений


Измерение времени производилось с помощью штатного секундомера ( класс System.Diagnostics.Stopwatch), в основе которого лежит QueryPerformanceCounter(). Естественно, интересовали не миллисекунды, а тики: в случае крохотных массивов все измерения в миллисекундах были бы нулевыми. Также была идея задействовать свой «велосипед» на основе RDTSC[6], но, во-первых, несколько первых прогонов показали, что для текущей методики точности вполне хватает, а во-вторых, предупреждение о необходимости использования ProcessThread.ProcessorAffinity, которое появилось в последних версиях документации, позволяет предположить, что в основе работы этого класса лежит вышеупомянутый счётчик тактов процессора. Все измерения повторялись 10 раз, и бралось лучшее время. Число 10 было подобрано экспериментально, как дающее достаточно точные результаты при минимальных затратах времени.
Функция, производящая все измерения
      private static MeasurementsResults DoMeasurements()
      {
         MeasurementsResults result;
         result.SimplestTime = 0;
         result.SequenceEqualTime = 0;
         result.PInvokeTime = 0;
         result.IStructuralEquatableTime = 0;
         result.UnsafeTime = 0;

         for (int measurementNumber = 0; measurementNumber < MeasurementsCount; measurementNumber++)
         {
            Console.WriteLine("Стартует измерение номер {0}", measurementNumber);

            result.SimplestTime = MeasureComparisonTime(CompareArraysWithSimplestMethod,
                                                        result.SimplestTime,
                                                        measurementNumber);

            result.SequenceEqualTime = MeasureComparisonTime(CompareArraysWithSequenceEqualMethod,
                                                             result.SequenceEqualTime,
                                                             measurementNumber);

            result.PInvokeTime = MeasureComparisonTime(CompareArraysWithPInvokeMethod,
                                                       result.PInvokeTime,
                                                       measurementNumber);

            result.IStructuralEquatableTime = MeasureComparisonTime(CompareArraysWithIStructuralEquatableMethod,
                                                                    result.IStructuralEquatableTime,
                                                                    measurementNumber);

            result.UnsafeTime = MeasureComparisonTime(CompareArraysWithUnsafeMethod,
                                                      result.UnsafeTime,
                                                      measurementNumber);
         }

         return result;
      }



Результаты измерений и первые выводы


Перед началом эксперимента я примерно догадывался, какой метод окажется победителем, а какой аутсайдером, однако результаты меня всё-таки удивили. Мои прогнозы оказались не совсем верны.
Лучшее время (тики) Размер массива (байты) unsafe В лоб PInvoke SequenceEqual IStructuralEquatable
276
1
1,7
1
6
10,5
55
276
1
1,7
1
6,3
10,1
55,7
325
2
1,3
1
5,3
11
95,2
374
4
1,1
1
4,8
11,4
121,3
413
8
1
1,3
5
14,1
181,2
412
13
1
1,7
4,7
17,5
252,5
490
23
1
2,3
3,7
22,1
364,8
554
39
1
3,4
3,5
30,1
535,9
691
67
1
4,3
2,9
39,1
727,5
887
114
1
5,6
2,4
50,3
964,1
1212
194
1
4,6
2,1
61,5
1190,9
1875
328
1
4,8
1,8
65,8
1295,8
2897
556
1
5
1,6
71,5
1416,9
4565
942
1
5,3
1,4
76,3
1521,1
7711
1595
1
5,2
1,3
76,2
1521,2
12482
2702
1
5,4
1,3
79,4
1593,6
20692
4576
1
5,5
1,2
81,2
1626,2
34369
7750
1
5,6
1,2
82,8
1657,1
58048
13124
1
5,6
1,2
82,9
1661,9
97511
22226
1
5,6
1,2
83,6
1677,3
173805
37640
1
5,4
1,1
79,5
1585,7
295989
63743
1
5,3
1,1
79,3
1574,9
588797
107949
1
4,6
1,1
67,5
1340,9
1010768
182811
1
4,6
1,1
67
1340,4
1705668
309590
1
4,6
1,1
67,3
1334,1
2885452
524287
1
4,6
1,1
67,3
1329,1


Результаты удивили следующим:
Первое: CRT функция просто обязана быть хорошо оптимизирована, и я рассчитывал, что на определённом этапе (размере тестового массива) её скорость перекроет накладные расходы (overhead) платформенного вызова, но этого не произошло. Позже я повторил тестирования с массивами значительно большего размера, но даже на 1.5 мегабайтах unsafe-код оказывался быстрее.

Второе: я догадывался, что IStructuralEquatable окажется медленным, но цифры меня просто поразили: такого я точно не ожидал.

Диазассемблирование и анализ отдельных функций


Столь серьёзная разница между unsafe и Simplest на больших массивах (я ожидал не более двух-трёхкратного «перевеса») позволяет предположить, что с оптимизацией циклов и обращений к элементам массива в .Net не всё так гладко, как утверждают приверженцы .Net. Соответственно, я не отказал себе в удовольствии посмотреть на результаты работы JIT'ера, т.е. на непосредственно генерируемый машинный код.

Анализ функции CompareArraysWithSimplestMethod()


Для этого в начало метода был вставлен Thread.Sleep(60 * 1000); после запуска релизной сборки я подцепился к процессу OllyDebug'ом. Такой хитрый ход нужен был для того, чтобы ни в коем случае не порушить оптимизации CLR — увидеть картину такой, какая есть.

Скриншот окна отладчика со стрелочками

Спустившись вниз по стеку вызовов от ntdll.NtDelayExecution() и SleepEx(), я нашёл свою функцию и, после её внимательного изучения, был в очередной раз неприятно удивлён. Что мне здесь очень не понравилось:
  1. Вместо единственной проверки RngChkFail (для всего цикла сразу), CLR делает эту проверку для каждого индекса!!!
  2. Цикл остался в том виде, в котором я его написал: компилятор не стал его «разворачивать».
  3. Поэтому сравнение так и осталось побайтным, хотя CLR вполне по силам было его оптимизировать, например, сделав сравнение по 4 байта (размер регистра).
  4. Вместо единственного return'а c единственным эпилогом и очисткой стека, CLR скопировал их три раза, благодаря чему код «опух». Фактически машинный код повторяет код на C# почти один в один. В связи с этим возникает вопрос: а он вообще оптимизировал код?! Он умеет это делать?
  5. Вероятно, благодаря предыдущему пункту (опухший код), функция не была заинлайнена.


Анализ функции UnsafeCompare()


Результат декомпиляции этой функции разжёг моё любопытство и навёл на мысль об остальных функциях. Я решил сравнить CRT-функцию и unsafe-вариант. Сперва я решил посмотреть на unsafe-вариант. Для этого я проделал те же операции, что и для первой функции, за исключением того, что Thread.Sleep() вставил не в саму функцию, а перед её вызовом. Это вряд ли могло как-либо повлиять на суть происходящего, но несколько упростило декомпиляцию: unsafe-функция явно сложнее первой.
Место вставки Thread.Sleep()
      private static bool CompareArraysWithUnsafeMethod()
      {
         var result = true;
         for (int i = 0; i < CountArrays; i++)
            for (int j = 0; j < CountArrays; j++)
            {
               Thread.Sleep( 60 * 1000 );
               var tmp = UnsafeCompare(s_arrays[i], s_arrays[j]);



Интерес также представляет первая половина этой функции, т.е. до момента вызова UnsafeCompare(). Она, так же, как и первая, демонстрирует, что любое обращение к элементу массива вызывает проверку индекса на вхождение в границы массива. Я подчеркнул это в листинге.
CPU Disasm CompareArraysWithUnsafeMethod
;Address   Hex dump          Command                                 Comments
001B0B88    55              push    ebp                             ; Стандартный пролог
001B0B89    8BEC            mov     ebp, esp                        

001B0B8B    57              push    edi                             
001B0B8C    56              push    esi                             
001B0B8D    53              push    ebx                             
                                                                    
001B0B8E    BF 01000000     mov     edi, 1                          ; result = true;
                                                                    
001B0B93    33DB            xor     ebx, ebx                        ; for (int i = 0;
001B0B95    33F6            xor     esi, esi                        ; for (int j = 0;
                                                                    
001B0B97    B9 60EA0000     mov     ecx, 0EA60                      ; Thread.Sleep( 60 * 1000 );
001B0B9C    E8 0CFBC161     call    clr.ThreadNative::Sleep         
                                                                    
001B0BA1    8B15 A8337A03   mov     edx, [s_arrays]                 ; EDX  <-- s_arrays
001B0BA7    3B5A 04         cmp     ebx, [edx+4]                    ; Compare(s_arrays.Length, первый индекс) (1) !!!
001B0BAA    73 31           jae     short stub_CLR.JIT_RngChkFail   
                                                                    
001B0BAC    8B4C9A 0C       mov     ecx, [ebx*4+edx+0C]             ; ECX <-- s_arrays[i]
                                                                    
001B0BB0    3B72 04         cmp     esi, [edx+4]                    ; Compare(s_arrays.Length, второй индекс) (2) !!!
001B0BB3    73 28           jae     short stub_CLR.JIT_RngChkFail   
                                                                    
001B0BB5    8B54B2 0C       mov     edx, [esi*4+edx+0C]             ; EDX <-- s_arrays[j]
001B0BB9    FF15 F0381400   call    near UnsafeCompare			   



Результат декомпиляции функции оказался довольно большим и на один экран не помещался, поэтому я не стал приводить скриншот окна дебагера. Так как большой цельный листинг читать утомительно и непродуктивно, то здесь я привожу его логически объединёнными кусками, сопровождая каждый кусок кратким комментарием.
UnsafeCompare().ParametersChecking
;a1 ========> ECX
;a2 ========> EDX

;Address   Hex dump          Command                Comments
001B0BF8    55              push    ebp            ; Стандартный пролог
001B0BF9    8BEC            mov     ebp, esp
       
001B0BFB    57              push    edi            ; сохранение регистров в стеке нужно, вероятно, затем, чтобы
001B0BFC    56              push    esi            ; использовать их в дальнейшем
001B0BFD    53              push    ebx            ;
                                                   
001B0BFE    83EC 0C         sub     esp, 0C        ; вершина стека выше сохранённых регистров на 3*sizeof(DWORD), т.е. будет 3 переменных
                                                   
001B0C01    33C0            xor     eax, eax       ;                      (!)
001B0C03    8945 F0         mov     [ebp-10], eax  ; var1 <-- 0           (!)
001B0C06    8945 EC         mov     [ebp-14], eax  ; var2 <-- 0           (!)
                                                   
001B0C09    85C9            test    ecx, ecx       ; Compare(a1, null)
001B0C0B    74 0C           je      short return1 
                                                   
001B0C0D    85D2            test    edx, edx       ; Compare(a2, null)
001B0C0F    74 08           je      short return1 
                                                   
001B0C11    8B41 04         mov     eax, [ecx+4]   ; eax <-- a1.Length
001B0C14    3B42 04         cmp     eax, [edx+4]   ; Compare(eax, a2.Length)
001B0C17    74 0A           je      short argsIsValid 

return1:
001B0C19    33C0            xor     eax, eax       ; result <-- 0
001B0C1B    8D65 F4         lea     esp, [ebp-0C]  

001B0C1E    5B              pop     ebx            
001B0C1F    5E              pop     esi            
001B0C20    5F              pop     edi            

001B0C21    5D              pop     ebp            
001B0C22    C3              ret

argsIsValid:
; Часть кода опущена



В соответствии с соглашением вызова fastcall, которому следует .NET Framework [7][8], в регистрах ecx и edx находятся первый и второй параметры, в соответствии с порядком слева направо. В приведённом листинге хорошо видна последовательная проверка входных параметров, он почти однозначно соответствует коду на C#
         if (a1 == null || a2 == null || a1.Length != a2.Length)
            return false;

Однако, особого внимания заслуживают выделенные строки: назначение их неясно, и они запутывают. Чтобы понять, что это такое и зачем оно может быть нужно, мне пришлось поставить ещё один эксперимент, в ходе которого я написал простейшую unsafe-функцию на C#, которая использует предложение fixed и обращение по указателю, и провёл с ней аналогичные действия.
      private static unsafe int func1(byte[] param1)
      {
         fixed (byte* p = param1)
         {
            return *p;
         }
      }


Дизасм простейшей Unsafe функции

;param1 ========> ECX

Address   Hex dump          Command                                  Comments
$ ==>       55              push    ebp                              ; Стандартный пролог
$+1         8BEC            mov     ebp, esp

$+3         50              push    eax                              ;                                 (!)
$+4         33C0            xor     eax, eax                         ;                                 (!)
$+6         8945 FC         mov     [ebp-4], eax                     ; var1 <-- 0                      (!)

$+9         85C9            test    ecx, ecx                         ; Compare(param1, null)
$+B         74 06           je      short param_is_null

$+D         8379 04 00      cmp     dword ptr [ecx+4], 0             ; Compare(param1.Length, 0)
$+11        75 07           jne     short not_zero_len

param_is_null:
$+13        33D2            xor     edx, edx
$+15        8955 FC         mov     [ebp-4], edx                    ; var1 <-- 0
$+18        EB 0C           jmp     short ret_1

not_zero_len:
$+1A        8379 04 00      cmp     dword ptr [ecx+4], 0
$+1E        76 10           jbe     short call.JIT_RngChkFail

$+20        8D49 08         lea     ecx, [ecx+8]                    ; ecx <-- param1.BufferPointer
$+23        894D FC         mov     [ebp-4], ecx                    ; var1 <-- ecx

ret_1:
$+26        8B45 FC         mov     eax, [ebp-4]                    ; eax <-- var1
$+29        0FB600          movzx   eax, byte ptr [eax]             ; eax <-- *eax

$+2C        8BE5            mov     esp, ebp                        ; Стандартный эпилог
$+2E        5D              pop     ebp

$+2F        C3              ret

call.JIT_RngChkFail:
$+30        E8 B3BDC861     call    clr.JIT_RngChkFail
$+35        CC              int3	  



Из приведённого листинга становится понятным, что в результате JIT-компиляции переменная в предложении fixed обязательно помещается в стек, вне зависимости от доступности регистров общего назначения. Это хорошо видно из того факта, что регистр eax был сохранён в стеке, в дальнейшем не использовался и, следовательно, был свободным и доступным для операций (до смещения 0x26 от начала функции), но под хранение временных данных была использована стековая переменная по смещению [ebp-4] (назовём её var1). Переменная сразу же обязательно инициализируется нулём, несмотря на то, что потом это значение не используется, а просто затирается. Например, по смещению 0x15 в var1 снова заносится ноль, несмотря на то, что там к этому моменту уже хранится ноль.

Таким образом, становится понятным, что никакого особого смысла выделенные строки в листинге UnsafeCompare.CPU Disasm.ParametersChecking не несут, это всего лишь побочный эффект компиляции. Также из вышеприведённого листинга становится очевидным, что проверка массива в выражении fixed производится в три этапа: сначала массив проверяется на равенство null, потом его длина проверяется на равенство нулю (команда jne анализирует только ZF), и только затем на равенство нулю и отрицательность значения (jbe проверяет и ZF и CF). С моей точки зрения весьма странно, что последние два действия не были объединены в одно, и тем более странно, что команда cmp выполняется дважды, ведь условный переход не сбрасывает флаги. Кроме всего прочего, я искренне благодарен тем из вас, кто прочитал эту строку, потому что это означает, что я не зря старался, и мои раскопки в ассемблерных листингах были не напрасны.

Проведённый эксперимент значительно упрощает дальнейший анализ кода.

Предложение fixed из функции CompareArraysWithUnsafeMethod()
argsIsValid:

001B0C23    8379 04 00      cmp     dword ptr [ecx+4], 0       ; Compare(a1.Length, 0) это первая проверка длины первого массива
001B0C27    75 07           jne     short a1Len_NonZero        ; только неравенство

001B0C29    33C0            xor     eax, eax
001B0C2B    8945 F0         mov     [ebp-10], eax              ; var1 <-- 0
001B0C2E    EB 10           jmp     short a1Len_Zero


a1Len_NonZero:
001B0C30    8379 04 00      cmp     dword ptr [ecx+4], 0       ; Compare(a1.Length, 0) вторая (последняя) проверка длины первого массива
001B0C34    0F86 B5000000   jbe     call.JIT_RngChkFail        ; если равно или меньше

001B0C3A    8D41 08         lea     eax, [ecx+8]               ; eax <-- a1.BufferPointer
001B0C3D    8945 F0         mov     [ebp-10], eax              ; var1 <-- eax


a1Len_Zero:
001B0C40    837A 04 00      cmp     dword ptr [edx+4], 0       ; Compare(a2.Length, 0) это первая проверка длины второго массива
001B0C44    75 07           jne     short a2Len_NonZero        ; только неравенство

001B0C46    33D2            xor     edx, edx
001B0C48    8955 EC         mov     [ebp-14], edx              ; var2 <-- 0
001B0C4B    EB 10           jmp     short part3


a2Len_NonZero:
001B0C4D    837A 04 00      cmp     dword ptr [edx+4], 0       ; Compare(a2.Length, 0) вторая (последняя) проверка длины второго массива
001B0C51    0F86 98000000   jbe     call.JIT_RngChkFail        ; если равно или меньше

001B0C57    8D52 08         lea     edx, [edx+8]               ; edx <-- a2.BufferPointer
001B0C5A    8955 EC         mov     [ebp-14], edx              ; var2 <-- edx



Никаких сюрпризов компилятор здесь не преподнёс, т.е. алгоритм компиляции даёт легко предсказуемые результаты. Например, переменные, инициализируемые в предложении fixed, в любом случае размещаются в стеке.
Инициализация переменных внутри блока fixed:
part3:
; ECX              <======= a1
; EDX              <======= a2.BufferPointer
; var1             <======= a1.BufferPointer
; var2             <======= a2.BufferPointer
001B0C5D    8B45 F0         mov     eax, [ebp-10]              ; eax <-- var1
001B0C60    8BF0            mov     esi, eax                   ; esi <-- eax

001B0C62    8B45 EC         mov     eax, [ebp-14]              ; eax <-- var2
001B0C65    8BF8            mov     edi, eax                   ; edi <-- eax

001B0C67    8B41 04         mov     eax, [ecx+4]               ; eax <-- a1.Length
001B0C6A    8945 E8         mov     [ebp-18], eax              ; var3 <-- eax


Инициализация переменных внутри блока fixed любопытна тем, что хорошо демонстрирует принцип, по которому JIT-компилятор генерирует код. Здесь хорошо видно, что вместо прямой пересылки значений из стековых переменных в индексные регистры, значения сначала помещаются в регистр-аккумулятор. Может быть, в этом и есть какой-нибудь тайный магический смысл, но выглядит это (пересылка в eax) просто как лишнее действие.
Цикл по 8 байт
001B0C6D    33C9            xor     ecx, ecx                   ; счётчик цикла <-- 0

001B0C6F    8BD8            mov     ebx, eax                   ; ebx <-- a1.Length
001B0C71    85DB            test    ebx, ebx
001B0C73    79 03           jns     short ebx_greaterZero
001B0C75    83C3 07         add     ebx, 7                     ; если отрицательно, прибавляем 7
ebx_greaterZero:
001B0C78    C1FB 03         sar     ebx, 3                     ; ebx <-- a1.Length / 8

001B0C7B    85DB            test    ebx, ebx
001B0C7D    7E 1D           jle     short fourBytesComparing


for8_body:
001B0C7F    8B06            mov     eax, [esi]
001B0C81    8B56 04         mov     edx, [esi+4]

001B0C84    3B57 04         cmp     edx, [edi+4]
001B0C87    75 04           jne     short setResult_jumpReturn

001B0C89    3B07            cmp     eax, [edi]
001B0C8B    74 04           je      short for8_increment
setResult_jumpReturn:
001B0C8D    33C0            xor     eax, eax                   ; result <-- 0
001B0C8F    EB 56           jmp     short return2              ; goto return


for8_increment:
001B0C91    41              inc     ecx
001B0C92    83C6 08         add     esi, 8
001B0C95    83C7 08         add     edi, 8
for8_expression:
001B0C98    3BD9            cmp     ebx, ecx
001B0C9A  ^ 7F E3           jg      short for8_body



Структура цикла достаточно тривиальна, например, счётчик цикла традиционно располагается в ecx, граничное значение счётчика располагается в ebx, что тоже традиционно. Примечательно здесь лишь то, что первая проверка условия цикла располагается сразу за инициализацией и выглядит не так, как основное условие цикла. Также очевидно, что чудес не бывает, и префикс REX недоступен ни в Protected Mode, ни в Compatible Mode, т.е. сравнение QWORD-блоками невозможно, поэтому сравниваются блоки размером DWORD. Однако из кода видно, что перед выполнением сравнений в регистры eax, edx загружаются соответствующие части первого массива, т.е. JIT-компилятор попытался произвести машинный код, максимально соответствующий исходному коду.

Бросается в глаза то, что компилятор здесь не стал применять строковую инструкцию CMPSD, а именно, её «короткую» форму, которая выполняет сравнение DWORD-блоков, размещённых по адресам esi и edi, выставляя соответствующие флаги. В этом случае размер машинного кода был бы меньше в несколько раз: команда mov здесь имеет размер 2 и 3 байта, команда cmp – 2 и 3 байта, а размер каждой команды CMPSD (в короткой форме) был бы всего 1 байт, т.е. для двух команд всего 2 байта. Это наводит на мысли о нежелании JIT-компилятора оптимизировать код.

Из приведённых листингов очевидно, что пара команд, первая из которых – пересылка в eax, является паттерном, которому компилятор следует неукоснительно.

Попытка сравнить блоки размером DWORD, выполняется, если такой объём остался:
fourBytesComparing:
001B0C9C    F745 E8 0400000 test    dword ptr [ebp-18], 00000004    ; ZF <-- (var3 & 4) == 0
001B0CA3    74 10           je      short length_lowerThenFour

001B0CA5    8B06            mov     eax, [esi]

001B0CA7    3B07            cmp     eax, [edi]
001B0CA9    74 04           je      short dwords_equals              ; если блоки равны, переход к инкрименту регистров

001B0CAB    33C0            xor     eax, eax
001B0CAD    EB 38           jmp     short return2

dwords_equals:
001B0CAF    83C6 04         add     esi, 4
001B0CB2    83C7 04         add     edi, 4


Попытка сравнить блоки размером WORD, выполняется, если такой объём остался:
length_lowerThenFour:
001B0CB5    F745 E8 0200000 test    dword ptr [ebp-18], 00000002    ; ZF <-- (var3 & 2) == 0
001B0CBC    74 10           je      short length_lowerThenTwo

001B0CBE    0FBF06          movsx   eax, word ptr [esi]

001B0CC1    66:3B07         cmp     ax, [edi]
001B0CC4    74 04           je      short words_equals              ; если блоки равны, переход к инкрименту регистров

001B0CC6    33C0            xor     eax, eax
001B0CC8    EB 1D           jmp     short return2

words_equals:
001B0CCA    46              inc     esi
001B0CCB    46              inc     esi
001B0CCC    47              inc     edi
001B0CCD    47              inc     edi


Попытка сравнить блоки размером BYTE, выполняется, если такой объём остался:
length_lowerThenTwo:
001B0CCE    F745 E8 0100000 test    dword ptr [ebp-18], 00000001   ; ZF <-- (var3 & 1) == 0
001B0CD5    74 0B           je      short 001B0CE2

001B0CD7    0FB606          movzx   eax, byte ptr [esi]

001B0CDA    3A07            cmp     al, [edi]
001B0CDC    74 04           je      short 001B0CE2                 ; если блоки равны, переход к инкрименту регистров

001B0CDE    33C0            xor     eax, eax
001B0CE0    EB 05           jmp     short return2

001B0CE2    B8 01000000     mov     eax, 1


Возврат результата и выброс исключения:
return2:
001B0CE7    8D65 F4         lea     esp, [ebp-0C]
001B0CEA    5B              pop     ebx
001B0CEB    5E              pop     esi
001B0CEC    5F              pop     edi
001B0CED    5D              pop     ebp
001B0CEE    C3              ret

JIT_RngChkFail:
001B0CEF    E8 C4B1DB61     call    clr.JIT_RngChkFail
001B0CF4    CC              int3


Анализ CRT функции memcmp()


Эта функция представляет интерес ещё и потому, что не просто сравнивает два буфера, а выясняет отношение между ними, а значит, она сложнее, чем те, что рассматривались ранее.

После подцепления дебагером я выяснил, что в память процесса по базовому адресу 0x76C20000 была загружена C:\Windows\SysWOW64\msvcrt.dll версии 7.0.7601.17744.

Информационные окошки отладчика

Это важное уточнение, поскольку код разных версий библиотек может сильно отличаться, т.к. они могут быть скомпилированы с разными опциями компилятора, и даже более того, разными компиляторами.

Первый же взгляд на препарируемую функцию меня несколько смутил: во-первых, перед стандартным прологом, в самом начале функции, располагалась странная инструкция, а во-вторых, размеры этой функции поражают воображение. Бросилось в глаза наличие «длинных» джампов, к тому же switch с 32 case’ами устрашает.

Странная инструкция:
76C37975   .  8BFF          mov     edi, edi                                   ; <--(!) Здесь начало функции INT msvcrt.memcmp(buf1,buf2,count)
76C37977   .  55            push    ebp
76C37978   .  8BEC          mov     ebp, esp


Она копирует регистр сам в себя, не обновляя при этом никаких флагов, т.е. результат её выполнения нулевой, прямо как nop, но размером в 2 байта. Промотав код в окне отладчика, я обнаружил, что точно так же начинаются множество других функций. Благодаря блогу Рэймонда Чена объяснение нашлось быстро. Это действительно аналог nop.
It's a hot-patch point.
The MOV EDI, EDI instruction is a two-byte NOP, which is just enough space to patch in a jump instruction so that the function can be updated on the fly. The intention is that the MOV EDI, EDI instruction will be replaced with a two-byte JMP $-5 instruction to redirect control to five bytes of patch space that comes immediately before the start of the function. Five bytes is enough for a full jump instruction, which can send control to the replacement function installed somewhere else in the address space.
blogs.msdn.com/b/oldnewthing/archive/2011/09/21/10214405.aspx


Длинные джампы и очень большой switch
Address   Hex dump              Command                                               Comments
75A9797C   .  8B7D 10           mov     edi, [ebp+10]                                 ; edi <-- length
75A9797F   .  8BC7              mov     eax, edi
75A97981   .  83E8 00           sub     eax, 0                                        ;
75A97984   .  0F84 E7070100     je      msvcrt.zeroResult_GoReturn                     ; (length == 0)=> {result <-- 0, goto return;} (!) Обратите внимание на размер инструкции
; часть кода опущена
; часть кода опущена
75A979BC   .  83FF 1F           cmp     edi, 1F                                       ; Switch (cases 1..1F, 32. exits)
75A979BF   .  77 5B             ja      short msvcrt.75A97A1C
75A979C1   .  FF24BD 1F8AA975   jmp     near [edi*4+msvcrt.75A98A1F]                  ; (!) Джамп на адрес из таблицы переходов (!) Обратите внимание на размер инструкции
; часть кода опущена
; часть кода опущена
75A98A1F   .  1C7AA975          dd      msvcrt.75A97A1C                               ; (00) Начало таблицы переходов, здесь jump на выход из функции
75A98A23   .  E88AA975          dd      msvcrt.75A98AE8                               ; (01)
75A98A27   .  CA8AA975          dd      msvcrt.75A98ACA                               ; (02)
75A98A2B   .  8C8BA975          dd      msvcrt.75A98B8C                               ; (03)
75A98A2F   .  0A7AA975          dd      msvcrt.75A97A0A                               ; (04)
75A98A33   .  088FA975          dd      msvcrt.75A98F08                               ; (05)
75A98A37   .  B88AA975          dd      msvcrt.75A98AB8                               ; (06)
75A98A3B   .  758BA975          dd      msvcrt.75A98B75                               ; (07)
75A98A3F   .  F479A975          dd      msvcrt.75A979F4                               ; (08)
75A98A43   .  238FA975          dd      msvcrt.75A98F23                               ; (09)
75A98A47   .  9F8AA975          dd      msvcrt.75A98A9F                               ; (0A)
75A98A4B   .  A18BA975          dd      msvcrt.75A98BA1                               ; (0B)
75A98A4F   .  DE79A975          dd      msvcrt.75A979DE                               ; (0C)
75A98A53   .  3A8FA975          dd      msvcrt.75A98F3A                               ; (0D)
75A98A57   .  FD8AA975          dd      msvcrt.75A98AFD                               ; (0E)
75A98A5B   .  ED8EA975          dd      msvcrt.75A98EED                               ; (0F)
75A98A5F   .  C879A975          dd      msvcrt.75A979C8                               ; (10)
75A98A63   .  518FA975          dd      msvcrt.75A98F51                               ; (11)
75A98A67   .  BA8EA975          dd      msvcrt.75A98EBA                               ; (12)
75A98A6B   .  6A98A975          dd      msvcrt.75A9986A                               ; (13)
75A98A6F   .  8990A975          dd      msvcrt.75A99089                               ; (14)
75A98A73   .  CD98A975          dd      msvcrt.75A998CD                               ; (15)
75A98A77   .  D58EA975          dd      msvcrt.75A98ED5                               ; (16)
75A98A7B   .  8598A975          dd      msvcrt.75A99885                               ; (17)
75A98A7F   .  1899A975          dd      msvcrt.75A99918                               ; (18)
75A98A83   .  E898A975          dd      msvcrt.75A998E8                               ; (19)
75A98A87   .  698FA975          dd      msvcrt.75A98F69                               ; (1A)
75A98A8B   .  9D98A975          dd      msvcrt.75A9989D                               ; (1B)
75A98A8F   .  3399A975          dd      msvcrt.75A99933                               ; (1C)
75A98A93   .  0099A975          dd      msvcrt.75A99900                               ; (1D)
75A98A97   .  848FA975          dd      msvcrt.75A98F84                               ; (1E)
75A98A9B   .  B598A975          dd      msvcrt.75A998B5                               ; (1F) Окончание таблицы переходов



В связи с большой трудоёмкостью анализа всей функции было решено не дизассемблировать её полностью, к тому же интерес представляли лишь две вещи:

  • Оценка накладных расходов (overhead) на «платформенный» вызов (PInvoke)
  • Внешняя оценка основного кода функции.


Оценка накладных расходов на взаимодействие с платформой

Для оценки накладных расходов на вызов функции было решено провести трассировку кода от управляемого кода до начала самой функции. Для этого в начале функции была установлена точка останова, и после возврата из Thread.Sleep() начата трассировка. Однако результат первой попытки трассировки оказался неудачным: лог трассировки оказался слишком большим (около 100 тысяч строк), что, вероятно, говорило о том, что была выполнена DllMain(), также существовала вероятность, что был захвачен какой-то код CLR, возможно, код JIT-компилятора. Что именно там выполнялось, я не стал выяснять: это не представляло интереса, т.к. подобный стартовый код выполняется лишь единожды и на общую картину почти не влияет. Чтобы исключить этот код, я перед вызовом Thread.Sleep() вставил ещё один вызов memcmp() и заново произвёл трассировку. В результате чего получил чуть более ста строк.

Окно лога трассировки

Часть лога трассировки:
main  00480AEA                    call    0031C19C                        ESP=0016F368
; часть кода опущена
main  clr.628C3B5F                call    near [eax+14]                   ESP=0016F248        ; (1)
; часть кода опущена
main  00480B87                    mov     eax, [ebp-1C]                   EAX=00313880
main  00480B8A                    mov     eax, [eax+14]                   EAX=0031391C
main  00480B8D                    mov     ecx, [eax]                      ECX=75A97975        ; (2)
main  00480B8F                    push    dword ptr [ebp+0C]              ESP=0016F328
main  00480B92                    push    dword ptr [ebp+8]               ESP=0016F324
main  00480B95                    push    edi                             ESP=0016F320
main  00480B96                    push    dword ptr [ebp-10]              ESP=0016F31C
main  00480B99                    mov     dword ptr [ebp-2C], 0
main  00480BA0                    mov     [ebp-28], esp
main  00480BA3                    mov     dword ptr [ebp-24], 480BB0
main  00480BAA                    mov     byte ptr [ebx+8], 0
main  00480BAE                    call    ecx                             ESP=0016F318        ; (3)
main  msvcrt.memcmp               mov     edi, edi
--------  Logging stopped

Из приведённого лога видно, что, во-первых, по пути к функции происходит как минимум один косвенный вызов, а во-вторых, CLR достаёт адрес конечной функции из какой-то структуры данных, т.е. вызов обладает значительной косвенностью и не оставляет блоку предсказания переходов никакой надежды на выполнение его миссии. Это делает бессмысленным вынос таких функций за пределы управляемого кода в том случае, если они не обрабатывают большие порции данных единовременно и не требуют большого времени вычислений.

Оценка основного кода функции

В лучшем, наименее ресурсоёмком, случае функция обнаружит различие в первом же байте и вернёт результат. Именно в этом случае функция затратит наименьшее время. В худшем случае функция сравнит массивы целиком и не обнаружит различий. Очевидно, что во втором случае данные будут сравниваться блоками в цикле.

Поскольку провести дизассемблирование и анализ функции целиком за приемлемое время возможным не представляется, то для оценки выполняемого кода было решено сделать две трассировки, и уже по логу трассировки оценивать оба этих случая. Для анализа лучшего случая, во-первых, была модифицирована функция генерации тестовых данных так, чтобы все массивы отличались, начиная с первого байта, а во-вторых, модифицирована функция, сравнивающая все массивы, так, чтобы в первой же итерации цикла сравнивались разные массивы.
Модифицированная функция сравнения массивов
      private static bool CompareArraysWithPInvokeMethod()
      {
         var result = true;
         for (int i = CountArrays - 1; i >= 0; i--) //Цикл в обратном направлении
            for (int j = 0; j < CountArrays; j++)
            {
               var tmp = ByteArrayCompareWithPInvoke(s_arrays[i], s_arrays[j]);

               result = result && tmp;
            }
         return result;
      }



Первая трассировка (лучший случай)
main  msvcrt.memcmp               mov     edi, edi
main  msvcrt.75A97977             push    ebp                             ESP=0041EC74
main  msvcrt.75A97978             mov     ebp, esp                        EBP=0041EC74

main  msvcrt.75A9797A             push    esi                             ESP=0041EC70
main  msvcrt.75A9797B             push    edi                             ESP=0041EC6C

main  msvcrt.75A9797C             mov     edi, [ebp+10]                   EDI=00080000                     ; edi <-- count

main  msvcrt.75A9797F             mov     eax, edi                        EAX=00080000                     ; eax <-- edi
main  msvcrt.75A97981             sub     eax, 0                                                           ; if (eax == 0) {result <-- 0; return;}
main  msvcrt.75A97984             je      msvcrt.zeroResult_GoReturn
main  msvcrt.75A9798A             dec     eax                             EAX=0007FFFF
main  msvcrt.75A9798B             je      msvcrt.75A98C10
main  msvcrt.75A97991             dec     eax                             EAX=0007FFFE
main  msvcrt.75A97992             je      msvcrt.75A9E610
main  msvcrt.75A97998             dec     eax                             EAX=0007FFFD
main  msvcrt.75A97999             je      msvcrt.75A9E5DF
main  msvcrt.75A9799F             dec     eax                             EAX=0007FFFC
main  msvcrt.75A979A0             je      msvcrt.75A98BD2

main  msvcrt.75A979A6             mov     ecx, [ebp+0C]                   ECX=034C53B8                    ; ecx <-- buf1
main  msvcrt.75A979A9             mov     eax, [ebp+8]                    EAX=05C41038                    ; eax <-- buf2
main  msvcrt.75A979AC             push    ebx                             ESP=0041EC68
main  msvcrt.75A979AD             push    20                              ESP=0041EC64                    ; Очень необычный способ поместить число в регистр
main  msvcrt.75A979AF             pop     edx                             EDX=00000020, ESP=0041EC68

;--------------------------------Начало цикла сравнения
main  msvcrt.75A979B0             cmp     edi, edx
main  msvcrt.75A979B2             jae     msvcrt.75A993A7

main  msvcrt.75A993A7             mov     esi, [eax]                      ESI=4241403F
main  msvcrt.75A993A9             cmp     esi, [ecx]
main  msvcrt.75A993AB             jne     msvcrt.75AA80E7                                                 ; Обнаружено отличие

main  msvcrt.75AA80E7             movzx   esi, byte ptr [eax]             ESI=0000003F
main  msvcrt.75AA80EA             movzx   ebx, byte ptr [ecx]             EBX=00000001
main  msvcrt.75AA80ED             sub     esi, ebx                        ESI=0000003E                    ; Вычиление разницы между нулевыми байтами DWORD’а
main  msvcrt.75AA80EF             jne     msvcrt.75AA8178


main  msvcrt.75AA8178             xor     ebx, ebx                        EBX=00000000                    ; Формирование результата в регистре ebx
main  msvcrt.75AA817A             test    esi, esi
main  msvcrt.75AA817C             setg    bl                              EBX=00000001
main  msvcrt.75AA817F             lea     ebx, [ebx+ebx-1]
main  msvcrt.75AA8183             mov     esi, ebx                        ESI=00000001
main  msvcrt.75AA8185             test    esi, esi
main  msvcrt.75AA8187             jne     msvcrt.75A98AB1

main  msvcrt.75A98AB1             mov     eax, esi                        EAX=00000001
main  msvcrt.75A98AB3             jmp     msvcrt.75A97A1E

main  msvcrt.75A97A1E             pop     ebx                             EBX=00852AE0, ESP=0041EC6C
main  msvcrt.return1              pop     edi                             ESP=0041EC70, EDI=034C53B8
main  msvcrt.75A97A20             pop     esi                             ESP=0041EC74, ESI=034C53B0
main  msvcrt.75A97A21             pop     ebp                             ESP=0041EC78, EBP=0041ECC4
main  msvcrt.75A97A22             ret                                     ESP=0041EC7C



Первое, что здесь бросается в глаза – то, что обработка частных случаев, т.е. случаев, когда параметр count лежит в пределах [0..4], сделана довольно необычно. Остаётся только гадать, является ли это результатом компиляции предложения switch или там действительно была заведена локальная переменная, которая декрементировалась на каждом шаге проверки. Однако отладочная информация утверждает, что это всё-таки был switch. С точки зрения оптимизации это вполне разумное действие, т.к. не выполняется инициализация цикла.

Второе, что сразу же бросилось в глаза – весьма необычный способ занесения числа 0x20 в регистр edx (через стек). Это очень похоже на какой-то артефакт компиляции, и явно говорит о том, что функция писалась не на ассемблере. Человек бы такого не написал, т.к. это бессмысленно: стек находится в памяти, а к ней обращения всегда медленнее, чем к регистрам. Рискну предположить, что это артефакт встраивания (inline).

После обнаружения различия двойных слов в буферах выполняется переход по адресу 0x75AA8178, где происходит загрузка первых байтов из исходных буферов в регистры esi и ebx по адресам, где было обнаружено различие. Затем следует вычисление разницы между этими байтами, и, если не обнаружено различий, то загружаются следующие байты, и так для всего двойного слова. Примечательно, что результат не зависит от номера байта, в котором обнаружено различие. Это видно из того, что код формирования результата для последнего байта в DWORD’е полностью идентичен коду аналогичного назначения для первого байта, приведённому выше в трэйслоге первой трассировки.

Последовательное сравнение байтов двойного слова
;Address   Hex dump          Command                                  Comments
75AA80E7   >  0FB630        movzx   esi, byte ptr [eax]
75AA80EA   .  0FB619        movzx   ebx, byte ptr [ecx]
75AA80ED   .  2BF3          sub     esi, ebx                           ; Вычиление разницы между нулевыми байтами DWORD’а
75AA80EF   .- 0F85 83000000 jne     msvcrt.75AA8178                    ; Джамп на формирование результата в регистре ebx

75AA80F5   >  0FB670 01     movzx   esi, byte ptr [eax+1]
75AA80F9   .  0FB659 01     movzx   ebx, byte ptr [ecx+1]
75AA80FD   .  2BF3          sub     esi, ebx
75AA80FF   .- 0F84 1EF9FEFF je      msvcrt.75A97A23
; часть кода опущена

75A97A23   >  0FB670 02     movzx   esi, byte ptr [eax+2]
75A97A27   .  0FB659 02     movzx   ebx, byte ptr [ecx+2]
75A97A2B   .  2BF3          sub     esi, ebx
75A97A2D   .- 74 15         je      short msvcrt.75A97A44
; часть кода опущена

75A97A44   >  0FB670 03     movzx   esi, byte ptr [eax+3]
75A97A48   .  0FB659 03     movzx   ebx, byte ptr [ecx+3]
75A97A4C   .  2BF3          sub     esi, ebx
75A97A4E   .- 0F84 5F190000 je      msvcrt.75A993B3                    ; Джамп куда-то внутрь цикла

75A97A54   .  33DB          xor     ebx, ebx                           ; Формирование результата в регистре ebx
75A97A56   .  85F6          test    esi, esi
75A97A58   .  0F9FC3        setg    bl
75A97A5B   .  8D5C1B FF     lea     ebx, [ebx+ebx-1]
75A97A5F   .  8BF3          mov     esi, ebx
75A97A61   .- E9 4D190000   jmp     msvcrt.75A993B3

; часть кода опущена
75A993B1   . |33F6          xor     esi, esi
75A993B3   > |85F6          test    esi, esi
75A993B5   .-|0F85 F6F6FFFF jne     msvcrt.75A98AB1



Дублирование кода нехорошо, но не страшно, а вот последовательное сравнение байтов – не лучший способ сравнения двойных слов, тем более что номер байта на результат не влияет. Таким образом, уже видно, что этот код несколько странноват, возможно, потому, что исходники ещё более странноваты.

Первый взгляд на лог второй трассировки: за одну итерацию цикла сравниваются 8 двойных слов, и это хорошо: видно, что цикл развёрнут, а с другой стороны, после каждого сравнения идёт абсолютно одинаковый бесполезный код: в регистр esi заносится 0 и анализируется содержимое регистра esi. У меня нет никаких предположений о том, зачем это было сделано, однако есть предположение о том, как такое могло получиться: во-первых, это очень похоже на результат работы какого-то макроса, формировавшего ассемблерный код, а во-вторых, похоже, что майкрософтовский компилятор C не так хорош, как я об этом думал раньше.
Вторая трассировка (только цикл)
;--------------------------------Начало цикла сравнения
main  msvcrt.75A979B0             cmp     edi, edx
main  msvcrt.75A979B2             jae     msvcrt.75A993A7

main  msvcrt.75A993A7             mov     esi, [eax]                      ESI=00000000
main  msvcrt.75A993A9             cmp     esi, [ecx]
main  msvcrt.75A993AB             jne     msvcrt.75AA80E7
main  msvcrt.75A993B1             xor     esi, esi
main  msvcrt.75A993B3             test    esi, esi
main  msvcrt.75A993B5             jne     msvcrt.75A98AB1

main  msvcrt.75A993BB             mov     esi, [eax+4]
main  msvcrt.75A993BE             cmp     esi, [ecx+4]
main  msvcrt.75A993C1             jne     msvcrt.75AA811F
main  msvcrt.75A993C7             xor     esi, esi
main  msvcrt.75A993C9             test    esi, esi
main  msvcrt.75A?993CB             jne     msvcrt.75A98AB1

main  msvcrt.75A993D1             mov     esi, [eax+8]
main  msvcrt.75A993D4             cmp     esi, [ecx+8]
main  msvcrt.75A993D7             jne     msvcrt.75A97A9A
main  msvcrt.75A993DD             xor     esi, esi
main  msvcrt.75A993DF             test    esi, esi
main  msvcrt.75A993E1             jne     msvcrt.75A98AB1


main  msvcrt.75A993E7             mov     esi, [eax+0C]
main  msvcrt.75A993EA             cmp     esi, [ecx+0C]
main  msvcrt.75A993ED             jne     msvcrt.75A97B1F
main  msvcrt.75A993F3             xor     esi, esi
main  msvcrt.75A993F5             test    esi, esi
main  msvcrt.75A993F7             jne     msvcrt.75A98AB1


main  msvcrt.75A993FD             mov     esi, [eax+10]
main  msvcrt.75A99400             cmp     esi, [ecx+10]
main  msvcrt.75A99403             jne     msvcrt.75A97BA4
main  msvcrt.75A99409             xor     esi, esi
main  msvcrt.75A9940B             test    esi, esi
main  msvcrt.75A9940D             jne     msvcrt.75A98AB1


main  msvcrt.75A99413             mov     esi, [eax+14]
main  msvcrt.75A99416             cmp     esi, [ecx+14]
main  msvcrt.75A99419             jne     msvcrt.75A97C29
main  msvcrt.75A9941F             xor     esi, esi
main  msvcrt.75A99421             test    esi, esi
main  msvcrt.75A99423             jne     msvcrt.75A98AB1


main  msvcrt.75A99429             mov     esi, [eax+18]
main  msvcrt.75A9942C             cmp     esi, [ecx+18]
main  msvcrt.75A9942F             jne     msvcrt.75AA1172
main  msvcrt.75A99435             xor     esi, esi
main  msvcrt.75A99437             test    esi, esi
main  msvcrt.75A99439             jne     msvcrt.75A98AB1


main  msvcrt.75A9943F             mov     esi, [eax+1C]
main  msvcrt.75A99442             cmp     esi, [ecx+1C]
main  msvcrt.75A99445             jne     msvcrt.75A97CFC
main  msvcrt.75A9944B             xor     esi, esi
main  msvcrt.75A9944D             test    esi, esi
main  msvcrt.75A9944F             jne     msvcrt.75A98AB1


main  msvcrt.75A99455             add     eax, edx                        EAX=031353B8
main  msvcrt.75A99457             add     ecx, edx                        ECX=031353B8
main  msvcrt.75A99459             sub     edi, edx                        EDI=0007FFE0
main  msvcrt.75A9945B             jmp     msvcrt.75A979B0



Примечательно, что на больших объёмах тестовых данных этот код показал результат на ~10% хуже, чем код, использующий unsafe. Понятно, что основное время при сравнении массивов данных уходит на операции чтения из памяти, которая значительно медленнее, чем кэш процессора и, тем более, регистры. Но столь серьёзная разница, которую дали одни лишь операции с регистрами процессора, говорит о том, что оптимизации компилятора крайне важны. Рискну предположить, что тестирование на более слабом процессоре, например, на процессоре с меньшей тактовой частотой, дало бы значительно более существенную разницу.

Выводы


  1. Если надо быстро сравнивать маленькие (7 байт и меньше) массивы, берём наиболее очевидный способ (побайтное сравнение в цикле), большие — unsafe, а всё остальное от лукавого.
  2. Вокруг .Net и CLR ходит много легенд. Людей убедили в том, что JIT-компилятор генерирует хороший, оптимизированный код, что CLR «затачивает» машинный код под конкретный процессор. Это неправда. В теории JIT-компилятор способен творить чудеса оптимизации, но на практике не делает этого. Нужен быстрый код — берите C++-компилятор от Intel, а если нужно вообще максимум из железа выжать, то вооружайтесь руководством по оптимизации от одноимённой фирмы (AMD или Intel) и пишите на ассемблере.
  3. Анализ C-RunTime функции показывает, что компилятор не творит чудес, даже если это один из лучших C-компиляторов – MS VC. Цитата из статьи «О реализации метода оптимизации при компиляции» (http://rsdn.ru/article/optimization/optimization.xml): «Только если особый случай не найден, компилятор выполняет реализацию, рассчитанную на самый общий случай и потому потенциально менее эффективную».


Список литературы


  1. Intel® 64 and IA-32 Architectures Software Developer Manuals.CHAPTER 2. Intel ® 64 Architecture
  2. AMD64 Architecture Programmer’s Manual Volume 1: Application Programming CHAPTER 1 Long Mode
  3. Intel® 64 and IA-32 Architectures Optimization Reference Manual. CHAPTER 3. Alignment
  4. Windows Internals, Sixth Edition, Part 1, CHAPTER 5 Processes, Threads, and Jobs
  5. Windows Internals, Sixth Edition, Part 2, CHAPTER 10. Memory Management
  6. Intel® 64 and IA-32 Architectures Software Developer Manuals. CHAPTER 17. TIME-STAMP COUNTER
  7. MSDN Magazine 2005, May: Drill Into .NET Framework Internals to See How the CLR Creates Runtime Objects
  8. Joe Duffy, Professional .NET Framework 2.0 (Programmer to Programmer). Chapter 3: Inside the CLR, Just-In-Time (JIT) Compilation




Обновление от 21.03.2014 4:37


  • Исправлены некоторые опечатки, например «CRL».
  • Исправлен внешний вид ссылок на документацию (только косметические изменения), а так же добавлены ссылки на описания некоторых функций в MSDN.
  • Исправлен список литературы.

В прошлый раз я в комментариях выложил некорректные исходники. Дело в том, что в процессе экспериментов, о которых я знесь не писал, или писал частично, исходники оказались не годными для получения результатов из статьи. Например:
  • Были закомментированы некоторые вызовы в методе DoMeasurements(). А так же была добавлена строка result.SequenceEqualTime = result.IStructuralEquatableTime = result.PInvokeTime;
  • Метод PrepareTestData(int p_ArraySize) генерировал массивы, отличающиеся с первого байта.
  • Константы были выставлены таким образом, чтобы стартовый размер массива был 512*1024, а массиво было всего 64.
  • Метод CompareArraysWithPInvokeMethod() тоже был изменён так, чтобы первыми сравнивались отличающиеся массивы. Хотя это, теоретически, не должно было сильно сказаться на итоговых данных.

В итоге это привело к тому, что те, кто их скачал и запустил, не смогли повторить результаты из статьи.
Исправленные сорцы я положил сюда
Пока я занимался исправлениями опечаток и ошибок, Saladin поправил и выложил сорцы на GitHub, так что можно не скачивать, а просто посмотреть.

Обновление от 25.03.2014 6:37


По многочисленным просьбам я исследовал RtlCompareMemory().

Перед изучением кода функции, я её протестировал, предварительно выставив атрибут SuppressUnmanagedCodeSecurity для функции memcmp() и RtlCompareMemory()
Любопытно, что системная функция, которую можно вызывать и из user-mode и из kernel-mode, оказалась медленнее чем функция из набора CRT.
Callers of RtlCompareMemory can be running at any IRQL if both blocks of memory are resident.

Результаты под катом
Размер массива  Минимальное время  Unsafe     MemCMP     RtlCompareMemory  Простейший метод
1               279                1 : 001,7  1 : 003,2  1 : 008,8         1 : 001,0
1               278                1 : 001,8  1 : 003,2  1 : 008,9         1 : 001,0
2               325                1 : 001,3  1 : 002,9  1 : 006,1         1 : 001,0
4               374                1 : 001,1  1 : 002,6  1 : 009,0         1 : 001,0
7               422                1 : 001,0  1 : 002,5  1 : 007,0         1 : 001,1
12              426                1 : 001,0  1 : 002,5  1 : 006,9         1 : 001,7
19              490                1 : 001,0  1 : 002,2  1 : 006,0         1 : 001,9
32              560                1 : 001,0  1 : 002,0  1 : 005,3         1 : 002,7
54              622                1 : 001,0  1 : 002,0  1 : 005,4         1 : 003,8
89              802                1 : 001,0  1 : 001,7  1 : 004,3         1 : 004,7
147             1092               1 : 001,0  1 : 001,5  1 : 003,7         1 : 004,0
242             1571               1 : 001,0  1 : 001,4  1 : 003,0         1 : 004,2
398             2328               1 : 001,0  1 : 001,4  1 : 002,7         1 : 004,5
657             3664               1 : 001,0  1 : 001,2  1 : 002,2         1 : 004,6
1082            5519               1 : 001,0  1 : 001,2  1 : 002,1         1 : 005,0
1782            8554               1 : 001,0  1 : 001,2  1 : 002,1         1 : 005,3
2936            13520              1 : 001,0  1 : 001,2  1 : 002,0         1 : 005,5
4837            21771              1 : 001,0  1 : 001,2  1 : 002,0         1 : 005,6
7967            35464              1 : 001,0  1 : 001,2  1 : 001,9         1 : 005,7
13124           58073              1 : 001,0  1 : 001,2  1 : 001,9         1 : 005,7
21618           96457              1 : 001,0  1 : 001,2  1 : 001,9         1 : 005,7
35610           167952             1 : 001,0  1 : 001,1  1 : 001,8         1 : 005,4
58656           285282             1 : 001,0  1 : 001,1  1 : 001,8         1 : 005,3
96617           534712             1 : 001,0  1 : 001,1  1 : 001,6         1 : 004,7
159146          924569             1 : 001,0  1 : 001,1  1 : 001,6         1 : 004,5
262143          1520968            1 : 001,0  1 : 001,1  1 : 001,6         1 : 004,5


На скриншоте с окошками дебагера версия библиотеки



Функция оказалась на удивление маленькой, она вся здесь, под катом. В функции активно используются строковые операции сравнения c префиксом повторения (cmps*). Сравнение памяти идёт в прямом порядке. Это определяется флагом DF, который сбрасывается командой cld. Размер и простота этой функции, наводят на мысли, что она писалась на ассемблере, хотя в этом я не уверен.
Алгоритм работы строковых операций сравнения исключительно прост, например сравнение DWORD'ов в прямом направлении, задающееся вот такой командой:
repe cmpsd                               ; В цикле по ecx сравниваем DWORD'ы;

на ЯВУ можно представить так:
         while 
          (
             ( 0 != ecx )
          & ( 0 == Compare( (DWORD) RAM[esi], (DWORD) RAM[edi] ) )
          )
         {
            --ecx;
            edi += 4;
            esi += 4;
         }

Почти так же можно представить равнение слов и байтов.
Дизасм с комментариями под катом
 push    esi                              ; сохранить значения регистров в стеке
 push    edi

 cld                                      ; DF  <-- 0

 mov     esi, [esp+0C]                    ; esi <-- Source1
 mov     edi, [esp+10]                    ; edi <-- Source2
 mov     ecx, [esp+14]                    ; ecx <-- SIZE_T

 shr     ecx, 2                           ; ecx <-- (ecx >> 2) ( делим счётчик на 4)
 jz      short smaller_4                  ; 

 repe cmpsd                               ; В цикле по ecx сравниваем DWORD'ы;
 jne     short not_zero                   ; if ( !ZF ) goto not_zero;



smaller_4:
 mov     ecx, [esp+14]                    ; ecx <-- SIZE_T

 and     ecx, 00000003                    ; ecx &= 3
 jz      short return_SIZE_T              ; if ( ZF ) goto return_SIZE_T;

 repe cmpsb                               ; в цикле сравниваем байты
 jne     short found_difference



return_SIZE_T:
 mov     eax, [esp+14]                   ; eax <-- SIZE_T
 pop     edi                             ; восстанавливаем значения регистров
 pop     esi
 ret     0C                              ; return eax


not_zero:
 sub     esi, 4                          ; esi -= 4
 sub     edi, 4                          ; edi -= 4
 mov     ecx, 4                          ; ecx -= 4
 repe cmpsb                              ; в цикле сравниваем байты


found_difference:
 dec     esi                             ; --esi
 sub     esi, [esp+0C]                   ; esi <-- (esi - Source1)
 mov     eax, esi                        ; eax <-- esi

 pop     edi                             ; восстанавливаем значения регистров
 pop     esi

 ret     0C                              ; return eax

Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 83

    +5
    Колоссальная работа,

    1. что значит «p_»?
    2. В ByteArrayCompareWithSimplest зря закешировали длину массива, т.к. это немного ухудшает производительность
    3. В каком режиме вы компилировали программу? Release или Debug? с оптимизацией или без?
      0
      За счет чего кеширование длины ухудшает производительность?
        +1
        Да, именно так, но только в случае с массивами.
        1. Компилятор знает, что длина массива не изменяется при итерировании.
        2. Если не кэшировать длину, то используется специальная IL-инструкция ldlen, если кэшировать, то используется переменная, а это медленнее.

        Вот тут подробнее: habrahabr.ru/post/192130/
        0
        > что значит «p_»?
        Это у меня так параметры именуются. Их так проще отличить от полей и локальных переменных. Кстати, многие заблуждаются, но это не Венгерская нотация, а нечто иное, т.к. Венгенская нотация оговаривает префиксы в зависимости от типа (или размера) переменой. Чтобы понять отличие, достаточно взглянуть на имена параметров WinAPI'шных функций, там именно она. Например "LPCTSTR lpFileName".
        Венгерская нотация затрудняет рефакторинг (при изменении типа приходится переименовывать все переменные), а мои префиксы — нет.

        >… зря закешировали длину массива, т.к. это немного ухудшает производительность
        Не ухудшает. Только что специально перепроверил (перекомпилил, посмотрел дизасм). Код у вас есть — проверьте сами.

        >В каком режиме вы компилировали программу…
        Релиз — дебаг в таких эксперимента не интересен.
          0
          Не могли бы вы выложить весь ваш исходный код в какой-нибудь открытый репозиторий, например, с помощью на GitHub?
          Было бы интересно посмотреть и, чем черт не шутит, прогнать тесты у себя.

          P.S.
          Спасибо за статью, вы провели действительно большую работу!
            0
            Вот так пойдёт? files.rsdn.ru/67254/ConsoleApplication22014_03_20151019.zip

            Там кода совсем чуть-чуть, и он практически весь приведён в статье, поэтому я изначально не стал его выкладывать никуда.
              +1
              Спасибо, сойдет!

              Я запустил вашу программу со значениями констатнт указанными вами в статье и получил следующее.

              Результаты



              Мои результаты, почему-то очень сильно отличаются от ваших.

              Что я использую:
              Windows 7 x64 со всеми последними обновлениями для .Net 4.0 Client Profile и настройками Microsoft Visual Studio 2012 по-умолчанию, и только для конфигурации x86.
                +4
                Windows 8.1 x64, VS 2013, все обновления.

                .net 4 client
                Размер массива  Минимальное время  Unsafe   PInvoke  Простейший метод  SequenceEqual  IStructuralEquatable
                524288          11108              1 : 1.0  1 : 1.5  1 : 5.8           1 : 1.5        1 : 1.5             
                690001          13547              1 : 1.0  1 : 1.6  1 : 6.2           1 : 1.6        1 : 1.6             
                908093          18188              1 : 1.0  1 : 1.6  1 : 6.1           1 : 1.6        1 : 1.6             
                1195118         23089              1 : 1.0  1 : 1.7  1 : 6.3           1 : 1.7        1 : 1.7             
                1572863         29947              1 : 1.0  1 : 1.7  1 : 6.5           1 : 1.7        1 : 1.7             
                
                .net 4.5.1
                Размер массива  Минимальное время  Unsafe   PInvoke  Простейший метод  SequenceEqual  IStructuralEquatable
                524288          11048              1 : 1.0  1 : 1.6  1 : 5.9           1 : 1.6        1 : 1.6             
                690001          14056              1 : 1.0  1 : 1.6  1 : 6.1           1 : 1.6        1 : 1.6             
                908093          17823              1 : 1.0  1 : 1.6  1 : 6.3           1 : 1.6        1 : 1.6             
                1195118         23763              1 : 1.0  1 : 1.6  1 : 6.2           1 : 1.6        1 : 1.6             
                1572863         30210              1 : 1.0  1 : 1.7  1 : 6.3           1 : 1.7        1 : 1.7             

                Компиляция изначально 32-битного приложения в 64 бита умножает необходимую для него память и снижает его производительность
                Ради интереса прогнал ваш код на x86-64:

                .net 4.5.1
                Размер массива  Минимальное время  Unsafe   PInvoke  Простейший метод  SequenceEqual  IStructuralEquatable
                524288          8392               1 : 1.5  1 : 1.0  1 : 8.9           1 : 1.0        1 : 1.0             
                690001          11161              1 : 1.5  1 : 1.0  1 : 8.8           1 : 1.0        1 : 1.0             
                908093          14559              1 : 1.5  1 : 1.0  1 : 9.0           1 : 1.0        1 : 1.0             
                1195118         18972              1 : 1.5  1 : 1.0  1 : 9.0           1 : 1.0        1 : 1.0             
                1572863         24114              1 : 1.6  1 : 1.0  1 : 9.3           1 : 1.0        1 : 1.0     
                  0
                  Интересно, то, что у нас получились результаты, соврешенно отличные от авторских.
                  Причем, производительность IStructuralEquatable явно не сильно отстает от своих конкурентов(тем более на три порядка), а вашем втором примере она вообще показывает лучший результат, даже в абсолютном сравнении!
                    +1
                    Автор явно что-то делал не так. Такие порядки различия (1:261 по минимальному времени и… 1:216954 (o_O) по времени IStructuralEquatable) можно объяснить только серьёзным изъяном в тестировании. Это я не говорю о том, что методика изначально неправильная — ни квантилей, ни прогрева кэша, ни сборки мусора…

                    Вообще, мне интересно, почему PInvoke/SequenceEqual/IStructuralEquatable в варианте x86-64 стали показывать совершенно другие результаты. Сходу не могу это объяснить :)
                    0
                    Отписался ниже.

                    habrahabr.ru/post/214841/#comment_7422181
                +1
                1. Ваша нотация еще хуже «венгерской», т.к. она мешает intelli-sense. Для того, чтобы отличать параметры от полей и локальных переменных нужно использовать нормальную IDE (VS + ReSharper + Color Identifiers, например)

                2. Ухудшает, см тут: habrahabr.ru/post/192130/

                3. Как раз интересен, потому что компилируется разный CIL, (не) используются разные оптимизации, по разному работает GC. От этого даже может измениться поведение кода.
                  0
                  2) Попробуй сам, и убедись, что это не так.
                  Будет время — посмотрю статью, возможно прокомментирую.
                  +1
                  >Релиз — дебаг в таких эксперимента не интересен.

                  stackoverflow.com/a/4045073/259946

                  * Array index checking elimination. An important optimization when working with arrays (all .NET collection classes use an array internally). When the JIT compiler can verify that a loop never indexes an array out of bounds then it will eliminate the index check. Big one.

                  * Loop unrolling. Short loops (up to 4) with small bodies are eliminated by repeating the code in the loop body. Avoids the branch misprediction penalty.

                  * Code hoisting. Code inside a loop that is not affected by the loop can be moved out of the loop.

                  Вы не находите, что это именно то, о чем вы возмущаетесь в статье, что JIT этого не делает?
                    0
                    Мне дебаг был неинтересен именно потому, что я хотел самолично взглянуть на оптимизации JIT'ера.
                    И соответственно, я в статье показал, что:

                    *Array index checking elimination…
                    этого нет

                    * Loop unrolling.…
                    Этого тоже нет. Что может быть проще цикла с тремя действиями ( 1)проверка индекса, 2)чтение, 3)сравнение)?! Но нет, не JIT'ер его не развернул, он скомпилировал именно так, как я написал.

                    * Code hoisting.
                    Насчёт этого — не знаю. В плюсах — есть, здесь не интересовался.
                      +2
                      Еще раз спрошу: вы уверены, что вы делали тесты в Release режиме? Потому что я у себя вижу стабильные 1000 лишних тиков при кэшированой длине, и в 1.5 раза медленнее, если навесить на методы [MethodImpl(MethodImplOptions.NoOptimization)].
                        0
                        >Еще раз спрошу: вы уверены, что вы делали тесты в Release режиме?
                        Абсолютно.
                          +1
                          У меня самый «долгий тест» ~34000 тиков.
                            +3
                            Ещё нужно учесть, что если скомпилировать программу в Release, но запустить её с отладчиком, jit-оптимизации не отработают. Для того, чтобы посмотреть оптимизированный asm, нужно запустить программу без отладчика, прогнать тесты и только тогда (например, пока программа ждёт в Console.ReadKey()) приаттачиться отладчиком к внешнему процессу.
                          +3
                          Loop unrolling делается, но не всегда. Выбор конкретной стратегии развёртки цикла зависит от:
                          — Архитектуры x86/x64
                          — Количество итераций цикла
                          — Размещение массива в памяти.
                          Можете взглянуть на мою заметку по этому поводу, там некоторые нюансы освещены. Для n=2^k под x64 развёртка делается практически всегда.
                            0
                            Спасибо, это интересно.
                            Попробую поэкспериментировать с x64…
                    +1
                    Спасибо за статью! На самом деле это хорошая идея для продукта — написать свой nGen, который будет транслировать MSIL в понятный для Intel C++ Compiler формат. Есть ли что-то типа LLVM для Intel?
                      0
                      Mono AOT
                        0
                        Я про Intel Compiler, чтобы он научился понимать сборки, нужна понятная обоим компиляторам, прослойка
                      0
                      Статья великолепная, браво! Есть пара мыслей на ее счет:
                      1. В что если в способе «PInvoke, для CRT функции memcmp()» тоже использовать fixed + unsafe и уже передавать в memcmp непосредственно указатели? Думается, я меньше вашего разбираюсь в .NET'e, но это место выглядит подозрительным)
                      2. Мой опыт со студийным (MS VS) компилятором убедил меня в том, что в Release сборке он «божит», оптимизации порой фантастические. Можете поделиться пруфом, что интеловский круче?)
                        0
                        1) 100 с лишним строк на асме — это мало, почти ничто, а основная масса кода, который выполняется по пути к неуправляемому — проверка всяких security, и её исключить вряд ли получится. Т.е. очень сомнительно, что там что-то можно оптимизировать. А т.к. подобное развлечение весьма утомительно, то я этим заниматься не буду. Если было бы необходимо выжать максимум из машины, то я бы попробовал взглянуть в сторону грязных хаков (напр. пропатчить какую-нибудь функцию, или делегат). Однако всё это путь в никуда: завтра где-нибудь в исходниках CLR подправят выравнивание, или поледобавят, или баг какой-нибудь исправят, и всё перестанет работать.

                        2) Ни разу не видел чтобы он глючил. Видел, что в дебажном и релизном коде финализаторы в другом порядке вызываются (и ещё что-то там про финализаторы было), но всё всегда работало корректно, по крайней мере CLR.
                          0
                          Выравнивание не подправят. Суровая объективная реальность современных процессоров. У всех компиляторов сейчас выравнивание по-умолчанию — минимум 32 бита. Так что в этом плане можно не бояться.
                            0
                            Если под DDR4 будут затачивать, то могут поменять DWORD alignment на как минимум QWORD. И всё поплывёт, все грязные хаки перестанут работать.
                              0
                              Гхм… DDR4 тут никоим даже боком.
                              Разрядность процессора и длина строки кэш памяти только могут влиять.
                              Но самое главное — это будет УВЕЛИЧЕНИЕ выравнивания. Если адрес выравнен на 4, то если его выравнять на 8, то он всё равно будет выравнен на 4.
                          +2
                          В что если в способе «PInvoke, для CRT функции memcmp()» тоже использовать fixed + unsafe и уже передавать в memcmp непосредственно указатели?
                          Ничего особенного не случится. Для массива байт маршаллер и так фиксирует (pin) массив в памяти и передаёт в unmanaged-код обычный указатель.

                          Подробнее:
                          Copying and Pinning (Formatted Blittable Classes)
                          Blittable and Non-Blittable Types
                          +1
                          Не хотите изучить еще и RtlCompareMemory?
                            +2
                            Перед изучение функции протестировал, предварительно выставив атрибут SuppressUnmanagedCodeSecurity для функции memcmp() и RtlCompareMemory()

                            Результаты
                            Размер массива  Минимальное время  Unsafe     MemCMP     RtlCompareMemory  Простейший метод
                            1               279                1 : 001,7  1 : 003,2  1 : 008,8         1 : 001,0
                            1               278                1 : 001,8  1 : 003,2  1 : 008,9         1 : 001,0
                            2               325                1 : 001,3  1 : 002,9  1 : 006,1         1 : 001,0
                            4               374                1 : 001,1  1 : 002,6  1 : 009,0         1 : 001,0
                            7               422                1 : 001,0  1 : 002,5  1 : 007,0         1 : 001,1
                            12              426                1 : 001,0  1 : 002,5  1 : 006,9         1 : 001,7
                            19              490                1 : 001,0  1 : 002,2  1 : 006,0         1 : 001,9
                            32              560                1 : 001,0  1 : 002,0  1 : 005,3         1 : 002,7
                            54              622                1 : 001,0  1 : 002,0  1 : 005,4         1 : 003,8
                            89              802                1 : 001,0  1 : 001,7  1 : 004,3         1 : 004,7
                            147             1092               1 : 001,0  1 : 001,5  1 : 003,7         1 : 004,0
                            242             1571               1 : 001,0  1 : 001,4  1 : 003,0         1 : 004,2
                            398             2328               1 : 001,0  1 : 001,4  1 : 002,7         1 : 004,5
                            657             3664               1 : 001,0  1 : 001,2  1 : 002,2         1 : 004,6
                            1082            5519               1 : 001,0  1 : 001,2  1 : 002,1         1 : 005,0
                            1782            8554               1 : 001,0  1 : 001,2  1 : 002,1         1 : 005,3
                            2936            13520              1 : 001,0  1 : 001,2  1 : 002,0         1 : 005,5
                            4837            21771              1 : 001,0  1 : 001,2  1 : 002,0         1 : 005,6
                            7967            35464              1 : 001,0  1 : 001,2  1 : 001,9         1 : 005,7
                            13124           58073              1 : 001,0  1 : 001,2  1 : 001,9         1 : 005,7
                            21618           96457              1 : 001,0  1 : 001,2  1 : 001,9         1 : 005,7
                            35610           167952             1 : 001,0  1 : 001,1  1 : 001,8         1 : 005,4
                            58656           285282             1 : 001,0  1 : 001,1  1 : 001,8         1 : 005,3
                            96617           534712             1 : 001,0  1 : 001,1  1 : 001,6         1 : 004,7
                            159146          924569             1 : 001,0  1 : 001,1  1 : 001,6         1 : 004,5
                            262143          1520968            1 : 001,0  1 : 001,1  1 : 001,6         1 : 004,5
                            



                            Окошки дебагера (смотрите версию библиотеки)



                            Функция оказалась на удивление маленькой, она вся здесь, под катом. В функции активно используются строковые операции сравнения c префиксом повторения (cmps*).

                            Например, сравнение DWORD'ов выглядит так:

                                     while 
                                      (
                                        ( 0 != ecx )
                                      & ( 0 == Compare( (DWORD) RAM[esi], (DWORD) RAM[edi] ) )
                                      )
                                     {
                                        --ecx;
                                        edi += 4;
                                        esi += 4;
                                     }
                            


                            Почти так же можно представить побайтное сравнение.

                            То, что функция оказалась медленнее unsafe я могу обяснить только тем, что в unsafe за одну итерацию цикла читаются два соседних DWORD'а для каждого массива, а здесь только один (цикл не развёрнут).

                            Дизассемблер с комментариями
                            77A52780  /$  56            push    esi                              ; сохранить значения регистров в стеке
                            77A52781  |.  57            push    edi
                            
                            77A52782  |.  FC            cld                                      ; DF  <-- 0
                            
                            77A52783  |.  8B7424 0C     mov     esi, [esp+0C]                    ; esi <-- Source1
                            77A52787  |.  8B7C24 10     mov     edi, [esp+10]                    ; edi <-- Source2
                            77A5278B  |.  8B4C24 14     mov     ecx, [esp+14]                    ; ecx <-- SIZE_T
                            
                            77A5278F  |.  C1E9 02       shr     ecx, 2                           ; ecx <-- (ecx >> 2) ( делим счётчик на 4)
                            77A52792  |.- 74 04         jz      short smaller_4                  ; 
                            
                            77A52794  |.  F3:A7         repe cmpsd                               ; В цикле по ecx сравниваем DWORD'ы;
                            77A52796  |.- 75 16         jne     short not_zero                   ; if ( !ZF ) goto not_zero;
                            
                            
                            
                            smaller_4:
                            77A52798  |>  8B4C24 14     mov     ecx, [esp+14]                    ; ecx <-- SIZE_T
                            
                            77A5279C  |.  83E1 03       and     ecx, 00000003                    ; ecx &= 3
                            77A5279F  |.- 74 04         jz      short return_SIZE_T              ; if ( ZF ) goto return_SIZE_T;
                            
                            77A527A1  |.  F3:A6         repe cmpsb                               ; в цикле сравниваем байты
                            77A527A3  |.- 75 16         jne     short found_difference
                            
                            
                            
                            return_SIZE_T:
                            77A527A5  |>  8B4424 14     mov     eax, [esp+14]                   ; eax <-- SIZE_T
                            77A527A9  |.  5F            pop     edi                             ; восстанавливаем значения регистров
                            77A527AA  |.  5E            pop     esi
                            77A527AB  |.  C2 0C00       ret     0C                              ; return eax
                            
                            
                            not_zero:
                            77A527AE  |>  83EE 04       sub     esi, 4                          ; esi -= 4
                            77A527B1  |.  83EF 04       sub     edi, 4                          ; edi -= 4
                            77A527B4  |.  B9 04000000   mov     ecx, 4                          ; ecx -= 4
                            77A527B9  |.  F3:A6         repe cmpsb                              ; в цикле сравниваем байты
                            
                            
                            found_difference:
                            77A527BB  |>  4E            dec     esi                             ; --esi
                            77A527BC  |.  2B7424 0C     sub     esi, [esp+0C]                   ; esi <-- (esi - Source1)
                            77A527C0  |.  8BC6          mov     eax, esi                        ; eax <-- esi
                            
                            77A527C2  |.  5F            pop     edi                             ; восстанавливаем значения регистров
                            77A527C3  |.  5E            pop     esi
                            
                            77A527C4  \.  C2 0C00       ret     0C                              ; return eax
                            

                              0
                              Спасибо! Добавьте пожалуйста это в топик для потомков, хотя бы как ссылку.
                            +1
                            Вот такое работает в полтора раза быстрее, чем SequentalEqual:

                            !a.Where((t, i) => t != b[i]).Any()
                              0
                              Спасибо за статью. Было бы интересно посмотреть на сравнение с x64.
                                +3
                                И еще одна цитата на счет JIT, просто на заметку:
                                The good news is that we do eliminate bounds checks for what we believe to be the most common form of array accesses: accesses that occur within a loop over all the indices of the loop. So, there is no dynamic range check for the array access in this program:
                                static void Test_SimpleAscend(int[] a) {
                                for (int i = 0; i < a.Length; i++)
                                a[i] = i; // We get this.
                                }

                                Unfortunately, we do not eliminate the range check for the descending version of this loop:
                                static void Test_SimpleDescend(int[] a) {
                                for (int i = a.Length — 1; i >= 0; i--)
                                a[i] = i; // We DO NOT get this.
                                }

                                Мои опыты еще на .Net 2.0 показали, что буквально любым усложнением можно нарушить тонкую грань, после которой JIT и/или компилятор перестает оптимизировать что-либо. Показательный пример когда есть приватный метод, берущий на вход IList<byte> и пробегающий по элементам, но используется только с byte[], а затем добавляется где-то еще код с LinkedList<byte> с вызовом этого метода и все начинает работать медленнее — компилятор переделывает метод на итераторы и страдает производительность той части, которая не менялась.
                                  +3
                                  буквально любым усложнением можно нарушить тонкую грань

                                  Косвенно в тему Вашему посту расскажу свою историю.

                                  Однажды на работе зашел разговор на тему оптимизаций. Поведали историю о том, как один человек отстаивал свою точку зрения против отдела (~10 человек). Он утверждал, что любой код с заранее известными исходными данными компилятор студии в релизе свернет до mov eax, <результат>. И тогда он победил — писали циклы с тремя уровнями вложенности, хитрили, но не смогли побороть это поведение. Естественно, я тоже решил проверить, и с первой попытки написал for одного уровня вложенности, который компилятор не смог на стадии компиляции вычислить. У меня получилось эту тонкую грань перейти.

                                  Вообще, оптимизации в компиляторах это крайне сложная часть computer science.
                                  0
                                  Вот такой unsafe код где-то в 1.5 раза быстрее вашего

                                  if (x.Length != y.Length)
                                  return false;
                                  fixed (byte* xp = x, yp = y)
                                  {
                                  int* xip = (int*) xp, yip = (int*) yp;
                                  int b = 0;
                                  int s = sizeof (int*);
                                  var il = x.Length/s;
                                  for (int i = 0; i < il; i++, b += s)
                                  {
                                  if (xip[i] != yip[i])
                                  return false;
                                  }
                                  for (; b < x.Length; b ++)
                                  {
                                  if (x[b] != y[b])
                                  return false;
                                  }
                                  }
                                  return true;
                                    +1
                                    Вы хотели сказать:
                                    public static unsafe bool CompareByteArrays(byte[] x, byte[] y)
                                    {
                                        if (x.Length != y.Length)
                                            return false;
                                        fixed (byte* xp = x, yp = y)
                                        {
                                            int* xip = (int*)xp, yip = (int*)yp;
                                            int b = 0;
                                            int s = sizeof(int);
                                            var il = x.Length / s;
                                            for (int i = 0; i < il; i++, b += s)
                                            {
                                                if (xip[i] != yip[i])
                                                    return false;
                                            }
                                            for (; b < x.Length; b++)
                                            {
                                                if (x[b] != y[b])
                                                    return false;
                                            }
                                        }
                                        return true;
                                    }
                                    

                                    В строке int s = sizeof(int*); у вас была ошибка, надо было без *, это совпадение что для x86 sizeof(int) == sizeof(int*).
                                    0
                                    во втором цикле начальное значение b всегда будет равно il * s, нет смысла из-за этого добавлять второй счетчик в основной цикл, ведь уже для размера 1025 байт мы выполним 256 лишних сложений.
                                      –1
                                      Я делал с умножением, но это оказалось медленнее.
                                        0
                                        В общем мой компилятор оказался достаточно умным и разница между умножением и сложением оказалась в пределах погрешности.
                                    0
                                    -del
                                      +1
                                      64 бита умножает необходимую для него память и снижает его производительность

                                      Возможность сразу сравнить 8 байт вместо 4 ой как снижает производительность, особенно в вашей задаче.
                                        0
                                        В .NET нативный метод string.equal использует, как мне помнится, как раз таки unsafe сравнение кусков памяти. Не пробовали его в своих тестах?
                                          0
                                          Статья написана с толком, но вот результаты у меня не получается воспроизвести. Я прогнал ваш тест на своей машине на Win 8.1 x64 VS 2010, скомпилировав под .NET 4.0 Client Profile/x86/Release. Кстати, зачем-то .NET Client Profile?

                                          Результаты внизу. Как видите Unsafe очень быстр, а PInvoke, SequenceEqual, и IStructuralEquatable показывают одинаковые цифры.

                                          Размер массива Минимальное время Unsafe PInvoke Простейший метод SequenceEqual IStructuralEquatable
                                          524288 14760 1: 001.0 1: 001.8 1: 006.9 1: 001.8 1: 001.8
                                          690001 18649 1: 001.0 1: 001.9 1: 007.4 1: 001.9 1: 001.9
                                          908093 24894 1: 001.0 1: 001.9 1: 007.2 1: 001.9 1: 001.9
                                          1195118 32039 1: 001.0 1: 001.9 1: 007.3 1: 001.9 1: 001.9
                                          1572863 41681 1: 001.0 1: 001.9 1: 007.5 1: 001.9 1: 001.9


                                          Так что с вашими выводами касательно производительности оптимизаций дотнета согласиться не могу.
                                            0
                                            1) В процессе экспериментов с большими массивами и отладчиком, я закомментировал некоторые вызовы в MeasurementsResults DoMeasurements().
                                            2) Метод PrepareTestData(int p_ArraySize) поправьте на тот, что в статье. Он был исправлен с той же целью.
                                            3) Константы тоже несколько отличаются, например private const int StartArraySize = 512 * 1024;
                                            3) Метод CompareArraysWithPInvokeMethod() тоже был изменён, в исследовательских целях. Однако это не столь сильно должно сказаться на итоговых данных.
                                            Посмотрите, поправьте, попробуйте.

                                            Посыпаю голову пеплом. Надо было поле получения итоговой таблицы, зазиповать исходники.

                                              +2
                                              О, ну здрасьте!
                                              result.SequenceEqualTime = result.IStructuralEquatableTime = result.PInvokeTime;
                                              Конечно же, это всё существенно меняет.

                                              (Я извиняюсь, на большее чем 32К меня не хватило. Может быть, Saladin будет более усидчив :)
                                              .net 4.5.1 x86
                                              Размер массива  Минимальное время  Unsafe   PInvoke  Простейший метод  SequenceEqual  IStructuralEquatable
                                              32768           17168              1 : 1.0  1 : 1.8  1 : 7.5           1 : 128.2      1 : 2267.8          

                                              .net 4.5.1 x86-64
                                              Размер массива  Минимальное время  Unsafe   PInvoke  Простейший метод  SequenceEqual  IStructuralEquatable
                                              32768           10878              1 : 2.2  1 : 1.0  1 : 13.6          1 : 286.5      1 : 2732.5          

                                              По поводу оптимизаций в Simplest:

                                              Осторожно! Ассемблер
                                                          if (p_BytesLeft.Length != p_BytesRight.Length)
                                              00000000  push        ebp 
                                              00000001  mov         ebp,esp 
                                              00000003  push        edi 
                                              00000004  push        esi 
                                              00000005  push        ebx 
                                              00000006  mov         edi,edx 
                                              00000008  mov         ebx,dword ptr [ecx+4] 
                                              0000000b  cmp         ebx,dword ptr [edi+4] 
                                              0000000e  je          00000017 
                                                          {
                                                              return false;
                                              00000010  xor         eax,eax 
                                              00000012  pop         ebx 
                                              00000013  pop         esi 
                                              00000014  pop         edi 
                                              00000015  pop         ebp 
                                              00000016  ret 
                                                          }
                                              
                                                          for (int i = 0; i < p_BytesLeft.Length; ++i) //вот так, без всяких хитростей мы байты сравниваем
                                              00000017  xor         esi,esi 
                                              00000019  test        ebx,ebx 
                                              0000001b  jle         00000039 
                                                          {
                                                              if (p_BytesLeft[i] != p_BytesRight[i])
                                              0000001d  movzx       eax,byte ptr [ecx+esi+8] 
                                              00000022  cmp         esi,dword ptr [edi+4] 
                                              00000025  jae         00000043 
                                              00000027  cmp         al,byte ptr [edi+esi+8] 
                                              0000002b  je          00000034 
                                                                  return false;
                                              0000002d  xor         eax,eax 
                                              0000002f  pop         ebx 
                                              00000030  pop         esi 
                                              00000031  pop         edi 
                                              00000032  pop         ebp 
                                              00000033  ret 
                                                          for (int i = 0; i < p_BytesLeft.Length; ++i) //вот так, без всяких хитростей мы байты сравниваем
                                              00000034  inc         esi 
                                              00000035  cmp         ebx,esi 
                                              00000037  jg          0000001D 
                                                          }
                                              
                                                          return true;
                                              00000039  mov         eax,1 
                                              0000003e  pop         ebx 
                                              0000003f  pop         esi 
                                              00000040  pop         edi 
                                              00000041  pop         ebp 
                                              00000042  ret 
                                              00000043  call        73039937 
                                              00000048  int         3

                                              Как видите, clr.JIT_RngChkFail действительно присутствует. В данном случае это связано с тем, что for ограничивает индекс границами p_BytesLeft, но этот же самый индекс используется для доступа к p_BytesRight. Таким образом, jit-компилятор не может убрать проверку. Да, мы выше проверяем длины массивов на равенство, но jit-компилятор сильно ограничен в возможностях оптимизации, поскольку его главная задача — быстро компилировать msil.

                                              Итого:
                                              1) В более простых случаях итерирования одного массива с помощью for, закэшировав длину массива, вы гарантированно ломаете оптимизации;
                                              2) Подумайте, почему 64-битный код и PInvoke оказываются быстрее (в лучшем случае — почти в 2 раза!), а unsafe код — медленнее ;)
                                                +1
                                                Вот чёрт, а я только репозиторий создал и залил туда исправленные исходники. Ссылка.
                                                Придется исправлять.
                                                  0
                                                  Да, наверное, это я должен был сделать с самого начала.
                                                  Сейчас добавлю ссылку в топик.
                                                0
                                                Если ещё точнее, то одну из двух проверок на границы jit-компилятор всё-таки выкинул.
                                                  0
                                                  Так там ведь проверяются длины массивов на равенство. Было бы совсем печально, если бы он этого не сделал.
                                                    +2
                                                    Так там ведь проверяются длины массивов на равенство.
                                                    Это не помогает :) А вообще, вот, советую к прочтению: Array Bounds Check Elimination in the CLR.
                                                  0
                                                  Кроме того, в исходниках, которые вы запускали, в методе DoMeasurements() присутствует строка:
                                                              result.SequenceEqualTime = result.IStructuralEquatableTime = result.PInvokeTime;
                                                  
                                                  Из-за этого результаты и неверны.

                                                  Поправлю опечатки и исходники — обновлю статью, выложу корректные исходники.

                                                  Смотрите, проверяйте, перепроверяйте. Увы, у меня без таких обидных ляпов не получается…
                                                    +2
                                                    Кстати, Эрик Липперт написал цикл замечательных статей о наиболее часто встречающихся ошибках при написании benchmark'ов. Рекомендую ознакомится: tech.pro/blog/1293/c-performance-benchmark-mistakes-part-one
                                              • UFO just landed and posted this here
                                                  0
                                                  Вы выходите за пределы массивов:
                                                            x1 += 2;
                                                            x2 += 2;
                                                  x1, x2 — это int*, => вы передвинетесь на 8 байтов.
                                                  • UFO just landed and posted this here
                                                      0
                                                      Вы только четверть массива итерируете. Либо вы делаете

                                                      int l = a1.Length, end = l/sz;
                                                      for (int i=0; i < end; i++, x1++, x2++ )

                                                      Либо

                                                      int l = a1.Length, end = l/sz;
                                                      for (int i=0; i < l; i+=sz, x1++, x2++ )

                                                      Если исправить, то вариант по результатам не отличается от моего
                                                      • UFO just landed and posted this here
                                                  • UFO just landed and posted this here
                                                    • UFO just landed and posted this here
                                                        0
                                                        ˂code˃ не сохраняет переводы строк ;) Но результаты понятны.
                                                        P.S. Нажимайте хотя бы разочек «Предпросмотр» — так вы убедитесь, что хабрапарсер не съел чего-нибудь лишнего.
                                                    +1
                                                    В комментариях возникло много нареканий на чистоту эксперимента. Могу предложить вам воспользоваться моим решением для построения .NET-бенчмарков: BenchmarkDotNet. Автоматически выставится ProcessorAffinity, приоритеты для потоков, делается прогрев кеша, итоговые статистики считаются по некоторой выборке экспериментов и т.п.
                                                      0
                                                      Я воспользовался вашим советом и переписал тесты с использованием BenchmarkDotNet. Результат здесь.

                                                      Однако, видимо, я что-то сделал не так, потому что иногда ошибка(Err) достигает 1055,11%.
                                                      Не могли бы взглянуть, правильно ли использован класс BenchmarkCompetition?
                                                      Результат запуска benchmark
                                                      E:\GitHub\Best-Way-to-Compare-Byte-Arrays-in-.Net\Benchmarks\bin\Release>Bench
                                                      rks.exe 1204000
                                                      BenchmarkCompetition: start
                                                      
                                                      ***** Simplest: start *****
                                                      WarmUp:
                                                      Ticks: 7706 ms: 2
                                                      Ticks: 4806 ms: 1
                                                      Ticks: 4700 ms: 1
                                                      Ticks: 4739 ms: 1
                                                      Stats: MedianTicks=4772, MedianMs=1, Error=63.96%
                                                      
                                                      Result:
                                                      Ticks: 4726 ms: 1
                                                      Ticks: 4784 ms: 1
                                                      Ticks: 4775 ms: 1
                                                      Ticks: 4736 ms: 1
                                                      Ticks: 4749 ms: 1
                                                      Ticks: 4798 ms: 1
                                                      Ticks: 4865 ms: 1
                                                      Ticks: 4716 ms: 1
                                                      Ticks: 4785 ms: 1
                                                      Ticks: 4797 ms: 1
                                                      Stats: MedianTicks=4779, MedianMs=1, Error=03.16%
                                                      ***** Simplest: end *****
                                                      
                                                      ***** SequenceEqual: start *****
                                                      WarmUp:
                                                      Ticks: 47214 ms: 15
                                                      Ticks: 41995 ms: 13
                                                      Ticks: 40726 ms: 13
                                                      Ticks: 41666 ms: 13
                                                      Stats: MedianTicks=41830, MedianMs=13, Error=15.93%
                                                      
                                                      Result:
                                                      Ticks: 40865 ms: 13
                                                      Ticks: 40682 ms: 13
                                                      Ticks: 40700 ms: 13
                                                      Ticks: 41486 ms: 13
                                                      Ticks: 43097 ms: 14
                                                      Ticks: 41157 ms: 13
                                                      Ticks: 41609 ms: 13
                                                      Ticks: 43426 ms: 14
                                                      Ticks: 41876 ms: 13
                                                      Ticks: 40337 ms: 13
                                                      Stats: MedianTicks=41321, MedianMs=13, Error=07.66%
                                                      ***** SequenceEqual: end *****
                                                      
                                                      ***** IStructuralEquatable: start *****
                                                      WarmUp:
                                                      Ticks: 700334 ms: 231
                                                      Ticks: 706967 ms: 234
                                                      Ticks: 703792 ms: 233
                                                      Stats: MedianTicks=703792, MedianMs=233, Error=00.95%
                                                      
                                                      Result:
                                                      Ticks: 700858 ms: 232
                                                      Ticks: 706920 ms: 234
                                                      Ticks: 699373 ms: 231
                                                      Ticks: 698729 ms: 231
                                                      Ticks: 697655 ms: 230
                                                      Ticks: 699388 ms: 231
                                                      Ticks: 699028 ms: 231
                                                      Ticks: 696725 ms: 230
                                                      Ticks: 702334 ms: 232
                                                      Ticks: 695562 ms: 230
                                                      Stats: MedianTicks=699200, MedianMs=231, Error=01.63%
                                                      ***** IStructuralEquatable: end *****
                                                      
                                                      ***** Unsafe: start *****
                                                      WarmUp:
                                                      Ticks: 5533 ms: 1
                                                      Ticks: 619 ms: 0
                                                      Ticks: 588 ms: 0
                                                      Ticks: 485 ms: 0
                                                      Ticks: 481 ms: 0
                                                      Ticks: 479 ms: 0
                                                      Stats: MedianTicks=536, MedianMs=0, Error=1055.11%
                                                      
                                                      Result:
                                                      Ticks: 553 ms: 0
                                                      Ticks: 474 ms: 0
                                                      Ticks: 622 ms: 0
                                                      Ticks: 475 ms: 0
                                                      Ticks: 551 ms: 0
                                                      Ticks: 683 ms: 0
                                                      Ticks: 479 ms: 0
                                                      Ticks: 480 ms: 0
                                                      Ticks: 476 ms: 0
                                                      Ticks: 480 ms: 0
                                                      Stats: MedianTicks=480, MedianMs=0, Error=44.09%
                                                      ***** Unsafe: end *****
                                                      
                                                      ***** PInvoke: start *****
                                                      WarmUp:
                                                      Ticks: 2076 ms: 0
                                                      Ticks: 619 ms: 0
                                                      Ticks: 568 ms: 0
                                                      Ticks: 557 ms: 0
                                                      Ticks: 564 ms: 0
                                                      Stats: MedianTicks=568, MedianMs=0, Error=272.71%
                                                      
                                                      Result:
                                                      Ticks: 567 ms: 0
                                                      Ticks: 628 ms: 0
                                                      Ticks: 558 ms: 0
                                                      Ticks: 364 ms: 0
                                                      Ticks: 362 ms: 0
                                                      Ticks: 454 ms: 0
                                                      Ticks: 364 ms: 0
                                                      Ticks: 362 ms: 0
                                                      Ticks: 438 ms: 0
                                                      Ticks: 571 ms: 0
                                                      Stats: MedianTicks=446, MedianMs=0, Error=73.48%
                                                      ***** PInvoke: end *****
                                                      
                                                      BenchmarkCompetition: finish
                                                      
                                                      Competition results:
                                                      Simplest             :   1ms
                                                      SequenceEqual        :  13ms
                                                      IStructuralEquatable : 231ms
                                                      Unsafe               :   0ms
                                                      PInvoke              :   0ms
                                                      



                                                      P.S. не весь код из ваших примеров компилируется, не молги бы вы поправить его?

                                                        0
                                                        Ну там, где Error=1055.11%, это warm up, можно в общем-то не обращать внимания.
                                                        А вот Error=73.48% PInvoke::Result (или 44.09% Unsafe::Result) — это звоночек.
                                                          0
                                                          Потому что для PInvoke получаются очень маленькие числа, поэтому большая ошибка.
                                                            0
                                                            Ticks: 567 ms: 0
                                                            Да, не обратил сначала внимания. Спасибо.
                                                          0
                                                          Сразу бросается в глаза большая ошибка: слишком малое время работы одного запуска бенчмарка. Увеличьте количество итераций. Время работы в районе 1–2ms не показывает вообще ничего, т.к. время работы бенчмарка сравнимо с временем накладных расходов (по запуску CLR, JIT-компиляции и т.п.) Нужно ЗНАЧИТЕЛЬНО увеличить время работы одного run-а. Да, в целом бенчмарк будет гоняться очень долго (особенно, с учётом нормального прогрева), вполне возможно что полный запуск всего займёт, скажем, час. Но зато у вас будут актуальные результаты на руках, которыми можно с чистой совестью делиться с общественностью.
                                                          Принято считать, что если Error>5%, то что-то пошло не так.

                                                          P.S. Ок, посмотрю что там за проблемы с компиляцией.
                                                            0
                                                            Я немного непонял, насчет значительного времени увелечения одного прогона. Нужно увеличить время выполнения теста, то есть скажем пробовать сравнить очень большие массивы. Или всё-таки увеличить количество самих прогонов, например увеличив BenchmarkSettings.Instance.DefaultResultIterationCount скажем до 10 миллионов?

                                                            Я больше склоняюсь ко второму варианту.
                                                              0
                                                              Тут нужно пробовать разные соотношения количества прогонов и размера массива. Нужно учитывать следующее:
                                                              1. Если массив будет слишком маленьким, то бенчмарк будет некорректен из-за того, что процессор мб сможет как-то хитро организовать кэширование данных. Возможно одни методы сравнения массивов более чувствительны к кешу, чем другие.
                                                              2. Если массив будет слишком большим, то бенчмарк будет некорректен из-за того, что на сцену могут выйти какие-нибудь memory issue (по типу использования файла подкачки или других реакций ОС не нехватку памяти).

                                                              Вообще, если проводить полноценное исследование, то нужно сравнивать методы в зависимости от размера массива, количества оперативки и процессорной архитектуры (размеры кешей и выбор x86/x64 имеют первостепенное значение). Но если задача состоит построить первое приближение к полноценному исследованию, то нужно постараться подобрать золотую середину — среднее значение величины массива, которое не вызовет сайд-эффектов. При этом нужно понимать, что вывод вида «один метод будет лучше другого в абстрактной ситуации» можно делать только при качественной разнице во времени работы. Разница в 5–10% может быть легко компенсирована сменой процессорной архитектуры.

                                                              Как только вы подберёте «оптимальный» размер массива, можно приступать к наращиванию количества прогонов. Один прогон должен выполняться хотя бы секунду, чтобы результаты были адекватны. Чем больше — тем лучше (тут всё зависит от того, насколько долго вы готовы ждать результатов).
                                                            0
                                                            P.S. не весь код из ваших примеров компилируется, не молги бы вы поправить его?

                                                            Мм. А какая у вас ошибка компиляции? У меня всё отлично собирается.
                                                              0
                                                              Код из этого примера github.com/AndreyAkinshin/BenchmarkDotNet/blob/master/BenchmarkDotNet.Samples/CustomSampleProgram.cs
                                                              Не компилируется, так как метод AddTask принимает два параметра вместо трёх.
                                                                0
                                                                Эмм. Вот сигнатура вызываемого метода:
                                                                public void AddTask(string name, Action initialize, Action action, Action clean)

                                                                Вот вызовы этого метода:
                                                                
                                                                competition.AddTask("For",
                                                                    () => { array = new int[ArraySize]; },
                                                                    () => For(),
                                                                    () => { array = null; });
                                                                competition.AddTask("Linq",
                                                                    () => { array = new int[ArraySize]; },
                                                                    () => Linq(),
                                                                    () => { array = null; });
                                                                

                                                                Метод должен принимать 4 параметра (точнее говоря, есть такая перегрузка этого метода). И при вызове ему как раз передаётся 4 параметра. Всё ещё не вижу проблемы.
                                                                  0
                                                                  Ну смотрите, я выкачал NuGet пакет версии «0.5.1».

                                                                  Этот пакет включает библиотеку «BenchmarkDotNet.dll» той же версии.
                                                                  Эта библиотека содержит класс BenchmarkCompetition. Вот его определение:

                                                                  // Type: BenchmarkDotNet.BenchmarkCompetition
                                                                  // Assembly: BenchmarkDotNet, Version=0.5.1.0, Culture=neutral, PublicKeyToken=null
                                                                  // MVID: A1FDCA59-3DB1-4AC6-9C3F-8307BAA3104A
                                                                  // Assembly location: E:\GitHub\Best-Way-to-Compare-Byte-Arrays-in-.Net\packages\BenchmarkDotNet.0.5.1\lib\net35\BenchmarkDotNet.dll
                                                                  
                                                                  using System;
                                                                  
                                                                  namespace BenchmarkDotNet
                                                                  {
                                                                    public class BenchmarkCompetition
                                                                    {
                                                                      public void AddTask(string name, Action initialize, Action action);
                                                                      public void AddTask(string name, Action action);
                                                                      public void Run();
                                                                      public void PrintResults();
                                                                    }
                                                                  }
                                                                  


                                                                  Вполне возможно, что проблема в том, что опубликованный NuGet пакет не первой свежести, но это все что я нашел через NuGet поиск.
                                                                    0
                                                                    Да, всё верно, проблема в версии. После публикации версии 0.5.1 в NuGet было ещё несколько коммитов (в том числе коммит, включающий обсуждаемый Sample). Я сегодня/завтра доберусь до репозитория и выложу в NuGet свежую версию (она будет иметь номер 0.5.2). Вы можете либо подождать, либо скачать исходники с GitHub-а и ручками подключить в свой Solution проект со свежей версией (однако, если вы собираетесь обновлять свой бенчмарк на GitHub-е, то советую дождаться обновлённой версии, чтобы просто подцепить зависимость).
                                                                      +1
                                                                      Обновил версию пакета в NuGet до 0.5.2. Теперь можете работать со свежими обновлениями: https://www.nuget.org/packages/BenchmarkDotNet/
                                                                0
                                                                И ещё один совет: в вашем примере разумно создавать массивы один раз в самом начале, нет нужны пересоздавать их на каждый Task. Конечно, профилактические вызовы GC делаются в нужных местах, но всё же в бенчмарках хорошо бы максимально сократить подобные операции.
                                                              0
                                                              Хм, а почему бы не попробовать сделать сравнение буферов в несколько потоков?
                                                                0
                                                                Пробовал делать через AsParallel — производительности не прибавляется.
                                                                +3
                                                                Пожалуйста, повторите измерение для PInvoke, применив атрибут SuppressUnmanagedCodeSecurity.

                                                                Описание говорит, что он ускоряет дело. Есть надежда получить результат близкий к наибыстрейшему даже на коротких массивах.
                                                                  +1
                                                                  Не знал, большое спасибо и за подсказку и за внимательность!

                                                                  Применение атрибута дало хороший эффект. Прогон от 1 байта до 12 Кб дал вот такие результаты:

                                                                  Размер массива  Минимальное время  Unsafe     PInvoke    Простейший метод  SequenceEqual  IStructuralEquatable
                                                                  1               273                1 : 001,8  1 : 003,5  1 : 001,0         1 : 010,5      1 : 055,3
                                                                  1               271                1 : 001,8  1 : 003,5  1 : 001,0         1 : 010,3      1 : 055,6
                                                                  2               325                1 : 002,4  1 : 003,0  1 : 001,0         1 : 010,9      1 : 092,2
                                                                  3               326                1 : 002,4  1 : 003,0  1 : 001,0         1 : 010,7      1 : 092,3
                                                                  4               377                1 : 001,1  1 : 002,7  1 : 001,0         1 : 011,4      1 : 118,7
                                                                  6               425                1 : 001,0  1 : 002,7  1 : 001,0         1 : 011,6      1 : 138,8
                                                                  9               426                1 : 001,0  1 : 002,6  1 : 001,2         1 : 013,5      1 : 174,0
                                                                  13              426                1 : 001,0  1 : 002,7  1 : 001,6         1 : 016,7      1 : 241,4
                                                                  20              490                1 : 001,0  1 : 002,4  1 : 002,1         1 : 020,5      1 : 330,4
                                                                  29              490                1 : 001,0  1 : 002,5  1 : 002,7         1 : 026,5      1 : 448,2
                                                                  43              560                1 : 001,0  1 : 002,2  1 : 003,4         1 : 032,3      1 : 572,4
                                                                  63              638                1 : 001,0  1 : 002,1  1 : 004,2         1 : 039,8      1 : 731,8
                                                                  91              806                1 : 001,0  1 : 001,8  1 : 004,7         1 : 044,2      1 : 832,3
                                                                  133             1012               1 : 001,0  1 : 001,7  1 : 003,9         1 : 052,5      1 : 960,5
                                                                  195             1335               1 : 001,0  1 : 001,5  1 : 004,1         1 : 057,2      1 : 1066,8
                                                                  284             1769               1 : 001,0  1 : 001,4  1 : 004,4         1 : 061,7      1 : 1172,5
                                                                  414             2414               1 : 001,0  1 : 001,3  1 : 004,5         1 : 064,8      1 : 1247,9
                                                                  603             3380               1 : 001,0  1 : 001,2  1 : 004,6         1 : 066,9      1 : 1292,7
                                                                  879             4750               1 : 001,0  1 : 001,2  1 : 004,7         1 : 068,6      1 : 1343,9
                                                                  1282            6423               1 : 001,0  1 : 001,2  1 : 005,0         1 : 073,8      1 : 1449,2
                                                                  1868            8893               1 : 001,0  1 : 001,2  1 : 005,2         1 : 077,5      1 : 1526,0
                                                                  2723            12667              1 : 001,0  1 : 001,2  1 : 005,4         1 : 079,0      1 : 1560,1
                                                                  3969            18042              1 : 001,0  1 : 001,2  1 : 005,4         1 : 080,9      1 : 1598,8
                                                                  5785            25872              1 : 001,0  1 : 001,2  1 : 005,5         1 : 082,1      1 : 1640,5
                                                                  8431            37341              1 : 001,0  1 : 001,2  1 : 005,6         1 : 083,2      1 : 1645,5
                                                                  12288           54115              1 : 001,0  1 : 001,2  1 : 005,6         1 : 083,6      1 : 1653,2
                                                                  


                                                                  Трэйс от управляемого кода к функции показал всего 50 команд.
                                                                  main  00540F14                    call    001DC2F4                        ESP=001AEE14
                                                                  main  001DC2F4                    mov     eax, 1D38D8                     EAX=001D38D8
                                                                  main  001DC2F9                    mov     ebp, ebp
                                                                  main  001DC2FB                    jmp     00540F40
                                                                  main  00540F40                    push    ebp                             ESP=001AEE10
                                                                  main  00540F41                    mov     ebp, esp                        EBP=001AEE10
                                                                  main  00540F43                    push    edi                             ESP=001AEE0C
                                                                  main  00540F44                    push    esi                             ESP=001AEE08
                                                                  main  00540F45                    push    ebx                             ESP=001AEE04
                                                                  main  00540F46                    sub     esp, 28                         ESP=001AEDDC
                                                                  main  00540F49                    mov     [ebp-18], eax
                                                                  main  00540F4C                    xor     ebx, ebx                        EBX=00000000
                                                                  main  00540F4E                    mov     [ebp-10], ebx
                                                                  main  00540F51                    mov     [ebp-14], ebx
                                                                  main  00540F54                    mov     esi, fs:[0E38]                  ESI=002F2AE0
                                                                  main  00540F5B                    mov     dword ptr [ebp-30], 645CABC8
                                                                  main  00540F62                    mov     dword ptr [ebp-34], C28DAB21
                                                                  main  00540F69                    mov     eax, [esi+0C]                   EAX=001AF09C
                                                                  main  00540F6C                    mov     [ebp-2C], eax
                                                                  main  00540F6F                    mov     [ebp-1C], ebp
                                                                  main  00540F72                    mov     dword ptr [ebp-20], 0
                                                                  main  00540F79                    lea     eax, [ebp-30]                   EAX=001AEDE0
                                                                  main  00540F7C                    mov     [esi+0C], eax
                                                                  main  00540F7F                    xor     ebx, ebx
                                                                  main  00540F81                    test    ecx, ecx
                                                                  main  00540F83                    je      short 00540F8F
                                                                  main  00540F85                    mov     [ebp-10], ecx
                                                                  main  00540F88                    mov     eax, ecx                        EAX=023B42E4
                                                                  main  00540F8A                    add     eax, 8                          EAX=023B42EC
                                                                  main  00540F8D                    mov     ebx, eax                        EBX=023B42EC
                                                                  main  00540F8F                    xor     edi, edi                        EDI=00000000
                                                                  main  00540F91                    test    edx, edx
                                                                  main  00540F93                    je      short 00540F9F
                                                                  
                                                                  main  00540F95                    mov     [ebp-14], edx
                                                                  main  00540F98                    mov     eax, edx                        EAX=023B42E4
                                                                  main  00540F9A                    add     eax, 8                          EAX=023B42EC
                                                                  main  00540F9D                    mov     edi, eax                        EDI=023B42EC
                                                                  main  00540F9F                    mov     eax, [ebp-18]                   EAX=001D38D8
                                                                  main  00540FA2                    mov     eax, [eax+14]                   EAX=001D397C
                                                                  main  00540FA5                    mov     ecx, [eax]                      ECX=75A97975
                                                                  main  00540FA7                    push    dword ptr [ebp+0C]              ESP=001AEDD8
                                                                  main  00540FAA                    push    dword ptr [ebp+8]               ESP=001AEDD4
                                                                  main  00540FAD                    push    edi                             ESP=001AEDD0
                                                                  main  00540FAE                    push    ebx                             ESP=001AEDCC
                                                                  main  00540FAF                    mov     dword ptr [ebp-28], 0
                                                                  main  00540FB6                    mov     [ebp-24], esp
                                                                  main  00540FB9                    mov     dword ptr [ebp-20], 540FC6
                                                                  main  00540FC0                    mov     byte ptr [esi+8], 0
                                                                  main  00540FC4                    call    ecx                             ESP=001AEDC8
                                                                  
                                                                  

                                                                Only users with full accounts can post comments. Log in, please.