В предыдущей статье, посвященной анализу производительности целочисленного умножения были получены удивительные результаты, требующие интерпретации, а именно — почему при генерации кода в VS2012 значительно (в 5,5 раз) падает скорость, а в VS2010 такого не наблюдается, в чем секрет быстрого кода?
Оказывается, дело было в использовании замечательной команды ADC, которая просто необходима при сложении (или умножении) чисел большой разрядности. Она позволяет задействовать флажок переноса и отпадает необходимость хитрых манипуляций с битами, чтобы вычислить перенос другими способами.
Но команду ADC почему-то не любят компиляторы, причем настолько не любят, что нет простого способа заставить компилятор начать использовать команду ADC вкупе с флажком Carry. Можно, конечно, написать это на ассемблере. Но написание быстрого кода вручную — это непосильная задача, предусмотреть все тонкости и сделать что-то быстрее оптимизирующего компилятора практически невозможно. Еще есть проблема, что в Visual Studio C++ x64 зачем-то отказались от встроенной команды _asm, и чтобы воспользоваться ассемблерными вставками, нужно создавать отдельный ASM-файл, что делать очень не хочется.
На самом деле — нам бы очень пригодился явный intrinsic команды add-with-carry, но Microsoft hard-working создатели компилятора, когда у них спросили об этом напрямую, заявили что add-with-carry intrinsic имеет ограниченное применение и поэтому в текущем компиляторе его нет. Очень и очень зря.
Для примера, рассмотрим код на Си сложения двух чисел большой разрядности. При умножении похожий код с участием ADC тоже встречается, но в неявном виде.
#include <stdio.h>
typedef unsigned long long BN_WORD;
int Add(BN_WORD c[8], BN_WORD a[8], BN_WORD b[8])
{
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0]);
c[2] = a[2] + b[2] + (c[1] < a[1]);
c[3] = a[3] + b[3] + (c[2] < a[2]);
c[4] = a[4] + b[4] + (c[3] < a[3]);
c[5] = a[5] + b[5] + (c[4] < a[4]);
c[6] = a[6] + b[6] + (c[5] < a[5]);
c[7] = a[7] + b[7] + (c[6] < a[6]);
return (c[7] < a[7]);
}
int main(void)
{
int i;
BN_WORD a[8], b[8], c[8], Carry;
//это ухищрение, чтобы избежать inline вставки кода функции Add в тело main
int (*add)(BN_WORD c[8], BN_WORD a[8], BN_WORD b[8]) = Add;
for( i=0; i<8; i++)
{
a[i] = b[i] = 0x8000000000000000;
}
Carry = add(c, a, b);
//проверим результат
for( i=0; i<8; ++i)
{
if (Carry!=1 || c[i]!=(i!=0))
{
printf("Something wrongn");
return 1;
}
}
printf("Ok!n", Carry);
return 0;
}
Этот код, после компиляции Visual Studio 10.0 SP1 превращается в ассемблерный листинг:
?Add@@YAXQEA_K00@Z PROC ; Add, COMDAT
; Line 6
$LN3:
mov QWORD PTR [rsp+8], rbx
mov QWORD PTR [rsp+16], rdi
; Line 7
mov r10, QWORD PTR [rdx]
; Line 15
mov rdi, QWORD PTR [rsp+16]
mov rbx, rdx
add r10, QWORD PTR [r8]
mov r11, r8
mov QWORD PTR [rcx], r10
cmp r10, QWORD PTR [rdx]
mov r8, QWORD PTR [r8+8]
adc r8, 0
add r8, QWORD PTR [rdx+8]
mov QWORD PTR [rcx+8], r8
cmp r8, QWORD PTR [rdx+8]
mov rdx, QWORD PTR [r11+16]
adc rdx, 0
add rdx, QWORD PTR [rbx+16]
mov QWORD PTR [rcx+16], rdx
cmp rdx, QWORD PTR [rbx+16]
mov rdx, QWORD PTR [r11+24]
adc rdx, 0
add rdx, QWORD PTR [rbx+24]
mov QWORD PTR [rcx+24], rdx
cmp rdx, QWORD PTR [rbx+24]
mov rdx, QWORD PTR [r11+32]
adc rdx, 0
add rdx, QWORD PTR [rbx+32]
mov QWORD PTR [rcx+32], rdx
cmp rdx, QWORD PTR [rbx+32]
mov rdx, QWORD PTR [r11+40]
adc rdx, 0
add rdx, QWORD PTR [rbx+40]
mov QWORD PTR [rcx+40], rdx
cmp rdx, QWORD PTR [rbx+40]
mov rdx, QWORD PTR [r11+48]
adc rdx, 0
add rdx, QWORD PTR [rbx+48]
mov QWORD PTR [rcx+48], rdx
cmp rdx, QWORD PTR [rbx+48]
mov rax, QWORD PTR [rbx+56]
adc rax, QWORD PTR [r11+56]
mov rbx, QWORD PTR [rsp+8]
mov QWORD PTR [rcx+56], rax
ret 0
?Add@@YAXQEA_K00@Z ENDP ; Add
_TEXT ENDS
Явно видно наличие повторяющего набора команд ADD + CMP + ADC, например:
add r8, QWORD PTR [rdx+8]
mov QWORD PTR [rcx+8], r8
cmp r8, QWORD PTR [rdx+8]
mov rdx, QWORD PTR [r11+16]
adc rdx, 0
Но зачем нам лишний CMP? Лишний CMP нам не нужен. Он используется не более чем для повторной установки флажка Carry, который сам по себе уже был ранее установлен командой ADD и поэтому CMP можно смело удалять. Попробуем взять на себя смелость и сбрить «торчащие усы» в виде лишних CMP прямым модифицированием бинарного кода в памяти и еще раз замерить скорость.
Модифицирование бинарного кода программы происходит так:
- Сначала парсим листинг функции Add, находим все cmp и их длины.
- Потом прямо внутри реального кода Add удаляем все найденные cmp, перемещая на место Cmp остаток до конца функции, благо что код полностью линейный, то есть никаких jmp в коде нет.
#include <stdio.h>
#include <windows.h>
typedef unsigned long long BN_WORD;
int Add(BN_WORD c[8], BN_WORD a[8], BN_WORD b[8])
{
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0]);
c[2] = a[2] + b[2] + (c[1] < a[1]);
c[3] = a[3] + b[3] + (c[2] < a[2]);
c[4] = a[4] + b[4] + (c[3] < a[3]);
c[5] = a[5] + b[5] + (c[4] < a[4]);
c[6] = a[6] + b[6] + (c[5] < a[5]);
c[7] = a[7] + b[7] + (c[6] < a[6]);
return (c[7] < a[7]);
}
void ReadMem(__int64 pos, char *patch, int len)
{
DWORD my_id = GetCurrentProcessId();
HANDLE p_hand = OpenProcess(PROCESS_VM_READ | PROCESS_VM_OPERATION, NULL, my_id);
if (ReadProcessMemory(p_hand, (LPDWORD)pos, patch, len, NULL)==0) {
printf("Error %d read from memoryn", GetLastError());
}
CloseHandle(p_hand);
}
void WriteMem(__int64 pos, char *patch, int len)
{
DWORD my_id = GetCurrentProcessId();
HANDLE p_hand = OpenProcess(PROCESS_VM_WRITE | PROCESS_VM_OPERATION, NULL, my_id);
if (WriteProcessMemory(p_hand, (LPDWORD)pos, patch, len, NULL)==0) {
printf("Error %d write to memoryn", GetLastError());
}
CloseHandle(p_hand);
}
void udalit_usi(int pos, int size, int full_size)
{
char *mem = (char*)malloc(full_size-pos);
__int64 pos_add = (__int64)Add;
//читаем от позиции усов и до конца
ReadMem(pos_add + pos, mem, full_size-pos);
//пишем обратно, но уже без усов, размер которых size
WriteMem(pos_add + pos, mem+size, full_size-pos-size);
free(mem);
}
char *add_listing =
" 00000000 ?Add@@YAHQEA_K00@Z PROC ; Add, COMDATn"
" ; Line 7n"
" 00000000 $LN3:n"
" 00000000 48/ 89 5C 24 mov QWORD PTR [rsp+8], rbxn"
" 08n"
" 00000005 48/ 89 7C 24 mov QWORD PTR [rsp+16], rdin"
" 10n"
" ; Line 8n"
" 0000000A 4C/ 8B 12 mov r10, QWORD PTR [rdx]n"
" ; Line 17n"
" 0000000D 48/ 8B 5C 24 mov rbx, QWORD PTR [rsp+8]n"
" 08n"
" 00000012 48/ 8B FA mov rdi, rdxn"
" 00000015 4D/ 03 10 add r10, QWORD PTR [r8]n"
" 00000018 4D/ 8B D8 mov r11, r8n"
" 0000001B 4C/ 89 11 mov QWORD PTR [rcx], r10n"
" 0000001E 4C/ 3B 12 cmp r10, QWORD PTR [rdx]n"
" 00000021 4D/ 8B 40 08 mov r8, QWORD PTR [r8+8]n"
" 00000025 49/ 83 D0 00 adc r8, 0n"
" 00000029 4C/ 03 42 08 add r8, QWORD PTR [rdx+8]n"
" 0000002D 4C/ 89 41 08 mov QWORD PTR [rcx+8], r8n"
" 00000031 4C/ 3B 42 08 cmp r8, QWORD PTR [rdx+8]n"
" 00000035 49/ 8B 53 10 mov rdx, QWORD PTR [r11+16]n"
" 00000039 48/ 83 D2 00 adc rdx, 0n"
" 0000003D 48/ 03 57 10 add rdx, QWORD PTR [rdi+16]n"
" 00000041 48/ 89 51 10 mov QWORD PTR [rcx+16], rdxn"
" 00000045 48/ 3B 57 10 cmp rdx, QWORD PTR [rdi+16]n"
" 00000049 49/ 8B 53 18 mov rdx, QWORD PTR [r11+24]n"
" 0000004D 48/ 83 D2 00 adc rdx, 0n"
" 00000051 48/ 03 57 18 add rdx, QWORD PTR [rdi+24]n"
" 00000055 48/ 89 51 18 mov QWORD PTR [rcx+24], rdxn"
" 00000059 48/ 3B 57 18 cmp rdx, QWORD PTR [rdi+24]n"
" 0000005D 49/ 8B 53 20 mov rdx, QWORD PTR [r11+32]n"
" 00000061 48/ 83 D2 00 adc rdx, 0n"
" 00000065 48/ 03 57 20 add rdx, QWORD PTR [rdi+32]n"
" 00000069 48/ 89 51 20 mov QWORD PTR [rcx+32], rdxn"
" 0000006D 48/ 3B 57 20 cmp rdx, QWORD PTR [rdi+32]n"
" 00000071 49/ 8B 53 28 mov rdx, QWORD PTR [r11+40]n"
" 00000075 48/ 83 D2 00 adc rdx, 0n"
" 00000079 48/ 03 57 28 add rdx, QWORD PTR [rdi+40]n"
" 0000007D 48/ 89 51 28 mov QWORD PTR [rcx+40], rdxn"
" 00000081 48/ 3B 57 28 cmp rdx, QWORD PTR [rdi+40]n"
" 00000085 49/ 8B 53 30 mov rdx, QWORD PTR [r11+48]n"
" 00000089 48/ 83 D2 00 adc rdx, 0n"
" 0000008D 48/ 03 57 30 add rdx, QWORD PTR [rdi+48]n"
" 00000091 48/ 89 51 30 mov QWORD PTR [rcx+48], rdxn"
" 00000095 48/ 3B 57 30 cmp rdx, QWORD PTR [rdi+48]n"
" 00000099 49/ 8B 53 38 mov rdx, QWORD PTR [r11+56]n"
" 0000009D 48/ 83 D2 00 adc rdx, 0n"
" 000000A1 33 C0 xor eax, eaxn"
" 000000A3 48/ 03 57 38 add rdx, QWORD PTR [rdi+56]n"
" 000000A7 48/ 89 51 38 mov QWORD PTR [rcx+56], rdxn"
" 000000AB 48/ 3B 57 38 cmp rdx, QWORD PTR [rdi+56]n"
" 000000AF 48/ 8B 7C 24 mov rdi, QWORD PTR [rsp+16]n"
" 10n"
" 000000B4 0F 92 C0 setb aln"
" 000000B7 C3 ret 0n"
" 000000B8 ?Add@@YAHQEA_K00@Z ENDP ; Addn"
" 000000B8 _TEXT ENDSn";
int full_size_add_listing = 0x000000B8;
#define MAX_USI 100
int usi_pos[MAX_USI];
int usi_len[MAX_USI];
int kol_usi;
void sbrivaem_usi(void)
{
char *p;
int i, j;
for( kol_usi=0, p=add_listing;;) //небольшой парсинг листинга
{
//ищем cmp
p = strstr(p, "cmp");
if (p==NULL) break;
for(;;p--) //ищем перед ним 2 пробела
{
if (p[0]==' ' && p[1]==' ') break;
}
p-=2; //встали на позицию
sscanf(p, "%x", &(usi_pos[kol_usi]));
p+=4;
for(i=0;;i++)
{
if (p[0]<0x20) break;
p+=2;
if (p[0]=='/') p++;
if (p[0]==' ') p++;
}
usi_len[kol_usi]=i;
kol_usi++;
if (kol_usi>=MAX_USI)
{
printf("too much");
exit(0);
}
p = strstr(p, "cmp"); //вернулись к нашему cmp
p++; //следующий
}
//начинаем удалять с последнего уса
for( i=kol_usi-1; i>=0; --i)
{
udalit_usi(usi_pos[i], usi_len[i], full_size_add_listing);
full_size_add_listing -= usi_len[i];
}
}
int main(void)
{
LARGE_INTEGER lFrequency, lStart, lEnd;
double dfTime1;
int i, j, k, usi;
BN_WORD a[8], b[8], c[8], Carry;
//это ухищрение, чтобы избежать inline вставки кода функции Add в тело main
int (*add)(BN_WORD c[8], BN_WORD a[8], BN_WORD b[8]) = Add;
for( i=0; i<8; i++)
{
a[i] = b[i] = 0x8000000000000000;
}
for( usi=0; usi<=1; ++usi)
{
QueryPerformanceFrequency(&lFrequency);
QueryPerformanceCounter(&lStart);
for( i=0; i<1000; ++i)
{
for( j=0; j<1000000; ++j)
{
Carry = add(c, a, b);
}
for( k=0; k<8; ++k)
{
if (Carry!=1 || c[k]!=(k!=0))
{
printf("Something wrongn");
return 1;
}
}
}
QueryPerformanceCounter(&lEnd);
dfTime1 = (double)(lEnd.QuadPart - lStart.QuadPart) / (double)lFrequency.QuadPart;
if (usi==0) {
//печатаем время с усами
printf("Time = %g secn", dfTime1);
//сбриваем усы прямо в коде
sbrivaem_usi();
}
else
{
//печатаем время без усов
printf("Time(without cmp) = %g secn", dfTime1);
}
}
return 0;
}
Компилировать нужно на Visual Studio 2010 SP1 с включенным параметром оптимизации -O2 и не забыть настройки x64:
call "C:Program Files (x86)Microsoft Visual Studio 10.0VCvcvarsall.bat" amd64
cl.exe -O2 /Faadd_with_carry.asm add_with_carry.cpp
Итого, время работы:
Time = 7.07075 sec
Time(without cmp) = 5.36317 sec
Получилось неплохо, не правда ли? Практически на 30% быстрее.
Автор: kostik450
