我最近一直在阅读有关缓存遗忘的数据结构，例如辅助缓冲区堆。这些数据结构通过将最近访问的元素保存在高速缓存中来工作，因此任何后续访问也更快。
这些数据结构中的大多数都是用 C/C++ 等低级语言实现的。尝试将这些数据结构移植到像 Python 这样的动态语言是否值得，或者在虚拟机上运行的开销是否会破坏这些数据结构的所有性能优势？似乎是后者，但我想我会问是否有人真的有这方面的经验。
问问题
661 次
2 回答
2
在 C（或 C++）中，您可以对每个数据结构的确切大小进行细粒度控制。您还可以对存储分配进行细粒度控制。毕竟，您可以扩展该new方法，malloc直接使用或以其他方式构建内存来创建空间局部性。
在大多数动态语言（如 Python）中，您根本无法控制任何东西的确切大小，更不用说它的位置了。
在 Python 中，您可能有一些时间局部性，但您几乎没有或没有空间局部性。
时间局部性可以通过简单的结果记忆来增强。这是一种常见的加速方式，人们通常会包含一个 memoization 装饰器，以将 memoization（时间局部性）与核心算法分离。
我不认为 C 或 C++ 缓存遗忘实现转换为动态语言，因为我认为您没有足够的控制权。相反，只需利用记忆化来加速。
于 2010-01-22T14:37:26.613 回答
1
缓存遗忘算法的一大要点是对象的大小并不重要（因为无论如何你都不知道下一级内存分页的大小），因此无法知道确切的大小并不重要. 在某些时候，超过 1 个对象的大小“适合”到下一个内存块大小。（注意：不知道对象的大小是缓存感知实现的一个重要问题）。
此外，大多数 VM 内存分配器将在生成空间结束时分配，因此只要您同时分配所有对象，就可以开始。不幸的是，一些缓存遗忘算法假设您可以更改内存布局，这对于 VM 来说通常是不可能的。
另一个大问题是大多数基于 VM 的实现都使用对象引用。所以一个包含三个字符串的对象实际上是 4 个对象（对象本身和 3 个字符串对象）。除非这四个对象彼此相邻分配，否则算法的分析就会失败。
添加压缩垃圾收集器和 VM 可以自由执行的其他“优化”，您需要的控制与这些算法的当前研究状态之间存在很大差距。
于 2010-07-16T19:09:09.280 回答