Dlaczego ten kod zespołu jest szybszy?

Question

Eksperymentuję z lexerem i odkryłem, że przejście z pętli while na if-statement i pętlę do-while w jednej części programu prowadzi do ~ 20% szybszego kodu, co wydawało się szalone. Wyodrębniłem różnicę w kodzie generowanym przez kompilator do tych fragmentów zestawu. Czy ktoś wie, dlaczego szybki kod jest szybszy?

W zespole "edi" jest bieżącą pozycją tekstową, "ebx" jest końcem tekstu, a "isAlpha" jest tabelą odnośników, która ma 1, jeśli litera jest alfabetyczna, a 0 w przeciwnym razie.

Powolny Kod:

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: 

Szybko Kod:

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: 

Jeśli uruchomić tylko te fragmenty zespołu przed megabajta tekst składający się tylko z literą „a”, szybki kod jest o 30% szybszy. Domyślam się, że powolny kod jest powolny z powodu błędnej interpretacji gałęzi, ale pomyślałam, że to jednorazowy koszt.

Oto program, który kiedyś przetestować oba fragmenty:

#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; 
} 

Wyjście z programu testu jest

slow in 8455 ticks 
fast in 5694 ticks 

Answer 1

Niestety, nie udało mi się odtworzyć kodu dokładnie na GCC (Linux), ale mam pewne wyniki i myślę, że główny pomysł został zapisany w moim kodzie.

Istnieje narzędzie firmy Intel do analizy wydajności fragmentu kodu: http://software.intel.com/en-us/articles/intel-architecture-code-analyzer/ (Intel IACA). Można go pobrać i przetestować.

W moim doświadczeniu, raport o powolnym pętli:

Intel(R) Architecture Code Analyzer Version - 2.0.1 
Analyzed File - ./l2_i 
Binary Format - 32Bit 
Architecture - SNB 
Analysis Type - Throughput 

Throughput Analysis Report 
-------------------------- 
Block Throughput: 3.05 Cycles  Throughput Bottleneck: Port5 

Port Binding In Cycles Per Iteration: 
------------------------------------------------------------------------- 
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 
------------------------------------------------------------------------- 
| Cycles | 0.5 0.0 | 0.5 | 1.0 1.0 | 1.0 1.0 | 0.0 | 3.0 | 
------------------------------------------------------------------------- 

N - port number or number of cycles resource conflict caused delay, DV - Divide 
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path 
F - Macro Fusion with the previous instruction occurred 

| Num Of |    Ports pressure in cycles    | | 
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | | 
--------------------------------------------------------------------- 
| 1 |   |  |   |   |  | 1.0 | CP | cmp edi, 
| 0F |   |  |   |   |  |  | | jz 0xb 
| 1 |   |  | 1.0 1.0 |   |  |  | | movzx ebx 
| 2 |   |  |   | 1.0 1.0 |  | 1.0 | CP | cmp cl, b 
| 0F |   |  |   |   |  |  | | jz 0x3 
| 1 | 0.5  | 0.5 |   |   |  |  | | inc edi 
| 1 |   |  |   |   |  | 1.0 | CP | jmp 0xfff 

Do szybkiej pętli:

Throughput Analysis Report 
-------------------------- 
Block Throughput: 2.00 Cycles  Throughput Bottleneck: Port5 

Port Binding In Cycles Per Iteration: 
------------------------------------------------------------------------- 
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 
------------------------------------------------------------------------- 
| Cycles | 0.5 0.0 | 0.5 | 1.0 1.0 | 1.0 1.0 | 0.0 | 2.0 | 
------------------------------------------------------------------------- 

N - port number or number of cycles resource conflict caused delay, DV - Divide 
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path 
F - Macro Fusion with the previous instruction occurred 

| Num Of |    Ports pressure in cycles    | | 
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | | 
--------------------------------------------------------------------- 
| 1 | 0.5  | 0.5 |   |   |  |  | | inc edi 
| 1 |   |  |   |   |  | 1.0 | CP | cmp edi, 
| 0F |   |  |   |   |  |  | | jz 0x8 
| 1 |   |  | 1.0 1.0 |   |  |  | | movzx ebx 
| 2 |   |  |   | 1.0 1.0 |  | 1.0 | CP | cmp cl, b 
| 0F |   |  |   |   |  |  | | jnz 0xfff 

Więc w zwolnionym pętli JMP jest dodatkowa instrukcja w Critical Path. Wszystkie pary cmp + jz/jnz są scalane (Macro-fusion) w pojedynczy u-op. W mojej implementacji kodu najważniejszym zasobem jest Port5, który może wykonywać ALU + JMP (i jest to jedyny port z obsługą JMP).

PS: Jeśli ktoś nie ma pojęcia, gdzie znajdują się porty, znajdują się zdjęcia firstsecond; i artykuł: rwt

PPS: IACA ma pewne ograniczenia; modeluje tylko część CPU (jednostek wykonawczych) i nie uwzględnia błędów w pamięci podręcznej, niedociągnięć w odgałęzieniach, różnych kar, zmian częstotliwości/mocy, przerwań systemu operacyjnego, rywalizacji HyperThreading dla jednostek wykonawczych i wielu innych efektów. Ale jest to przydatne narzędzie, ponieważ pozwala szybko spojrzeć w najbardziej wewnętrzny rdzeń współczesnego procesora Intela. Działa to tylko dla wewnętrznych pętli (podobnie jak pętle w tym pytaniu).

Answer 2

Tekst Test powoduje pętlę biec do ukończenia dla każdego iteracja, a szybka pętla ma jedno mniej instrukcji.