0

バイナリ検索アルゴリズムの glibc の実装をコピーし、必要に応じて少し変更しました。私はそれをテストし、GCC について学んだ他のこと (属性と組み込み) をテストすることにしました。コードは次のようになります。

int main() {
  uint_fast16_t a[61] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 };
  uint64_t t1 = Time(0);
  for(register uint_fast16_t i = 0; i < 10000000; ++i) {
    binary_search(rand() % 62, a, 61);
  }
  printf("%ld\n", Time(0) - t1);
  return 0;
}

さて、このプログラムは問題なく動作します。たとえば、次のようなコード行を追加すると、問題が発生します。

uint_fast16_t a[61] __attribute__ ((aligned (64) )) = /* ... */

この場合、より高速なコードが期待できますが、複数のテスト (数十回のテスト) の後でもパフォーマンスは変わりませんでした。また、プログラムを 8 と 1 の位置合わせでテストしましたが、変更はありませんでした。タイプサイズよりも小さいアラインメントを使用しているため（私の場合、64ビットマシンではuint_fast16_tは8バイトです）、gccがエラー/警告をスローすることさえ期待していましたが、何もありませんでした。次に、キャッシングを追加する別の変更 (GCC 9 で導入)。for ループの前に次のコードを追加しました。

caches(a, uint_fast16_t, uint_fast16_t, 61, 0, 3);
// where "caches" is:
#define caches(x, type, data_type, size, rw, l) ({ \
  for(type Q2W0 = 0; Q2W0 < size; Q2W0 += 64 / sizeof(data_type)) { \
    __builtin_prefetch(x + Q2W0, rw, l); \
  } \
})

性能も変わらない。CPU が最初に配列を自動的にキャッシュしている可能性があることがわかったbinary_searchので、ループを排除しfor、キャッシュ ラインの有無にかかわらず再度数回測定しましたが、パフォーマンスの変化にも気づいていません。
詳しくは：

  1. CentOS8 64bit 最新カーネルを使用
  2. GCC 9.2.1 20191120 の使用
  3. でコンパイル、コンパイル-O3 -Wall -pthread -lanl -Wno-missing-braces -Wmissing-field-initializers中にエラー/警告なし
  4. 物事は最適化されていません（チェックされたasm出力）

私は何かを知らないと確信しています/私は何か間違ったことをしています。

完全なコードはこちらから入手できます。

4

1 に答える 1

1

  • register uint_fast16_t時期尚早の最適化です。どの変数をレジスターに配置するかをコンパイラーに決定させます。registerほとんど時代遅れのキーワードと見なしてください。

  • コメントに記載されているようにuint_fast16_t i = 0; i < 10000000、バグまたは悪い習慣です。代わりに、おそらく次のようにする必要があります。

    const uint_fast16_t MAX = 10000000; 
... i < MAX

    この場合、値が適合しない場合、初期化時にコンパイラ エラーが発生するはずです。または、静的アサーションで値を確認してください。

    さらに良いことsize_tに、この場合は for ループ イテレータを使用します。

  • __attribute__ ((aligned (64) ))「この場合、より高速なコードが期待できます」

    なんで？そもそも配列がずれていたと思われる理由は何ですか? コンパイラは、変数の位置合わせを誤って行うことはありません。特に、配列メンバーが次のように宣言されている場合はそうではありませんuint_fastnn-使用の全体的なポイントuint_fast16_tは、実際には正しい配置を取得することです。

    .quadこの場合、配列は x86/64 の gcc と clang の両方になり、一連のアセンブラー命令を吐き出し、完全に整列されたデータになります。

  • キャッシュ コマンドに関しては、私はそれらがどのように機能するかをほとんど知りません。ただし、この場合、すでに理想的なデータ キャッシュ パフォーマンスが得られている可能性があります。アレイはデータ キャッシュ内にある必要があります。

    命令キャッシュに関しては、その性質上大量の分岐が伴うバイナリ検索では、あまり効果がありません。場合によっては、まさにこの理由から、力ずくの線形検索が二分検索よりも優れていることがあります。ベンチマークして見てください。(そして、ブルート フォースが二分探索よりもはるかに高速であることが判明した場合は、古いコンピューター サイエンス アルゴリズムの先生に大きな O をぶつけてください。)

  • rand() % 62ボトルネックになる場合とそうでない場合があります。システムによっては、rand 関数とモジュラスの両方が多くのオーバーヘッドを意味する可能性があります。

于 2020-11-26T15:11:55.897 に答える