Show HN: C++ virtual_vec vector implementation
github.com
github.com
The actual virtual address space on current x86-64 processors is only 48 bits[0], so unless I am mistaken, you can only create thousands (around 2^16), not billions.
[0] https://en.wikipedia.org/wiki/X86-64#Architectural_features
You can see this in how, at worse case, a hardware virtualized page table walk can take 20 memory accesses by my count if it completes without trapping, Host addresses will by definition all reference the same PML4, so that'll be cached, but everything else could have to go all the way out to DRAM. In practice the overhead of that is typically in the low single digit percentage range.
*ptr = T(std::forward<Args>(args)...)
That's an rvalue ref so std::move is superfluous. Not an assign
new (ptr) T; // default-initialization of T
*ptr = T(std::forward<Args>(args)...); // Constructs a new T, then calls operator=(T&&) on ptr, then destroys the T that got moved
new (ptr) T(std::forward<Args>(args)...) // Constructs directly on ptr
Is this too simplistic and this package is doing something else?
It's not obvious to me that it buys you much to reserve without committing. You're taking the hint, then ignoring it. Why bother? Why not just do nothing?r
$ ./1
allocating 4294967296 bytes
^Z
[1]+ Stopped ./1
$ grep -E VmSize\|RssAnon /proc/$!/status
VmSize: 4199804 kB
RssAnon: 144 kB ~ $ cat a.cpp
#include <vector>
int main() {
std::vector<int> v;
v.reserve(1ULL<<32);
}
~ $ g++ a.cpp
~ $ sudo sh -c 'echo 0 > /proc/sys/vm/overcommit_memory'
~ $ ./a.out
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
~ $ sudo sh -c 'echo 1 > /proc/sys/vm/overcommit_memory'
~ $ ./a.out
~ $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/
2. You want to avoid the risk of overflowing the stack.
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[]/
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).
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.
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 )