c++ - 绳索:什么是 "large enough to benefit from cache effects"？

Question

来自 Wikipedia :

The main disadvantages are greater overall space usage and slower indexing, both of which become more severe as the tree structure becomes larger and deeper. However, many practical applications of indexing involve only iteration over the string, which remains fast as long as the leaf nodes are large enough to benefit from cache effects.

我正在绳索和弦之间实现一种折衷。基本上它只是绳索，除了当连接的字符串很短时我将连接对象展平成字符串。这有几个原因:

1. 当连接的字符串很短时，连接对象的好处微乎其微(以正常形式连接两个字符串不会花费太长时间)。
2. 这样做可以减少树的大小/深度(减少绳索的缺点)。
3. 这样做会增加叶节点的大小(以更好地利用缓存)。

但是，随着长度变长，绳索的优势也会降低，所以我想找到一些折衷方案。 “最佳点”在逻辑上似乎是在“叶节点足够大以从缓存效应中受益”的地方。问题是，我不知道它有多大。

编辑:当我写这篇文章时，我突然想到理想的大小应该是缓存页面的大小，因为这样绳索只会导致缓存未命中，而它们无论如何都会在字符串中发生。所以我的第二个问题是，这个推理是否正确？是否有跨平台的方法来检测缓存页面的大小？

我的目标语言是 C++。

Answer 1

绳状字符串的极限情况将建立在 std::list<char> 之上.这显然不是很有效。迭代时，每个“叶”/字符可能有一个缓存未命中。随着每片叶子的字符数增加，平均未命中数下降，一旦您的叶子分配超过单个缓存行，就会出现中断。

拥有更大的叶子可能仍然是个好主意；缓存层次结构中的内存传输可能在不同级别具有不同的粒度。此外，当针对混合的 CPU 集(即消费者 PC)时，叶大小是 2 的更高次幂将是更多机器上缓存行大小的整数倍。例如。如果您使用 16 字节和 32 字节高速缓存行对 CPU 进行寻址，则 32 字节将是更好的选择，因为它始终是整数个高速缓存行。浪费半个缓存行是一种耻辱。