0

u_int64[8]C/C++ で2 つの配列を比較する最速の方法は何ですか?

配列 1 はstd::vector(~10k 要素) 内にあり、配列 2 は動的に割り当てられた構造体内にあります。（memcmp()ここで誤検知は無料ですか？）

私の（疑似C）実装：

typedef struct {            
    u_int64_t array[8];
}work_t;

/* alloc and fill array work_t* work = new (std::nothrow) work_t etc... */

for(u_int32_t i=0; i < some_std_vector.size(); i++) {       

                if((some_std_vector[i]->array[0] == work->array[0]) &&
                   (some_std_vector[i]->array[1] == work->array[1]) &&
                   (some_std_vector[i]->array[2] == work->array[2]) &&
                   (some_std_vector[i]->array[3] == work->array[3]) &&
                   (some_std_vector[i]->array[4] == work->array[4]) &&
                   (some_std_vector[i]->array[5] == work->array[5]) &&
                   (some_std_vector[i]->array[6] == work->array[6]) &&
                   (some_std_vector[i]->array[7] == work->array[7])) {
                    //...do some stuff...
                }
}

ターゲット プラットフォームは Linux x86_64 gcc 4.9.2 で、ループは 内にありpthread、tcmallocが使用され、コードは -O2 でコンパイルされます。

4

4 に答える 4

1

この質問に真に答える唯一の方法は、提供されたループを使用するルーチンと memcmp を使用するルーチンの 2 つを作成することだと思います。次に、逆アセンブリを分析して見て、最も効率的であるように見えるものを確認します。(執着してプロファイラーを使用することもできます。)

また、それらを直接比較するカスタム ルーチンをアセンブリに記述し (つまり、見ているものを正確に比較するために特別に機能する memcmp のカスタム バージョン)、それを他の 2 つと一緒に比較することもできます。

いずれにせよ、すべてがおそらくかなり近いものになるだろうという他の人たちに同意します（最新のコンパイラーを使用）。ただし、本当にそれについて保持したい場合は、プロファイラーでテストするか、作成されたアセンブリを見て、どちらがより高速かを視覚的に知るスキルを持っている必要があります。

于 2014-12-05T13:24:29.107 に答える
1

速度を改善するためのいくつかの提案を次に示します。

可能であればローカル変数を使用する

-> 演算子などのポインターを使用する代わりに、ローカル変数を使用するか、変数を参照として渡します。コンパイラーは、ポインターをレジスターにロードし、レジスターを逆参照して値を取得するための追加のコードを生成する場合があります。

プロセッサのデータ キャッシュを使用する 最近のほとんどのプロセッサにはデータ キャッシュがあります。いくつかの変数にデータをロードして比較できる場合は、プロセッサのデータ キャッシュを呼び出すことができます。

また、データ キャッシュ ラインに効率的に収まるようにデータを設計します。これは、データ メンバー (配列を含む) が互いに隣り合っているか、非常に接近している必要があることを意味します。

ブロック比較

最低レベルでは、多くの連続したバイトを比較しています。他の人が述べたように、メモリ比較機能を使用するとパフォーマンスが向上する場合があります。

もう 1 つの提案は、値を個別の変数にロードして値を比較することにより、コンパイラーを支援することです。

for (/*...*/)
{
//...
    uint64_t a1 = some_std_vector[i]->array[0];
    uint64_t a2 = some_std_vector[i]->array[1];
    uint64_t a3 = some_std_vector[i]->array[2];
    uint64_t a4 = some_std_vector[i]->array[3];

    uint64_t b1 = work->array[0];
    uint64_t b2 = work->array[1];
    uint64_t b3 = work->array[2];
    uint64_t b4 = work->array[3];

    if ((a1 == b1) && (a2 == b2) && (a3 == b3) && (a4 == b4))
    {
       //...
    }
}

ここでの概念は、最初に変数を複数のレジスタにロードしてから、レジスタを比較することです。

アセンブリ言語とプロファイルの確認

回答に示されているすべての手法を使用して、最善の方法は、コードを作成し、アセンブリ言語とプロファイルを確認することです。速度を上げるために、最適化レベルを高く設定することを忘れないでください。

プロセスにこれを高速化できる特別な命令がある場合は、コンパイラがそれらを使用していること、またはそれらを使用しない正当な理由があることを確認する必要があります。

于 2014-12-05T15:30:12.077 に答える
0

使用しているデバイスと使用しているコンパイラに応じて、いくつかの「特定の」問題を試すことができます。たとえば、一部のコンパイラには、メモリからのワイド ロードを実行できる手法があり、その結果として最速の多重比較が行われます。また、ループを手動でアンロールする方法もあるため、より高速に実行できます。しかし、それはコンパイラに依存します。いつでもいくつかの方法を試し、アセンブラー コードをチェックして、どの方法が最速かを確認できます。

于 2014-12-05T13:22:32.877 に答える
0

いくつかのテストを行い、gcc memcmp、glibc memcmp、および上記のコードを調べました。glibc-2.20 memcmp は、プラットフォーム固有の最適化を使用するため (私の場合)、fastes の方法です。

gcc memcmp はかなり遅いです。(バグ 43052、-fno-builtin-memcmp でコンパイル)

于 2014-12-08T08:42:22.240 に答える