私は最近、補助バッファー ヒープのようなキャッシュを無視するデータ構造について読んでいます。これらのデータ構造は、最近アクセスされた要素をキャッシュ メモリに保持することで機能するため、その後のアクセスも高速になります。
これらのデータ構造のほとんどは、C/C++ などの低レベル言語で実装されています。これらのデータ構造を Python のような動的言語に移植する価値はありますか? それとも、仮想マシン上で実行するオーバーヘッドがこれらのデータ構造のパフォーマンス上の利点をすべて台無しにしますか? 後者のようですが、実際に使った経験のある方に聞いてみようと思いました。
C (または C++) では、各データ構造の正確なサイズをきめ細かく制御できます。また、ストレージの割り当てをきめ細かく制御することもできます。結局のところ、newメソッドを拡張したり、malloc直接使用したり、構造化メモリを使用して空間的局所性を作成したりできます。
ほとんどの動的言語 (Python など) では、正確なサイズを制御することはできません。ましてや、場所を制御することはできません。
Python では、一時的な局所性はあるかもしれませんが、空間的な局所性はほとんどまたはまったくありません。
一時的な局所性は、結果の単純なメモ化によって強化される可能性があります。これは非常に一般的な高速化であり、コア アルゴリズムからメモ化 (時間的局所性) を分離するためにメモ化デコレータを含めることがよくあります。
C または C++ のキャッシュ無視の実装が動的言語に変換されるとは思いません。十分な制御ができないからです。代わりに、スピードアップのためにメモ化を活用してください。
キャッシュを無視するアルゴリズムの主なポイントの1つは、オブジェクトのサイズは実際には重要ではないため（とにかく、次のレベルのメモリページングのサイズがわからないため）、正確なサイズを知ることができないことは重要ではありません。 。ある時点で、複数のオブジェクトのサイズが次のメモリブロックサイズに「適合」します。（注：オブジェクトのサイズがわからないことは、キャッシュ対応の実装にとって重大な問題です）。
さらに、ほとんどのVMメモリアロケータは、すべてのオブジェクトを同時に割り当てる限り、生成スペースの最後に割り当てます。残念ながら、一部のキャッシュ忘却アルゴリズムは、VMでは通常不可能なメモリレイアウトを変更できることを前提としています。
もう1つの大きな問題は、ほとんどのVMベースの実装がオブジェクトの参照を使用することです。したがって、3つの文字列を含むオブジェクトは、実際には4つのオブジェクト（オブジェクト自体と3つの文字列オブジェクト）です。これらの4つのオブジェクトが隣り合って割り当てられていない限り、アルゴリズムの分析は失敗します。
ガベージコレクターの圧縮やVMが自由に実行できるその他の「最適化」を追加すると、必要な制御とこれらのアルゴリズムに関する現在の研究状況との間に大きなギャップが生じます。