Funkcje wbudowane są specjalnymi funkcjami kompilatora. Przeważnie funkcja wbudowana jest zastępowana zbiorem instrukcji procesora (nie jest to dokładnie funkcja
inline). W debug zaś wywoływana jest z reguły niezoptymalizowana wersja biblioteczna. W przypadku funkcji dostępnych pod podanym wcześniej adresem większość z nich w wersji zoptymalizowanej to pojedyncze instrukcje procesora. Część z nich można w debug zastąpić wersjami bibliotecznymi (np: _byteswap_ulong), a część nie (obsługa wirtualizacji). Instrukcje SIMD nie mają one odpowiedników bibliotecznych. Niektóre funkcje wbudowane przeznaczone są na konkretną architekturę procesora. Niektóre działają na dowolnej, co nie oznacza, że w zależności od architektury nie zostanie wygenerowany inny kod. Np. używając funkcji wbudowanych SIMD na architekturę x86 wcale nie jest powiedziane, że wszystkie będą działać zarówno na procesorach AMD jak i Intel. Sprawdzenie tego leży po naszej stronie. Kompilator zastąpi funkcję odpowiednimi instrukcjami procesora. Kompilator w przypadku funkcji wbudowanych może w zależności od sytuacji wygenerować różny kod, funkcja nie jest nigdzie zapisana, nie jest to zwykła funkcja inline. Użycie funkcji wbudowanych czyni nasz kod trudno przenoszalnym. Wracając do głównego tematu: rotowanie i zmiana bajtów w słowie. Bardzo często spotykana implementacja tych zadań wygląda tak:
#define ROT32a(x,n) (((x >> n) | (x << (32 - n))))
#define ROT32b(x,n) _rotr(x, n)
#define BYTESWAPa(x) ((x << 24) + (( x & 0x0000FF00) << 8) + \
((x & 0x00FF0000) >> 8) + (x >> 24))
Kompilator nie jest w stanie zorientować się o co nam chodzi i wygenerować jedną instrukcję procesora, które obie definicje posiadają.
Możemy to oczywiście zrobić sami używając
__asm, co już czyni nasz kod przenoszalnym pomiędzy kompilatorami, ale ciągle uwiązanym do danej architektury. Wersja tych makr z wykorzystaniem funkcji wbudowanych:
#define ROT32b(x,n) _rotr(x, n) #define BYTESWAPb(x) _byteswap_ulong(x)
No i teraz najważniejsze. Czas wykonania:
void test()
{
const int size = 100000000;
int* memory = new int[size];
std::srand(GetTickCount());
for (int i=0; i<size; i++)
memory[i] = std::rand();
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
memory[i] = ROT32a(i, i);
std::wprintf(L"ROT32a: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
{
int sum = memory[i];
for (int j=0; j<64; j++)
{
int x = sum + i;
sum+= ROT32a(x, i);
}
memory[i] = sum;
}
std::wprintf(L"ROT32a: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
memory[i] = ROT32b(i, i);
std::wprintf(L"ROT32b: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
{
int sum = memory[i];
for (int j=0; j<64; j++)
{
int x = sum + i;
sum+= ROT32b(x, i);
}
memory[i] = sum;
}
std::wprintf(L"ROT32b: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
memory[i] = BYTESWAPa(i);
std::wprintf(L"BYTESWAPa: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
{
int sum = memory[i];
for (int j=0; j<64; j++)
{
int x = sum + i;
sum+= BYTESWAPa(x);
}
memory[i] = sum;
}
std::wprintf(L"BYTESWAPa: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
memory[i] = BYTESWAPb(i);
std::wprintf(L"BYTESWAPb: %d [ms]\n", sw.GetElapsedTime());
}
{
Helpers::StopWatch sw;
for (int i=0; i<size; i++)
{
int sum = memory[i];
for (int j=0; j<64; j++)
{
int x = sum + i;
sum+= BYTESWAPb(x);
}
memory[i] = sum;
}
std::wprintf(L"BYTESWAPb: %d [ms]\n", sw.GetElapsedTime());
}
std::getchar();
}
Rozmiar tablicy jest dużo większy niż pamięć cache. Dodatkowo druga wersja mieli trochę daną z pamięci, sprawiając, że oczekiwanie na dane z pamięci nie stanowi o prędkości programu. Wyniki:
ROT32a: 209 [ms]
ROT32a: 17807 [ms]
ROT32b: 191 [ms]
ROT32b: 8874 [ms]
BYTESWAPa: 270 [ms]
BYTESWAPa: 26587 [ms]
BYTESWAPb: 187 [ms]
BYTESWAPb: 16022 [ms]Widać wyraźnie, że w przypadku gdy "szybko" lecimy po obszarze danych nie mieszczącym się w pamięci cache różnice są minimalne. Druga wersja pokazuje prawdziwą różnicę w czasie wykonania, kiedy czas wykonania przekracza czas napływu danych.
Po zmniejszeniu rozmiaru tablicy do 0.5 MB:
ROT32a: 0 [ms]
ROT32a: 89 [ms]
ROT32b: 0 [ms]
ROT32b: 45 [ms]
BYTESWAPa: 1 [ms]
BYTESWAPa: 149 [ms]
BYTESWAPb: 0 [ms]
BYTESWAPb: 80 [ms]Widzimy, że różnice dla mielących daną wersjami zostały utrzymane. Wniosek to nie pamięć tak spowalniała tylko dość długi kod pętli, który sprawił, że procesor nie mógł efektywnie przetworzyć kodu w potoku. Powiedzmy sobie szczerze, ja optymalizację niskopoziomową uważam za rodzaj sztuki i magii zarazem, nigdy nie wiadomo co nam wyjdzie.
Czasy zostały zdjęte na procesorze x64 i kodzie x32. Kod x64 daje podobne rezultaty.
Na koniec tak wygląda wymiana bajtów w wersji makrowej:
memory[i] = BYTESWAPa(i);
00F059BD mov edx,eax
00F059BF and edx,0FF00h
00F059C5 add edx,ecx
00F059C7 mov edi,eax
00F059C9 sar edi,8
00F059CC and edi,0FF00h
00F059D2 shl edx,8
00F059D5 add edx,edi
00F059D7 mov edi,eax
00F059D9 sar edi,18h
00F059DC add edx,edi
00F059DE mov dword ptr [esi+eax*4],edx , zaś tak w wersji wbudowanej:
00F05A80 mov ecx,eax
00F05A82 bswap ecx
00F05A84 mov dword ptr [esi+eax*4],ecx A czas wykonania przy sprzyjających okolicznościach może być taki sam.
