Comparing Linked List and Vector

bench.cc

#include <chrono>
#include <iomanip>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>

#include <benchmark/benchmark.h>

using Nanos = std::chrono::duration<double, std::nano>;
using benchmark::DoNotOptimize;

static void BM_Vector(benchmark::State &state) {
  const int ListSize = state.range(0);

  for (int i = 0; i < 5; i++) {
    std::vector<int> v(ListSize, 42);
    for (auto _ : state) {
      v.insert(v.begin() + (ListSize / 2), 42);
      DoNotOptimize(&v);
      int sum = 0;
      for (auto &x : v) {
        sum += x;
        DoNotOptimize(&x);
      }
      DoNotOptimize(sum);
      v.erase(v.end() - 1);
      DoNotOptimize(&v);
    }
  }
}

static void BM_LinkedList(benchmark::State &state) {
  const int ListSize = state.range(0);

  // Linked-list insert/remove
  for (int i = 0; i < 5; i++) {
    std::list<int> l(ListSize, 42);
    auto iter = l.begin();
    for (int j = 0; j < ListSize; j++) {
      iter++;
    }

    for (auto _ : state) {
      auto toRemove = l.insert(iter, 42);
      DoNotOptimize(&toRemove);
      int sum = 0;
      for (auto &x : l) {
        sum += x;
        DoNotOptimize(&x);
      }
      DoNotOptimize(sum);
      l.erase(toRemove);
      DoNotOptimize(&l);
    }
  }
}

BENCHMARK(BM_LinkedList)
    ->Arg(100)
    ->Arg(1000)
    ->Arg(10'000)
    ->Arg(100'000)
    ->Arg(10'000'000);
BENCHMARK(BM_Vector)->Arg(100)->Arg(1000)->Arg(10'000)->Arg(100'000)->Arg(
    10'000'000);
BENCHMARK_MAIN();

CMakeLists.txt

cmake_minimum_required(VERSION 3.20)
project(LinkedListBenchmark)

set(CMAKE_CXX_STANDARD 17)

find_package(benchmark REQUIRED)

add_executable(bench bench.cc)
target_link_libraries(bench benchmark::benchmark)

add_executable(original original.cc)
target_link_libraries(original benchmark::benchmark)

original.cc

// Adapted from https://news.ycombinator.com/item?id=27170090 for macOS.
// Replaced custom and Windows-specific DoNotOptimize with the one from
// google/benchmark.

#include <chrono>
#include <iomanip>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>

#include <benchmark/benchmark.h>

using Nanos = std::chrono::duration<double, std::nano>;
using benchmark::DoNotOptimize;

template <typename T, std::size_t COUNT = 10'000> Nanos measure(T t) {
  // record start time
  auto start = std::chrono::high_resolution_clock::now();
  for (size_t i = 0; i < COUNT; i++) {
    t();
  }
  // record end time
  auto end = std::chrono::high_resolution_clock::now();
  return (end - start) / COUNT;
}

int main() {
  for (int ListSize : {100, 1000, 10'000, 100'000}) {
    std::cout << std::fixed << std::setprecision(0) << std::left;
    // Vector insert/remove
    for (int i = 0; i < 5; i++) {
      std::vector<int> v(ListSize, 42);
      auto duration = measure([&] {
        v.insert(v.begin() + (ListSize / 2), 42);
        DoNotOptimize(&v);
        int sum = 0;
        for (auto &x : v) {
          sum += x;
          DoNotOptimize(&x);
        }
        DoNotOptimize(sum);
        v.erase(v.end() - 1);
        DoNotOptimize(&v);
      });
      std::cout << "Vector size " << ListSize << "  took " << duration.count()
                << "ns\n";
    }

    // Linked-list insert/remove
    for (int i = 0; i < 5; i++) {
      std::list<int> l(ListSize, 42);
      auto iter = l.begin();
      for (int j = 0; j < ListSize; j++) {
        iter++;
      }
      auto duration = measure([&] {
        auto toRemove = l.insert(iter, 42);
        DoNotOptimize(&toRemove);
        int sum = 0;
        for (auto &x : l) {
          sum += x;
          DoNotOptimize(&x);
        }
        DoNotOptimize(sum);
        l.erase(toRemove);
        DoNotOptimize(&l);
      });
      std::cout << "Linked-list size " << ListSize << "  took "
                << duration.count() << "ns\n";
    }
  }
}