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 字节将是更好的选择，因为它始终是整数的高速缓存行。浪费半个缓存行是一种耻辱。