現在、メモリが非常に少ないモバイルプラットフォームのソフトウェアに取り組んでいます。I/O ボトルネック関数では、シーク操作を使用して img ファイルから数バイトを読み取る必要があります (シークは、メモリから直接読み取るよりも約 10 倍遅いと想定できます)。私のテストでは、この関数は 7480325 回呼び出され、bytes_offset 6800 から 130000 までのバイトを読み取るため、すべてのバイトは平均で 100 回読み取られます (3 ～ 4 回読み取られるバイトもあれば、1000 回以上読み取られるバイトもあります)。
以下は私の統計です。
bytes offset 6800 ~ 6900: 170884 times
bytes offset 6900 ~ 7000: 220944 times
bytes offset 7000 ~ 7100: 24216 times
bytes offset 7100 ~ 7200: 9576 times
bytes offset 7200 ~ 7300: 14813 times
bytes offset 7300 ~ 7400: 22109 times
bytes offset 7400 ~ 7500: 19748 times
bytes offset 7500 ~ 7600: 43110 times
bytes offset 7600 ~ 7700: 157976 times
...
bytes offset 121200 ~ 121300: 1514 times
bytes offset 121300 ~ 121400: 802 times
bytes offset 121400 ~ 121500: 606 times
bytes offset 121500 ~ 121600: 444 times
bytes offset 121600 ~ 121700: 398 times
max_bytes_offset 121703
min_bytes_offset 6848
次に、LRU スキーマを使用してキャッシュを構築し、I/O パフォーマンスを向上させたいと考えています。他の人の質問では、ハッシュテーブル + 二重リンク リストが良い方法だと思います。しかし、私の問題を最善の方法で改善するための構造を作るにはどうすればよいでしょうか? 1300 個のバケットを作成する予定で、すべてのバケットが最大サイズ 10 の二重リンク リストを所有しています。この場合、必要な合計メモリは約 13KB です。実装と保守は簡単ですが、効率は最高ではないと思います。
私の統計では、一部のバイト オフセット間隔ではヒット率が高く、一部の間隔ではヒット率が低くなります。統計を適応させるための構造を構築するにはどうすればよいですか?
また、キーを検索するときは、サイズ 10 のリスト全体をトラバーサルする必要があります。検索効率の高い方法は他にありますか?
一部のモバイル プラットフォームではキャッシュにより多くのメモリを使用できますが、他のプラットフォームではより少ないメモリを使用できます。バケットのサイズを変更する以外に、許可されたメモリの変更をキャッシュに適応させるにはどうすればよいですか?
cafの方法の方が良さそうです。大きな二重リンク リストと、キーをノード エントリにマッピングする大きなハッシュ テーブルを使用することは、より理にかなっていて、LRU をより活用できます。しかし、ハッシュ関数の設計は難しい問題になりつつあります。
あなたの提案を待っています、ありがとう〜