Конечно, всё серьёзные шахматные программы пишут на 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++ = 0x48; *ptr++ = 0x0F; *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, <PatchCallSite>
call rax
add rsp, 0x20 ; поправляем стэк обратно
pop rax ; достаём из него ответ
ret
Всем этим занимается функция Patcher.PatchMethod, которую мы вызовем для всех методов, которые надо пропатчить.
Вот как это выглядит на живом примере (из PerfTest):
(если картинку не видно)
и после первого прохода:
(если картинку не видно)
Теперь остались мелочи: 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. Вот детали тестов.
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
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
Специально для сайта ITWORLD.UZ. Новость взята с сайта Хабр