跳转至

💡 一分钟速览：结合两个基准示例说明 C++ 查表法的输入范围、计算与访存取舍，以及 std::inplace_merge 测试中重复使用已排序数据的陷阱。

最后更新：2026-10-13

C++ 查表法：什么时候有用？

查表用一次索引读取代替重复计算。只有输入范围小且确定、表能有效利用缓存，并且真实测量表明计算成本重要时，这种取舍才有意义。第一个示例仅接受 0 到 15 的值；超出范围索引数组属于未定义行为，不能把它当成通用的 powf 替代品。

以下片段来自关联项目的 Google Benchmark 实验，不表示查表在所有机器上都更快。若独立编译，需要安装 Google Benchmark 并添加常规的 BENCHMARK_MAIN() 入口；链接的 Quick Bench 运行展示了当时特定环境下的结果。

#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

来源：StarRocks PR #16351。比较时应让两个函数读取相同输入，检查数值容差，并在目标 CPU 和编译选项下重新测量。查表把算术开销换成访存开销，缓存行为可能改变结论。

std::inplace_merge vs std::merge

两者接口不同：std::merge 写入另一个输出区间，std::inplace_merge 重排原区间。旧版原地合并基准在每轮重复使用同一向量；首轮之后它已经整体有序，后续迭代测量的是另一种输入。下方代码已改为每次迭代在计时之外恢复两段已排序数据。

#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; // 恢复输入，重置过程不计时
        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

来源：StarRocks PR #14609。重置修复了输入变化问题，但两种算法的输出形式与分配行为仍不同。比较耗时时还要检查正确性、内存、输入规模、编译参数和数据分布。

如果要测量实际程序的堆内存峰值，可继续看 Valgrind Massif 指南。

相关主题

评论