java list 並び替え - ソートされた配列をソートされていない配列よりも処理する方が速いのはなぜですか?



10 Answers

分岐予測。

ソートされた配列では、条件data[c] >= 128は、値のスジで最初にfalseになり、その後のすべての値に対してtrueになります。 予測するのは簡単です。 並べ替えられていない配列では、分岐コストを支払うことになります。

任意 逆順 複数

非常に奇妙な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);
    }
}

やや似ていますが、それほど極端な結果はありません。

私の最初の考えは、並べ替えがデータをキャッシュに持ち込むことでしたが、次に配列が生成されたばかりなので、それがどれほどばかげているのだろうと思いました。

  • 何が起こっている?
  • ソートされた配列をソートされていない配列よりも処理する方が速いのはなぜですか?
  • コードはいくつかの独立した用語を要約しており、順序は重要ではありません。



このコードに対してさらに最適化が可能かどうか不安な場合は、次の点を考慮してください。

元のループから始める:

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ループが実行されている間、 if条件が一定であることがわかります。if outをホイストできます:

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

浮動小数点モデルでは、内部ループを単一の式にまとめることができます(たとえば、/ fp:fastがスローされます)

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

その1つは以前より100,000倍高速です




私はちょうどこの質問とその答えを読んで、私は答えが見つからないと感じています。

管理された言語で特にうまく動作することが判明したブランチ予測を排除する一般的な方法は、ブランチを使用するのではなくテーブル参照です(この場合はテストしていませんが)。

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

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

背景と理由

それで、何が意味するはずなのですか?

プロセッサの観点からは、メモリは低速です。 速度の違いを補うために、プロセッサは、プロセッサ内の2つのキャッシュ(L1 / L2キャッシュ)を構築します。 それであなたの素晴らしい計算をして、あなたが記憶を必要としていることを想像してください。 プロセッサは「ロード」オペレーションを取得し、メモリにキャッシュをロードし、キャッシュを使用して残りの計算を実行します。 メモリは比較的遅いので、この '負荷'はプログラムの速度を落とします。

分岐予測と同様に、これはPentiumプロセッサで最適化されました。プロセッサは、データがキャッシュにヒットする前に、データをロードしてキャッシュにロードしようとすると予測します。 すでに見てきたように、分岐予測は時にはひどく間違っています。最悪のシナリオでは、戻って実際にメモリ負荷を待つ必要があります。つまり、永続的な分岐予測ができません。分岐予測が失敗した後の負荷は恐ろしいです! )。

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

私たちが最初に知る必要があるのは、 小さいものですか? 通常は小さい方が良いですが、経験則は4096バイト以下のルックアップテーブルに固執することです。 上限として、ルックアップテーブルが64Kより大きい場合は、再検討する価値があります。

テーブルの作成

だから私たちは小さなテーブルを作ることができるとわかった。 次に行うべきことは、適切なルックアップ機能を得ることです。 ルックアップ関数は、基本的な整数演算(および、または、xor、shift、add、remove、おそらく乗算)を使用する小さな関数です。 ルックアップ関数によって入力をテーブル内の一意のキーに変換したいと思っています。それは単に、あなたが望むすべての作業の答えを提供します。

この場合:> = 128は値を保持できることを意味し、<128はそれを取り除くことを意味します。 これを行う最も簡単な方法は、 'AND'を使用することです:もしそれを保つなら、それを7FFFFFFFとANDします。 128を2の累乗といいます - 32768/128の整数の表を作成して1つの0とたくさんの値を入れることができます7FFFFFFFFです。

管理言語

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

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

管理された言語のために、このブランチをなくすことにかなりの仕事がありました。 例えば:

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

この場合、境界条件が決して打たれないことはコンパイラには明らかです。 少なくともMicrosoft JITコンパイラ(しかし、私はJavaが似たようなことをするだろうと期待しています)がこれに気づき、チェックを完全に削除します。 ワウ - それは枝がないことを意味する。 同様に、それは他の明白なケースを扱うでしょう。

管理された言語のルックアップに問題が発生した場合は、境界チェックを予測可能にするためにルックアップ関数に& 0x[something]FFFを追加して、それがより速く進行することを鍵にしています。

この場合の結果

// 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.Next(256);

//To keep the spirit of the code in-tact 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();



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

しかし、この場合、値は[0,255]の範囲内にあり、値> = 128のみを扱うことがわかります。つまり、値を必要とするかどうかを示す単一のビットを簡単に抽出できます。右の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コード内で "LookUp Table"のために想像以上に呼ばれています)。 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の配列を持つ2つの名前付きポインタ(pLeftおよびpRightその他のもの)を使用するのではなく、 "決定ビット"手法を使用して、たとえば、次の代わりに:

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

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

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

このコードへのリンクは次のとおりです:Red Black TreesEternally Confuzzled




分岐予測のために、上記の現象が発生しています。

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

どの命令も一連のステップに分割され、異なるステップを並行して同時に実行することができます。この技法は命令パイプラインと呼ばれ、これは最新のプロセッサーのスループットを向上させるために使用されます。これをよりよく理解するには、Wikipediaのこの例をご覧ください。

一般に、現代のプロセッサはかなり長いパイプラインを持っていますが、簡単にこれらの4つのステップだけを考えてみましょう。

  1. IF - メモリから命令をフェッチする
  2. ID - 命令をデコードする
  3. EX - 命令を実行する
  4. WB - CPUレジスタにライトバックする

一般に4ステージパイプラインで2命令が実行されます。

上記の質問に戻って、次の手順を考えてみましょう。

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

分岐予測がないと、次のようになります。

命令Bまたは命令Cを実行するためには、命令Aまたは命令Cに進む決定が命令Aの結果に依存するため、プロセッサは命令AがパイプラインのEXステージまで到達しなくなるまで待たなければならない。このように見えます。

条件が真を返すとき:

条件がfalseを返す場合:

命令Aの結果を待った結果、上記の場合(分岐予測なし、真と偽の両方)に費やされた合計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サイクルを必要とします。




同じ行(これはどの答えでも強調表示されていないと思います)では、時には(特にLinuxカーネルのようなパフォーマンスが重要なソフトウェアで)、次のようなif文があることがあります。

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

または同様に:

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

両方likely()unlikely()は実際に__builtin_expectはコンパイラがユーザが提供する情報を考慮して条件を優先するための予測コードを挿入するのを助けるためにGCCのようなものを使って定義されるマクロです。 GCCは、実行中のプログラムの動作を変更したり、キャッシュのクリアなどの低レベルの命令を出すことができる他の組み込み関数をサポートしています。このドキュメントでは、GCCの組み込み関数を参照しています。

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




それは確かだ!...

分岐予測は、コード内で発生する切り替えのために、ロジックの実行速度を低下させます。それはあなたがまっすぐ通りに行くか、まっすぐなものがすばやく行われることを確かめるために、たくさんの旋律を持っているようなものです...

配列がソートされている場合、最初のステップで条件がfalseにdata[c] >= 128なります。その後、通りの終わりまでの真の値になります。それがロジックの終わりまで速く到達する方法です。一方、ソートされていない配列を使用すると、コードの実行速度が遅くなるような処理と処理が必要になります...

下に作成した画像を見てください。どの通りが早く終わるだろうか?

プログラムでは、分岐予測によってプロセスが遅くなります...

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

1.静的

2.ダイナミック

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

ために効果的に書くとき、これらの規則を利用するようにコードを書くためのif-elseのか、切り替え文を、最初の最も一般的な例をチェックして、少なくとも共通にまで徐々に働きます。ループイテレータの条件だけが通常使用されるため、ループでは静的分岐予測のためのコードの特別な順序付けを必ずしも必要としません。




分岐予測ゲイン!

ブランチ誤予測がプログラムを遅らせるわけではないことを理解することが重要です。欠落予測のコストは、分岐予測が存在せず、実行するコードを決定するために式の評価を待っているかのようになります(次の段落でさらに説明します)。

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

if-else\ switchステートメントがあるときはいつでも、式を評価してどのブロックを実行するかを決定する必要があります。コンパイラによって生成されたアセンブリコードには、条件branch命令が挿入されています。

分岐命令は、コンピュータに異なる命令シーケンスの実行を開始させ、命令を実行するデフォルト動作から逸脱することができる(すなわち、式が偽である場合、プログラムはifブロックのコードをスキップする)。私たちの場合の表現の評価。

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

視覚化:

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

パイプラインを洗い流すのは超高速ですが、今日ではこの賭けをする価値があります。並べ替えられたデータやゆっくりと変化するデータを予測することは、高速な変更を予測するよりも、常に簡単で良い。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------



これは分岐予測に関するものです。 それは何ですか?

  • 分岐予測子は、現代のアーキテクチャとの関連性を見いだす古典的な性能向上技術の1つです。単純な予測技法は、迅速な検索および電力効率を提供するが、それらは高い誤予測率を被る。

  • 一方、複雑な分岐予測(神経ベースまたは2レベル分岐予測のバリアント)は、予測精度は向上しますが、より多くの消費電力と複雑さが指数関数的に増加します。

  • これに加えて、複雑な予測技術では、ブランチを予測するのにかかる時間自体が2〜5サイクルと非常に高く、実際のブランチの実行時間に匹敵します。

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

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

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

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

無条件分岐 - これには、ジャンプ、プロシージャ呼び出し、および特定の条件のないリターンが含まれます。例えば、無条件ジャンプ命令はアセンブリ言語で単に「jmp」としてコード化され、命令ストリームはジャンプ命令によって指し示される目標位置に直ちに導かれなければならないが、「jmpne」として符号化され得る条件ジャンプは、前の「比較」命令における2つの値の比較の結果が値が等しくないことを示す場合にのみ、命令ストリームをリダイレクトする。 (x86アーキテクチャで使用されるセグメント化されたアドレッシングスキームは、ジャンプが "セグメント"内の "近く"またはセグメント外の "遠い"のいずれかになる可能性があるため、複雑さが増します。

静的/動的分岐予測:条件分岐が最初に発生したときに、マイクロプロセッサが静的分岐予測を使用し、条件分岐コードの後続実行のために動的分岐予測が使用される。

参考文献:




分岐予測が遅くなるという事実以外にも、ソートされた配列には別の利点があります。

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

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }



Related