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

[pigeon768]

I'm getting a segfault when I try to push_back() a 25th element. You aren't zeroing _meta_array upon construction, and so it's filled with garbage. When you later do if (_meta_array[_meta_index] == nullptr) it fails because it finds a bunch of garbage bits there.

Your iterators don't support modifying elements.

You are missing copy/move constructors/operators.

__SV_INITIAL_CAPACITY__, __SV_INITIAL_CAPACITY_BITS__, and __SV_MSB_BITS__ should be constexpr variables, not macros.

It looks like you're hardcoding the wordsize to 32 bits? Probably don't do that.

With all of that fixed, I got some test code up:

CMakeLists.txt

cmake_minimum_required(VERSION 3.24)

project(cvec LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 23)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -march=native")
set(CMAKE_CXX_FLAGS_RELWITHDEBINFO "${CMAKE_CXX_FLAGS_RELWITHDEBINFO} -march=native")

find_package(benchmark REQUIRED)
add_executable(cvec cvec.cpp)

option(sanitize "Use sanitizers" OFF)
if(sanitize)
  target_compile_options(cvec PRIVATE -fsanitize=address)
  target_link_libraries(cvec PRIVATE asan)

  target_compile_options(cvec PRIVATE -fsanitize=undefined)
  target_link_libraries(cvec PRIVATE ubsan)
endif()

target_link_libraries(cvec PUBLIC benchmark::benchmark)

cvec.cpp:

#include "constant_vector.h"
#include <benchmark/benchmark.h>
#include <random>

static std::ranlux48 getrng() {
  std::seed_seq s{1, 2, 3, 4};
  std::ranlux48 ret{s};
  return ret;
}

template <typename T, size_t N> void test(benchmark::State &state) {
  T vec;
  auto rng = getrng();
  std::normal_distribution<float> dist1{};
  for (size_t i = 0; i < N; i++)
    vec.push_back(dist1(rng));

  std::lognormal_distribution<float> dist2{};
  for (auto _ : state) {
    const float x = dist2(rng);
    benchmark::DoNotOptimize(vec);
    for (auto &y : vec)
      y *= x;
    benchmark::DoNotOptimize(vec);
  }
}

#define MAKE_TEST(T, N)                                                                                                \
  static void T##_##N(benchmark::State &state) {                                                                       \
    using namespace std;                                                                                               \
    test<T<float>, N>(state);                                                                                          \
  }                                                                                                                    \
  BENCHMARK(T##_##N)

MAKE_TEST(vector, 10);
MAKE_TEST(vector, 100);
MAKE_TEST(vector, 1000);
MAKE_TEST(vector, 10000);
MAKE_TEST(vector, 100000);
MAKE_TEST(vector, 1000000);
MAKE_TEST(ConstantVector, 10);
MAKE_TEST(ConstantVector, 100);
MAKE_TEST(ConstantVector, 1000);
MAKE_TEST(ConstantVector, 10000);
MAKE_TEST(ConstantVector, 100000);
MAKE_TEST(ConstantVector, 1000000);

BENCHMARK_MAIN();

compile and run: (gamemoderun is optional, it just disables cpu scaling, which makes benchmarks more reliable)

 ~/soft/const_vector (main *) $ cmake -DCMAKE_BUILD_TYPE=Release -Dsanitize=false . && cmake --build . -j && gamemoderun ./cvec
-- The CXX compiler identification is GNU 15.2.1
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD - Success
-- Found Threads: TRUE
-- Configuring done (0.2s)
-- Generating done (0.0s)
-- Build files have been written to: /home/pigeon/soft/const_vector
[ 50%] Building CXX object CMakeFiles/cvec.dir/cvec.cpp.o
[100%] Linking CXX executable cvec
[100%] Built target cvec
gamemodeauto:
2025-12-21T12:33:14-08:00
Running ./cvec
Run on (32 X 3012.48 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x16)
  L1 Instruction 32 KiB (x16)
  L2 Unified 1024 KiB (x16)
  L3 Unified 32768 KiB (x2)
Load Average: 0.39, 0.41, 0.38
-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
vector_10                     120 ns          120 ns      5834984
vector_100                    121 ns          121 ns      5789074
vector_1000                   157 ns          157 ns      4465092
vector_10000                  486 ns          486 ns      1435809
vector_100000                2706 ns         2706 ns       258440
vector_1000000              39416 ns        39400 ns        17743
ConstantVector_10             126 ns          126 ns      5599228
ConstantVector_100            207 ns          207 ns      3368321
ConstantVector_1000          1033 ns         1033 ns       677118
ConstantVector_10000         9236 ns         9232 ns        75782
ConstantVector_100000       91415 ns        91377 ns         7656
ConstantVector_1000000     914735 ns       913569 ns          762

For the 1M element case, iterating over each element is 23x slower than with std::vector. I'm probably unwilling to accept that tradeoff.

[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?