过早优化有时也挺有趣

# invlpg – 有时过早优化也很有趣 来源：https://invlpg.com/posts/2025-06-19-premature-optimization.html 最近一位同事和我讨论了他正在开发的一个连接监控系统。它并不复杂，只是向几个不同的服务器发送 ICMP Echo 请求，并监控 1 分钟、5 分钟和 15 分钟周期内的延迟和丢包平均值。接着谈到了这些数据应该如何处理，自然想到用 512 条目的环形缓冲区，每个条目类似下面这样： ```c struct ping_timestamp { uint64_t sent_ns; // 发送时间（单位：纳秒） uint64_t received_ns; // 接收时间（单位：纳秒） in_addr_t source_addr; // 源地址 uint16_t seq_no; // 回显请求序号 bool received; // 是否已收到请求 }; ``` 并用以下数组来存储： ```c struct ping_timestamp pings_rb[512]; // ... printf("%zu\n", sizeof(pings_rb)); // 12288 ``` 12 KiB。挺浪费的吧？我们肯定能做得更好。是否真的需要同时保留 `sent` 和 `received` 两个字段？我们真正关心的是延迟。我们需要知道一个包何时发送，但也只用到知道何时收到为止，此后我们想保留的数据是 `received - sent`，那么为什么不把它做成一个带标签的联合体呢？ ```c struct ping_timestamp_2 { union { uint64_t sent_ts; // 单位：100μs uint64_t elapsed_ts; // 单位：100μs }; in_addr_t source_addr; uint16_t seq_no; bool received; }; // ... printf("%zu\n", sizeof(pings_rb)); // 8192 ``` 不错，已经节省了整整一页。我们还能进一步优化。 纳秒级的精度？在我们这种情况下，ping 时间通常为几十、几百甚至几千*毫秒*。我们不需要保留那么多多余的比特。如果将单位从纳秒改为 100 微秒增量（0.1ms），那么 43 比特就足以记录长达 20 年的 ping 时间¹。20 年还是有点过于长远，但稍微考虑点未来兼容性也没什么坏处。 至于 `received`？用一个字节（8 位）来存储 true/false 也似乎太浪费了。答案：位域。 ```c struct ping_timestamp_3 { uint64_t sent_or_elapsed_ts: 43; uint64_t received: 1; uint64_t seq_no: 16; in_addr_t source_addr; }; // ... printf("%zu\n", sizeof(pings_rb)); // 8192 ``` 等等，怎么回事？为什么一点空间都没节省？ 答案是结构体填充。`ping_timestamp_2` 的布局是这样的： ``` 0 8 16 24 32 40 48 56 64... +-------+-------+-------+-------+-------+-------+-------+-------+ | sent/elapsed | +-------+-------+-------+-------+-------+-------+-------+-------+ ...64 72 80 88 96 104 112 120 128 +-------+-------+-------+-------+-------+-------+-------+-------+ | source_address | seq_no | recv? | pad | +---------------------------------------------------------------+ ``` 末尾的填充字节是为了满足对齐要求。而 `ping_timestamp_3` 的布局如下： ``` 0 8 16 24 32 40 R? 48 56 64... +-------+-------+-------+-------+-------+-------+-------+-------+ | sent/elapsed || seq_no | P | +-------+-------+-------+-------+-------+-------+-------+-------+ ...64 72 80 88 96 104 112 120 128 +-------+-------+-------+-------+-------+-------+-------+-------+ | source_address | padding | +---------------------------------------------------------------+ ``` 所以我们的优化实际上并没有节省任何空间。我们浪费了 36 位的填充。有没有办法做得更好？ 我们保留源地址是因为产品在运行过程中（在移动数据网络上）它会频繁变化。当地址改变时，我们还会重置序号，原因与本主题无关。过去遇到过这样的情况：不同源地址但序号相同的包同时被我们的应用处理（异步编程的乐趣），因此源地址用于区分这些变化。 但还有另一种区分方法。 ICMP 回显请求有一个 16 位的 `identifier` 字段，供应用程序识别哪些回显请求包是它们发送的。其值完全随机。在 Linux 上，`iputils ping` 将其设置为 `getpid() & 0xFFFF`；在 OpenBSD 上则使用随机数。 虽然它有 16 位，但我们实际上不需要使用全部 16 位。在我们的 `ping_timestamp_3` 的前 8 字节中还有 4 个空闲位。我们的想法是使用一个滚动的 4 位计数器，每次源地址改变时递增（地址变化由程序其他地方监控），这样就能唯一标识²每个包来自哪个源地址。 最终的结构体如下： ```c struct ping_timestamp { uint64_t elapsed_or_sent_ts : 43; uint64_t received : 1; uint64_t counter: 4; uint64_t seq_no: 16; }; // ... printf("%zu\n", sizeof(pings_rb)); // 4096 ``` 好多了。总共节省了 8 千字节，并且数据只占用一页内存。你可能注意到我稍微调整了字段的顺序。这样做是为了让 `seq_no` 对齐到 16 位边界，这样加载它只需要一条 `ldrh` 指令，而无需移位操作。类似地，读取 `elapsed_or_sent_ts` 只需要一个掩码操作。 最终，这完全是无意义的练习。我们的应用程序在内存方面一点也不受限。 但过程很有趣。 ## 附录 2025-06-21 我发现还有一种方法可以稍微进一步“优化”。通过交换 `received` 和 `counter` 字段的顺序，访问 `received` 位只需要移位指令，而不需要移位加掩码（参见 [Compiler Explorer](https://godbolt.org/z/G8ne56Geb)）： ```c struct ping_timestamp { uint64_t elapsed_or_sent_ts : 43; uint64_t counter: 4; uint64_t received : 1; uint64_t seq_no: 16; }; ``` ## 附录 2025-06-22 上述代码存在一个小的“问题”³：`received` 现在访问起来便宜了很多，但代价是 `counter` 需要额外掩码掉 `received` 位。 不过我们可以解决！我们只在 `received` 为真（即 1）时才读取 `counter`。如果 `received` 为 0，并且我们能告诉编译器假定它为 0，那么就不需要掩码了。 解决方案？反转 `received` 位的意思。 ```c struct ping_timestamp { uint64_t elapsed_or_sent_ts : 43; uint64_t counter: 4; uint64_t not_received : 1; uint64_t seq_no: 16; }; ``` 现在，如果对 `counter` 的读取只发生在检查 `not_received` 为 0 的条件之内，那么编译器就能完全省略掩码（参见 [Compiler Explorer](https://godbolt.org/z/KMEc5aWsP)）。 --- 1. 时间戳来自 Linux 内核的单调时钟，测量的是自启动以来经过的时间。如果是从 Unix 纪元开始测量，则需要 51 位。↩︎ 2. 只要 IP 地址在我们监控的周期内变化不超过 16 次，这种情况我们从未遇到过。↩︎ 3. 我用这个词很宽松，我们甚至没有做过基准测试。↩︎