kostik450 9 июл 2012 в 17:09

Тайна лишнего CMP или зачем Володька сбрил усы?

7 мин

В предыдущей статье, посвященной анализу производительности целочисленного умножения были получены удивительные результаты, требующие интерпретации, а именно — почему при генерации кода в 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 wrong\n");
    		return 1;
    	}
    }

    printf("Ok!\n", Carry);
    return 0;
}

Этот код, после компиляции Visual Studio 10.0 SP1 превращается в ассемблерный листинг:

Смотрим код на Asm

?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 memory\n", 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 memory\n", 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, COMDAT\n"
"				; Line 7\n"
" 00000000			$LN3:\n"
" 00000000  48/ 89 5C 24			mov	QWORD PTR [rsp+8], rbx\n"
"	   08\n"
" 00000005  48/ 89 7C 24			mov	QWORD PTR [rsp+16], rdi\n"
"	   10\n"
"				; Line 8\n"
" 0000000A  4C/ 8B 12			mov	r10, QWORD PTR [rdx]\n"
"				; Line 17\n"
" 0000000D  48/ 8B 5C 24			mov	rbx, QWORD PTR [rsp+8]\n"
"	   08\n"
" 00000012  48/ 8B FA			mov	rdi, rdx\n"
" 00000015  4D/ 03 10			add	r10, QWORD PTR [r8]\n"
" 00000018  4D/ 8B D8			mov	r11, r8\n"
" 0000001B  4C/ 89 11			mov	QWORD PTR [rcx], r10\n"
" 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, 0\n"
" 00000029  4C/ 03 42 08			add	r8, QWORD PTR [rdx+8]\n"
" 0000002D  4C/ 89 41 08			mov	QWORD PTR [rcx+8], r8\n"
" 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, 0\n"
" 0000003D  48/ 03 57 10			add	rdx, QWORD PTR [rdi+16]\n"
" 00000041  48/ 89 51 10			mov	QWORD PTR [rcx+16], rdx\n"
" 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, 0\n"
" 00000051  48/ 03 57 18			add	rdx, QWORD PTR [rdi+24]\n"
" 00000055  48/ 89 51 18			mov	QWORD PTR [rcx+24], rdx\n"
" 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, 0\n"
" 00000065  48/ 03 57 20			add	rdx, QWORD PTR [rdi+32]\n"
" 00000069  48/ 89 51 20			mov	QWORD PTR [rcx+32], rdx\n"
" 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, 0\n"
" 00000079  48/ 03 57 28			add	rdx, QWORD PTR [rdi+40]\n"
" 0000007D  48/ 89 51 28			mov	QWORD PTR [rcx+40], rdx\n"
" 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, 0\n"
" 0000008D  48/ 03 57 30			add	rdx, QWORD PTR [rdi+48]\n"
" 00000091  48/ 89 51 30			mov	QWORD PTR [rcx+48], rdx\n"
" 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, 0\n"
" 000000A1  33 C0			xor	eax, eax\n"
" 000000A3  48/ 03 57 38			add	rdx, QWORD PTR [rdi+56]\n"
" 000000A7  48/ 89 51 38			mov	QWORD PTR [rcx+56], rdx\n"
" 000000AB  48/ 3B 57 38			cmp	rdx, QWORD PTR [rdi+56]\n"
" 000000AF  48/ 8B 7C 24			mov	rdi, QWORD PTR [rsp+16]\n"
"	   10\n"
" 000000B4  0F 92 C0			setb	al\n"
" 000000B7  C3				ret	0\n"
" 000000B8			?Add@@YAHQEA_K00@Z ENDP					; Add\n"
" 000000B8			_TEXT	ENDS\n";

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 wrong\n");
    				return 1;
    			}
		    }
		}
	    QueryPerformanceCounter(&lEnd);
	    dfTime1 = (double)(lEnd.QuadPart - lStart.QuadPart) / (double)lFrequency.QuadPart;

		if (usi==0) {
			//печатаем время с усами
			printf("Time = %g sec\n", dfTime1);
			//сбриваем усы прямо в коде
			sbrivaem_usi();
		}
		else
		{
			//печатаем время без усов
			printf("Time(without cmp) = %g sec\n", dfTime1);
		}
    }
    return 0;
}

Компилировать нужно на Visual Studio 2010 SP1 с включенным параметром оптимизации -O2 и не забыть настройки x64:

call "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" amd64
cl.exe -O2 /Faadd_with_carry.asm add_with_carry.cpp

Итого, время работы:
Time = 7.07075 sec
Time(without cmp) = 5.36317 sec

Получилось неплохо, не правда ли? Практически на 30% быстрее.

Теги:

Хабы:

Тайна лишнего CMP или зачем Володька сбрил усы?

Публикации

Истории

Работа

Ближайшие события