17、数据结构优化：选择合适的数据结构，避免伪共享，使用紧凑结构
说到性能优化，很多人第一反应是「调循环、改算法」。但说实话，我见过太多项目，折腾了半天汇编级优化，结果换个数据结构，性能直接翻倍。数据结构选对了，很多问题根本不会出现。
这一章，咱们就聊聊数据结构的三个核心维度：选型、伪共享、紧凑布局。这三个点，任何一个踩了坑，性能都会大打折扣。
17.1 选对数据结构，比什么都重要
我刚开始做嵌入式开发时，有个模块需要频繁查找。当时图省事，用了链表。结果跑起来慢得离谱。后来换成哈希表，查找时间从毫秒级降到了微秒级。你想想看，同样的CPU，同样的编译器，差别就这么大。
选数据结构的核心原则其实就几条：
- 查找频繁 → 哈希表、平衡树（别用链表）
- 顺序访问 → 数组（缓存友好）
- 频繁插入/删除 → 链表、跳表
- 小数据量 → 线性搜索有时比二分快（分支预测友好）
重要：不要迷信「高级数据结构」。我见过有人用红黑树存10个元素，结果性能还不如数组遍历。数据量小的时候，简单就是快。
17.2 伪共享：看不见的性能杀手
伪共享（False Sharing）这东西，说白了就是「两个线程各自用不同的变量，但这两个变量恰好挤在同一个缓存行里」。结果呢？一个线程改自己的变量，另一个线程的缓存行就失效了。明明没共享数据，却产生了共享的代价。
我曾经在一个多线程日志系统里踩过这个坑。四个线程各自写自己的日志缓冲区，按理说互不干扰。但性能就是上不去，CPU利用率高得吓人。后来一查，四个缓冲区紧挨着，全在同一个缓存行里。每个线程写日志，其他三个线程的缓存全失效了。
避坑指南：我曾经因为伪共享，把一个多线程程序的吞吐量从100万QPS降到了30万。排查了整整两天，最后发现只是结构体成员排列的问题。
解决伪共享，常用的方法就两个：
- 缓存行对齐：用
__attribute__((aligned(64)))或alignas(64)强制对齐 - 填充：在变量之间插入无用字节，让它们分到不同缓存行
// 伪共享版本
struct ThreadData {
int counter; // 线程1用
int counter2; // 线程2用 —— 和counter在同一个缓存行！
};
// 优化版本
struct ThreadData {
int counter;
char padding[60]; // 填充到64字节
int counter2;
char padding2[60];
};小技巧：现代CPU缓存行一般是64字节。你可以用 sysconf(_SC_LEVEL1_DCACHE_LINESIZE) 确认一下。不过大多数x86和ARM平台都是64。
17.3 紧凑结构：省内存就是省时间
紧凑结构，说白了就是让数据挨得近一点。为什么？因为CPU加载数据是按缓存行来的。你一个结构体占128字节，但只用到了前8字节，那剩下的120字节就浪费了。更糟的是，下一个结构体可能被挤到另一个缓存行里，访问它又要重新加载。
我建议你养成一个习惯：写结构体之前，先想想成员怎么排列最省空间。C语言的结构体成员顺序，直接影响内存布局。
// 浪费版
struct Bad {
char a; // 1字节
int b; // 4字节，对齐到4，浪费3字节
short c; // 2字节，对齐到2，浪费2字节
double d; // 8字节，对齐到8，浪费4字节
}; // 总大小：24字节
// 紧凑版
struct Good {
double d; // 8字节
int b; // 4字节
short c; // 2字节
char a; // 1字节
}; // 总大小：16字节（节省33%）
你看，同样的数据，只是换了个顺序，大小就从24字节降到了16字节。如果数组里有100万个元素，那就是8MB的差距。这8MB可能决定了你的数据能不能塞进L2缓存。
核心原则：把大的成员放前面，小的放后面。按类型大小降序排列，能最大程度减少填充。
17.4 实战：一个数据结构的优化案例
我记得有个网络包处理项目，结构体定义得乱七八糟。每个包要解析几十个字段，性能一直上不去。我接手后，做了三件事：
- 重新排列成员：按类型大小降序，从8字节到1字节
- 拆分热数据：把频繁访问的字段单独放一个结构体，冷数据放另一个
- 缓存行对齐：热数据结构体按64字节对齐
结果呢？包处理速度提升了40%。而且代码几乎没改，就是调整了一下结构体定义。
下面这张图，展示了优化前后的内存布局差异：
17.5 总结几条实用建议
嗯，说了这么多，最后给你几条我这些年总结出来的经验：
- 先想清楚访问模式：读多写少？写多读少？顺序访问？随机访问？不同的模式，最优数据结构完全不同
- 多线程共享数据，一定要考虑伪共享：特别是高频写入的场景。加个填充，成本极低，收益极大
- 结构体成员按大小降序排列：这是最省事的优化，改一下顺序就能省内存
- 热数据和冷数据分开：频繁访问的字段放一起，不常访问的放另一个结构体。这样缓存利用率更高
- 别过度优化：如果数据量只有几百个，结构体大小差几字节根本无所谓。先跑起来，再分析，再优化
我的习惯：每次写完结构体，我都会用 sizeof() 和 offsetof() 检查一下实际大小和成员偏移。有时候编译器会偷偷加填充，肉眼看不出来。
数据结构优化，说白了就是让数据更「听话」。让它们待在该待的地方，别互相干扰，别浪费空间。CPU 喜欢连续、紧凑、对齐的数据。你顺着它的脾气来，性能自然就上去了。