Вызов MASM PROC из C++/CLI в режиме x64 приводит к неожиданным проблемам с производительностью
Это мой первый вопрос здесь...
Я пишу целочисленный класс произвольной точности для использования в C# (64-бит). В настоящее время я работаю над процедурой умножения, использующей рекурсивный алгоритм "разделяй и властвуй", чтобы разбить многобитовое умножение на серию примитивных умножений от 64 до 128 битов, результаты которых затем объединяются простым дополнение. Чтобы значительно повысить производительность, я пишу код на нативном x64 C++, встроенном в оболочку C++/CLI, чтобы сделать его доступным из кода C#.
Пока все отлично работает, в отношении алгоритмов. Однако моя проблема заключается в оптимизации скорости. Поскольку умножение с 64 на 128 бит является настоящим узким местом, я попытался оптимизировать свой код прямо здесь. Моим первым простым подходом была функция C++, которая реализует это умножение, выполняя четыре 32-разрядных умножения и объединяя результаты с парой сдвигов и добавлений. Это исходный код:
// 64-bit to 128-bit multiplication, using the following decomposition:
// (a*2^32 + i) (b*2^32 + i) = ab*2^64 + (aj + bi)*2^32 + ij
public: static void Mul (UINT64 u8Factor1,
UINT64 u8Factor2,
UINT64& u8ProductL,
UINT64& u8ProductH)
{
UINT64 u8Result1, u8Result2;
UINT64 u8Factor1L = u8Factor1 & 0xFFFFFFFFULL;
UINT64 u8Factor2L = u8Factor2 & 0xFFFFFFFFULL;
UINT64 u8Factor1H = u8Factor1 >> 32;
UINT64 u8Factor2H = u8Factor2 >> 32;
u8ProductL = u8Factor1L * u8Factor2L;
u8ProductH = u8Factor1H * u8Factor2H;
u8Result1 = u8Factor1L * u8Factor2H;
u8Result2 = u8Factor1H * u8Factor2L;
if (u8Result1 > MAX_UINT64 - u8Result2)
{
u8Result1 += u8Result2;
u8Result2 = (u8Result1 >> 32) | 0x100000000ULL; // add carry
}
else
{
u8Result1 += u8Result2;
u8Result2 = (u8Result1 >> 32);
}
if (u8ProductL > MAX_UINT64 - (u8Result1 <<= 32))
{
u8Result2++;
}
u8ProductL += u8Result1;
u8ProductH += u8Result2;
return;
}
Эта функция ожидает два 64-битных значения и возвращает 128-битный результат в виде двух 64-битных величин, переданных в качестве ссылки. Это отлично работает. На следующем шаге я попытался заменить вызов этой функции кодом ASM, который вызывает инструкцию MUL процессора. Поскольку встроенного ASM в режиме x64 больше нет, код должен быть помещен в отдельный файл.asm. Это реализация:
_TEXT segment
; =============================================================================
; multiplication
; -----------------------------------------------------------------------------
; 64-bit to 128-bit multiplication, using the x64 MUL instruction
AsmMul1 proc ; ?AsmMul1@@$$FYAX_K0AEA_K1@Z
; ecx : Factor1
; edx : Factor2
; [r8] : ProductL
; [r9] : ProductH
mov rax, rcx ; rax = Factor1
mul rdx ; rdx:rax = Factor1 * Factor2
mov qword ptr [r8], rax ; [r8] = ProductL
mov qword ptr [r9], rdx ; [r9] = ProductH
ret
AsmMul1 endp
; =============================================================================
_TEXT ends
end
Это очень просто и понятно. На функцию ссылаются из кода C++, используя extern "C" прямое определение:
extern "C"
{
void AsmMul1 (UINT64, UINT64, UINT64&, UINT64&);
}
К моему удивлению, это оказалось значительно медленнее, чем функция C++. Чтобы правильно оценить производительность, я написал функцию C++, которая вычисляет 10000000 пар псевдослучайных 64-разрядных значений без знака и выполняет умножения в узком цикле, используя эти реализации одну за другой, с точно такими же значениями. Код скомпилирован в режиме Release с включенными оптимизациями. Время, проведенное в цикле, составляет 515 мсек для версии ASM, по сравнению с 125 мсек (!) Для версии C++.
Это довольно странно. Поэтому я открыл окно разборки в отладчике и скопировал код ASM, сгенерированный компилятором. Вот что я нашел там, слегка отредактированный для удобства чтения и для использования с MASM:
AsmMul3 proc ; ?AsmMul3@@$$FYAX_K0AEA_K1@Z
; ecx : Factor1
; edx : Factor2
; [r8] : ProductL
; [r9] : ProductH
mov eax, 0FFFFFFFFh
and rax, rcx
; UINT64 u8Factor2L = u8Factor2 & 0xFFFFFFFFULL;
mov r10d, 0FFFFFFFFh
and r10, rdx
; UINT64 u8Factor1H = u8Factor1 >> 32;
shr rcx, 20h
; UINT64 u8Factor2H = u8Factor2 >> 32;
shr rdx, 20h
; u8ProductL = u8Factor1L * u8Factor2L;
mov r11, r10
imul r11, rax
mov qword ptr [r8], r11
; u8ProductH = u8Factor1H * u8Factor2H;
mov r11, rdx
imul r11, rcx
mov qword ptr [r9], r11
; u8Result1 = u8Factor1L * u8Factor2H;
imul rax, rdx
; u8Result2 = u8Factor1H * u8Factor2L;
mov rdx, rcx
imul rdx, r10
; if (u8Result1 > MAX_UINT64 - u8Result2)
mov rcx, rdx
neg rcx
dec rcx
cmp rcx, rax
jae label1
; u8Result1 += u8Result2;
add rax, rdx
; u8Result2 = (u8Result1 >> 32) | 0x100000000ULL; // add carry
mov rdx, rax
shr rdx, 20h
mov rcx, 100000000h
or rcx, rdx
jmp label2
; u8Result1 += u8Result2;
label1:
add rax, rdx
; u8Result2 = (u8Result1 >> 32);
mov rcx, rax
shr rcx, 20h
; if (u8ProductL > MAX_UINT64 - (u8Result1 <<= 32))
label2:
shl rax, 20h
mov rdx, qword ptr [r8]
mov r10, rax
neg r10
dec r10
cmp r10, rdx
jae label3
; u8Result2++;
inc rcx
; u8ProductL += u8Result1;
label3:
add rdx, rax
mov qword ptr [r8], rdx
; u8ProductH += u8Result2;
add qword ptr [r9], rcx
ret
AsmMul3 endp
Копирование этого кода в мой исходный файл MASM и вызов его из моей процедуры тестирования производительности привело к потере 547 мсек в цикле. Это немного медленнее, чем функция ASM, и значительно медленнее, чем функция C++. Это даже странно, поскольку последние должны выполнять точно такой же машинный код.
Поэтому я попробовал другой вариант, на этот раз с использованием оптимизированного вручную кода ASM, который выполняет те же четыре умножения 32–64 разрядов, но более простым способом. Код должен избегать скачков и непосредственных значений, использовать флаги ЦП для оценки переноса и использовать чередование инструкций, чтобы избежать сбоев регистра. Вот что я придумал:
; 64-bit to 128-bit multiplication, using the following decomposition:
; (a*2^32 + i) (b*2^32 + j) = ab*2^64 + (aj + bi)*2^32 + ij
AsmMul2 proc ; ?AsmMul2@@$$FYAX_K0AEA_K1@Z
; ecx : Factor1
; edx : Factor2
; [r8] : ProductL
; [r9] : ProductH
mov rax, rcx ; rax = Factor1
mov r11, rdx ; r11 = Factor2
shr rax, 32 ; rax = Factor1H
shr r11, 32 ; r11 = Factor2H
and ecx, ecx ; rcx = Factor1L
mov r10d, eax ; r10 = Factor1H
and edx, edx ; rdx = Factor2L
imul rax, r11 ; rax = ab = Factor1H * Factor2H
imul r10, rdx ; r10 = aj = Factor1H * Factor2L
imul r11, rcx ; r11 = bi = Factor1L * Factor2H
imul rdx, rcx ; rdx = ij = Factor1L * Factor2L
xor ecx, ecx ; rcx = 0
add r10, r11 ; r10 = aj + bi
adc ecx, ecx ; rcx = carry (aj + bi)
mov r11, r10 ; r11 = aj + bi
shl rcx, 32 ; rcx = carry (aj + bi) << 32
shl r10, 32 ; r10 = lower (aj + bi) << 32
shr r11, 32 ; r11 = upper (aj + bi) >> 32
add rdx, r10 ; rdx = ij + (lower (aj + bi) << 32)
adc rax, r11 ; rax = ab + (upper (aj + bi) >> 32)
mov qword ptr [r8], rdx ; save ProductL
add rax, rcx ; add carry (aj + bi) << 32
mov qword ptr [r9], rax ; save ProductH
ret
AsmMul2 endp
Тест показал 500 мсек, так что, похоже, это самая быстрая версия этих трех реализаций ASM. Тем не менее, различия в производительности довольно незначительны - но все они примерно в четыре раза медленнее, чем наивный подход C++!
Так что здесь происходит? Мне кажется, что есть некоторые общие потери производительности для вызова кода ASM из C++, но я не могу найти в Интернете ничего, что могло бы объяснить это. Я взаимодействую с ASM именно так, как Microsoft рекомендует.
Но теперь, остерегайтесь другой, еще более странной вещи! Ну, есть встроенные компиляторы, не так ли? _umul128 Предполагается, что intrinsic должен делать именно то, что делает моя функция AsmMul1, то есть вызывать 64-битную инструкцию CPU MUL. Поэтому я заменил вызов AsmMul1 на соответствующий вызов _umul128, Теперь посмотрим, какие значения производительности я получаю взамен (опять же, я запускаю все четыре теста последовательно в одной функции):
_umul128: 109 msec
AsmMul2: 94 msec (hand-optimized ASM)
AsmMul3: 125 msec (compiler-generated ASM)
C++ function: 828 msec
Теперь версии ASM невероятно быстрые, с примерно такими же относительными различиями, как и раньше. Тем не менее, функция C++ теперь очень ленива! Каким-то образом использование встроенного переворачивает все значения производительности с ног на голову. Страшно...
У меня нет никакого объяснения этому странному поведению, и я был бы благодарен, по крайней мере, за любые подсказки о том, что здесь происходит. Было бы еще лучше, если бы кто-то мог объяснить, как взять под контроль эти проблемы с производительностью. В настоящее время я весьма обеспокоен, потому что, очевидно, небольшое изменение в коде может иметь огромное влияние на производительность. Я хотел бы понять механизмы, лежащие в основе этого, и как получить надежные результаты.
И еще: почему MUL от 64 до 128 бит работает медленнее, чем четыре IMUL от 64 до 64 бит?!
Заранее спасибо!
1 ответ
После долгих проб и ошибок и дополнительных обширных исследований в Интернете, кажется, я нашел причину этого странного поведения производительности. Волшебное слово - гром через точки входа в функцию. Но позвольте мне начать с самого начала.
Одно из наблюдений, которое я сделал, заключается в том, что на самом деле не имеет значения, какой встроенный компилятор используется для того, чтобы перевернуть результаты моих тестов вверх дном. На самом деле, достаточно положить __nop() (Код операции CPU NOP) в любом месте внутри функции, чтобы вызвать этот эффект. Это работает, даже если он находится прямо перед return, Другие тесты показали, что эффект ограничен функцией, которая содержит встроенную функцию. __nop() ничего не делает в отношении потока кода, но, очевидно, изменяет свойства содержащей функции.
Я нашел вопрос о стековом потоке, который, кажется, решает похожую проблему: как лучше избежать двойного преобразования в собственных типах C++/CLI. В комментариях найдена следующая дополнительная информация:
Один из моих собственных классов в нашей базовой библиотеке, который использует MFC, вызывается около миллиона раз. Мы наблюдаем огромные спорадические проблемы с производительностью, и, запуская профилировщик, я вижу громадину прямо внизу этой цепочки. Этот поток занимает больше времени, чем вызов метода.
Это именно то, что я наблюдаю - "что-то" на пути вызова функции занимает примерно в четыре раза больше, чем мой код. О некоторых функциях объясняется в некоторой степени в документации к модификатору __clrcall и в статье о Double Thunking. В первом случае есть подсказка для побочного эффекта использования встроенных функций:
Вы можете напрямую вызывать функции __clrcall из существующего кода C++, который был скомпилирован с использованием / clr, если эта функция имеет реализацию MSIL. Функции __clrcall нельзя вызывать напрямую из функций, которые имеют встроенный asm и, например, вызывают специфичные для ЦП intrinisics, даже если эти функции скомпилированы с / clr.
Итак, насколько я понимаю, функция, которая содержит встроенные функции, теряет свою __clrcall модификатор, который добавляется автоматически при указании параметра компилятора / clr, что обычно имеет место, если функции C++ должны быть скомпилированы в собственный код.
Я не понимаю всех деталей этого "двойного" и "двойного", но, очевидно, это необходимо для того, чтобы неуправляемые функции можно было вызывать из управляемых функций. Тем не менее, можно отключить его для каждой функции, вставив его в #pragma managed(push, off) / #pragma managed(pop) пара. К сожалению, эта #pragma не работает внутри блоков пространства имен, поэтому может потребоваться некоторое редактирование, чтобы разместить ее везде, где она должна происходить.
Я попробовал этот трюк, поместив весь свой собственный код с множественной точностью в эту #pragma, и получил следующие результаты теста:
AsmMul1: 78 msec (64-to-128-bit CPU MUL)
AsmMul2: 94 msec (hand-optimized ASM, 4 x IMUL)
AsmMul3: 125 msec (compiler-generated ASM, 4 x IMUL)
C++ function: 109 msec
Теперь это выглядит разумно, наконец! Теперь все версии имеют примерно одинаковое время выполнения, чего я и ожидал от оптимизированной программы C++. Увы, счастливого конца еще нет... Размещение победителя AsmMul1 в мой множитель с мульти-точностью дал вдвое больше времени исполнения версии с функцией C++ без #pragma. По моему мнению, объяснение состоит в том, что этот код вызывает неуправляемые функции в других классах, которые находятся за пределами #pragma и, следовательно, имеют __clrcall модификатор. Это, кажется, создает значительные накладные расходы снова.
Честно говоря, я устал от дальнейшего изучения этой проблемы. Хотя ASM PROC с единственной инструкцией MUL, кажется, побеждает все другие попытки, выигрыш не такой большой, как ожидалось, и устранение путаницы приводит к стольким изменениям в моем коде, что я не думаю, что это стоит того хлопот. Итак, я продолжу с функцией C++, которую я написал в самом начале, изначально предназначенной для того, чтобы быть просто заменителем чего-то лучшего...
Мне кажется, что ASM-интерфейс в C++/CLI не очень хорошо поддерживается, или, может быть, я все еще здесь упускаю что-то базовое. Может быть, есть способ избавиться от этой функции только для функций ASM, но пока я не нашел решения. Даже отдаленно.
Не стесняйтесь добавлять свои собственные мысли и наблюдения здесь - даже если они просто умозрительные. Я думаю, что это все еще очень интересная тема, которая требует гораздо большего изучения.