为什么libc ++ std :: vector内部保存三个指针，而不是一个指针和两个大小？ [英] Why the libc++ std::vector internally keeps three pointers instead of one pointer and two sizes?

问题描述

我在看libc ++中的 std :: vector 的实现，我注意到它在内部保持三个指针（一个开始，一个结束，一个到分配的内存结尾），而不是我本能地做的，即一个指针指向开始和两个 size 和 capacity 成员。

I'm looking at the implementation of std::vector in libc++ and I noticed that it internally keeps three pointers (one to the begin, one the end, and one to the end of the allocated memory) instead of what I'd instinctively do, i.e., one pointer to the begin and two size and capacity members.

这里是来自libc ++的< vector> 对，我知道它的意思）。

Here is the code from libc++'s <vector> (ignore the compressed pair, I know what it means).

pointer                                    __begin_;
pointer                                    __end_;
__compressed_pair<pointer, allocator_type> __end_cap_;

我注意到其他标准库也是一样的（例如Visual C ++）。
我看不到任何特别的原因，为什么这个解决方案应该比另一个更快，但我可能是错误的。

I noticed that also other standard libraries do the same (e.g. Visual C++). I don't see any particular reason why this solution should be faster than the other one, but I might be wrong.

因此有一个特定的原因三指针解决方案比指针+大小优先？

So is there a particular reason the "three pointers" solution is preferred to the "pointer + sizes" one?

推荐答案

这是因为基本原理是性能应针对迭代器而非索引进行优化。 >
（换句话说，应优化 begin（） / end（） size（） / operator [] 。）

为什么？因为迭代器是广义指针，因此C ++鼓励它们的使用，反过来确保它们的性能与两个等效时的裸指针的性能相匹配。

It's because the rationale is that performance should be optimized for iterators, not indices.
(In other words, performance should be optimized for begin()/end(), not size()/operator[].)
Why? Because iterators are generalized pointers, and thus C++ encourages their use, and in return ensures that their performance matches those of raw pointers when the two are equivalent.

要了解为什么是性能问题，请注意 c>

To see why it's a performance issue, notice that the typical for loop is as follows:

for (It i = items.begin(); i != items.end(); ++i)
    ...

除了最不平常的情况，如果我们跟踪大小而不是指针，会发生什么是比较 i！ = items.end（）会变成 i！= items.begin（）+ items.size（） d期望。 （在许多情况下，优化器通常很难分解代码。）这在一个紧缩循环中显着减慢了事情，因此避免了这种设计。

Except in the most trivial cases, if we kept track of sizes instead of pointers, what would happen is that the comparison i != items.end() would turn into i != items.begin() + items.size(), taking more instructions than you'd expect. (The optimizer generally has a hard time factoring out the code in many cases.) This slows things down dramatically in a tight loop, and hence this design is avoided.

我已经验证这是一个性能问题，当尝试为 std :: vector 编写自己的替换。）

(I've verified this is a performance problem when trying to write my own replacement for std::vector.)

编辑：Yakk在评论中指出，使用索引而不是指针也会导致生成指令，当元素大小不是2的幂时，这是相当昂贵，并在一个严格的循环显而易见。我在写这个答案时没有想到这一点，但这是一个被我咬了的现象（例如，请参见此处）。 ..底线是，在一个紧的循环一切重要。

As Yakk pointed out in the comments, using indices instead of pointers can also result in the generation of a multiplication instruction when the element sizes aren't powers of 2, which is pretty expensive and noticeable in a tight loop. I didn't think of this when writing this answer, but it's a phenomenon that's bitten me before (e.g. see here)... bottom line is, in a tight loop everything matters.

这篇关于为什么libc ++ std :: vector内部保存三个指针，而不是一个指针和两个大小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！