Ropes：什么“足够大以从缓存效应中受益”？
来自维基百科：
主要缺点比较大 整体空间使用率较慢 索引，两者都变得更加 随着树结构变得严重 更大更深。然而，许多 索引的实际应用 仅涉及迭代 字符串，只要 叶节点足够大 受益于缓存效果。
我正在绳索和绳子之间实现某种折衷。基本上它只是绳索，除了当连接的字符串很短时我将连接对象压平为字符串。这样做有几个原因：
- 当连接的字符串很短时（以正常形式连接两个字符串不需要太长时间），连接对象的好处很小。
- 这样做可以减少树的大小/深度（减少绳索的缺点）。
- 这样做会增加叶节点的大小（以更好地利用缓存）。
然而，随着长度变长，绳索的优势也会减少，所以我想找到一些折衷方案。从逻辑上讲，“最佳点”似乎位于“叶节点足够大以从缓存效应中受益”的地方。问题是，我不知道它有多大。
编辑：当我写这篇文章时，我想到理想的大小是缓存页面的大小，因为这样绳索只会在字符串中发生缓存未命中时导致缓存未命中。所以我的第二个问题是，这个推理正确吗？有没有跨平台的方法来检测缓存页面的大小？
我的目标语言是C++。
From 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.
I'm implementing a sort of compromise between ropes and strings. Basically it's just ropes, except that I'm flattening concatenation objects into strings when the concatenated strings are short. There are a few reasons for this:
- The benefits of concatenation objects are minimal when the concatenated strings are short (it doesn't take too long to concatenate two strings in their normal form).
- Doing this reduces the largeness/depth of the tree (reducing the downsides of ropes).
- Doing this increases the size of the leaf nodes (to take better advantage of cache).
However, as length gets longer, the advantages of the ropes also decrease, so I'd like to find some compromise. The "sweet spot" logically seems to be around where "the leaf nodes are large enough to benefit from cache effects". The problem is, I don't know how large that is.
EDIT: While I was writing this, it occurred to me that the ideal size would be the size of a cache page, because then the rope only causes cache misses when they would happen anyway in a string. So my second question is, is this reasoning correct? And is there a cross-platform way to detect the size of a cache page?
My target language is C++.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
绳状字符串的极限情况将构建在
std::list之上。这显然不是很有效。迭代时，每个“叶子”/字符可能有一次缓存未命中。随着每个叶子的字符数增加，平均未命中数会下降，一旦叶子分配超过单个缓存行，就会出现不连续性。拥有更大的叶子可能仍然是个好主意；缓存层次结构中的内存传输可能在不同级别具有不同的粒度。此外，当针对一组混合 CPU（即消费者 PC）时，叶子大小（2 的较高幂）将是更多机器上高速缓存行大小的整数倍。例如，如果您要使用 16 和 32 字节高速缓存行来寻址 CPU，则 32 字节将是更好的选择，因为它始终是整数数量的高速缓存行。浪费半个缓存行是一种耻辱。
The limit case for a rope-like string would be built on top of a
std::list<char>. That obviously isn't very effective. When iterating, you are likely to have have one cache miss per "leaf"/char. As the number of characters per leaf goes up, the average number of misses goes down, with a discontinuity as soon as your leaf allocation exceeds a single cache line.It might still be a good idea to have larger leafs; memory transfers in cache hierarchies might have different granularities at different levels. Also, when targetting a mixed set of CPUs (i.e. consumer PCs) a leaf size which is a higher power of two will be an integral multiple of the cache line size on more machines. E.g. if you're addressing CPUs with 16 and 32 byte cache lines, 32 bytes would be the better choice, as it's an always integral number of cache lines. Wasting half a cache line is a shame.