왜이 어셈블리 코드가 더 빠릅니까?

Question

나는 렉서 (lexer)를 실험하고 있는데, 프로그램의 한 부분에서 while-loop에서 if-statement와 do-while-loop로 전환하면 ~ 20 % 더 빠른 코드가 만들어져 미친 것처럼 보였다. 필자는 컴파일러에서 생성 된 코드의 차이점을이 어셈블리 조각에 격리 시켰습니다. 누구든지 빠른 코드가 더 빠른 이유를 알고 있습니까?

어셈블리에서 'edi'는 현재 텍스트 위치이고 'ebx'는 텍스트의 끝이고 'isAlpha'는 문자가 영문자이면 1, 그렇지 않으면 0 인 찾아보기 테이블입니다.

느린 코드 :

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: 

빠른 코드 :

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: 

나는 텍스트는 문자 구성의 메가 바이트에 불과 이러한 조립 미리보기를 실행하면 'A', 빠른 코드 30 % 빨라집니다. 내 생각 엔 느린 코드는 분기 오보 (misprediction)로 인해 속도가 느려지지만 루프에서 한 번만 비용이들 것이라고 생각했습니다.

이

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

테스트 프로그램의 출력은

이

slow in 8455 ticks 
fast in 5694 ticks 

Answer 1

죄송합니다. GCC (Linux)에서 코드를 정확히 재현하지 못했습니다. 그러나 몇 가지 결과가 있으며 주요 아이디어가 제 코드에 저장되어 있다고 생각합니다.

Intel에서 코드 조각 성능을 분석 할 수있는 도구가 있습니다 (http://software.intel.com/en-us/articles/intel-architecture-code-analyzer/ (Intel IACA)). 무료로 다운로드하여 테스트 할 수 있습니다. 느린 루프 내 실험에서

은 보고서 :

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 

빠른 루프의 경우 :

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 

그래서 느린 루프 JMP가 임계 경로에 추가 명령어입니다. cmp + jz/jnz의 모든 쌍이 단일 u-op로 합쳐집니다 (매크로 융합). 그리고 코드를 구현할 때 중요한 리소스는 ALU + JMP (JMP 기능이있는 유일한 포트)를 실행할 수있는 Port5입니다.

추신 : 포트가 어디에 있는지 전혀 모르는 사람은 그림이 있습니다. firstsecond; 및 기사 : rwt

PPS : IACA에는 몇 가지 제한이 있습니다. CPU (Execution units)의 일부만 모델링하고, 캐시 미스, 분기 오판, 다른 벌칙, 빈도/전원 변경, OS 인터럽트, 실행 단위에 대한 HyperThreading 경합 및 기타 많은 영향을 설명하지 않습니다. 그러나 그것은 현대 인텔 CPU의 가장 내부 코어를 빠르게 볼 수 있기 때문에 유용한 도구입니다. 그리고 내부 루프 (이 질문의 루프처럼)에서만 작동합니다.

Answer 2

테스트 텍스트는 각각의 모든에 대해 완료 될 때까지 실행하는 루프를 원인입니다 : 여기

내가 두 조각을 테스트하는 데 사용되는 프로그램입니다 반복 및 빠른 루프는 명령어가 하나 더 적습니다.