5 ms·
Show HN: C++ virtual_vec vector implementation
- Galanwe 5y agoThe README make it look like a vector with a reserve(4GB)
- _3u10 5y agoYes it reserves 4GB of virtual address space, it does not allocate 4GB of memory.
- banachtarski 5y agoAnd the title would clue you in that it’s a 4G virtual address reservation which isn’t the same thing
- nanidin 5y agostd::vector::push_back() has a documented complexity issue that occurs if a reallocation must occur as a result of the push (in order to grow the memory backing the vector). 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/ https://www.cplusplus.com/reference/vector/vector/reserve/
- _4r6j 5y agoIf you know the size of your data upfront this isn't applicable. Usually I use std::vector when I don't know how much data I have. If you already know the size why not avoid allocating on the heap altogether? I will update the README to be more clear.
- Cyph0n 5y ago1. You only know the size at runtime. 2. You want to avoid the risk of overflowing the stack.
- omegalulw 5y agoBecause you can't put arbitrarily large objects on the stack and unless your program is going to be using that memory for all of it's lifetime, it makes no sense to use static storage.
- ddlutz 5y agoYou have a large collection of large objects and don't want to allocate on the stack.
- _4r6j 5y agoyeah it's not any better in that case then. i updated README to reflect that.
- nanidin 5y agoIs there any benefit to using virtual_vec as opposed to a std::deque then? It guarantees constant time pushes to the back and constant time random element access via operator[][0]. 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[]/ https://www.cplusplus.com/reference/deque/deque/operator[]/
- 5y ago
- gary_0 5y ago> This implementation is hardcoded to use 4GB virtual address for each vector, so you can have billions of these per process. 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 https://en.wikipedia.org/wiki/X86-64#Architectural_features
- _4r6j 5y agogood catch will update
- moonchild 5y agoMoreover, the kernel generally takes the entire top half, so you actually only get 47 bits.
- gary_0 5y agoYou also have to account for any shared objects that might get mapped in, the executable data, the stack, and the heap. AFAIK, usually only the low 32 address bits are used for all that, leaving us with 46 bits.
- monocasa 5y agoSince Ice Lake, a 57bit virtual address space has been allowed, but the core piece of your comment absolutely still applies.
- judofyr 5y agoHow does this compare to just calling .reserve(4GB) on a regular std::vector?
- _4r6j 5y agoThat will actually allocate 4GB to your process, EDIT: OS dependent. This just reserves 4GB of virtual memory addresses.
- judofyr 5y agoI’ll have to admit that I don’t fully know how these things work, but my impression was that a malloc(4GB) on most systems will not actually allocate 4GB, but only acquire virtual memory and the OS will give it memory when it’s being used. Is this too simplistic and this package is doing something else?
- woodruffw 5y agoI haven't looked at this implementation yet, but your understanding is correct: reserving 4GB up-front with `std::vector` should only acquire virtual memory and not require an actual commitment, unless `std::vector` is doing something nuts internally like default-constructing each element that's been reserved. But I don't believe it does that.
- tom_ 5y agoI think you've got two sensible options in this case: commit, or do nothing. The standard's wording accommodates both: it's valid for a reserve to be a no-op, a situation the caller can detect (if they want to - assuming they even imagined anybody would ever do this! - I certainly never did, until now) by checking the new capacity. 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
- jeffbee 5y agoThat is incorrect. If I call std::vector<int>::reserve(1<<30) on Linux w/ GNU standard library, using the GNU default allocator, memory is lazily allocated: $ ./1 allocating 4294967296 bytes ^Z [1]+ Stopped ./1 $ grep -E VmSize\|RssAnon /proc/$!/status VmSize: 4199804 kB RssAnon: 144 kB
- Koshkin 5y agoThis is an example of the sensible use of a low-level, hardware-supported abstraction. (The practical computer science is about computers after all.)
- woodruffw 5y agoA small thing, but you're missing any sort of inclusion guard or pragma on `virtual_vec.h`. Adding one will prevent people from confusing themselves on multiple/transitive inclusions in the same translation unit.
- _4r6j 5y agoSomeone added one for me https://github.com/keur/virtual_vec/pull/1 https://github.com/keur/virtual_vec/pull/1 :)
- Matheus28 5y agoYour implementation is missing header guards. It's using placement new wrong in a lot of places (for example, your emplace_back calls the constructor, then the assignment operator). It isn't calling destructors on clear. It doesn't have a destructor (to call clear). Probably a couple more issues regarding the initialization/destruction of objects that need to be ironed out.
- deleted 5y ago[deleted]
- _4r6j 5y agoI believe you are talking about *ptr = T(std::forward<Args>(args)...) That's an rvalue ref so std::move is superfluous. Not an assign
- Matheus28 5y agoThis is how it's being done in one of the places: 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 I meant he should do the placement new like this: new (ptr) T(std::forward<Args>(args)...) // Constructs directly on ptr See https://godbolt.org/z/9nT94zxoE https://godbolt.org/z/9nT94zxoE
- Matheus28 5y agoAlso, your std::string tests happen to work because it's taking advantage of small string optimization, otherwise it'd leak memory and wouldn't pass valgrind.
- ant6n 5y agoIs there a way to tell the kernel to memmove large chunks of page-aligned memory by just changing the page table?
- murderfs 5y ago`mremap` with `MREMAP_FIXED`, but this consumes the original mapping. If you want to actually copy, this isn't possible without destroying the source (because modifications to the destination would be reflected in the source otherwise).
- deleted 5y ago[deleted]