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

    В предыдущей статье, посвященной анализу производительности целочисленного умножения были получены удивительные результаты, требующие интерпретации, а именно — почему при генерации кода в 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% быстрее.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 11

      +5
      Можно плюсовать уже только за суровую модификацию кода прямо в памяти :)
      +1
      Это тест ради теста или у него есть какое-то прикладное применение?
      Оптимизирование скалярной функции в отрыве от «места применения» само по себе странное занятие, если вы только не пишете какую-то матбиблиотеку.
        0
        Это точно, матбиблиотека уже написана, но вот какой компилятор взять, чтобы работало быстро — вот в чем вопрос. Раньше (лет 10 назад) это никого не волновало, можно и нужно было писать на голом асме и это работало всегда быстро. Сейчас же на асме писать бесполезно, компилятор все-равно сделает лучше. Я хотел было использовать компилятор от Intel, но оказывается и MS тоже весьма неплох. Осталось еще пощупать gcc (он же mingw) и clang.
        0
        Если очень нужно то можно и на ассемблере критичные функции реализовать, как например в OpenSSL сделано.
          0
          А когда новые процы появятся — какие-нибудь Indy Bridge — опять всё переписывать?
            0
            Если появилась новая инструкция которая значительно ускоряет ваш алгоритм — пишите еще один вариант кода. В противном случае не надо заморачиваеться.

            Речь же не идет о том, чтобы писать «обычный» код лучше компилятора; речь идет о доступе к вычислительным возможностям, к которым сложно доступиться конвенциональными средствами.
          +2
          Ассемблер как меч джедая — лучше держать в запасе… Код становится непортируемым…
            +1
            предлагаю еще раз подумать что делает связка
            ...
            cmp	 rdx, QWORD PTR [rdi+24]
            ...
            adc	 rdx, 0
            


            если есть код
            + (c[0] < a[0])
            


              0
              В том-то и дело, что вместо
                  c[0] = a[0] + b[0];
                  c[1] = a[1] + b[1] + (c[0] < a[0]);

              Хотелось бы иметь
                  Carry = _add_with_carry(&c[0], a[0],  b[0]);
                  c[1] = a[1] + b[1] + Carry;

              И тогда cmp вообще нигде не фигурирует.
              +1
              цель понятна,

              а дальше мешаються кони, люди, разрядности…

              причем без указания реальной причины,
              смотрим стандарты:
              Section 6.2.5, para. 9, and the C standard [ISO/IEC 9899:2011], states:
                  A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
              

              www.securecoding.cert.org/confluence/display/seccode/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap

              и по signed:
              www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false

              Пока не прийдут изменения стандарта — явная поддержка Carry в C/C++ будет (если будет) уникальна для каждого компилятора, поэтому они, разраб. компиляторов и не особо стремятся

              В итоге: как реальная работа и в срезе одного компилятора, одного test case — отлично.

              до установления первопричины не был сделан последний шаг, один шаг.

              Only users with full accounts can post comments. Log in, please.