使用限制大小的C中的LRU緩存設計

Question

我現在正在研究移動平臺中的內存非常小的軟件。在I/O瓶頸功能中，我需要使用seek操作從img文件中讀取一些字節（您可以假設seek比從memmry直接讀取的速度慢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性能更好。在其他人的問題中，我發現hashtable +雙向鏈表是一個好方法。但是，如何讓結構以最佳方式改善我的問題？我打算建立1300個桶，每個桶都擁有一個最大大小爲10的雙向鏈表。然後，總共需要13KB的內存。實施和維護很簡單，但我認爲效率並不是最好的。

在我的統計中，有些字節偏移間隔有更多的命中率而有些間隔更少。我如何建立一個結構來適應我的統計數據？

當我搜索一個密鑰時，我需要遍歷整個列表大小爲10.是否有任何其他方法的搜索效率更高？

在某些移動平臺上，可以使用更多的內存進行緩存，而其他平臺允許使用更少的內存。如何讓我的緩存適應允許的內存更改，除了更改桶的大小？

看來caf的方法更好。使用一個大的雙向鏈表和一個大的散列表將映射鍵映射到節點條目會更有意義，並可以更好地利用LRU。但是設計散列函數正在成爲一個難題。

我等待着您的建議，謝謝〜

Answer 1

如果你只打算最多有10個項目在每個桶，那麼你很可能會更好的分配與雙向鏈表並且讓每個桶成爲一個圓形數組（這只是10個條目和「列表頂部」索引）。

你甚至可以放棄10路組合關聯設計，並使用直接映射緩存（其中有一個更大的散列表，每個桶只存儲一個條目）進行更好。集合關聯設計在硬件方面非常好，您可以使用專用硬件並行執行n-way比較，但軟件並不那麼多（除非您有一個可用於此目的的矢量單元）。

一來適應你的統計方法是設計你的哈希函數，使其大小不同的地址範圍映射到每個桶，使得每個桶能存取的大致相等的頻率。

更改散列表的大小是縮放高速緩存大小的另一個顯而易見的方法。