使用限制大小的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比较，但软件并不那么多（除非您有一个可用于此目的的矢量单元）。

一来适应你的统计方法是设计你的哈希函数，使其大小不同的地址范围映射到每个桶，使得每个桶能存取的大致相等的频率。

更改散列表的大小是缩放高速缓存大小的另一个显而易见的方法。