Sto sperimentando un lexer e ho scoperto che passare da un while-loop a un if-statement e un do-while-loop in una parte del programma portava a un codice ~ 20% più veloce, il che sembrava assurdo. Ho isolato la differenza nel codice generato dal compilatore in questi frammenti di assembly. Qualcuno sa perché il codice veloce è più veloce?Perché questo codice assembly è più veloce?
Nell'assembly, 'edi' è la posizione del testo corrente, 'ebx' è la fine del testo e 'isAlpha' è una tabella di ricerca che ha un 1 se il carattere è alfabetico e 0 altrimenti.
Il codice lento:
slow_loop:
00401897 cmp edi,ebx
00401899 je slow_done (4018AAh)
0040189B movzx eax,byte ptr [edi]
0040189E cmp byte ptr isAlpha (4533E0h)[eax],0
004018A5 je slow_done (4018AAh)
004018A7 inc edi
004018A8 jmp slow_loop (401897h)
slow_done:
Il codice veloce:
fast_loop:
0040193D inc edi
0040193E cmp edi,ebx
00401940 je fast_done (40194Eh)
00401942 movzx eax,byte ptr [edi]
00401945 cmp byte ptr isAlpha (4533E0h)[eax],0
0040194C jne fast_loop (40193Dh)
fast_done:
Se corro solo questi frammenti di assemblaggio nei confronti di un megabyte di testo costituito solo la lettera 'a', il codice veloce è il 30% più veloce. La mia ipotesi è che il codice lento sia lento a causa di una errata previsione del ramo, ma ho pensato in un ciclo che sarebbe costato una volta.
Ecco il programma che ho usato per testare entrambi i frammenti:
#include <Windows.h>
#include <string>
#include <iostream>
int main(int argc, char* argv[])
{
static char isAlpha[256];
for (int i = 0; i < sizeof(isAlpha); ++i)
isAlpha[i] = isalpha(i) ? 1 : 0;
std::string test(1024*1024, 'a');
const char* start = test.c_str();
const char* limit = test.c_str() + test.size();
DWORD slowStart = GetTickCount();
for (int i = 0; i < 10000; ++i)
{
__asm
{
mov edi, start
mov ebx, limit
inc edi
slow_loop:
cmp edi,ebx
je slow_done
movzx eax,byte ptr [edi]
cmp byte ptr isAlpha [eax],0
je slow_done
inc edi
jmp slow_loop
slow_done:
}
}
DWORD slowEnd = GetTickCount();
std::cout << "slow in " << (slowEnd - slowStart) << " ticks" << std::endl;
DWORD fastStart = GetTickCount();
for (int i = 0; i < 10000; ++i)
{
__asm
{
mov edi, start
mov ebx, limit
fast_loop:
inc edi
cmp edi,ebx
je fast_done
movzx eax,byte ptr [edi]
cmp byte ptr isAlpha [eax],0
jne fast_loop
fast_done:
}
}
DWORD fastEnd = GetTickCount();
std::cout << "fast in " << (fastEnd - fastStart) << " ticks" << std::endl;
return 0;
}
L'uscita del programma di test è
slow in 8455 ticks
fast in 5694 ticks
Questo * è * pazzesco - è un ottimizzazione molto comune per i compilatori di fare da soli. Per quanto riguarda il motivo per cui è più veloce, c'è un salto in meno per iterazione nel codice veloce, e salti hanno solo un throughput limitato. – harold
un profiler del registro basato sulle prestazioni probabilmente darebbe la risposta migliore, ma a parte l'ovvio salto, sto indovinando che il secondo bit di codice è più veloce perché si adatta meglio alla cache del codice (ci sono anche pochi byte per fetch-and- decodificare, ma quello overhead non ha senso qui). l'allineamento del target di salto può anche essere un altro fattore, ma questo è difficile da dire qui senza indirizzi – Necrolis
Brian, qual è la tua CPU? Date un'occhiata a http://www.agner.org/optimize/ E harold, i jmps statici sono previsti come sempre presi su CPU x86 moderne (non Atom), quindi non dovrebbero costare nulla. – osgx