3 ms·
Calling reserve alone is huge. vector has shrink_to_fit, so one can return memory, but doing a blanket 1-4kb reservation gets around a large number of the earl
by beached_whale 5y ago
Calling reserve alone is huge. vector has shrink_to_fit, so one can return memory, but doing a blanket 1-4kb reservation gets around a large number of the early reallocations and can result in significant improvements(in JSON parsing to user data stuctures I was seeing 25% from that alone). The cost is in the allocation call.
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.
- jeffbee 5y agoThat's what absl::InlinedVector does. It has internal space for N and if needed it reallocates. Brilliant if you can arrive at a reasonable N. https://github.com/abseil/abseil-cpp/blob/master/absl/container/inlined_vector.h https://github.com/abseil/abseil-cpp/blob/master/absl/contai...
- beached_whale 5y agoPMR is slightly different, the memory wouldn't exist in the vector itself but up the stack. InlinedVector looks like SBO used in string, pretty neat still. 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 )