Skip to content

💡 TL;DR:When does a C++ lookup table help? Two benchmark case studies show the input-range precondition, cost trade-offs, and how to avoid timing already-sorted data.

Last updated:2026-10-13

C++ lookup tables: when are they useful?

A lookup table replaces repeated computation with an indexed read. That trade-off is useful only when the input range is small and known, the table stays cache-friendly, and profiling shows the computation matters. The first example uses a 16-entry table for values from 0 through 15; indexing outside that range is undefined behavior. It is not a general replacement for powf.

The following snippets are Google Benchmark experiments from the linked projects, not a claim that the table is always faster. To run them as standalone files, install Google Benchmark and add its usual BENCHMARK_MAIN() entry point. The linked Quick Bench runs provide the original harness and results for their specific compiler and environment.

#include <benchmark/benchmark.h>
#include <cstdint>
#include <cmath>
#include <random>


const int HLL_COUNT = 16;


static float harmonic_mean_table(const uint64_t* data) {
    static const float harmonic_tables[16] = {
        1.0f / static_cast<float>(1L << 0),
        1.0f / static_cast<float>(1L << 1),
        1.0f / static_cast<float>(1L << 2),
        1.0f / static_cast<float>(1L << 3),
        1.0f / static_cast<float>(1L << 4),
        1.0f / static_cast<float>(1L << 5),
        1.0f / static_cast<float>(1L << 6),
        1.0f / static_cast<float>(1L << 7),
        1.0f / static_cast<float>(1L << 8),
        1.0f / static_cast<float>(1L << 9),
        1.0f / static_cast<float>(1L << 10),
        1.0f / static_cast<float>(1L << 11),
        1.0f / static_cast<float>(1L << 12),
        1.0f / static_cast<float>(1L << 13),
        1.0f / static_cast<float>(1L << 14),
        1.0f / static_cast<float>(1L << 15),
    };

    float harmonic_mean = 0.0f;
    for (int i = 0; i < HLL_COUNT; ++i) {
        harmonic_mean += harmonic_tables[data[i]];
    }

    return harmonic_mean;
}

static float harmonic_mean_calc(const uint64_t* data) {
    float harmonic_mean = 0.0f;
    for (int i = 0; i < HLL_COUNT; ++i) {
        harmonic_mean += powf(2.0f, -data[i]);
    }

    return harmonic_mean;
}


uint64_t global_data[HLL_COUNT];

static void CustomArguments(benchmark::internal::Benchmark* b) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<uint64_t> dis(0, HLL_COUNT - 1);

    for (int i = 0; i < HLL_COUNT; ++i) {
        global_data[i] = dis(gen);
    }
}

static void BM_HarmonicMeanTable(benchmark::State& state) {
    for (auto _ : state) {
        benchmark::DoNotOptimize(harmonic_mean_table(global_data));
    }
}
BENCHMARK(BM_HarmonicMeanTable)->Apply(CustomArguments);


static void BM_HarmonicMeanCalc(benchmark::State& state) {
    for (auto _ : state) {
        benchmark::DoNotOptimize(harmonic_mean_calc(global_data));
    }
}
BENCHMARK(BM_HarmonicMeanCalc)->Apply(CustomArguments);

https://quick-bench.com/q/KtYyI4wutSurcnCrEezhRrH3Oks

Source discussion: StarRocks PR #16351. Compare the same input values in both functions, check numerical tolerance, and rerun on your target CPU and compiler flags before adopting the table. A table read trades arithmetic for memory access; cache effects can reverse a microbenchmark result.

std::inplace_merge vs std::merge

The next example compares two different interfaces: std::merge writes into a separate output range, while std::inplace_merge rearranges one range. The earlier version of the in-place benchmark reused the same vector in every iteration. After the first merge, that vector was fully sorted, so later iterations measured a different workload. The code below resets the input outside the timed section for each iteration.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <benchmark/benchmark.h>


std::vector<int> generateTestData(int size) {
    std::vector<int> vec(size);

    for (int i = 0; i < size / 2; ++i) {
        vec[i] = 2 * i + 1;
    }

    for (int i = size / 2; i < size; ++i) {
        vec[i] = 2 * (i - size / 2) + 2;
    }

    return vec;
}

static void BM_Merge(benchmark::State& state) {
    state.PauseTiming();
    std::vector<int> vec = generateTestData(state.range(0) * 2);
    std::vector<int> result(state.range(0) * 2);
    state.ResumeTiming();
    for (auto _ : state) {
        std::merge(vec.begin(), vec.begin() + state.range(0), vec.begin() + state.range(0), vec.end(), result.begin());
    }
}
BENCHMARK(BM_Merge)->Range(8, 8 << 10);

static void BM_InplaceMerge(benchmark::State& state) {
    state.PauseTiming();
    const std::vector<int> original = generateTestData(state.range(0) * 2);
    std::vector<int> vec = original;
    state.ResumeTiming();

    for (auto _ : state) {
        state.PauseTiming();
        vec = original; // restore two sorted halves; do not time the reset
        auto middle = vec.begin() + state.range(0);
        state.ResumeTiming();
        std::inplace_merge(vec.begin(), middle, vec.end());
        benchmark::DoNotOptimize(vec.data());
    }
}
BENCHMARK(BM_InplaceMerge)->Range(8, 8 << 10);

https://quick-bench.com/q/u1WQpxF-KxrvW2s4mrnPkC6ZvLw

Source discussion: StarRocks PR #14609. This reset fixes the changing-input problem but does not make the two operations interchangeable: they have different output and allocation behavior. Inspect correctness, memory use, data sizes, compiler flags, and input distribution before comparing timings.

For an end-to-end memory measurement, see the Valgrind Massif guide.

Comments