2

これはおそらく言語に依存しませんが、私は C++ のバックグラウンドから質問しています。

組み込みシステム (AVR、8 ビット) 用のリング バッファを一緒にハッキングしています。仮定しましょう：

const uint8_t size = /* something > 0 */;
uint8_t buffer[size];
uint8_t write_pointer;

次のように、バッファが 2 のべき乗である場合に、効率的なブランチレス ロールオーバーを行うために&、書き込みポインタと読み取りポインタを ing する巧妙なトリックがあります。size-1size

// value = buffer[write_pointer];
write_pointer = (write_pointer+1) & (size-1);

ただし、サイズが 2 の累乗でない場合、フォールバックはおそらくポインター (つまりインデックス) とサイズの比較であり、条件付きリセットを行います。

// value = buffer[write_pointer];
if (++write_pointer == size) write_pointer ^= write_pointer;

リセットはめったに発生しないため、これはあらゆる分岐予測にとって簡単なはずです。

ただし、これは、ポインターがメモリ内で前方に進む必要があることを前提としています。sizeこれは直感的ですが、反復ごとにの負荷が必要です。通常のケースでは、順序を逆にする (後方に進む) と、より良い CPU 命令 (すなわち ) が生成されると思います。これは、リセット中にのみ必要になるためです。jump if not zerosize

// value = buffer[--write_pointer];
if (write_pointer == 0) write_pointer = size;

それで

TL;DR: 私の質問は次のとおりです:メモリを後方に移動すると、キャッシュ ミスが原因で実行時間に悪影響がありますか (メモリを単純に前方に読み取ることができないため)、またはこれは有効な最適化ですか?

4

4 に答える 4

0

メモリを逆行すると、キャッシュ ミスが原因で実行時間に悪影響がありますか (メモリは単純に前方に読み取ることができないため)。

なぜキャッシュミスが発生すると思いますか? キャッシュの外（順方向または逆方向）にアクセスしようとすると、キャッシュ ミスが発生します。

于 2013-06-15T22:29:31.403 に答える
0

明確化が必要な点がいくつかあります。

  1. そのサイズは毎回ロードする必要があります (これは const であるため、不変でなければなりません)。
  2. あなたのコードが正しいこと。たとえば、0 から始まるインデックス (C/C++ で配列アクセスに使用される) では、値0' is a valid pointer into the buffer, and the valuesize はそうではありません。xor同様に、単純に を割り当てることができる場合は必要ありません。同様0にモジュロ演算子が機能します ( writer_pointer = (write_pointer +1) % size)。
  3. 仮想メモリ (つまり、論理的に隣接するアドレスが実メモリ マップのいたるところにある可能性がある)、ページング (ページ単位でキャッシュされる可能性がある) およびその他の要因 (からの圧力) で一般的なケースで何が起こるか外部プロセス、割り込み)

要するに、これは、真のパフォーマンスの向上よりも、足に関連する怪我の増加につながるような最適化です。さらに、ベクトル化されたコード (SIMD) を使用すると、はるかに優れたゲインが得られることはほぼ確実です。

EDIT：そして、インタープリター言語またはJITされた言語では、およびその他の使用にまったく依存できると仮定するのは少し楽観的かもしれません。問題は、 と の比較と との比較JNZの間に実際にどれだけの違いがあるかということです。loading size0

于 2013-06-15T22:43:23.280 に答える
0

いつものように、手動でコードを最適化する場合は、特定のハードウェアに関する広範囲にわたる詳細な知識が必要です。それがない場合は、手動での最適化を試みるべきではありません。話の終わりです。

したがって、あなたの質問はさまざまな奇妙な仮定で満たされています。

  • まず、write_pointer = (write_pointer+1) & (size-1)投稿した XOR の例など、他のものよりも効率的であると想定します。ここで推測しているだけですが、コードを逆アセンブルして、どちらがより少ない CPU 命令を生成するかを確認する必要があります。

    なぜなら、小さなプリミティブな 8 ビット MCU のコードを記述する場合、コードを高速化するためにコアで行われることはあまりないからです。私は AVR8 を知りませんが、小さな命令パイプを持っている可能性が高いと思われます。分岐予測の邪魔になることはほとんどないようです。データおよび/または命令キャッシュがある可能性は非常に低いようです。フレンドリーな CPU コアのマニュアルをお読みください。

  • メモリを逆行することに関しては、プログラムのパフォーマンスにまったく影響を与える可能性はほとんどありません。古くてくだらないコンパイラでは、ループ条件が値ではなくゼロとの比較である場合、わずかに効率的なコードが得られます。最新のコンパイラでは、これは問題になりません。キャッシュ メモリの懸念については、キャッシュ メモリについて心配する必要はないと思います。

8 ビット MCU で効率的なコードを記述する最善の方法は、可能な限り 8 ビット演算に固執し、疫病のような 32 ビット演算を避けることです。そして、浮動小数点と呼ばれるものについて聞いたことがあることを忘れてください。これがプログラムを効率的にするものであり、手動でコードを最適化するより良い方法を見つけることはまずありません。

于 2013-06-17T06:51:03.060 に答える