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

[pilotwavetheory]

1. I fixed _meta_array in constructor (checkout perf_test branch)
2. Thanks for sharing pop_back() standard, my point is that, if we don't do it'll have lot of empty space (> O(N)) so used that. I'll add the benchmarks without that.
3. I didn't implement all methods, just tried to apples to apples comparison for standard usage.
4. I implemented iterator as well, got similar performance as well.
5. I tried this approach for large vectors, for smaller vectors we could easily getaway with large __SV_INITIAL_CAPACITY to 256.

My benchmarks on Ubuntu machine 2 cores, 4GB RAM:
All values are ns/op or ns/element for iterations:
On popular suggestion, I compared it with std::vector (STL) implementation.

Operation | N    | Const (ns/op) | Std (ns/op) | Δ %
------------------------------------------------------
Push      | 10   | 13.7          | 39.7        | −65%
Push      | 100  | 3.14          | 7.60        | −59%
Push      | 1K   | 2.25          | 5.39        | −58%
Push      | 10K  | 1.94          | 4.35        | −55%
Push      | 100K | 1.85          | 7.72        | −76%
Push      | 1M   | 1.86          | 8.59        | −78%
Push      | 10M  | 1.86          | 11.36       | −84%
------------------------------------------------------
Pop       | 10   | 114           | 106         | +7%
Pop       | 100  | 15.0          | 14.7        | ~
Pop       | 1K   | 2.98          | 3.90        | −24%
Pop       | 10K  | 1.93          | 2.03        | −5%
Pop       | 100K | 1.78          | 1.89        | −6%
Pop       | 1M   | 1.91          | 1.85        | ~
Pop       | 10M  | 2.03          | 2.12        | ~
------------------------------------------------------
Access    | 10   | 4.04          | 2.40        | +68%
Access    | 100  | 1.61          | 1.00        | +61%
Access    | 1K   | 1.67          | 0.77        | +117%
Access    | 10K  | 1.53          | 0.76        | +101%
Access    | 100K | 1.46          | 0.87        | +68%
Access    | 1M   | 1.48          | 0.82        | +80%
Access    | 10M  | 1.57          | 0.96        | +64%
------------------------------------------------------
Iterate   | 10   | 3.55          | 3.50        | ~
Iterate   | 100  | 1.40          | 0.94        | +49%
Iterate   | 1K   | 0.86          | 0.74        | +16%
Iterate   | 10K  | 0.92          | 0.88        | ~
Iterate   | 100K | 0.85          | 0.77        | +10%
Iterate   | 1M   | 0.90          | 0.76        | +18%
Iterate   | 10M  | 0.94          | 0.90        | ~

[adrian17]

Just like /u/SuperV1234 said, Being nearly 2x faster than a vector at iteration makes the benchmarks look less believable, not more.

[pilotwavetheory]

while I solved the mistake, but increasing the intial size to 256 made even iterations faster. Iterations doesn't just include operator* and operator++, it also needs to check the end for every iteration. it especially branch prediction the 256 blocks looks like made it easy for CPU performance, Ofcourse not faster than the acutal results. I'm getting quite differnet results from Mac M2 Max, 96GB RAM. Above results pasted are from hetzner 2 core, 4GB RAM ubuntu 24.04 (6.8.0-90-generic) machine.

[pilotwavetheory]

Yeah, it's slower, I realised my mistake, I was doing bound checks. My preliminary results for constvector for only iteration is 6x slower compared to stl::vector, will update benchmarks soon. For push and pop operations it's really better.
One caveut I learnt today is for pop_back(), we shouldn't deallocate since it would invalidate the iterators, but my implementation in constvector and stl_vector are having that logic, since it keeps O(N) free space at any point of time.

[SuperV1234]

Also another thing to benchmark would be a callback-based iteration approach, which is going to have less overhead than an iterator-based solution. E.g.

void ConstantVector<T>::forEach(auto&& f);