缓存二叉树的局部性

Question

如果我有一棵如下的树

struct tree_t {
    //data
    tree_t *left;
    tree_t *right;
};

我想开始为叶子分配内存,有没有办法确保当我遍历树时,叶子被缓存？如果我使用的是malloc,那么我认为叶子会分散在堆中,每次尝试访问时都会出现缓存未命中.

Answer 1

其他人给出了正确的答案,一个固定大小的池(https://en.wikipedia.org/wiki/Memory_pool),但还有一些额外的警告需要更全面的解释.使用内存池分配的叶子仍然可能或甚至可能具有低缓存命中率.在64字节边界上对齐的8*n tree_t块是理想的,尽管在n == 1024之上没有任何好处.

作为旁注,请查看Judy数组,这是一种缓存优化的树状数据结构(https://en.wikipedia.org/wiki/Judy_array).

(简要地)查看缓存如何工作是有帮助的.高速缓存分为多组固定大小的行.通常,线路大小在L1中为64字节; 英特尔和AMD已经使用64字节L1缓存15年,现代ARM处理器(如A15)也使用64字节线.关联性确定对应于一组的行数.当数据进入缓存时,某些函数会将地址哈希到集合中.数据可以存储在集合中的任何行中.例如,在双向组关联高速缓存中,任何给定地址都可以存储在两个可能的高速缓存行之一中.

最大化可缓存性涉及减少缓存行提取:
1.将数据组织到缓存行大小的块中.
2.在高速缓存行边界上对齐块.
3.在映射到不同缓存集的地址处分配块.
4.在同一缓存行中存储具有时间局部性(即,大约在同一时间访问)的数据.
5.如果可能,减小数据大小以增加密度.

如果您不执行(1),则提取将引入附近的,可能无用的数据,从而减少您关注的数据的空间量.如果你不这样做(2),那么你的对象可能跨越缓存行,需要两倍的提取.如果不执行(3),则某些缓存集可能未得到充分利用,效果与(1)类似.如果你不这样做(4),那么即使你最大化缓存利用率,大多数提取的数据在没有用时它被取出,并且在数据变得有用之前该行可能被逐出.(5)通过将它们打包到更小的空间中来增加适合缓存的对象的数量.例如,如果您可以保证少于2 ^ 32个叶子,那么您可以将uint32_t索引存储到tree_t []数组而不是指针中,这在64位平台上是100%的改进.

注意: malloc()通常返回8字节或16字节对齐的块,这些块不合适; 在GCC上使用posix_memalign()或在MSVC上使用_aligned_malloc().

在你的情况下,你正在遍历一棵树,大概是一个有序的遍历.除非您的数据集适合缓存,否则叶子可能会均匀分布,并且ergo不太可能在同一缓存行中具有节点的时间局部性.在这种情况下,您可以做的最好的事情是通过分配缓存行大小和缓存行对齐的块来确保您的对象不跨越缓存行.

我在64字节高速缓存行和4字节指针的保守假设下选择了8*n tree_t的块,这导致8字节的tree_t和64/8 = 8 tree_t/line.n == 1024的上限是由于特定的x86 CPU(此时它逃脱了我)忽略了地址的第18位以便选择一个集合.