To benchmark this virtual_vec fairly against std::vector, you would need to call std::vector::reserve() with the intended number of items you intend to store in the vector before you start calling std::vector::push_back() in a tight loop.
[0] https://www.cplusplus.com/reference/vector/vector/reserve/
The unfortunate part, if I were to design a vector now for a standard, it would be std::pmr::vector or someting like it. The cost of a single allocation can be a little higher(extra pointer indirection) but the allocator is type erased. So that one can use a bump allocator or something else without changing the interfaces.
The real win for vector would be to use a local allocation or memory resource that calls into std::allocator after it is ehausted. I saw upwards of 50% improvement in some task with that. This was prior to reserving up front.
https://github.com/abseil/abseil-cpp/blob/master/absl/contai...
N is actually pretty simple here and doesn't need to be perfect. I have used 1-4kb / sizeof( T ) and it seems to work well. 4kb is an interesting number in that it is often the OS page size and it is what libc++ dequeue uses. But the memory that isn't used can be returned to the system and it costs about the same as sizeof( T )
I think the case for std::vector::reserve() is when you know you are about to add N elements via push_back(), you call reserve() with the appropriate size to ensure there is only one reallocation caused by that addition of N elements.
[0] https://www.cplusplus.com/reference/deque/deque/operator[]/
I was thrown for a bit of a loop working through virtual vs actual memory addresses and how this works under the hood, but it makes more sense now. In that case then virtual_vec would be better than std::deque in terms of iterating over the contained data in order.
MSVC allocates items in 16 byte chunks (as in, one allocation per item if sizeof(T) > 8). This will not change due to binary compatibility.
From a theoretical perspective I agree with you though - having chunked allocations is going to be significantly better, and using iterators instead of raw pointers you can also avoid any trouble that might result from non-contiguity (e.g. trying to subtract two pointers - it will work just fine using the iterators).
2. You want to avoid the risk of overflowing the stack.