なぜこのアセンブリコードは高速ですか？

Question

私はレクサーを試していますが、プログラムのある部分でwhileループからif文と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: 

私は、テキストのみの文字からなるのメガバイトに対してだけでこれらのアセンブリのスニペットを実行する場合「」、高速なコード30％高速です。私の推測では、低速なコードは分岐の誤予測のために遅いですが、私はループで一度のコストと思っていました。

ここで私は両方のスニペットをテストするために使用するプログラムがあります：テストプログラムの

#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にマージされます（マクロ融合）。 そして、私のコードの実装では、重要なリソースはPort5で、ALU + JMPを実行することができます（それはJMP機能を備えた唯一のポートです）。

PS：どこにポートがあるか分からない人は、firstsecondです。記事：rwt

PPS：IACAにはいくつかの制限があります。 CPU（Execution unit）の一部のみをモデリングし、キャッシュミス、分岐予測ミス、違いペナルティ、周波数/パワー変更、OS割り込み、実行ユニットのHyperThreading競合その他の多くの影響を考慮していません。しかし、それは現代のインテルCPUの最も内部的なコアの内部を素早く見ることができるので便利なツールです。それは内部ループ（この質問のループのように）のみ機能します。

Answer 2

です高速ループでは命令が1つ少なくなります。