Constvector: Log-structured std:vector alternative – 30-40% faster push/pop

Usually std::vector starts with 'N' capacity and grows to '2 * N' capacity once its size crosses X; at that time, we also copy the data from the old array to the new array. That has few problems

1. Copy cost,
2. OS needs to manage the small capacity array (size N) that's freed by the application.
3. L1 and L2 cache need to invalidate the array items, since the array moved to new location, and CPU need to fetch to L1/L2 since it's new data for CPU, but in reality it's not.

std::vector's reallocations and recopies are amortised O(1), but at low level they have lot of negative impact. Here's a log-structured alternative (constvector) with power-of-2 blocks: Push: 3.5 ns/op (vs 5 ns std::vector) Pop: 3.4 ns/op (vs 5.3 ns) Index: minor slowdown (3.8 vs 3.4 ns) Strict worst-case O(1), Θ(N) space trade-off, only log(N) extra compared to std::vector.

It reduces internal memory fragmentation. It won't invalidate L1, L2 cache without modifications, hence improving performance: In the github I benchmarked for 1K to 1B size vectors and this consistently improved showed better performance for push and pop operations.
 
Github: https://github.com/tendulkar/constvector

Youtube: https://youtu.be/ledS08GkD40

Practically we can use 64 size for meta array (for the log(N)) as extra space. I implemented the bare vector operations to compare, since the actual std::vector implementations have a lot of iterator validation code, causing the extra overhead.

https://redd.it/1ps8k53
@r_cpp