非常に大きくなる可能性がある配列のコレクション（ an の最大値までのインデックスint）を含むアプリケーションがありますが、それらは遅延しています-それらの内容はその場で計算され、要求されるまで実際にはわかりません。配列も不変です。各配列の各要素の値は、プログラムの存続期間を通じて一定です。配列は、多くの場合、すべての配列要素の小さなサブセットのみが要求されるという意味で疎です (配列にはゼロの大きなブロックが含まれておらず、その意味で「疎」ではありません)。
配列要素を調べて (そしておそらくその過程で計算して) コストがかかる可能性があるため、キャッシュ レイヤーを追加したいと考えています。キャッシュは次のインターフェースを実装する必要があります。
void point_cache_store (gpointer data, gsize idx, gdouble value);
gdouble point_cache_fetch (gpointer data, gsize idx);
wheredataは、各配列の一意のハンドルとして機能します (これらは多数存在する可能性があります)。 に渡された引数をpoint_cache_fetch()同じ と の引数で返すか、特別な値を返すことでキャッシュ ミスを示す必要があります(呼び出し元がで呼び出すことはありません)。valuepoint_cache_store()dataidxDATUM_UNKNOWN_VALUEpoint_cache_storeDATUM_UNKNOWN_VALUE
問題は、どのように実装できpoint_cache_fetch()ますpoint_cache_store()か? (現在、これらは no-op スタブです。)
考慮すべき点:
- キャッシュの実装は、スレッドセーフである必要があります。複数のスレッドが同時に実行されており、これらのスレッドのいずれかがor引数を使用して
point_cache_store()orを呼び出すことができます。point_cache_fetch()dataidx - キャッシュは本当にキャッシュです。たとえその値を一度知っていたとしても、が
point_cache_fetch()を返すことは常に問題ありません。DATUM_UNKNOWN_VALUEその場合、呼び出し元は通常のルックアップを実行するだけです。 - 配列は不変であることを忘れないでください。与えられた
dataとidx引数に対して、呼び出し元は常に同じvalue引数を提供します。
これを行うには多くの方法があり、トレードオフが関係していることを認識しています。ただし、この質問については、1 つの非常に具体的な基準で回答を評価します。つまり、質問のきっかけとなったアプリケーションの特定のベンチマークでパフォーマンスが向上するかどうかです。さらに一歩進んで自分でベンチマークを実行したい場合は、次の方法で実行できます。
git clone git://github.com/gbenison/starparse
git clone git://github.com/gbenison/burrow-owl.git -b point-cache-base
関数point_cache_fetch()とpoint_cache_store()は「burrow/spectrum/point_cache.c」にあります。関連するベンチマークは「benchmarks/b_cache」です。