c - 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 schema 构建一个缓存，使 I/O 性能更好。在其他人的问题中，我发现哈希表+双向链表是一种好方法。但是如何构建一个结构来以最好的方式改善我的问题呢？我计划构建 1300 个桶，每个桶都有一个最大大小为 10 的双向链表。那么它占用的总内存约为 13KB。实现和维护简单，但我认为效率不是最好的。

在我的统计中，一些字节偏移间隔的命中率较高，而某些间隔的命中率较低。我如何构建一个结构来调整我的统计数据？

而且当我搜索一个key的时候，我需要遍历整个列表，大小为10，有没有其他搜索效率更高的方法？

在一些移动平台上，更多的内存可以用于缓存，而其他平台则允许更少。我怎样才能让我的缓存适应允许的内存变化，除了改变桶的大小？

好像caf的方法比较好。使用一个大的双向链表和一个大的哈希表将键映射到节点条目更有意义，并且可以更多地利用 LRU。但是设计哈希函数正在成为一个难题。

等待您的建议，谢谢~

Answer 1

如果每个桶中最多只有 10 个条目，那么最好不要使用双向链表，而是让每个桶成为一个循环数组(只有 10 个条目和一个“列表顶部”索引)。

您最好放弃 10 路集合关联设计并使用直接映射缓存(您有一个更大的哈希表，每个桶只存储一个条目)。集合关联设计适用于硬件，您可以使用专用硬件并行进行 n 路比较，但不适用于软件(除非您有可以为此利用的 vector 单元)。

适应您的统计数据的一种方法是设计您的哈希函数，使其将不同大小的地址范围映射到每个存储桶，这样每个存储桶获得大致相等的访问频率。

改变哈希表的大小是另一种明显的缩放缓存大小的方法。