STL: The Vector | Hacker News Reader

STL: The Vector

devblogs.microsoft.com

42 pointssigna119 comments

I think the most interesting part about Vector implementations is that some impls never actually copy data around on a push. They just use the huge virtual memory space to be initially allocated in an empty area and then just grow in place, requesting new physical pages as necessary.

The CS101 explanation of a Vector that copies values around whenever it exceeds its capacity is incorrect in many cases.

When I worked on perf at Windows, I vaguely recall someone telling me that the Windows impl doesn't do that for some reason. I'm curious if Raymond will cover why.

This is extra cute when you realize that such a vector is basically a 2 level array (first level is a static array of likesized pages, which are themselves arrays of the likesized items) where the first pointer deref is hardware accelerated. By lazily allocating the pages from the outer array we end up with a dynamically growing array constructed of only statically sized arrays. The tiny tradoff is that our array now statically grows in proportion to its max size (although this will probably be in kernel memory if we are using the page table)

That's interesting, but wouldn't that require each vector to take up a minimum of a page of memory?

I mean, I guess you can put them near the end of pages already occupied by other things, though then you need more knowledge/control of other memory allocations in the program...

It would be possible to get small capacities from malloc and then switch to mmap once the capacity has grown to page size and try to extend the mapping with MAP_FIXED_NOREPLACE. The downside is that if the mapping can't be contiguously extended, it's a wasted syscall, but I can't imagine that it wouldn't be worth it in a 48-bit "64-bit" address space.

Don't see what is incorrect. What you're talking about is taking advantage of a feature mostly unique to Linux (memory overcommit, not supported on Windows or most other OSs) to construct a vector whose capacity is some really large value so as to never need to perform a reallocation for a given data set.

In practice it is very common for C++ developers to preallocate a region of memory upfront that is large enough to handle their dataset without having to go to such an extreme and non-portable length.

None of this contradicts the CS101 explanation, preallocating memory is entirely consistent with the fundamental understanding of how dynamic arrays work.

On windows you can do this with RESERVE, e.g. MEM_RESERVE from https://learn.microsoft.com/en-us/windows/win32/api/memoryap... - For example when you have a callstack (on Windows), it can reserve (say) 1MB of contigous space, but then only "commit" some parts of it, and the tail (head?) be sort of guard page, in order to "commit" more from the reserve.

Now getting commit from reserve might fail, as you've mentioned because Windows does not overcommit, but it's possible to a degree.

I guess same with really large vector can be done.

The CS101 implementation of a Vector is that the data is only moved when the size of the vector reaches k*a^n where n is an integer and a is usually 2.

Then the time it takes to move the vector to a new location is amortized as the vector grows. Then push() takes constant time.

So the CS101 is optimal for the study of computer science.

Something that I need to remind myself often about why is that so: "In particular, the language forbids a “small vector optimization” analogous to the small string optimization (which we’ll see soon), because the standard requires that¹ moving a vector not invalidate iterators or references. The vector elements have to remain where they are. A small-vector optimization would put them in vector-internal storage, which would require that the element move from one vector to another on a vector move operation, which is not allowed."

Someone did a nice trick long time ago the other way around using std::basic_string with say... float or custom structure - for the benefit of "small vector optimization"

The implementation described looks so simple and reasonable; it is surprising what c++ actually ended up with, which is basically the type from the OP except that std::vector<bool> behaves incompatibility from every other vector and a std::vector<char> is slower than any other non-bool vector in mysterious ways.

Reply on news.ycombinator.com