Это мой первый вопрос здесь ...
Я пишу целочисленный класс произвольной точности для использования в 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 ++, которая вычисляет 10 000 000 пар псевдослучайных 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 ++, но я не могу найти в Интернете ничего, что могло бы объяснить это.Microsoft взаимодействует с ASM именно так, как рекомендует Microsoft.
Но теперь остерегайтесь еще более странной вещи!Ну, есть встроенные компиляторы, не так ли?Предполагается, что встроенная функция _umul128 должна делать именно то, что делает моя функция AsmMul1, то есть вызывать инструкцию MUL 64-битного процессора.Поэтому я заменил вызов AsmMul1 на соответствующий вызов _umul128.Теперь посмотрим, какие значения производительности я получаю взамен (опять же, я запускаю все четыре теста последовательно в одной функции):
_umul128: 109 msec
AsmMul2: 94 msec (hand-optimized ASM)
AsmMul3: 125 msec (compiler-generated ASM)
C++ function: 828 msec
Теперь версии ASM невероятно быстрые, с примерно такими же относительными различиями, как и раньше.Тем не менее, функция C ++ теперь очень ленива!Каким-то образом использование встроенного переворачивает все значения производительности с ног на голову.Страшно ...
У меня нет никакого объяснения этому странному поведению, и я был бы благодарен, по крайней мере, за любые подсказки о том, что здесь происходит.Было бы еще лучше, если бы кто-то мог объяснить, как взять под контроль эти проблемы с производительностью.В настоящее время я весьма обеспокоен, потому что, очевидно, небольшое изменение в коде может иметь огромное влияние на производительность.Я хотел бы понять механизмы, лежащие в основе этого, и как получить надежные результаты.
И еще одна вещь: почему 64-разрядный MUL медленнее, чем четыре 64-разрядных IMUL?!
Заранее спасибо!