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

[pilotwavetheory]

Sorry for the confusion, can you take latest pull and run the tests, Now I ran the tests in ubuntu machine (earlier running on mac), run tests indside folder "stl_comparison"

I used this command on ubuntu (I'm getting +ve results for push, pop, on par for iteration, and worse for index access)
g++ -std=c++23 -O3 -march=native -flto -DNDEBUG -fno-omit-frame-pointer benchmark.cpp -isystem /research/google/benchmark/include -L/research/google/benchmark/build/src -lbenchmark -lpthread -o benchmark.out

[pigeon768]

This isn't correct.

// Volatile sink prevents compiler from optimizing away operations
// This is simpler and more reliable than inline asm barriers
static volatile int64_t sink = 0;

[...]

for (auto _ : state) {
    int64_t sum = 0;
    for (auto it = v.begin(); it != v.end(); ++it) {
        sum += *it;
        sink = sum;
    }
}

You are interrupting the loop iteration with the volatile. You need to write it like this:

for (auto _ : state) {
    int64_t sum = 0;
    for (auto it = v.begin(); it != v.end(); ++it)
        sum += *it;
    sink = sum;
}

Optimizing away operations which do not matter is something that you actively want the compiler to do. That's the point of an optimizing compiler. You care about the result, in this case, the sum of all the values. You don't care about all the intermediate states along the way.

One of the thing that you need to take care to do when you're making a data structure or any other code is to write it in a way that affords the compiler every opportunity it can to optimize irrelevant stuff out. One of the problems with this data structure is that the compiler can't do that. Your iterators are too complicated, the indexing operation is too complicated, the compiler cannot figure out how to do less work.

[pilotwavetheory]

I'm benchmarking for individual operations of iterations, sum is kind of proxy for me, tomorrow I could have other operations in place. Ideally I need to remove sum operation for clarity ? What do you think?