ソートされた配列の処理が、ソートされていない配列の処理よりも速いのはなぜですか?

25045
GManNickG 2012-06-28 03:51.

これは、いくつかの非常に独特な動作を示すC ++コードの一部です。奇妙な理由で、データを奇跡的に並べ替えると、コードがほぼ6倍速くなります。

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • がないstd::sort(data, data + arraySize);場合、コードは11.54秒で実行されます。
  • ソートされたデータを使用すると、コードは1.93秒で実行されます。

当初、これは単なる言語またはコンパイラの異常である可能性があると思ったので、Javaを試しました。

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

同様ですが、それほど極端ではない結果になります。


私の最初の考えは、並べ替えによってデータがキャッシュに取り込まれることでしたが、配列が生成されたばかりであるため、それがどれほどばかげているかを考えました。

  • 何が起こっている?
  • ソートされた配列の処理が、ソートされていない配列の処理よりも速いのはなぜですか?

コードはいくつかの独立した用語を要約しているので、順序は重要ではありません。

26 answers

32502
Mysticial 2012-06-28 03:56.

あなたは分岐予測の失敗の犠牲者です。


分岐予測とは何ですか?

鉄道のジャンクションについて考えてみましょう。

ウィキメディアコモンズ経由のMecanismoによる画像。CC-By-SA3.0ライセンスの下で使用されます。

議論のために、これが1800年代に戻ったと仮定します-長距離または無線通信の前に。

あなたはジャンクションの運営者であり、電車が来るのが聞こえます。あなたはそれがどちらの方向に進むべきか見当がつかない。あなたは電車を止めて、運転手にどちらの方向を望むか尋ねます。次に、スイッチを適切に設定します。

電車は重くて慣性が大きいです。そのため、起動と速度低下に永遠に時間がかかります。

もっと良い方法はありますか?あなたは電車がどちらの方向に行くかを推測します!

  • あなたが正しく推測した場合、それは続きます。
  • あなたが間違って推測した場合、船長は停止し、後退し、スイッチを切り替えるようにあなたに怒鳴ります。その後、他のパスから再起動できます。

毎回正しく推測すれば、電車は止まる必要はありません。
よく間違えると、列車は停車、バックアップ、再起動に多くの時間を費やします。


ifステートメントについて考えてみます。プロセッサレベルでは、これは分岐命令です。

あなたはプロセッサであり、ブランチが表示されます。あなたはそれがどちらの方向に進むのか分かりません。職業はなんですか?実行を停止し、前の命令が完了するまで待ちます。次に、正しいパスを続行します。

最新のプロセッサは複雑で、パイプラインが長くなっています。したがって、彼らは「ウォームアップ」と「スローダウン」に永遠にかかります。

もっと良い方法はありますか?あなたは枝がどちらの方向に行くかを推測します!

  • あなたが正しく推測した場合、あなたは実行を続けます。
  • 推測が間違っている場合は、パイプラインをフラッシュしてブランチにロールバックする必要があります。その後、他のパスから再開できます。

毎回正しく推測すれば、実行を停止する必要はありません。
よく間違えると推測すると、ストール、ロールバック、再起動に多くの時間を費やします。


これが分岐予測です。列車は旗で方向を知らせることができるので、それは最良の例えではないことを認めます。しかし、コンピュータでは、プロセッサは最後の瞬間までブランチがどちらの方向に進むかを知りません。

では、列車が後退して他の経路を下る必要がある回数を最小限に抑えるために、戦略的にどのように推測しますか?あなたは過去の歴史を見ます!列車が99%の時間左に行く場合、あなたは左だと思います。それが交互になる場合、あなたはあなたの推測を交互にします。それが3回ごとに一方向に進む場合、あなたは同じことを推測します...

言い換えれば、あなたはパターンを特定し、それに従うことを試みます。これは多かれ少なかれ分岐予測子のしくみです。

ほとんどのアプリケーションには、正常に動作するブランチがあります。したがって、最新の分岐予測子は通常、90%を超えるヒット率を達成します。しかし、認識可能なパターンのない予測不可能な分岐に直面した場合、分岐予測子は事実上役に立ちません。

さらに読む:ウィキペディアの「分岐予測」の記事。


上から示唆されているように、原因は次のifステートメントです。

if (data[c] >= 128)
    sum += data[c];

データが0から255の間で均等に分散されていることに注意してください。データが並べ替えられると、反復のほぼ前半はifステートメントに入りません。その後、それらはすべてifステートメントに入ります。

分岐は何度も同じ方向に連続して進むため、これは分岐予測に非常に適しています。単純な飽和カウンターでも、方向を切り替えた後の数回の反復を除いて、ブランチを正しく予測します。

迅速な視覚化:

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

ただし、データが完全にランダムである場合、分岐予測子はランダムデータを予測できないため、役に立たなくなります。したがって、おそらく約50%の誤予測があります(ランダムな推測に勝るものはありません)。

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

では、何ができるでしょうか?

コンパイラーがブランチを条件付き移動に最適化できない場合、パフォーマンスのために可読性を犠牲にすることをいとわないのであれば、いくつかのハックを試すことができます。

交換:

if (data[c] >= 128)
    sum += data[c];

と:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

これにより、分岐が削除され、ビット単位の演算に置き換えられます。

(このハックは、元のifステートメントと厳密に同等ではないことに注意してください。ただし、この場合、のすべての入力値に対して有効ですdata[]。)

ベンチマーク:Core i7 920 @ 3.5 GHz

C ++-Visual Studio2010-x64リリース

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java-NetBeans 7.1.1 JDK 7-x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

観察:

  • ブランチあり:ソートされたデータとソートされていないデータには大きな違いがあります。
  • ハックの場合:ソートされたデータとソートされていないデータに違いはありません。
  • C ++の場合、データがソートされると、ハッキングは実際にはブランチよりも少し遅くなります。

一般的な経験則は、重要なループ(この例のように)でのデータ依存の分岐を回避することです。


更新:

  • x64を使用する-O3または使用-ftree-vectorizeするGCC4.6.1は、条件付き移動を生成できます。したがって、ソートされたデータとソートされていないデータの間に違いはありません。どちらも高速です。

    (またはやや速い:すでにソートされている場合、cmov特にGCCがそれを単にaddではなくクリティカルパスに置く場合、特にcmov2サイクルのレイテンシーがあるBroadwellの前のIntelでは:gcc最適化フラグ-O3はコードを-O2より遅くします)

  • VC ++ 2010は、の下でもこのブランチの条件付き移動を生成できません/Ox

  • インテルC ++コンパイラー(ICC)11は、奇跡的なことをします。それは2つのループを交換し、それによって予測できない分岐を外側のループに持ち上げます。したがって、予測ミスの影響を受けないだけでなく、VC ++およびGCCが生成できるものの2倍の速度もあります。言い換えれば、ICCはテストループを利用してベンチマークを打ち負かしました...

  • インテル®コンパイラーにブランチレス・コードを与えると、それは完全にベクトル化されます...そしてブランチと同じくらい高速です(ループ交換あり)。

これは、成熟した最新のコンパイラでさえ、コードを最適化する能力が大きく異なる可能性があることを示しています...

4212
Daniel Fischer 2012-06-28 03:54.

分岐予測。

ソートされた配列では、条件data[c] >= 128は最初に一連falseの値に対してであり、次にそれtrue以降のすべての値に対してになります。それは簡単に予測できます。ソートされていない配列では、分岐コストを支払います。

3409
WiSaGaN 2012-06-28 16:14.

Mysticialの回答で美しく説明されているように、データを並べ替えるとパフォーマンスが大幅に向上する理由は、分岐予測のペナルティが削除されるためです。

さて、コードを見ると

if (data[c] >= 128)
    sum += data[c];

この特定のif... else...ブランチの意味は、条件が満たされたときに何かを追加することであることがわかります。このタイプのブランチは、システム内で条件付き移動命令にコンパイルされる条件付き移動ステートメントに簡単に変換できます。分岐、したがって潜在的な分岐予測ペナルティが削除されます。cmovlx86

CこのようにC++、の条件移動命令に(任意の最適化なしで)直接コンパイルなる文はx86、三項演算子です... ? ... : ...。したがって、上記のステートメントを同等のステートメントに書き直します。

sum += data[c] >=128 ? data[c] : 0;

読みやすさを維持しながら、スピードアップファクターを確認できます。

Intel Core i7 -2600K @ 3.4GHzおよびVisualStudio 2010リリースモードでは、ベンチマークは(Mysticialからコピーされた形式)です。

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

結果は、複数のテストで堅牢です。分岐の結果が予測できない場合は大幅に高速化されますが、予測可能な場合は少し苦労します。実際、条件付き移動を使用する場合、パフォーマンスはデータパターンに関係なく同じです。

それでは、x86それらが生成するアセンブリを調査して、さらに詳しく見ていきましょう。簡単にするために、2つの関数max1とを使用しますmax2

max1条件分岐を使用しますif... else ...

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2三項演算子を使用します... ? ... : ...

int max2(int a, int b) {
    return a > b ? a : b;
}

x86-64マシンで、GCC -S以下のアセンブリを生成します。

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2命令を使用するため、使用するコードははるかに少なくなりますcmovge。ただし、実際の利点はmax2、ブランチジャンプjmpが含まれないことです。これは、予測結果が正しくない場合、パフォーマンスが大幅に低下します。

では、なぜ条件付き移動のパフォーマンスが向上するのでしょうか。

一般的なx86プロセッサでは、命令の実行はいくつかの段階に分けられます。大まかに言って、さまざまな段階を処理するためのさまざまなハードウェアがあります。したがって、新しい命令を開始するために1つの命令が終了するのを待つ必要はありません。これはパイプラインと呼ばれます。

分岐の場合、次の命令は前の命令によって決定されるため、パイプライン化はできません。待つか予測する必要があります。

条件付き移動の場合、実行条件付き移動命令はいくつかのステージに分割されますが、前のステージは前の命令の結果Fetchと同様でDecodeあり、依存しません。後の段階だけが結果を必要とします。したがって、1つの命令の実行時間のほんの一部を待ちます。これが、予測が容易な場合に条件付き移動バージョンがブランチよりも遅い理由です。

Computer Systems:A Programmer's Perspective』の第2版では、これについて詳しく説明しています。条件付き移動命令についてはセクション3.6.6、プロセッサアーキテクチャについては第4章全体、分岐予測と誤予測のペナルティの特別な扱いについてはセクション5.11.2を確認できます。

最近のコンパイラの中には、コードを最適化してパフォーマンスを向上させることができるものもあれば、できないものもあります(問題のコードはVisual Studioのネイティブコンパイラを使用しています)。予測できない場合のブランチと条件付き移動のパフォーマンスの違いを知ることは、シナリオが非常に複雑になり、コンパイラーがそれらを自動的に最適化できない場合に、パフォーマンスが向上したコードを作成するのに役立ちます。

2350
vulcan raven 2012-07-03 16:25.

このコードに対して実行できるさらに多くの最適化について知りたい場合は、次のことを検討してください。

元のループから開始します。

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

ループ交換を使用すると、このループを次のように安全に変更できます。

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

次に、ループifの実行中、条件が一定であることがわかります。そのため、次のことを実行iできますif

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

次に、浮動小数点モデルで許可されていると仮定すると、内側のループを1つの式に折りたたむことができることがわかります(/fp:fastたとえば、スローされます)。

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

それは以前より10万倍速いです。

1942
caf 2012-10-12 19:53.

間違いなく、CPUの分岐予測に問題のあるコードを特定する方法に興味を持つ人もいるでしょう。Valgrindツールにcachegrindは、--branch-sim=yesフラグを使用して有効化される分岐予測シミュレーターがあります。この質問の例で実行し、外部ループの数を10000に減らしてコンパイルするとg++、次の結果が得られます。

並べ替え:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

未分類:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

cg_annotate問題のループについて、によって生成された行ごとの出力にドリルダウンします。

並べ替え:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

未分類:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

これにより、問題のある行を簡単に特定できます。並べ替えられていないバージョンでは、if (data[c] >= 128)行はBcmcachegrindの分岐予測モデルで164,050,007の誤って予測された条件分岐()を引き起こしますが、並べ替えられたバージョンでは10,006しか発生しません。


または、Linuxでは、パフォーマンスカウンターサブシステムを使用して同じタスクを実行できますが、CPUカウンターを使用したネイティブパフォーマンスを使用します。

perf stat ./sumtest_sorted

並べ替え:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

未分類:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

また、分解してソースコードの注釈を付けることもできます。

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

詳細については、パフォーマンスチュートリアルを参照してください。

1392
atlaste 2013-04-24 20:26.

この質問とその答えを読んだところ、答えが欠けているように感じます。

マネージド言語で特にうまく機能することがわかった分岐予測を排除する一般的な方法は、分岐を使用する代わりにテーブルルックアップです(この場合はテストしていませんが)。

このアプローチは、一般的に次の場合に機能します。

  1. これは小さなテーブルであり、プロセッサにキャッシュされる可能性があります。
  2. 非常にタイトなループで物事を実行しているか、プロセッサがデータをプリロードできます。

背景とその理由

プロセッサの観点からは、メモリは低速です。速度の違いを補うために、いくつかのキャッシュがプロセッサに組み込まれています(L1 / L2キャッシュ)。だから、あなたがあなたの素晴らしい計算をしていると想像して、あなたがメモリの一部を必要としていることを理解してください。プロセッサは「ロード」操作を取得し、メモリの一部をキャッシュにロードします。その後、キャッシュを使用して残りの計算を実行します。メモリは比較的遅いので、この「ロード」はプログラムの速度を低下させます。

分岐予測と同様に、これはPentiumプロセッサで最適化されました。プロセッサは、データの一部をロードする必要があると予測し、操作が実際にキャッシュに到達する前に、それをキャッシュにロードしようとします。すでに見てきたように、分岐予測がひどく間違っていることがあります-最悪のシナリオでは、戻って実際にメモリのロードを待つ必要があります。これには永遠に時間がかかります(言い換えると、分岐予測の失敗は悪いです、メモリ分岐予測が失敗した後のロードはひどいです!)。

幸いなことに、メモリアクセスパターンが予測可能な場合、プロセッサはそれを高速キャッシュにロードし、すべてが順調です。

私たちが最初に知る必要があるのは、何が小さいのかということです。一般的には小さい方が良いですが、経験則では、サイズが4096バイト以下のルックアップテーブルに固執することです。上限として:ルックアップテーブルが64Kより大きい場合は、おそらく再検討する価値があります。

テーブルの作成

これで、小さなテーブルを作成できることがわかりました。次に行うことは、ルックアップ関数を配置することです。ルックアップ関数は通常、いくつかの基本的な整数演算(および、または、xor、shift、add、remove、およびおそらく乗算)を使用する小さな関数です。ルックアップ関数によって入力をテーブル内のある種の「一意のキー」に変換する必要があります。これにより、実行したいすべての作業の答えが得られます。

この場合:> = 128は値を保持できることを意味し、<128は値を取り除くことを意味します。これを行う最も簡単な方法は、「AND」を使用することです。それを保持する場合は、7FFFFFFFでANDします。それを取り除きたい場合は、0とANDします。128は2の累乗であることに注意してください。したがって、32768/128整数のテーブルを作成し、1つのゼロと多数の整数で埋めることができます。 7FFFFFFFFの。

管理言語

なぜこれが管理された言語でうまく機能するのか不思議に思うかもしれません。結局のところ、管理された言語は、分岐を使用して配列の境界をチェックし、混乱しないようにします...

まあ、正確には... :-)

管理言語のこのブランチを削除するためのかなりの作業がありました。例えば:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

この場合、境界条件が決してヒットされないことはコンパイラーにとって明らかです。少なくともMicrosoftJITコンパイラ(Javaも同様のことを行うと思います)はこれに気づき、チェックを完全に削除します。うわー、それはブランチがないことを意味します。同様に、他の明らかなケースも扱います。

管理言語でのルックアップで問題が発生した場合(重要なのは& 0x[something]FFF、ルックアップ関数にを追加して境界チェックを予測可能にすることです)、それがより高速になるのを監視します。

この事件の結果

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
1245
Saqlain 2013-02-15 21:24.

配列がソートされるとデータは0から255の間に分散されるため、反復の前半付近ifは-ifステートメントに入力されません(ステートメントは以下で共有されます)。

if (data[c] >= 128)
    sum += data[c];

問題は、ソートされたデータの場合のように、特定の場合に上記のステートメントが実行されない理由は何ですか?これが「分岐予測」です。分岐予測器は、if-then-elseこれが確実にわかる前に、分岐(構造など)がどちらの方向に進むかを推測しようとするデジタル回路です。分岐予測子の目的は、命令パイプラインのフローを改善することです。分岐予測は、高い効果的なパフォーマンスを達成する上で重要な役割を果たします。

それをよりよく理解するためにいくつかのベンチマーキングをしましょう

-ifステートメントのパフォーマンスは、その条件に予測可能なパターンがあるかどうかによって異なります。条件が常にtrueまたは常にfalseの場合、プロセッサの分岐予測ロジックがパターンを取得します。一方、パターンが予測できない場合、ifステートメントははるかに高価になります。

さまざまな条件でこのループのパフォーマンスを測定してみましょう。

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

さまざまな真偽パターンを使用したループのタイミングは次のとおりです。

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

悪い」真偽のパターンはif、「良い」パターンよりも最大6倍遅くなる可能性があります。もちろん、どのパターンが良いか悪いかは、コンパイラーによって生成された正確な命令と特定のプロセッサーに依存します。

したがって、分岐予測がパフォーマンスに与える影響については疑いの余地がありません。

1171
steveha 2013-07-22 22:29.

分岐予測エラーを回避する1つの方法は、ルックアップテーブルを作成し、データを使用してインデックスを作成することです。Stefan de Bruijnは、彼の答えの中でそれについて議論しました。

ただし、この場合、値が[0、255]の範囲にあることがわかっており、値が128以上であることがわかります。つまり、値が必要かどうかを示す1つのビットを簡単に抽出できます。シフトすることで、右側の7ビットのデータでは、0ビットまたは1ビットが残っており、1ビットの場合にのみ値を追加します。このビットを「決定ビット」と呼びましょう。

決定ビットの0/1値を配列へのインデックスとして使用することにより、データがソートされているかどうかに関係なく、同じように高速なコードを作成できます。コードは常に値を追加しますが、決定ビットが0の場合、気にしない場所に値を追加します。コードは次のとおりです。

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

このコードは追加の半分を無駄にしますが、分岐予測の失敗はありません。ランダムデータでは、実際のifステートメントを使用したバージョンよりも非常に高速です。

しかし、私のテストでは、明示的なルックアップテーブルはこれよりもわずかに高速でした。おそらく、ルックアップテーブルへのインデックス作成がビットシフトよりもわずかに高速だったためです。これは、私のコードがルックアップテーブル(lutコード内の「ルックアップテーブル」に対して想像を絶するほど呼び出された)を設定して使用する方法を示しています。C ++コードは次のとおりです。

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

この場合、ルックアップテーブルは256バイトしかないため、キャッシュにうまく収まり、すべてが高速でした。データが24ビット値であり、それらの半分だけが必要な場合、この手法はうまく機能しません...ルックアップテーブルは大きすぎて実用的ではありません。一方、上記の2つの手法を組み合わせることができます。最初にビットをシフトし、次にルックアップテーブルにインデックスを付けます。上半分の値のみが必要な24ビット値の場合、データを12ビット右にシフトし、テーブルインデックス用に12ビット値を残す可能性があります。12ビットのテーブルインデックスは、4096値のテーブルを意味します。これは実用的かもしれません。

ifステートメントを使用する代わりに、配列にインデックスを付ける手法を使用して、使用するポインターを決定できます。二分木を実装するライブラリを見ました。2つの名前付きポインタ(pLeftおよびpRightその他)を使用する代わりに、長さ2のポインタ配列を使用し、「決定ビット」手法を使用してどちらを使用するかを決定しました。たとえば、次の代わりに:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

このライブラリは次のようになります。

i = (x < node->value);
node = node->link[i];

このコードへのリンクは次のとおりです。赤黒木、永遠に混乱

1063
Yves Daoust 2013-07-24 21:57.

ソートされたケースでは、成功した分岐予測や分岐のない比較トリックに頼るよりもうまくいくことができます。つまり、分岐を完全に削除します。

実際、配列はとで連続したゾーンに分割され、data < 128別のゾーンではで分割されdata >= 128ます。したがって、(比較を使用して)二分検索でパーティションポイントを見つけ、Lg(arraySize) = 15そのポイントから直接累積する必要があります。

(チェックなし)のようなもの

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

または、もう少し難読化されています

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

ソート済みまたはソートされていない両方の近似解を与えるさらに高速なアプローチは次のとおりです:(sum= 3137536;真に均一な分布、期待値191.5の16384サンプルを想定):-)

869
Harsh Sharma 2015-07-04 05:35.

上記の動作は、分岐予測が原因で発生しています。

分岐予測を理解するには、最初に命令パイプラインを理解する必要があります。

命令は一連のステップに分割されるため、さまざまなステップを同時に並行して実行できます。この手法は命令パイプラインと呼ばれ、最新のプロセッサのスループットを向上させるために使用されます。これをよりよく理解するには、ウィキペディアのこの例を参照してください。

一般に、最近のプロセッサには非常に長いパイプラインがありますが、簡単にするために、これらの4つのステップのみを検討しましょう。

  1. IF-メモリから命令をフェッチします
  2. ID-命令をデコードします
  3. EX-命令を実行します
  4. WB-CPUレジスタに書き戻す

一般に2つの命令のための4段階のパイプライン。

上記の質問に戻って、次の手順を検討しましょう。

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

分岐予測がないと、次のことが起こります。

命令Bまたは命令Cに進むかどうかの決定は命令Aの結果に依存するため、命令Bまたは命令Cを実行するには、プロセッサは命令AがパイプラインのEXステージまで到達しないまで待機する必要があります。このようになります。

条件がtrueを返す場合:

条件がfalseを返す場合:

命令Aの結果を待った結果、上記の場合(分岐予測なし、trueとfalseの両方)に費やされた合計CPUサイクルは7です。

では、分岐予測とは何ですか?

分岐予測子は、これが確実にわかる前に、分岐(if-then-else構造)がどちらの方向に進むかを推測しようとします。命令AがパイプラインのEXステージに到達するのを待つことはありませんが、決定を推測してその命令(この例の場合はBまたはC)に進みます。

正しい推測の場合、パイプラインは次のようになります。

推測が間違っていたことが後で検出された場合、部分的に実行された命令は破棄され、パイプラインは正しい分岐で最初からやり直し、遅延が発生します。ブランチの予測ミスの場合に浪費される時間は、フェッチステージから実行ステージまでのパイプラインのステージ数に等しくなります。最近のマイクロプロセッサはパイプラインが非常に長い傾向があるため、予測ミスの遅延は10〜20クロックサイクルです。パイプラインが長いほど、優れた分岐予測子の必要性が高まります。

OPのコードでは、初めて条件付きの場合、分岐予測子には予測の基礎となる情報がないため、最初はランダムに次の命令を選択します。forループの後半では、履歴に基づいて予測を行うことができます。昇順でソートされた配列の場合、次の3つの可能性があります。

  1. すべての要素が128未満です
  2. すべての要素が128より大きい
  3. いくつかの最初の新しい要素は128未満であり、後で128より大きくなります

予測子が最初の実行で常に真の分岐を想定すると仮定しましょう。

したがって、最初のケースでは、歴史的にすべての予測が正しいため、常に真の分岐を取ります。2番目のケースでは、最初は間違った予測をしますが、数回繰り返すと正しく予測します。3番目のケースでは、要素が128未満になるまで、最初は正しく予測します。その後、しばらくの間失敗し、履歴に分岐予測の失敗が見られると、それ自体が修正されます。

これらすべての場合において、障害の数が少なすぎるため、部分的に実行された命令を破棄して正しいブランチからやり直す必要があるのは数回だけであり、CPUサイクルが少なくなります。

ただし、ランダムなソートされていない配列の場合、予測では部分的に実行された命令を破棄し、ほとんどの場合正しいブランチからやり直す必要があり、ソートされた配列と比較してCPUサイクルが多くなります。

764
Surt 2015-10-12 11:05.

公式の答えは

  1. Intel-ブランチの予測ミスのコストを回避する
  2. Intel-誤予測を防ぐためのブランチとループの再編成
  3. 科学論文-分岐予測コンピュータアーキテクチャ
  4. 書籍:JLヘネシー、DAパターソン:コンピューターアーキテクチャ:定量的アプローチ
  5. 科学出版物の記事:TY Yeh、YN Pattは、ブランチの予測についてこれらの多くを作成しました。

この素敵な図から、分岐予測が混乱する理由もわかります。

元のコードの各要素はランダムな値です

data[c] = std::rand() % 256;

そのため、予測子はstd::rand()打撃として側面を変更します。

一方、ソートされると、予測子は最初に強く取られない状態に移行し、値が高い値に変わると、予測子は3回の実行で、強く取られない状態から強く取られる状態に変わります。


734
rkachach 2015-09-24 04:57.

同じ行で(これはどの回答でも強調されていなかったと思います)、時々(特に、Linuxカーネルのようにパフォーマンスが重要なソフトウェアで)次のようなifステートメントを見つけることができることを言及するのは良いことです。

if (likely( everything_is_ok ))
{
    /* Do something */
}

または同様に:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

どちらlikely()unlikely()GCCのようなものを使用して定義されている実際のマクロである__builtin_expectアカウントにユーザーから提供された情報を取る条件を優先するように予測コードを挿入し、コンパイラを支援します。GCCは、実行中のプログラムの動作を変更したり、キャッシュのクリアなどの低レベルの命令を発行したりする可能性のある他のビルトインをサポートします。利用可能なGCCのビルトインについて説明しているこのドキュメントを参照してください。

通常、この種の最適化は、実行時間が重要で重要なハードリアルタイムアプリケーションまたは組み込みシステムで主に見られます。たとえば、1/10000000回しか発生しないエラー状態をチェックしている場合は、コンパイラにこれを通知しませんか?このように、デフォルトでは、分岐予測は条件が偽であると想定します。

718
Maciej 2015-10-10 14:30.

C ++で頻繁に使用されるブール演算は、コンパイルされたプログラムに多くの分岐を生成します。これらのブランチがループ内にあり、予測が難しい場合、実行が大幅に遅くなる可能性があります。ブール変数は値を持つ8ビットの整数として格納されている0ためfalse1のためにtrue

ブール変数は、すべての入力が以外の値を持っている場合、入力チェックとしてブール変数を持っている事業者という意味で過剰決定されている0か、1出力としてブール値を持っているが、事業者はよりも、他の値を生成することはできません01。これにより、ブール変数を入力として使用する操作の効率が必要以上に低くなります。例を考えてみましょう:

bool a, b, c, d;
c = a && b;
d = a || b;

これは通常、コンパイラによって次の方法で実装されます。

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

このコードは最適とはほど遠いです。予測を誤ると、ブランチに時間がかかる場合があります。オペランドが他の値よりもを持っていないことが確実に分かっている場合にブール演算は、はるかに効率化することができる01。コンパイラがそのような仮定を行わない理由は、変数が初期化されていないか、不明なソースからのものである場合、変数が他の値を持つ可能性があるためです。上記のコードは、有効な値に初期化されている場合abまたはブール出力を生成する演算子からのものである場合に最適化できます。最適化されたコードは次のようになります。

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

charブール演算子(および)の代わりにboolビット演算子(&および|)を使用できるようにするために、の代わりにが使用されます。ビット単位の演算子は、1クロックサイクルしかかからない単一の命令です。OR演算子は()しても動作しますし、以外の値を持っていますか。AND演算子()とEXCLUSIVE OR演算子()は、オペランドの値がと以外の場合、一貫性のない結果をもたらす可能性があります。&&|||ab01&^01

~NOTには使用できません。代わりに、既知の変数に対してブールNOTを作成する01、次のようにXORすることができ1ます。

bool a, b;
b = !a;

次のように最適化できます。

char a = 0, b;
b = a ^ 1;

a && ba & bifで置き換えることはできません。ifbは評価されるべきではない式aですfalse&&評価されませんb&will)。同様に、a || bと置き換えることができないa | b場合b場合に評価すべきではない表現です。atrue

ビット単位の演算子を使用すると、オペランドが比較である場合よりも、オペランドが変数である場合の方が有利です。

bool a; double x, y, z;
a = x > y && z < 5.0;

ほとんどの場合、最適です(&&式が多くのブランチの誤予測を生成することを期待しない限り)。

377
Alireza 2017-06-19 01:40.

それは確かだ!...

コードで切り替えが発生するため、分岐予測によってロジックの実行が遅くなります。まっすぐな道や曲がりくねった道を進んでいるようなものです。まっすぐな道の方が早くできるはずです!...

配列が並べ替えられている場合、最初のステップで条件はfalseにdata[c] >= 128なります。その後、通りの終わりまでずっと真の値になります。これにより、ロジックの最後にすばやく到達できます。一方、ソートされていない配列を使用すると、コードの実行が確実に遅くなる多くの回転と処理が必要になります...

下の画像をご覧ください。どの通りが早く完成するのでしょうか?

したがって、プログラム的に、分岐予測はプロセスを遅くします...

また、最後に、それぞれがコードに異なる影響を与える2種類のブランチ予測があることを知っておくとよいでしょう。

1.静的

2.動的

静的分岐予測は、条件分岐が最初に検出されたときにマイクロプロセッサによって使用され、動的分岐予測は、条件分岐コードの後続の実行に使用されます。

これらのルールを利用するコードを効果的に作成するには、if-elseまたはswitchステートメントを作成するときに、最も一般的なケースを最初に確認し、最も一般的でないケースまで徐々に作業を進めていきます。通常はループイテレータの条件のみが使用されるため、ループは静的分岐予測のためにコードの特別な順序を必ずしも必要としません。

334
ForeverLearning 2017-01-12 15:50.

この質問はすでに何度も見事に答えられています。それでも、グループの注意をさらに別の興味深い分析に向けたいと思います。

最近、この例(ごくわずかに変更)は、Windows上のプログラム自体の中でコードの一部をプロファイリングする方法を示す方法としても使用されました。途中で、作成者は、結果を使用して、ソートされた場合とソートされていない場合の両方で、コードがほとんどの時間を費やしている場所を判別する方法も示します。最後に、この記事では、HAL(Hardware Abstraction Layer)のあまり知られていない機能を使用して、ソートされていない場合に発生しているブランチの予測ミスの量を判断する方法も示しています。

リンクはここにあります:自己プロファイリングのデモンストレーション

306
Eugene 2017-11-07 06:15.

他の人がすでに言及しているように、謎の背後にあるのは分岐予測です。

私は何かを追加しようとしているのではなく、別の方法で概念を説明しています。ウィキには、テキストと図を含む簡潔な紹介があります。ダイアグラムを使用して分岐予測を直感的に詳しく説明する以下の説明が好きです。

コンピュータアーキテクチャでは、分岐予測子は、これが確実にわかる前に、分岐(たとえば、if-then-else構造)がどちらの方向に進むかを推測しようとするデジタル回路です。分岐予測子の目的は、命令パイプラインのフローを改善することです。分岐予測子は、x86などの多くの最新のパイプラインマイクロプロセッサアーキテクチャで高い効果的なパフォーマンスを実現する上で重要な役割を果たします。

双方向分岐は通常、条件付きジャンプ命令で実装されます。条件付きジャンプは、「実行されず」、条件付きジャンプの直後に続くコードの最初の分岐で実行を継続するか、「実行」されて、コードの2番目の分岐があるプログラムメモリ内の別の場所にジャンプすることができます。保存されます。条件が計算され、条件付きジャンプが命令パイプラインの実行ステージを通過するまで、条件付きジャンプが実行されるかどうかは定かではありません(図1を参照)。

説明したシナリオに基づいて、さまざまな状況でパイプラインで命令がどのように実行されるかを示すアニメーションデモを作成しました。

  1. 分岐予測なし。

分岐予測がない場合、プロセッサは、条件付きジャンプ命令が実行ステージを通過するまで待機してから、次の命令がパイプラインのフェッチステージに入る必要があります。

この例には3つの命令が含まれており、最初の命令は条件付きジャンプ命令です。後者の2つの命令は、条件付きジャンプ命令が実行されるまでパイプラインに入ることができます。

3つの命令が完了するまでに9クロックサイクルかかります。

  1. 分岐予測を使用し、条件付きジャンプを行わないでください。予測が条件付きジャンプを行っていないと仮定しましょう。

3つの命令が完了するまでに7クロックサイクルかかります。

  1. 分岐予測を使用して、条件付きジャンプを実行します。予測が条件付きジャンプを行っていないと仮定しましょう。

3つの命令が完了するまでに9クロックサイクルかかります。

ブランチの予測ミスの場合に浪費される時間は、フェッチステージから実行ステージまでのパイプラインのステージ数に等しくなります。最近のマイクロプロセッサはパイプラインが非常に長い傾向があるため、予測ミスの遅延は10〜20クロックサイクルです。その結果、パイプラインを長くすると、より高度な分岐予測子の必要性が高まります。

ご覧のとおり、分岐予測を使用しない理由はないようです。

これは、分岐予測の非常に基本的な部分を明確にする非常に単純なデモです。これらのgifが煩わしい場合は、回答から自由に削除してください。訪問者は、BranchPredictorDemoからライブデモのソースコードを入手することもできます。

238
Tony Tannous 2017-08-05 00:07.

分岐予測ゲイン!

ブランチの予測ミスがプログラムの速度を低下させないことを理解することが重要です。予測を逃した場合のコストは、分岐予測が存在せず、式の評価を待って実行するコードを決定するのと同じです(次の段落でさらに説明します)。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

if-else\switchステートメントがある場合は常に、実行するブロックを決定するために式を評価する必要があります。コンパイラが生成するアセンブリコードには、条件分岐命令が挿入されています。

分岐命令は、コンピュータに異なる命令シーケンスの実行を開始ifさせ、条件によっては、命令を順番に実行するデフォルトの動作から逸脱する可能性があります(つまり、式がfalseの場合、プログラムはブロックのコードをスキップします)。この場合の式の評価。

そうは言っても、コンパイラは実際に評価される前に結果を予測しようとします。ifブロックから命令をフェッチし、式が真であることが判明した場合は素晴らしいです!私たちはそれを評価するのにかかる時間を稼ぎ、コードを進歩させました。そうでない場合は、間違ったコードを実行し、パイプラインがフラッシュされ、正しいブロックが実行されます。

視覚化:

ルート1またはルート2を選択する必要があるとします。パートナーが地図を確認するのを待って、##で停止して待機しました。または、ルート1を選択して、運が良ければ(ルート1が正しいルートです)、そうすれば、パートナーがマップをチェックするのを待つ必要はありませんでした(パートナーがマップをチェックするのにかかる時間を節約できました)。そうしないと、元に戻ります。

パイプラインのフラッシュは超高速ですが、今日ではこのギャンブルをする価値があります。ソートされたデータまたはゆっくりと変化するデータを予測することは、速い変化を予測するよりも常に簡単で優れています。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
194
Luke Hutchison 2017-12-23 03:13.

ARMでは、すべての命令に4ビットの条件フィールドがあるため、分岐は必要ありません。このフィールドは、プロセッサステータスレジスタで発生する可能性のある16の異なる条件のいずれかを(ゼロコストで)テストし、命令の条件がfalseの場合、命令はスキップされます。これにより、短い分岐が不要になり、このアルゴリズムで分岐予測がヒットすることはありません。したがって、このアルゴリズムのソートされたバージョンは、ソートの余分なオーバーヘッドのために、ARMのソートされていないバージョンよりも実行が遅くなります。

このアルゴリズムの内部ループは、ARMアセンブリ言語では次のようになります。

MOV R0, #0   // R0 = sum = 0
MOV R1, #0   // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop  // Inner loop branch label
    LDRB R3, [R2, R1]   // R3 = data[c]
    CMP R3, #128        // compare R3 to 128
    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1      // c++
    CMP R1, #arraySize  // compare c to arraySize
    BLT inner_loop      // Branch to inner_loop if c < arraySize

しかし、これは実際には全体像の一部です。

CMPオペコードは、プロセッサステータスレジスタ(PSR)のステータスビットを常に更新します。これがその目的であるためですが、他のほとんどの命令は、オプションのSサフィックスを命令に追加しない限り、PSRに触れず、PSRを更新する必要があることを指定します。命令の結果。ただ、4ビットの条件接尾辞のように、PSRに影響を与えることなく、命令を実行できることはARMの枝の必要性を低減し、また、ハードウェアレベルでの注文発送のアウトを容易メカニズムであるため、更新することを、いくつかの操作Xを実行した後、ステータスビット、続いて(または並行して)ステータスビットに明示的に影響を与えない(または影響を受けない)他の一連の作業を実行してから、Xによって以前に設定されたステータスビットの状態をテストできます。

条件テストフィールドとオプションの「ステータスビットの設定」フィールドは、次のように組み合わせることができます。

  • ADD R1, R2, R3R1 = R2 + R3ステータスビットを更新せずに実行します。
  • ADDGE R1, R2, R3 ステータスビットに影響を与えた前の命令が大なり記号または等しい条件をもたらした場合にのみ、同じ操作を実行します。
  • ADDS R1, R2, R3実行添加した後、更新NZC及びV結果は陰性であったかどうかに基づいて、プロセッサステータスレジスタのフラグをゼロ(符号なし添加のため)を搭載し、またはオーバーフロー(符号付き加算のために)。
  • ADDSGE R1, R2, R3GEテストが真の場合にのみ加算を実行し、その後、加算の結果に基づいてステータスビットを更新します。

ほとんどのプロセッサアーキテクチャには、特定の操作でステータスビットを更新するかどうかを指定するこの機能がありません。これにより、ステータスビットを保存して後で復元するために追加のコードを記述する必要が生じたり、追加のブランチが必要になったり、プロセッサのアウトが制限されたりする可能性があります。注文実行効率の問題:ほとんどのCPU命令セットアーキテクチャがほとんどの命令の後にステータスビットを強制的に更新することの副作用の1つは、どの命令を互いに干渉せずに並列実行できるかを区別するのがはるかに難しいことです。ステータスビットの更新には副作用があるため、コードに線形化効果があります。アセンブリ言語プログラマーとコンパイラーの両方にとって、命令の後にステータスビットを更新するか更新しないかのオプションを備えた、任意の命令のブランチフリー条件テストを組み合わせて一致させるARMの機能は、非常に効率的なコードを生成します。

分岐する必要がない場合は、パイプラインをフラッシュして短い分岐になる時間コストを回避でき、さまざまな形式の投機的評価の設計の複雑さを回避できます。最近発見された多くのプロセッサの脆弱性(Spectreなど)に対する緩和策の最初の素朴な実装のパフォーマンスへの影響は、最新のプロセッサのパフォーマンスが複雑な投機的評価ロジックにどれだけ依存しているかを示しています。パイプラインが短く、分岐の必要性が劇的に減少しているため、ARMはCISCプロセッサほど投機的評価に依存する必要がありません。(もちろん、ハイエンドのARM実装には投機的評価が含まれていますが、それはパフォーマンスストーリーのごく一部です。)

ARMがなぜこれほど驚異的に成功したのか疑問に思ったことがある場合は、これら2つのメカニズムの優れた効果と相互作用(算術演算子またはオフセットメモリアクセスの2つの引数のいずれかを左右に「バレルシフト」できる別のメカニズムと組み合わせる)追加コストなしの演算子)は、ARMアーキテクチャの効率の最大の源のいくつかであるため、ストーリーの大きな部分を占めています。1983年のARMISAの元の設計者であるSteveFurberとRoger(現在のSophie)Wilsonの素晴らしさは、誇張することはできません。

167
Yochai Timmer 2017-11-24 04:28.

分岐予測が遅くなる可能性があるという事実に加えて、ソートされた配列には別の利点があります。

値をチェックするだけでなく、停止条件を設定することもできます。これにより、関連するデータのみをループし、残りは無視します。
分岐予測は1回だけ失敗します。

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
163
Farhad 2017-10-03 23:47.

それは分岐予測についてです。それは何ですか?

  • 分岐予測子は、現代のアーキテクチャとの関連性を今でも見つけている古代のパフォーマンス改善手法の1つです。単純な予測手法は高速なルックアップと電力効率を提供しますが、予測ミス率が高くなります。

  • 一方、複雑な分岐予測(ニューラルベースまたは2レベル分岐予測の変形)は、より優れた予測精度を提供しますが、より多くの電力を消費し、複雑さが指数関数的に増加します。

  • これに加えて、複雑な予測手法では、ブランチの予測にかかる時間自体が非常に長く、2〜5サイクルの範囲であり、実際のブランチの実行時間に匹敵します。

  • 分岐予測は本質的に最適化(最小化)問題であり、最小限のリソースで可能な限り低いミス率、低消費電力、および低複雑さを達成することに重点が置かれています。

実際には3種類のブランチがあります。

順方向条件分岐-実行時の条件に基づいて、PC(プログラムカウンター)は、命令ストリーム内の順方向アドレスを指すように変更されます。

後方条件分岐-PCは、命令ストリーム内で後方を指すように変更されます。分岐は、ループの最後のテストでループを再度実行する必要があると示されたときに、プログラムループの最初に逆方向に分岐するなど、いくつかの条件に基づいています。

無条件分岐-これには、特定の条件のないジャンプ、プロシージャコール、およびリターンが含まれます。たとえば、無条件ジャンプ命令はアセンブリ言語で単に「jmp」としてコーディングされ、命令ストリームはジャンプ命令が指すターゲット位置にすぐに転送される必要がありますが、条件付きジャンプは「jmpne」としてコーディングされる場合があります。前の「比較」命令で2つの値を比較した結果、値が等しくないことが示された場合にのみ、命令ストリームをリダイレクトします。(x86アーキテクチャで使用されるセグメント化されたアドレス指定スキームは、ジャンプが「近い」(セグメント内)または「遠い」(セグメント外)のいずれかになる可能性があるため、さらに複雑になります。各タイプは、分岐予測アルゴリズムに異なる影響を及ぼします。)

静的/動的分岐予測:静的分岐予測は、条件付き分岐に最初に遭遇したときにマイクロプロセッサによって使用され、動的分岐予測は、条件付き分岐コードの後続の実行に使用されます。

参照:

  • 分岐予測

  • 自己プロファイリングのデモンストレーション

  • 分岐予測レビュー

  • 分岐予測

147
omkaartg 2017-12-08 07:28.

分岐予測と呼ばれる現象により、ソートされた配列は、ソートされていない配列よりも高速に処理されます。

分岐予測子は、分岐がどちらの方向に進むかを予測しようとするデジタル回路(コンピューターアーキテクチャー内)であり、命令パイプラインのフローを改善します。回路/コンピュータは次のステップを予測して実行します。

間違った予測を行うと、前のステップに戻り、別の予測で実行されます。予測が正しいと仮定すると、コードは次のステップに進みます。予測が間違っていると、正しい予測が行われるまで同じ手順が繰り返されます。

あなたの質問への答えはとても簡単です。

ソートされていない配列では、コンピューターが複数の予測を行うため、エラーが発生する可能性が高くなります。一方、ソートされた配列では、コンピューターが行う予測が少なくなり、エラーの可能性が低くなります。より多くの予測を行うには、より多くの時間が必要です。

ソートされた配列:Straight Road ____________________________________________________________________________________ --- --- --- --- --- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未分類の配列:カーブした道路

______   ________
|     |__|

分岐予測:どの道路がまっすぐであるかを推測/予測し、チェックせずにそれをたどる

___________________________________________ Straight road
 |_________________________________________|Longer road

どちらの道路も同じ目的地に到達しますが、直線道路は短く、もう一方は長くなります。誤ってもう一方を選んだ場合、後戻りすることはないので、長い道を選ぶと余分な時間が無駄になります。これはコンピューターで起こることと似ており、これがあなたの理解を深めるのに役立つことを願っています。


また、コメントから@Simon_Weaverを引用したいと思います。

予測が少なくなるわけではありません。誤った予測が少なくなります。それでも、ループを通過するたびに予測する必要があります...

139
Shan 2012-12-31 06:16.

次のMATLABコードについて、MacBook Pro(Intel i7、64ビット、2.4 GHz)を使用してMATLAB2011bで同じコードを試しました。

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

上記のMATLABコードの結果は次のとおりです。

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

@GManNickGのようなCコードの結果は次のとおりです。

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

これに基づくと、MATLABはソートなしのC実装よりも約175倍遅く、ソートありの場合は350倍遅いようです。換言すれば、(分岐予測の)効果がある1.46x MATLABの実装とのための2.7倍Cの実装のために。

72
user2297550 2018-12-09 20:18.

データをソートする必要があるという他の回答による仮定は正しくありません。

次のコードは、配列全体を並べ替えるのではなく、配列の200要素のセグメントのみを並べ替えるため、最も高速に実行されます。

k要素セクションのみを並べ替えると、配列全体を並べ替えるのに必要な時間でO(n)はなく、線形時間で前処理が完了O(n.log(n))します。

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

これはまた、ソート順などのアルゴリズムの問​​題とは何の関係もないことを「証明」し、実際には分岐予測です。

54
Selcuk 2019-10-15 13:34.

この質問に対するBjarneStroustrupの回答:

それは面接の質問のように聞こえます。それは本当ですか?どうやって知る?最初にいくつかの測定を行わずに効率に関する質問に答えることは悪い考えです。したがって、測定方法を知ることが重要です。

それで、私は百万の整数のベクトルで試し、得ました:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

確かにそれを数回実行しました。はい、現象は本物です。私のキーコードは次のとおりです。

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

少なくともこの現象は、このコンパイラ、標準ライブラリ、およびオプティマイザの設定では現実的です。実装が異なれば、答えも異なります。実際、誰かがより体系的な調査を行い(簡単なWeb検索でそれが見つかります)、ほとんどの実装でその効果が示されています。

1つの理由は、分岐予測です“if(v[i] < pivot]) …”。ソートアルゴリズムの主要な操作は、または同等です。ソートされたシーケンスの場合、テストは常に真ですが、ランダムシーケンスの場合、選択されたブランチはランダムに変化します。

もう1つの理由は、ベクトルがすでに並べ替えられている場合、要素を正しい位置に移動する必要がないことです。これらの小さな詳細の効果は、私たちが見た5〜6倍です。

クイックソート(および一般的なソート)は複雑な研究​​であり、コンピューターサイエンスの最も優れた精神の一部を魅了しています。優れたソート関数は、優れたアルゴリズムを選択し、その実装でハードウェアのパフォーマンスに注意を払った結果です。

効率的なコードを書きたい場合は、マシンアーキテクチャについて少し知っておく必要があります。

47
hatirlatici 2019-10-24 11:35.

この質問は、CPUの分岐予測モデルに基づいています。このペーパーを読むことをお勧めします:

複数の分岐予測と分岐アドレスキャッシュによる命令フェッチレートの向上

要素を並べ替えると、IRはすべてのCPU命令を何度もフェッチする必要がなくなり、キャッシュからそれらをフェッチします。

40
Manoj Kashyam 2020-01-21 23:08.

分岐予測エラーを回避する1つの方法は、ルックアップテーブルを作成し、データを使用してインデックスを作成することです。Stefan de Bruijnは、彼の答えの中でそれについて議論しました。

ただし、この場合、値が[0、255]の範囲にあることがわかっており、値が128以上であることがわかります。つまり、値が必要かどうかを示す1つのビットを簡単に抽出できます。シフトすることで、右側の7ビットのデータでは、0ビットまたは1ビットが残っており、1ビットの場合にのみ値を追加します。このビットを「決定ビット」と呼びましょう。

決定ビットの0/1値を配列へのインデックスとして使用することにより、データがソートされているかどうかに関係なく、同じように高速なコードを作成できます。コードは常に値を追加しますが、決定ビットが0の場合、気にしない場所に値を追加します。コードは次のとおりです。

//テスト

clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

このコードは追加の半分を無駄にしますが、分岐予測の失敗はありません。ランダムデータでは、実際のifステートメントを使用したバージョンよりも非常に高速です。

しかし、私のテストでは、明示的なルックアップテーブルはこれよりもわずかに高速でした。おそらく、ルックアップテーブルへのインデックス作成がビットシフトよりもわずかに高速だったためです。これは、私のコードがルックアップテーブル(コード内の「ルックアップテーブル」の場合は想像を絶するほどにlutと呼ばれます)を設定して使用する方法を示しています。C ++コードは次のとおりです。

//ルックアップテーブルを宣言してから入力します

int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

この場合、ルックアップテーブルは256バイトしかないため、キャッシュにうまく収まり、すべてが高速でした。データが24ビット値であり、それらの半分だけが必要な場合、この手法はうまく機能しません...ルックアップテーブルは大きすぎて実用的ではありません。一方、上記の2つの手法を組み合わせることができます。最初にビットをシフトし、次にルックアップテーブルにインデックスを付けます。上半分の値のみが必要な24ビット値の場合、データを12ビット右にシフトし、テーブルインデックス用に12ビット値を残す可能性があります。12ビットのテーブルインデックスは、4096値のテーブルを意味します。これは実用的かもしれません。

ifステートメントを使用する代わりに、配列にインデックスを付ける手法を使用して、使用するポインターを決定できます。二分木を実装するライブラリを見ました。2つの名前付きポインタ(pLeftとpRightなど)の代わりに、長さ2のポインタ配列があり、「決定ビット」手法を使用してどちらに従うかを決定しました。たとえば、次の代わりに:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
this library would do something like:

i = (x < node->value);
node = node->link[i];

それは素晴らしい解決策であり、多分それはうまくいくでしょう。

Related questions

MORE COOL STUFF

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

Total War:Warhammer:Kotakuレビュー

Total War:Warhammer:Kotakuレビュー

私はこのゲームを嫌う準備ができていました。先週の前に、Total War:Warhammerについての私の考えがありました:それでもここに私は、私の手にある完成品であり、私は変わった男です。

涙の道:軍事化された帝国主義勢力がスタンディングロックキャンプを占領

涙の道:軍事化された帝国主義勢力がスタンディングロックキャンプを占領

スタンディングロックスー族のメンバーと水の保護者は、ノースダコタ州のスタンディングロックにあるオセティサコウィンキャンプを去ります。(Twitter経由のCNNスクリーンショット)火と煙がスカイラインを覆い、スタンディングロックスー族のメンバーと水の保護者が、聖なるものを守りながら建てた家、オセティサコウィン(セブンカウンシルファイアーズ)キャンプから行進し、太鼓を打ち、歌い、祈りました。ダコタアクセスパイプラインとしても知られる「ブラックスネーク」からの土地。

シアーズとKマートはイヴァンカ・トランプの商品を自分たちで取り除いています

シアーズとKマートはイヴァンカ・トランプの商品を自分たちで取り除いています

写真:APシアーズとKマートは、イヴァンカ・トランプのトランプホームアイテムのコレクションも、誰も購入したくないために削除しました。シアーズとKマートの両方の親会社であるシアーズホールディングスは、土曜日のABCニュースへの声明で、彼らが気にかけていると辛抱強く説明しましたトランプラインを売り続けるにはお金を稼ぐことについてあまりにも多く。

ポテトチップスでたった10分でスペインのトルティーヤを作る

ポテトチップスでたった10分でスペインのトルティーヤを作る

伝統的なスペインのトルティーヤは通常、オリーブオイルで柔らかくなるまで調理されたポテトから始まります(30分以上かかる場合があります)が、ケトルで調理されたポテトチップスの助けを借りてわずか10分でテーブルに置くことができます。上のビデオはすべてがバラバラにならないように裏返す方法を含め、レシピ全体を説明しますが、必要なのは4〜5個の卵と3カップのケトルチップスだけです。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language