data-structures - 有人可以从 Judy 数据结构文档中解释这一行吗？

Question

http://judy.sourceforge.net/downloads/10minutes.htm

问题——为什么只需要 4 个缓存行填充？这些天缓存行不是 64 字节吗？

对于 2^32（或 256^4）的扩展，对于最坏情况的高度填充的 256 进制数字树访问，最多需要 4 个缓存行填充。在 2^64（或 256^8）的范围内，8 个缓存行填充将是最坏的情况。在实践中，朱迪做得比这要好得多。原因（部分）是由于密钥的“密度”很少是“大多数”子扩展中的最低可能数字。增加朱迪树的深度需要高密度和高人口。解释原因需要很长时间。简短的版本是与沙子的类比。建造一个高大的沙堆需要大量的沙子，特别是如果它需要 256 个沙粒来支撑上面的 1 个沙粒。在 64 位 Judy 中，它可能需要比地球上现有的更多的 RAM 才能使其具有 8 个级别。

标签： data-structuresjudy-array

Answer 1

It's a 256-ary tree, so to traverse down to a single item in a densely populated tree with 32-bit keys, you need to descend log₂₅₆(2³²) = 4 levels.

To do that in 4 cache line fills, you need each 256-ary internal node, including encoded pointers to its 256 children, to fit into a single cache line. A cache line is only 512 bits, so that's pretty impressive.