c - ビットフィールド: セット vs テストアンドセット (パフォーマンスのため)

Question

次のような C 構造体のインスタンスが多数あります。

struct mystruct
{
    /* ... */
    unsigned flag: 1;
    /* ... */
};

flag最初は 0 ですが、特定の関数の終了時には 1 でなければなりません。

最も簡単な実装は次のとおりです。

void set_flag(struct mystruct *sp)
{
    sp->flag = 1U;
}

しかし、代わりにこれを行うと、パフォーマンスにどのような影響が生じる可能性がありますか:

void set_flag(struct mystruct *sp)
{
    if (sp->flag == 0U)
    {
        sp->flag = 1U;
    }
}

メインメモリへの書き込みを避けたいと思っています。最初のバージョンは常に書き込みを行い、2 番目のバージョンはフラグがまだ設定されていない場合にのみ書き込みを実行しますが、ほとんどの場合、フラグは既に設定されています。

パフォーマンスに影響を与える可能性が高いその他の要因 (分岐予測など) は?

これまでのところ、わずかな速度の向上を見てきましたが、データセットが大きくなるにつれて、さらに重要になることを願っています。

この変更により、大規模なデータセットでプログラムが遅くなるリスクはありますか? もしそうなら、どのような状況でこれが起こる可能性がありますか?

score 10 · Accepted Answer

セット前のテストは違いを生みますが、その程度はユースケースによって異なります。

どちらの場合でも、データは最終的にキャッシュラインになります (たとえば、書き込みまたはテストアンドセット)。

ただし、キャッシュラインがダーティ (変更など) またはクリーンとしてタグ付けされている場合は違いがあります。汚れたキャッシュラインはメインメモリに書き戻す必要がありますが、クリーンなキャッシュラインは単に忘れられ、新しいデータで満たされる可能性があります。

ここで、コードが大量のデータを破壊し、データの各チャンクに 1 回か 2 回しかアクセスしないとします。その場合、メモリアクセスのほとんどがキャッシュミスであると想定できます。キャッシュミスが発生した時点でキャッシュラインの大部分がダーティであり、キャッシュラインの大部分がダーティである場合はどうなりますか?

新しいデータをラインにロードする前に、それらをメインメモリに書き戻す必要があります。これは、キャッシュラインの内容を単に忘れるよりも遅くなります。また、キャッシュとメインメモリ間のメモリ帯域幅が 2 倍になります。

最近のメモリは高速であるため、1 つの CPU コアでは違いがないかもしれませんが、別の CPU が (うまくいけば) 他の作業も行います。バスがキャッシュラインの出し入れで忙しくない場合は、他の CPU コアがすべてを少し速く実行することを確認できます。

要するに、キャッシュラインをきれいに保つことで、必要な帯域幅が半分になり、キャッシュミスが少し安くなります。

ブランチについて: 確かに: コストはかかりますが、キャッシュミスはさらに悪いことです! また、運が良ければ、CPU はアウトオブオーダー実行機能を使用して、ブランチのコストでキャッシュミスを相殺します。

このコードから可能な限り最高のパフォーマンスを得たい場合、およびほとんどのアクセスがキャッシュミスである場合は、次の 2 つのオプションがあります。

キャッシュをバイパスする: x86 アーキテクチャには、この目的のための非一時的なロードとストアがあります。これらは SSE 命令セットのどこかに隠され、組み込み関数を介して C 言語から使用できます。
(上級者向け): テストアンドセット関数を CMOV (条件付き移動) 命令を使用するアセンブラに置き換えるインラインアセンブラの一部の行を使用します。これにより、キャッシュラインがきれいに保たれるだけでなく、分岐が回避されます。現在、CMOV は低速の命令であり、分岐が予測できない場合にのみ分岐よりも優れています。したがって、コードのベンチマークをより適切に行うことができます。

score 3 · Accepted Answer

これは興味深い質問であり、キャッシュラインに関する Nils の回答は間違いなく優れたアドバイスです。

実際のパフォーマンスを測定するためにコードをプロファイリングすることの重要性を強調したいと思います。遭遇したデータでそのフラグがすでに設定されている頻度を測定できますか? 答えによってパフォーマンスが大きく変わる可能性があります。

楽しみのために、あなたのコードを使用して、さまざまな比率の 1 で満たされた 5000 万要素の配列で、set と test-then-set の比較を少し実行しました。グラフは次のとおりです。

_{(ソース: natekohl.net )}

もちろん、これは単なるおもちゃの例です。しかし、私が期待していなかった非線形のパフォーマンスに注意してください。また、配列がほぼ完全に 1 で満たされている場合、テスト後セットは通常のセットよりも高速になります。

score 2 · Accepted Answer

これらはあなたの要求に対する私の解釈です。

フラグを個別に初期化しています
一度だけ（1に）設定され、その後はリセットされません
ただし、このセットの試みは同じフラグで何度も行われます
そして、これらのフラグインスタンスがたくさんあります (それぞれに同じ種類の処理が必要です)。

仮定して、

スペースの最適化は、時間の最適化よりもかなり低く重み付けされています。

以下のことを提案します。

まず、32 ビットシステムでは、アクセス時間が心配な場合は 32 ビット整数を使用すると便利です。
フラグ 'word' のチェックをスキップすると、書き込みは非常に高速になります。ただし、まだ設定されていない場合はチェックして設定する非常に多くのフラグがある場合は、条件付きチェックを維持することをお勧めします。
ただし、プラットフォームが並列操作を行う場合 (たとえば、通常、コードの実行と並行してディスクへの書き込みを送信できる場合) は、チェックをスキップする価値があります。

score 1 · Accepted Answer

この最適化により、より大きなデータセットに移動しても速度が低下することはほとんどありません。

値を読み取るときのキャッシュのスラッシングは同じになり、分岐予測のペナルティも同じになります。これらは、ここで最適化するための重要な要素です。

分岐予測は分岐命令ごとに履歴を保存するため、異なるアドレスの命令 (インライン関数など) で分岐する限り、インスタンスの数は気にしません。単一の関数エンティティ (インライン化されていない) がある場合、すべてに対して 1 つの分岐命令があり、これにより分岐予測が抑制され、より頻繁に失敗し、ペナルティが増加します。

score 0 · Accepted Answer

いつでもプロファイリングできますが、最初のバージョンの方が高速で、あいまいさが少ないと確信しています。

score 0 · Accepted Answer

どちらのアプローチでも、データをキャッシュにロードする必要があるため、唯一の節約は読み取り/書き込みと書き込みの違いになります。

この変更により、より大きなデータセットでコードが遅くなる可能性があることはわかりません。そのため、その面では十分安全である可能性があります.

私には、時期尚早の楽観主義のようなにおいがします。(プロファイリングでこれがボトルネックであると特定された場合を除く)

パフォーマンスに関連するすべてのものと同様に、コード変更の効果を確認する最善の方法は、それを測定することです。大量のテストデータを比較的簡単に作成できるはずです。

score 0 · Accepted Answer

時間のパフォーマンスが本当に心配な場合は、フラグをビットフィールドではなく完全な int に変更してください。次に、設定は単なる書き込みであり、ビットフィールドのように読み書きではありません。

しかし、すでに指摘したように、これはマイクロ最適化のにおいがします。

score 0 · Accepted Answer

セット前のテストは意味がありません。テストのないコードはよりクリーンで、少し高速です。

補足として、関数呼び出しのオーバーヘッドは関数本体よりも大きいため、このような関数をインライン化することは理にかなっていますが、最適化コンパイラーは何も考えずに実行する必要があります。

c - ビット フィールド: セット vs テスト アンド セット (パフォーマンスのため)

9 に答える 9

Related

Reference

c - ビットフィールド: セット vs テストアンドセット (パフォーマンスのため)