Расширенные инструкции процессора в .NET или «C# Intrinsics»
В шахматных программах широко используются «битовые доски» (битборды 1, 2) для представления фигур на доске. А так же и для других игр на той же доске 8×8, и даже для карточных игр. С битбордами часто проводят различные операции, например, найти первый установленный бит или посчитать количество установленных битов. Для этих операций придумано много «хитрых» алгоритмов, а на современных процессорах некоторые из этих операций доступны в расширенном наборе инструкций. Например, popcnt, доступный в SSE4.2 ABM. Также есть пара инструкций bsf/bsr, которые доступны уже давно, но из JIT-компилятора к ним нет никакого доступа.Конечно, всё серьёзные шахматные программы пишут на C++, но для прототипирования каких-нибудь алгоритмов хочется использовать C#, потому что я с ним лучше знаком и у меня меньше шансов выстрелить себе в ногу. Но производительность тоже не хочется терять просто так, в C/C++ интересующие нас инструкции доступны так называемые встроенные функции. Я попробовал сделать подобное решение и для C#.Для SIMD инструкций есть готовыебиблиотеки, а для манпуляций с битами — нет.Что делать? Надо как-то пропатчить имеющийся код.Остановимся на том, что мы используем 64-битный процессор (на 32х битном не так весело работать с битбордами), и этот процесор — x86_64. Для несовместимых архитектур надо иметь фоллбэки (реализацию на C#). При таких условиях bsf/bsr будут доступны всегда, а popcnt недоступен только на довольно древнем железе, но об этом позже.Самый простой вариант — написать DLL на С++ и экспортировать оттуда нужные нам функции. Но эти «функции» будут состоять из одной инструкции, а вокруг них будет несколько лишних джампов, которые возникнут при PInvoke.Второй вариант: использовать GetDelegateForFunctionPointer, он похож на первый, но не требует отдельной нативной DLL.Третий — подменять уже скомпилированный метод. Про это написано много интересных статей. Но тут возникают проблемы с тем, что это а) сложно б) появляются зависимости от внутренностей рантайма, а следовательно, и его версии. В итоге получаем громоздкое и нестбильное решение, это не наш путь.Остаётся последний вариант: патчить скомпилированный JIT-ом код.
Детали реализации Для начала нам надо убедиться, что метод скомпилирован: RuntimeHelpers.PrepareMethod (). А чтобы добраться до машинного кода, майкрософт заботливо предоставило нам метод RuntimeMethodHandle.GetFunctionPointer (). Но по этой ссылке в зависимости от рантайма может оказаться как сам метод, так и трамплин на него. Хорошо, что трамплин бывает только одного вида — JMP. Этим мы и воспользуемся: static byte* GetMethodPtr (MethodInfo method) { RuntimeHelpers.PrepareMethod (method.MethodHandle); var ptr = (byte*)method.MethodHandle.GetFunctionPointer (); // skip all jumps while (*ptr == 0xE9) { var delta = *(int*)(ptr + 1) + 5; ptr += delta; } return ptr; } Итак, адрес мы получили, попробуем записать туда что-нибудь. Надо учесть Call-Convention, благо на x86_64 он один (первые четыре аргумента в RCX, RDX, R8, R9, результат в RAX): //bsr rax, rcx; ret *ptr++ = 0×48; *ptr++ = 0×0F; *ptr++ = 0xBD; *ptr++ = 0xC1; *ptr++ = 0xC3; Пробуем… Ура, работает! Но сейчас наш вариант ничем не отличается по производительности от PInvoke/GetDelegateForFunctionPointer: тут есть лишние call/jmp из вызывающего метода. К тому же, если нашу функцию-фоллбэк компилятор зайинлайнил, то патч данного места ничем не поможет.От инлайна можно довольно легко отказаться с помощью атрибута [MethodImpl (MethodImplOptions.NoInlining)])].Ещё, как и в С++-intrinsics, необходимо полностью отказаться от call/jmp. С этим тоже довольно легко справиться, правда, придётся немного испачкать руки ассемблером. Патчить место вызова будем на лету. Для этого надо подменить код нашего фоллбэка не просто на нужную инструкцию, а на вызов «патчера» с нужными параметрами: по какому адресу и на что заменить.Начнём с определения адреса: у нас есть адрес возврата в стэке (в dword ptr [rax]), обычно вызов нашего метода случается как раз перед ним. Если это инструкция call (а обычно это она), то нам надо проверить предыдущие 5 байт, и если это действительно был вызов нужного метода, то заменить их целиком на опкод нашей инструкции. Метод-патчер будет выглядеть вот так:
static void PatchCallSite (byte* rsp, ulong code)
{
var ptr = rsp — 5;
// check call opcode
if (*ptr!= 0xE8) {
// throw ERROR
}
const ulong Mask5Bytes = (1uL << 40) - 1;
*(ulong*)ptr = *(ulong*)ptr & ~Mask5Bytes | (code & Mask5Bytes);
}
А вызывать мы его будем вручную из ассемблера, в итоге наш фоллбэк-метод будет заменён на такую штуку:
bsr rax, rcx ; заменяющая инструкция
nop ; дополним до 5 байт
push rax ; сохраним её ответ
sub rsp, 0x20 ; место под register spilling
mov rcx, QWORD PTR [rsp+0x28] ; первый аргумент — адрес возврата
; он был на стэке при входе в функию,
; а сейчас «уполз» на 0x20 + 8 байт
mov rdx, QWORD PTR [rip-0x16] ; второй аргумент — на что менять
; ссылается на начало этого куска кода
movabs rax,
Теперь остались мелочи: JIT может что-нибудь куда-нибудь очень сильно заинлайнить, или сделать tail-call оптимизацию, тогда адрес возврата не очень-то будет соответствовать вызову нашей функции. К сожалению, я не смог найти примеры таких агрессивных оптимизаций, но на всякий случай это тоже надо проверять. Зная место, откуда был совершён call, мы можем проверить, что он на самом деле вызывал. Тут тоже надо перепрыгнуть через все jmp-ы, и проверить, что они приведут нас в нужное место. А благодаря тому, что заменяющие инструкции мы поместили в самом начале патча в неизменном виде, сделать это очень легко:
// check call target var calltarget = ptr + *(int*)(ptr + 1) + 5; while (*calltarget == 0xE9) { var delta = *(int*)(calltarget + 1) + 5; calltarget += delta; } code &= Mask5Bytes; if ((*(ulong*)calltarget & Mask5Bytes) != code) { // throw ERROR } А ещё нам желательно ничего не трогать, если мы вдруг оказались на неподдерживаемой архитектуре. Для начала проверим, что она вообще 64-битная: (IntPtr.Size == 8). Дальше надо удостовериться, что это x86_64. Я не нашёл ничего лучше, чем сравнить пролог любой функции с заведомо верными инструкциями (см Patcher.VerifyPrologue в коде).Некоторые инструкции, например popcnt, доступны не на всех процессорах. Если вам важна скорость, то лучше такие процессоры вообще не использовать, но в библиотеке желательно оставить для них фолл-бэк. В интеловском мануале написано, что проверить наличие инструкции popcnt можно вызвав cpuid с eax=01H и проверить бит ECX.POPCNT[Bit 23]. Тут нам на помощь приходит stackoverflow-driven development, где можно найти готовый кусок кода для вызова cpuid из C#.
Осталось только красиво всё это завернуть: делаем атрибут [ReplaceWith («F3 48 0F B8 C1», Cpiud1ECX = 1 << 23)], который клеим к фолбэк-функциям. В нём содержится кода, на который надо заменить данный intrinsic, а также условие доступности нужной инструкции.
Бенчмарки Бенчмарки довольно примитивные: генерируем массив псевдо-случайных чисел, потом гоняем по нему 100 млн раз каждый метод. Чтобы исключить влияние цикла и прочей обвязки, сначала измеряем время пустого цикла. Отдельно протестирован специальный случай «разреженных» досок: довольно часто доска содержит до 8 фигур или помеченных клеток, и на таких досках текущий выбранный фолбэк должен отрабатывать быстрее.Я померял и проверил на двух процессорах, которые были под рукой: ноутбучный i7 и старый добрый Q6600. Вот детали тестов.i7–3667U Testing Rng… 78ms, sum=369736839
Testing BitScanForward… 123ms, sum=99768073
Testing FallBack.BitScanForward… 239ms, sum=99768073
Testing PopCnt64… 106ms, sum=-1092098543
Testing FallBack.PopCnt64… 3143ms, sum=-1092098543
Testing PopCnt32… 106ms, sum=1598980778
Testing FallBack.PopCnt32… 2139ms, sum=1598980778
Testing PopCnt64 on sparse data… 106ms, sum=758117720
Testing FallBack.PopCnt64 on sparse data… 952ms, sum=758117720 Q6600 Patch status: Ok Feature PopCnt is not supported by this CPU Feature PopCnt is not supported by this CPU
Testing Rng… 92ms, sum=369736839
Testing BitScanForward… 154ms, sum=99768073
Testing FallBack.BitScanForward… 323ms, sum=99768073
Testing PopCnt64… 3832ms, sum=-1092098543
Testing FallBack.PopCnt64… 3583ms, sum=-1092098543
Testing PopCnt32… 2414ms, sum=1598980778
Testing FallBack.PopCnt32… 3249ms, sum=1598980778
Testing PopCnt64 on sparse data… 1662ms, sum=758117720
Testing FallBack.PopCnt64 on sparse data… 1076ms, sum=758117720 Сводная таблица результатов, тут уже вычтено время «холостого» цикла:
bsf
bsf fallback
popcnt64
popcnt64 fallback
popcnt32
popcnt32 fallback
sparse popcnt64
sparse popcnt64 fallback
i7–3667U
45ms
161ms (~3.6x slower)
28ms
3065ms (~100x slower)
28ms
2061ms (~70x slower)
28ms
874ms (~30x slower)
Q6600
62ms
231ms (~3.7x slower)
N/A
3491ms
N/A
3157ms
N/A
984ms
Как мы видим, на инструкциях bsf/bsr наш фоллбэк работает достаточно быстро, так что прирост от интринсика будет небольшим, и даже незаметным на фоне других частей алгоритма. А вот для popcnt уже намного лучше, если у вас есть Core i5/i7, то он ускорится в десятки раз.Применительно к конечному алгоритму я получил ускорение всего-лишь на 15%, т.к. там ещё много кода, который не только считает биты. Как говорится, YMMV, проверяйте на своём коде.Где взять
Код можно взять на 
гитхабе.NuGet: Install-Package NetIntrinsics
