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 байт, а на каждом следующем шаге размер тестовых массивов умножался на одинаковый множитель.

Параметры задавались константами в коде:

Основной цикл тестирования выглядел вот так:

Размер массива на каждом шаге вычислялся вот так:

Это относительно новый для C# способ, он появился только в .NET 4, поэтому он представлял для меня особый интерес: любопытно было, насколько он всё-таки медленный.

Это один из самых простых методов, самый простой для реализации. Кроме того, это самый популярный метод.

Теоретически, это должен быть самый быстрый способ, но выяснилось, что это не всегда так: накладные расходы на взаимодействие с платформой съедают довольно большое время, и этот метод в некоторых случаях теряет свою привлекательность. Здесь я привожу его в тмо виде, в котором нашёл его на SO. Именно в таком виде я его и тестировал. На PInvoke.net он выглядит несколько иначе.

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

Кстати, одна из вариаций этого метода сравнения была использована в статье от самих Производителей СLR, притом именно в том котексте, в котором она понадобилась мне. Видимо, пользователи их доканали такими вопросами.

Автор метода утверждает, что этот оптимизированный метод делает сравнение блоками размером 64 бита для возможно большей части массива, рассчитывая на то, что начало массива выравнено по границе QWORD. Он также будет работать, если нет QWORD-выравнивания, но с меньшей скоростью. Однако, в 32 битной среде сравнения блоками в 64 бита можно добиться только с помощью ассемблера: регистры общего назначения 32 битные, а компилятор при генерации машинного кода, использует именно их. Так что, как этот метод дейсвтительно будет работать, зависит от того как он будет скомпилирован. В моём случае — точно не 64 бита.

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

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

Тестовые данные генерировались таким образом, чтобы отличались все массивы, а отличающийся элемент массива находился ровно посередине.

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

Однако тут есть одно «но»: если никак не использовать результат «вычислений», то CLR имеет полное право само «вычисление» не производить. Я с этим сталкивался раньше, когда экспериментировал с C++. При включенной оптимизации «-O3» было весьма проблематично что-либо измерить, т.к. время раз за разом получалось нулевым. Поэтому такой сценарий было решено исключить с самого начала, так что результат работы функции сравнения «аккумулировался» и возвращался, а на самом верхнем уровне анализировался.

Поскольку методов сравнений 5, а вышеописанный шаблон общий, то кажется логичным определить общий, «шаблонный» метод, и передать метод сравнения в него. Таким образом:

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

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

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

Перед началом эксперимента я примерно догадывался, какой метод окажется победителем, а какой аутсайдером, однако результаты меня всё-таки удивили. Мои прогнозы оказались не совсем верны. Лучшее время (тики) Размер массива (байты) 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'ера, т.е. на непосредственно генерируемый машинный код.

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

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

Интерес также представляет первая половина этой функции, т.е. до момента вызова UnsafeCompare(). Она, так же, как и первая, демонстрирует, что любое обращение к элементу массива вызывает проверку индекса на вхождение в границы массива. Я подчеркнул это в листинге.

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

В соответствии с соглашением вызова fastcall, которому следует .NET Framework [7][8], в регистрах ecx и edx находятся первый и второй параметры, в соответствии с порядком слева направо. В приведённом листинге хорошо видна последовательная проверка входных параметров, он почти однозначно соответствует коду на C#

Однако, особого внимания заслуживают выделенные строки: назначение их неясно, и они запутывают. Чтобы понять, что это такое и зачем оно может быть нужно, мне пришлось поставить ещё один эксперимент, в ходе которого я написал простейшую unsafe-функцию на C#, которая использует предложение fixed и обращение по указателю, и провёл с ней аналогичные действия.

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

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

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

Никаких сюрпризов компилятор здесь не преподнёс, т.е. алгоритм компиляции даёт легко предсказуемые результаты. Например, переменные, инициализируемые в предложении fixed, в любом случае размещаются в стеке. Инициализация переменных внутри блока fixed:

Инициализация переменных внутри блока fixed любопытна тем, что хорошо демонстрирует принцип, по которому JIT-компилятор генерирует код. Здесь хорошо видно, что вместо прямой пересылки значений из стековых переменных в индексные регистры, значения сначала помещаются в регистр-аккумулятор. Может быть, в этом и есть какой-нибудь тайный магический смысл, но выглядит это (пересылка в eax) просто как лишнее действие.

Структура цикла достаточно тривиальна, например, счётчик цикла традиционно располагается в 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, выполняется, если такой объём остался:

Попытка сравнить блоки размером WORD, выполняется, если такой объём остался:

Попытка сравнить блоки размером BYTE, выполняется, если такой объём остался:

Возврат результата и выброс исключения:

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

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

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

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

Она копирует регистр сам в себя, не обновляя при этом никаких флагов, т.е. результат её выполнения нулевой, прямо как nop, но размером в 2 байта. Промотав код в окне отладчика, я обнаружил, что точно так же начинаются множество других функций. Благодаря блогу Рэймонда Чена объяснение нашлось быстро. Это действительно аналог nop.

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

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

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

Часть лога трассировки:

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

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

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

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

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

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

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

Первый взгляд на лог второй трассировки: за одну итерацию цикла сравниваются 8 двойных слов, и это хорошо: видно, что цикл развёрнут, а с другой стороны, после каждого сравнения идёт абсолютно одинаковый бесполезный код: в регистр esi заносится 0 и анализируется содержимое регистра esi. У меня нет никаких предположений о том, зачем это было сделано, однако есть предположение о том, как такое могло получиться: во-первых, это очень похоже на результат работы какого-то макроса, формировавшего ассемблерный код, а во-вторых, похоже, что майкрософтовский компилятор C не так хорош, как я об этом думал раньше.

Примечательно, что на больших объёмах тестовых данных этот код показал результат на

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): «Только если особый случай не найден, компилятор выполняет реализацию, рассчитанную на самый общий случай и потому потенциально менее эффективную».

.CHAPTER 2. Intel ® 64 Architecture : Application Programming CHAPTER 1 Long Mode . CHAPTER 3. Alignment
1. Windows Internals, Sixth Edition, Part 1, CHAPTER 5 Processes, Threads, and Jobs
2. Windows Internals, Sixth Edition, Part 2, CHAPTER 10. Memory Management
3. Intel® 64 and IA-32 Architectures Software Developer Manuals. CHAPTER 17. TIME-STAMP COUNTER
4. Joe Duffy, Professional .NET Framework 2.0 (Programmer to Programmer). Chapter 3: Inside the CLR, Just-In-Time (JIT) Compilation

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

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

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

Перед изучением кода функции, я её протестировал, предварительно выставив атрибут SuppressUnmanagedCodeSecurity для функции memcmp() и RtlCompareMemory() Любопытно, что системная функция, которую можно вызывать и из user-mode и из kernel-mode, оказалась медленнее чем функция из набора CRT.

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