4 ms·

std::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

std::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 ago
If 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 ago
  1. You only know the size at runtime. 2. You want to avoid the risk of overflowing the stack.
- omegalulw 5y ago
  Because 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 ago
  You have a large collection of large objects and don't want to allocate on the stack.
  - _4r6j 5y ago
    yeah it's not any better in that case then. i updated README to reflect that.
- nanidin 5y ago
  Is 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[]/
  - MauranKilom 5y ago
    std::dequeue is useless from a practical/portability perspective. 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).
    - beached_whale 5y ago
      libc++ uses 4kb
  - _4r6j 5y ago
    iterating over vectors (of trivial types that aren't pointers) is generally going to be faster since the memory is contiguous. deque is implemented with chunks i believe? loading in new chunk could be cache eviction.
    - nanidin 5y ago
      Aha, so the contiguity of the actual memory pages must not be what is used for prefetching by the MMU, instead it is the contiguity of the virtual address space? 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.
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 ago
  That'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 ago
    PMR 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 )

_4r6j 5y ago

If 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 ago
1. You only know the size at runtime. 2. You want to avoid the risk of overflowing the stack.
omegalulw 5y ago
Because 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 ago
You have a large collection of large objects and don't want to allocate on the stack.
- _4r6j 5y ago
  yeah it's not any better in that case then. i updated README to reflect that.
nanidin 5y ago
Is 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[]/
- MauranKilom 5y ago
  std::dequeue is useless from a practical/portability perspective. 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).
  - beached_whale 5y ago
    libc++ uses 4kb
- _4r6j 5y ago
  iterating over vectors (of trivial types that aren't pointers) is generally going to be faster since the memory is contiguous. deque is implemented with chunks i believe? loading in new chunk could be cache eviction.
  - nanidin 5y ago
    Aha, so the contiguity of the actual memory pages must not be what is used for prefetching by the MMU, instead it is the contiguity of the virtual address space? 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.

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 ago
That'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 ago
  PMR 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 )