What Building a C++ Benchmarking Suite Taught Me About “Simple” Data Structures

构建 C++ 基准测试套件让我对“简单”数据结构有了哪些新认识

We all know the Big-O complexity of basic data structures. Arrays are O(n) for search. Hash maps are O(1). Linked lists are… well, complicated. But when I set out to build hashbrowns — a C++17 benchmarking suite comparing arrays, linked lists, and hash maps — I discovered that theory and practice are very different beasts. Here’s what I learned building this project from scratch, and why you should probably benchmark before you optimize. 我们都知道基本数据结构的大 O 复杂度。数组的搜索是 O(n)，哈希表是 O(1)，而链表……嗯，情况比较复杂。但当我着手构建 hashbrowns（一个对比数组、链表和哈希表的 C++17 基准测试套件）时，我发现理论与实践之间存在巨大的鸿沟。以下是我从零开始构建该项目所学到的经验，以及为什么你在优化代码前应该先进行基准测试。

🎯 The Goal Was Simple (Ha!)

🎯 目标很简单（哈！）

I wanted a clean, educational project that would: 我想要一个简洁且具有教育意义的项目，能够实现：

• Implement dynamic arrays, linked lists, and hash maps from scratch
• 从零实现动态数组、链表和哈希表
• Benchmark insert, search, and remove operations
• 对插入、搜索和删除操作进行基准测试
• Find the “crossover points” where one structure beats another
• 找出一种结构优于另一种结构的“交叉点”
• Export everything to CSV for analysis
• 将所有数据导出为 CSV 以供分析

Sounds straightforward, right? Four months later, I had written a custom memory tracker, implemented multiple hash map strategies, added statistical bootstrapping for confidence intervals, and learned more about CPU caches than I ever wanted to know. 听起来很简单，对吧？四个月后，我已经编写了一个自定义内存跟踪器，实现了多种哈希表策略，添加了用于置信区间的统计自举法（bootstrapping），并且对 CPU 缓存的了解程度远超我的预期。

📚 Lesson 1: Polymorphism Has a Price (But It’s Worth It)

📚 经验 1：多态是有代价的（但它值得）

My first architectural decision was creating a common DataStructure interface. This made benchmarking elegant — I could write generic code that tested any data structure. But virtual function calls have overhead. In tight loops, that vtable lookup adds up. I spent a whole weekend convinced my hash map was slower than expected… until I realized I was measuring the cost of polymorphism, not the data structure itself. The fix? I kept the clean interface for the benchmarking harness but used templates internally where performance-critical code needed direct calls. The polymorphic interface was still worth it for maintainability and adding new structures easily. 我的第一个架构决策是创建一个通用的 DataStructure 接口。这使得基准测试变得优雅——我可以编写通用代码来测试任何数据结构。但虚函数调用是有开销的。在紧凑的循环中，虚函数表（vtable）的查找开销会累积。我花了一整个周末确信我的哈希表比预期的慢……直到我意识到我测量的是多态的成本，而不是数据结构本身的性能。解决方法是什么？我为基准测试框架保留了简洁的接口，但在性能关键的内部代码中使用了模板以实现直接调用。对于可维护性和轻松添加新结构而言，多态接口依然是值得的。

⏱️ Lesson 2: Benchmarking Is Harder Than It Looks

⏱️ 经验 2：基准测试比看起来更难

My first timer was naive. The numbers were all over the place. Some runs were 10x faster than others. What was going on? 我最初的计时器非常简陋。测试数据波动极大，有些运行速度比其他快了 10 倍。到底发生了什么？

• Problem 1: Warm-up matters. The first few runs are always slower because CPU caches are cold and the branch predictor hasn’t learned patterns yet. I added configurable warm-up runs.
• 问题 1：预热很重要。 最初的几次运行总是较慢，因为 CPU 缓存是冷的，且分支预测器尚未学习到模式。我添加了可配置的预热运行。
• Problem 2: Outliers destroy your mean. That one run where your OS decided to run garbage collection? It’ll skew everything. I implemented automatic outlier detection using Z-scores.
• 问题 2：异常值会破坏平均值。 如果操作系统刚好在某次运行中执行了垃圾回收怎么办？这会扭曲所有数据。我使用 Z-score 实现了自动异常值检测。
• Problem 3: CPU frequency scaling. Modern CPUs boost and throttle constantly. I added options to pin CPU affinity and (on Linux) attempt to lock the CPU governor.
• 问题 3：CPU 频率缩放。 现代 CPU 会不断地加速和降频。我添加了绑定 CPU 亲和性的选项，并（在 Linux 上）尝试锁定 CPU 调频策略。
• Problem 4: You need more than the mean. Reporting mean ± stddev isn’t enough. I ended up implementing median, P95 percentiles, and bootstrap confidence intervals.
• 问题 4：仅有平均值是不够的。 仅报告“平均值 ± 标准差”是不够的。我最终实现了中位数、P95 百分位和自举置信区间。

🔧 Lesson 3: Growth Strategies Are a Rabbit Hole

🔧 经验 3：增长策略是一个深坑

When implementing DynamicArray, I thought I’d just double the capacity when full. But then I wondered: what if we used 1.5x growth? What about Fibonacci growth? I implemented all four and benchmarked them. The interesting insight: for most real-world workloads, the difference is negligible. The “obvious” choice of 2x doubling is usually fine. 在实现 DynamicArray 时，我本想在空间满时直接将容量翻倍。但后来我开始思考：如果使用 1.5 倍增长呢？斐波那契增长呢？我实现了所有四种策略并进行了基准测试。有趣的发现是：对于大多数实际工作负载，差异微乎其微。通常，“显而易见”的 2 倍增长策略就已经足够好了。

🗺️ Lesson 4: Hash Maps Have Hidden Complexity

🗺️ 经验 4：哈希表隐藏着复杂性

I implemented two hash map strategies: open addressing (linear probing) and separate chaining. Open addressing wins when the load factor is low and keys are well-distributed. Separate chaining wins when you have clustering or high load factors. The “tombstone” problem in open addressing was particularly sneaky — too many tombstones degrade performance as much as collisions. I ended up tracking probe counts per operation as a metric, which made it obvious when the hash function wasn’t distributing well. 我实现了两种哈希表策略：开放寻址法（线性探测）和链地址法。当负载因子较低且键分布均匀时，开放寻址法胜出；当出现聚集或负载因子较高时，链地址法更优。开放寻址法中的“墓碑（tombstone）”问题特别隐蔽——过多的墓碑会导致性能下降，其程度不亚于哈希冲突。我最终将每次操作的探测次数作为一项指标进行跟踪，这使得哈希函数分布不均的问题变得一目了然。

🧠 Lesson 5: Memory Tracking Reveals Everything

🧠 经验 5：内存跟踪揭示了一切

Early on, I built a MemoryTracker singleton that hooks into all allocations. Combined with a custom TrackedAllocator<T> that plugs into STL containers, I could see exactly how much memory each structure was consuming at any given moment. It turned out that my “simple” linked list was consuming significantly more memory than the array due to node overhead (pointers). 在项目早期，我构建了一个 MemoryTracker 单例，它挂钩了所有的内存分配。结合插入 STL 容器的自定义 TrackedAllocator<T>，我可以精确地看到每个结构在任何时刻消耗的内存量。结果发现，由于节点开销（指针），我那“简单”的链表消耗的内存远多于数组。