Hacker News Reader

Comment by barrkel | Hacker News Reader

I doubt there are any vector implementations that don't use exponential growth. Without exponential growth, push_back doesn't have constant time, and adding n elements doesn't take O(n) time. Since push_back is required to take amortized constant time, an implementation without exponential growth (or some kind of magic) wouldn't be standard conforming.

Whether the exponential growth is in the form of doubling or not is just a constant factor. There's nothing magical about using powers of two. Depending on the accounting used by the allocator you're using, there may be synergies, or there might not be - some allocators require a few bytes more than the allocation request, and this requirement might inflate the underlying memory request more than necessary.

View on HN

> I doubt there are any vector implementations that don't use exponential growth.

Trivia fact time: Westwood Studios wrote their own vector implementation for the original Command&Conquer, and reused it for later games in the same series, until Renegade/Generals. That implementation uses linear growth, capacity grows by 10 elements each time.

Indeed; however that's not conforming to the standard, so it is not an implementation of std::vector ;)

But it is an implementation, albeit a non-standard one.

Whether the exponential growth is in the form of doubling or not is just a constant factor. There's nothing magical about using powers of two.

Actually, powers-of-two reduce memory fragmentation for all objects of the same size. Since memory fragmentation is one of the central causes of performance problems in modern large projects, it's really important. Firefox spent a bunch of time realizing their performance problems were due to an incredible amount of fragmentation.

Exponential growth gives you most of the benefit, but specifically growing by a factor of 2 gives you the rest.

You're not saying anything I don't already know.

If the overhead of an allocation is h bytes, and your allocator stores it in e.g. the prefix of the memory allocation, then all your allocations will be for 2x+h. And this will not have nice effects for your memory fragmentation. In this case, you'd be better off allocating 2x-h each time.

Of course, modern allocators tend to store accounting information using separately reserved arrays of records to avoid exactly this problem. But if you use a language like C# or Java, you come back to around to this problem. Without using a double indirection for array data, object header and array length are stored contiguously with array data. So allocating an array with a power of two will again not be a power of two for the underlying allocator. Much less of a problem with precise GC, but not all GC'd languages use precise moving GC, and some languages let you pin arrays for interop with C. So it's something to be aware of.

Reply on news.ycombinator.com