基于Google Benchmark复现std::list与std::vector头部插入性能遇阻

原始性能结论（来自CppCon 2022） #

• std::list头部插入的耗时呈线性增长
• std::vector头部插入的耗时呈多项式增长
• 元素数量较少（<800）时，std::vector性能优于std::list

你的测试代码 #

#include <benchmark/benchmark.h>

static void bm_vec(benchmark::State &state) {
    for (auto _ : state)
    {
        state.PauseTiming();
        std::vector<int> v ;
        benchmark::DoNotOptimize(v.data());
        state.ResumeTiming();
        for (int i = 0; i < state.range(0); i++)
        {
           v.insert(v.begin(), 1);
        }
        benchmark::ClobberMemory();
    }
}

BENCHMARK(bm_vec)->DenseRange(10,2000,10);

static void bm_list(benchmark::State &state) {
    
    for (auto _ : state)
    {
        state.PauseTiming();
        std::list<int> v ;
        benchmark::DoNotOptimize(v.front());
        state.ResumeTiming();
        for (int i = 0; i < state.range(0); i++)
        {
            v.insert(v.begin(), 1);
        }
        
    }
}
BENCHMARK(bm_list)->DenseRange(10,2000,10);

BENCHMARK_MAIN();

代码问题与改进方案 #

1. 修复std::list的未定义行为与优化屏障错误 #

你的bm_list测试中，空std::list调用v.front()会触发未定义行为（空列表没有首元素），且DoNotOptimize的使用没有正确阻止编译器优化掉无意义的list操作。

修改方式：

• 移除v.front()调用，改为对list对象本身设置优化屏障：benchmark::DoNotOptimize(&v);
• 在list测试末尾添加benchmark::ClobberMemory();，确保编译器不会忽略list的内存修改操作。

2. 优化vector测试的内存屏障有效性 #

当前vector测试的ClobberMemory()位置可以保留，但要确保DoNotOptimize(v.data())持续生效——它能阻止编译器将vector的内存操作优化为无意义的代码。

3. 确保容器初始化完全脱离计时区间 #

当前的PauseTiming和ResumeTiming使用逻辑正确，但需确认初始化容器的代码完全落在暂停计时的区间内，避免初始化开销干扰测试结果。

改进后的完整代码 #

#include <benchmark/benchmark.h>
#include <vector>
#include <list>

static void bm_vec(benchmark::State &state) {
    for (auto _ : state)
    {
        state.PauseTiming();
        std::vector<int> v;
        benchmark::DoNotOptimize(v.data());
        state.ResumeTiming();
        
        for (int i = 0; i < state.range(0); ++i) {
            v.insert(v.begin(), 1);
        }
        
        benchmark::ClobberMemory();
    }
}
BENCHMARK(bm_vec)->DenseRange(10, 2000, 10);

static void bm_list(benchmark::State &state) {
    for (auto _ : state)
    {
        state.PauseTiming();
        std::list<int> v;
        benchmark::DoNotOptimize(&v); // 对list对象设置优化屏障
        state.ResumeTiming();
        
        for (int i = 0; i < state.range(0); ++i) {
            v.insert(v.begin(), 1);
        }
        
        benchmark::ClobberMemory(); // 确保内存修改被编译器观测到
    }
}
BENCHMARK(bm_list)->DenseRange(10, 2000, 10);

BENCHMARK_MAIN();

额外优化建议 #

• 添加->UseRealTime()到基准测试配置，避免CPU频率缩放影响结果：

  BENCHMARK(bm_vec)->DenseRange(10,2000,10)->UseRealTime();
  BENCHMARK(bm_list)->DenseRange(10,2000,10)->UseRealTime();
  

• 运行测试时关闭后台程序，确保系统资源充足，减少测试波动。

内容的提问来源于stack exchange，提问作者orfvl