Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 17.06.2014 | нет комментариев

Суть этого поста

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

Compilerrun-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-й тестовый на_lqvmk!br/> Так что, как данный способ дейсвтительно будет трудиться, зависит от того как он будет скомпилирован. В моём случае — верно не 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() (http://msdn.microsoft.com/ru-ru/library/system.diagnostics.stopwatch(v=vs.110).aspx ). Безусловно, волновали не миллисекунды, а тики: в случае крошечных массивов все измерения в миллисекундах были бы нулевыми. Также была идея задействовать свой «велосипед» на основе 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;
      }

Итоги измерений и первые итоги

Перед началом эксперимента я mk! 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 на крупных массивах (я ждал не больше 2-х-трёхкратного «перевеса») разрешает предположить, что с оптимизацией циклов и обращений к элементам массива в .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. Возможно, вследствие предыдущему пункту (опухший код), функция не была заинлайнена.

Обзор функции CompareArraysWithSimplestMethod()

Итог декомпиляции этой функции разжёг моё любопытство и навёл на мысль об остальных функциях. Я решил сравнить 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(). Она, так же, как и первая, показывает, что всякое обращение к элементу массива вызывает проверку индекса на вступление в границы массива. Я подчеркнул это в листинге.

Место вставки Thread.Sleep()

;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-й индекс) (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-й индекс) (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 находятся 1-й и 2-й параметры, в соответствии с порядком слева направо. В приведённом листинге отлично видна последовательная проверка входных параметров, он примерно однозначно соответствует коду на 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 был сохранён в стеке, в последующем не применялся и, следственно, был свободным и доступным для операций (до смещения 0×26 от начала функции), но под хранение временных данных была использована стековая переменная по смещению [ebp-4] (назовём её var1). Переменная сразу же непременно инициализируется нулём, невзирая на то, что потом это значение не применяется, а легко затирается. Скажем, по смещению 0×15 в 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-х команд каждого 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:WindowsSysWOW64msvcrt.dll версии 7.0.7601.17744.

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

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

1-й же взор на препарируемую функцию меня несколько смутил: во-первых, перед стандартным прологом, в самом начале функции, располагалась необычная инструкция, а во-вторых, размеры этой функции удивляют воображение. Кинулось в глаза присутствие «длинных» джампов, к тому же 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          ddmsvcrt.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. С точки зрения оптимизации это абсолютно умное действие, т.к. не выполняется инициализация цикла.

Второе, что сразу же кинулось в глаза – крайне странный метод занесения числа 0×20 в регистр 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

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

1-й взор на лог 2-й трассировки: за одну итерацию цикла сравниваются 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 Architecturewww.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html.
  2. AMD64 Architecture Programmer’s Manual Volume 1: Application Programming CHAPTER 1 Long Mode
    amd-dev.wpengine.netdna-cdn.com/wordpress/media/2012/10/24592_APM_v11.pdf
  3. Intel® 64 and IA-32 Architectures Optimization Reference Manual. CHAPTER 3. Alignmentwww.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html
  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
    msdn.microsoft.com/en-us/magazine/cc163791.aspx#S6
  8. Joe Duffy, Professional .NET Framework 2.0 (Programmer to Programmer). Chapter 3: Inside the CLR, Just-In-Time (JIT) Compilation
Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB