5 ms·

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 memo

by Arcuru 3y ago

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.

asvitkine 3y ago
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...
- mike_hock 3y ago
  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.
delusional 3y ago
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)
nroets 3y ago
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.
Kranar 3y ago
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.
- malkia 3y ago
  On windows you can do this with RESERVE, e.g. MEM_RESERVE from https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc 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.

by Arcuru 3y ago

asvitkine 3y ago

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...

mike_hock 3y ago
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.

delusional 3y ago

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)

nroets 3y ago

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.

Kranar 3y ago

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.

malkia 3y ago
On windows you can do this with RESERVE, e.g. MEM_RESERVE from https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc 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.