premature optimization is fun sometimes：一次关于内存布局的“无用”优化之旅

背景

在软件开发中，我们常听到“过早优化是万恶之源”（Premature optimization is the root of all evil）这句格言。然而，有时为了理解底层机制或纯粹出于技术好奇心，进行一些看似“过度”的优化也能带来乐趣和深刻的见解。

这篇文章源自 Hacker News 社区的一篇讨论，作者分享了他与同事在开发一个连通性监控系统（Connectivity Monitoring System）时的经历。该系统功能并不复杂：通过向不同的服务器发送 ICMP Echo Requests（即 Ping 请求），并监控其在 1 分钟、5 分钟和 15 分钟窗口内的延迟和丢包率。

在讨论数据存储方案时，作者从最初直觉性的内存分配出发，逐步通过位域（bitfields）、结构体填充（struct padding）分析以及语义重构，最终将内存占用减半。尽管作者最后承认这种优化在资源不受限的应用中是“完全多余的”，但这一过程展示了 C/C++ 内存布局、编译器行为以及底层数据结构的精妙之处。

核心内容

1. 初始方案：直观的环形缓冲区

作者最初设想使用一个包含 512 个条目的环形缓冲区（Ring Buffer）来存储 Ping 数据。每个条目包含发送时间、接收时间、源地址和序列号。

初始结构体定义如下：

struct ping_timestamp {
    uint64_t sent_ns;      // 发送时间 (纳秒)
    uint64_t received_ns;  // 接收时间 (纳秒)
    in_addr_t source_addr; // 源地址
    uint16_t seq_no;       // 序列号
    bool received;         // 是否已接收
};

该结构体数组 pings_rb[512] 的总大小为 12,288 字节 (12 KiB)。作者认为这很浪费，因为对于每个数据包，我们真正关心的核心指标是延迟（Latency），即 received - sent。既然不需要同时保留发送和接收两个绝对时间戳，是否可以优化？

2. 第一次优化：使用 Tagged Union 和降低精度

为了节省空间，作者引入了联合体（Union）来复用存储空间：在等待回复时存储 sent_ts，收到回复后将其替换为 elapsed_ts（延迟时间）。同时，考虑到 Ping 延迟通常在毫秒级别，纳秒级精度（64位）过于奢侈，于是将时间单位从纳秒改为 100微秒 (0.1ms)。

优化后的结构体：

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;
};

此时，结构体大小变为 8,192 字节 (8 KiB)。虽然节省了一个内存页，但作者认为还有优化空间。

3. 第二次尝试：位域（Bitfields）的陷阱

作者进一步思考：

• 时间精度：43 位足以表示 20 年内的时间（以 0.1ms 为单位），无需 64 位。
• 布尔值：bool 类型通常占用 8 位，对于真/假值来说太浪费，应使用位域。

于是有了第三个版本：

struct ping_timestamp_3 {
    uint64_t sent_or_elapsed_ts : 43; // 43 bits
    uint64_t received : 1;            // 1 bit
    uint64_t seq_no : 16;             // 16 bits
    in_addr_t source_addr;            // 32 bits
};

然而，计算结果显示大小依然是 8,192 字节。为什么没有节省空间？

原因分析：结构体填充（Struct Padding）

编译器为了满足内存对齐要求，会在成员变量之间插入填充字节。

• ping_timestamp_2 中，source_addr (4字节) 和 seq_no (2字节) 以及 received (1字节) 被打包在一起，末尾有 1 字节填充以对齐到 8 字节边界。
• ping_timestamp_3 中，前三个位域成员总共占用了 60 位（43+1+16）。由于 source_addr 是 32 位整数，编译器会将前 60 位打包进前 8 字节，但剩下的 4 位加上 source_addr 会导致布局混乱，最终为了对齐 source_addr 或整个结构体，产生了大量的内部填充。具体来说，前 8 字节中浪费了 36 位，导致整体大小未变。

4. 第三次优化：利用 ICMP 标识符消除源地址字段

既然 source_addr 占用 32 位是主要的大头，能否去掉它？

作者指出，保留 source_addr 是为了在移动网络中源 IP 频繁变化时，区分不同连接的数据包。虽然 IP 变化时会重置序列号，但异步处理可能导致不同 IP 但相同序列号的数据包同时存在。

替代方案： ICMP Echo Request 报文头中有一个 16 位的 Identifier 字段，用于标识发送该请求的应用程序。在 Linux iputils ping 中，它通常设置为 getpid() & 0xFFFF；在 OpenBSD 中则是随机数。

虽然 Identifier 是 16 位，但我们不需要完整的 16 位来区分不同的“会话”。作者提出使用一个 4 位的滚动计数器（Rolling Counter）。当源 IP 发生变化时，该计数器递增。只要监控周期内 IP 变化不超过 16 次（这在现实中极罕见），这 4 位就足以唯一标识数据包来自哪个 IP 会话。

这样，我们可以移除 source_addr 字段，并利用之前位域中剩余的 4 位空间来存储这个计数器。

最终结构体：

struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43; // 时间戳
    uint64_t received : 1;            // 是否接收
    uint64_t counter : 4;             // 会话计数器 (替代 source_addr)
    uint64_t seq_no : 16;             // 序列号
};

此时，结构体大小骤降至 4,096 字节 (4 KiB)。相比最初的 12 KiB，节省了整整 8 KiB，且整个缓冲区正好占据一个内存页（Page），有利于缓存友好性。

5. 极致优化：利用编译器假设消除掩码操作

作者并未止步于此，而是进一步探讨了 CPU 指令层面的优化。

• 字段顺序调整：将 seq_no 放在 16 位边界上，使其加载只需一条 ldrh 指令，而非移位操作。
• 位访问效率：
  • 原结构中，读取 counter 需要掩码（Mask）操作。
  • 如果将 received 和 counter 的顺序交换，读取 received 只需移位，但读取 counter 仍需掩码。
  • 关键洞察：代码中只有在 received 为真（即 1）时，才会读取 counter。如果 received 为假，counter 的值无关紧要。

最终重构：

struct ping_timestamp {
    uint64_t elapsed_or_sent_ts : 43;
    uint64_t counter : 4;
    uint64_t not_received : 1; // 语义翻转：0 表示已接收
    uint64_t seq_no : 16;
};

通过将 received 翻转为 not_received，并在代码逻辑中检查