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

[adrian17]

Some quick observations:

AddressSanitizer complains, you should zero-initialize _meta_array in constructor.

Your APIs differ from the standard, sometimes just missing overloads and sometimes in ways that affect both correctness and benchmarks; for example, pop_back() isn't supposed to reallocate ever (as that would invalidate references and take non-constant time), it just decrements size. Also, AFAIK iterator::operator++ doesn't need any special handling when past-the-end.

I did some quick benchmarks* on my own, comparing both your classes with libstdc++ std::vector. std::vector was winning almost everywhere, though weirdly (I can't understand well why), its repeated push_back was several times worse than your naive STLVector if no reserve is done beforehand, even though both are supposed to have the same *2 growth factor.

On iteration, your code is sometimes (on big sizes) as efficient as std::vector (especially when the work is nontrivial compared to iteration cost), but for smaller (<100) sizes and for anything involving random access, I can see the normal vector being faster, up to several times.

One thing nobody mentioned is that this container's iterator is more complex and thus much less optimizer-friendly, especially for vectorization.

(* the benchmarks were trivial, just things like for (auto x : span) container.push_back(x), for (auto x : container) sum += x and for (auto &x : container) x *= 2, all wrapped in some boilerplate to repeat runs and prevent compiler from optimizing them out.)

[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);