Расширенные инструкции процессора в .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++ = 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. Вот детали тестов.
    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
    Поделиться публикацией

    Похожие публикации

    Комментарии 10

      +5
      Круто, фактически патчинг JITter =)
        0
        Надо учесть Call-Convention, благо на x86_64 он один

        Кстати, если формально — то два, в UNIX-мире соглашение другое. Если хотите сделать код портируемым хотя бы на x86_64 + Mono — имеет смысл сделать детект и поддержку SysV-варианта.
          0
          Да, там сейчас проверяется на всякий случай пролог функции, и в моно он будет другим. Для моно не стал делать отдельного патча, потому что если требуется «выжать ещё немного скорости», то лучше пересесть с моно на дотнет, а если нет винды, то на c++ или jvm.
          0
          На моно не надо патчить, он сам умеет всё нужное. См. Mono.Simd
            0
            А там есть popcnt/bsf/bsr? Насколько я понял, оно умеет только SIMD инструкции, а нужные нам к ним не относятся, хотя появились примерно вместе с ними.
            +3
            А в 90-х мы так делали для инструкций x87 процессора на тот случай, если его нет. :)
              0
              Применительно к конечному алгоритму я получил ускорение всего-лишь на 15%

              «Всего лишь»? По-моему это очень неплохо.
                0
                это по сравнению с ускорениями до 100× в бенчмарках )
                +3
                Прежде всего хочется скачать большое спасибо за пост. Получил большое удовольствие от чтения. А теперь немного конструктивной критики.

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

                Хотелось бы более интеллекутальных бенчмарков.

                1. Нет прогрева и множественных замеров. Для получения действительно хороших результатов нужно сначала каждый тест прогнать несколько раз вхолостую, затем несколько раз с замером времени, взять среднее значение и обратить внимание на то, как «пляшет» время от запуску к запуску. Для автоматизации можете попробывать BenchmarkDotNet.
                2. Нет анализа того, как проводится развёртка цикла. Обычный JIT весьма коварен в этом плане. Иногда складывается такое ощущение, что он может принимать решение о развёртке цикла в зависимости от фазы луны. Если получится так, что в одних тестах цикл разворачивается, а в других — нет, то это очень грустно.
                3. Не указан размер кеша процессора и не сделаны выводы о возможных cache-miss-ах. При изменении размера массива они могут оказать значительное влияние на результаты бенчмарка.
                4. Да и в целом хорошо бы погонять бенчмарки на массивах разных размеров, чтобы исключить непредвиненные сайд-эффекты.
                5. Не помешает выставить ProcessorAffinity-маску, чтобы рантайм не перекидывал ваше приложение с одного ядра на другое — от этого опять-таки могут возникнуть неприятные сайд-эффекты.
                6. Скоро на экранах появится RuyJIT. Было бы здорово и на нём проверить вашу логику.

                Хотелось бы уточнить: я не говорю, что ваши бенчмарки дают неверные результаты. Возможно, что ни один сайд эффект не сработал, и временные замеры получились более или менее адекватные. Но просто так брать и доверять результатам бенчмарков нельзя — необходим более глубокий и внимательный подход.
                  0
                  Спасибо за конструктивную критику. Конечно, бенчмарки примитивные, просто не хотелось тратить на них много усилий.
                  В итоге я замерил ускорение на реальном проекте и успокоился на этом )

                  RyuJIT самому интересно посмотреть, но они (msft) сообщают, что он пока не готов, и сам тормознее текущей версии на 10-20%

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое