4. 数据结构与算法异构考虑：内存布局、数据对齐、缓存友好设计
大家做算法适配时，最容易踩的坑就是——数据结构在不同平台上的“长相”不一样。我的一个老项目，在 x86 上跑得飞快，移植到 ARM 上直接崩了。查了半天，问题出在内存布局上。说白了，你的结构体在内存里怎么排、成员怎么对齐、缓存怎么命中，这些东西跟平台强相关。今天我们把这三个问题拆开聊透。
4.1 内存布局：你的结构体可能比你想象的大
先看一个常见的例子：
struct Example {
char a; // 1 字节
int b; // 4 字节
short c; // 2 字节
};
你猜它在内存里占多大？按字段求和是 7 字节。但实际呢？
| 平台 | sizeof(Example) | 原因 |
|---|---|---|
| x86/x64 (默认 4 字节对齐) | 12 | b 对齐到 4 字节边界，a 后填充 3 字节；c 后填充 2 字节 |
| ARM (默认 4 字节对齐) | 12 | 同上 |
| ARM (使用 __attribute__((packed))) | 7 | 取消填充，但访问 b 可能产生非对齐访问异常 |
| RISC-V (默认 4 字节) | 12 | 与 x86 一致，但某些 RISC-V 核不支持非对齐访问 |
我在一个 AI 推理项目中，用 packed 结构体去读网络包，ARM 板子直接触发总线错误。为什么会这样？因为很多嵌入式平台（比如 Cortex-M3 之前的内核）硬件上不支持非对齐访问，一读就 fault。你想想看，这种坑你要是在算法适配时没注意，整个推理框架可能就得重写。
#pragma pack(push, 1) 或 __attribute__((packed)) 后，再按字节序列化。别依赖编译器默认布局。
4.2 数据对齐：CPU 读取数据的“胃口”
CPU 从内存读数据，不是一次读 1 字节，而是按“字”读——通常是 4 字节或 8 字节。如果数据地址不是字大小的倍数，CPU 就得读两次再拼起来。这就是性能杀手。我曾在优化一个卷积核时发现，关键性能瓶颈不是计算，而是非对齐访问导致的 cache miss 翻倍。
那么，对齐规则是什么？
- 基本类型对齐：int 按 4 字节对齐，short 按 2 字节，double 按 8 字节（在 64 位系统上）。
- 结构体对齐：按最宽成员对齐（比如含 double 就按 8 字节）。
- 数组对齐：数组整体按元素大小对齐，元素自身保持对齐。
举个例子：
struct AlignedStruct {
double d; // 8 字节，地址必须是 8 的倍数
int i; // 4 字节，后面填充 4 字节使总大小是 8 的倍数
char c; // 1 字节
// 最后填充 7 字节？不对，按最宽成员对齐到 8 字节
};
// sizeof(AlignedStruct) = 24 字节
实际项目中，我从网络收到的数据经常是字节流，直接强转成结构体会出问题。我用 memcpy 逐字段拷贝 + 手动对齐，虽然多了一次拷贝，但避开了非对齐陷阱。
4.3 缓存友好设计：从 DDR 到 CPU 的最后一公里
现代 CPU 的算力远远快于内存带宽。所以大部分时间，CPU 在等数据。这就是缓存发挥作用的地方——它把常用数据放在离 CPU 更近的 SRAM 里。可如果你数据结构设计不当，缓存就是摆设。
还记得我之前优化的一个图像处理管线吗？输入是一个二维数组 img[height][width]，每个像素是 RGB 三通道。原来代码按列循环：
for (int y = 0; y < height; y++) { // 行优先
for (int x = 0; x < width; x++) {
process(img[y][x]);
}
}
改成行优先遍历后，性能提升了 3 倍。原因很简单：C 语言中二维数组是按行连续存的，第一次访问 img[0][0] 时，CPU 会把这一行附近整个 cache line（通常 64 字节）都搬到 L1 缓存里。接下来再访问 img[0][1]、img[0][2] 就直接命中缓存，不用再到 DDR 里读。而列优先遍历每次都会跳到不同行，导致缓存频繁失效。
做成表格对比一下：
| 访问模式 | 缓存命中率 | 典型场景 |
|---|---|---|
| 行优先（stride=1） | 高（接近 100%） | 图像行扫描、矩阵乘法逐行累加 |
| 列优先（stride=width） | 低（可能不到 10%） | 图像列处理、转置后访问 |
| 随机访问 | 极低（取决于 locality） | 哈希表、指针链表遍历 |
| 按 block 分块访问 | 高（利用时间局部性） | tiled 矩阵乘法、Convolution 分块 |
4.4 结构体设计：把热点成员放在前面
你可能会想，结构体里成员顺序可能不重要？我曾经调一个搜索算法，结构体长这样：
struct Node {
double cost; // 8 字节
int index; // 4 字节
char flag; // 1 字节
float data[4]; // 16 字节
};
我们遍历这个结构体数组时，每次只访问 cost 和 index，极少访问 data 和 flag。但按默认顺序，cost 和 index 被 data 跨行了，导致每次取一个节点都要读 64 字节的 cache line，实际上只用了 12 字节。浪费率超过 80%。
优化很简单：把高频访问的成员放到结构体开头：
struct NodeOpt {
int index; // 4 字节
double cost; // 8 字节 （按最宽对齐后 index 后填充 4 字节）
float data[4]; // 16 字节
char flag; // 1 字节
// 最后填充 7 字节使结构体总大小 32 字节（对齐到 8）
};
这样 index 和 cost 加起来 16 字节，刚好在一个 cache line 里。访问第一个成员时顺便带上了第二个成员。我把这招用在一个路网规划引擎上，搜索速度提升了 40%。
4.5 数据结构选择：链表 vs 数组 vs AoS vs SoA
不同平台对数据结构的支持差异也很大。举个例子，链表在每个节点里存一个 next 指针，遍历时每次访问一个新节点，缓存就 miss 一次。在 x86 上有硬件预取能减轻一点，但在低端嵌入式 MCU 上，链表几乎就是性能灾难。我推荐你优先用数组或者 std::vector。如果非要用链表，记得一次性分配连续内存（比如用内存池）。
另一个经典选择：AoS（Array of Structures） 和 SoA（Structure of Arrays）。看个例子：
// AoS 方式
struct Particle {
float x, y, z;
float vx, vy, vz;
float mass;
};
Particle particles[1000];
// SoA 方式
struct ParticleSoA {
float x[1000], y[1000], z[1000];
float vx[1000], vy[1000], vz[1000];
float mass[1000];
};
如果我写一个只更新 x 坐标的循环，AoS 每次读一个粒子会拉进 28 字节，但其实我只需要 4 字节，其余 24 字节都浪费了。而 SoA 里 x 数组是连续存储的，for 循环访问 x[i] 就是连续地址，缓存效率极高。我在做粒子物理仿真时，从 AoS 切换到 SoA，性能翻了一倍。
当然，SoA 也有缺点：如果同时需要访问 x、y、z，它会分散在三个不同的内存区域，可能比 AoS 差。需要根据你的实际访问模式来选。
- 如果一次循环只访问少数几个成员 → 用 SoA
- 如果一次循环访问一个粒子的多个成员 → 用 AoS
- 如果混合模式 → 考虑 AoS 但按访问频率重新排列成员
4.6 知识框架总览
下面我用一张图把今天讲的内容串起来。你一看就能明白这三个维度是怎么影响算法适配的。
4.7 实操避坑总结
最后，我把这些年踩过的坑整理成清单，你写代码时对着检查：
- 检查结构体 sizeof：不要凭直觉，在每个平台上用
printf("%zu", sizeof(s))打印一遍。我曾经在 x86 上写死一个结构体大小 40，换到 RISC-V 变成 48，直接导致内存越界。 - 序列化用固定宽度类型：别用
int，用int32_t、uint16_t，避免不同平台int长度不同。 - 避免非对齐指针强转：从字节流里直接
*(int*)buf非常危险。应该先用memcpy到对齐的变量。 - 多级缓存不迷糊：优化时优先关注 L1 cache line（64 字节），然后是 L2 和 L3。热点数据尽量塞满一个 cache line。
- 区分访存模式：算复杂度和带宽时，别忘了缓存 miss 的时间可能比计算本身还高。
嗯，这一章的内容就到这。数据结构与算法在异构平台上的适配，核心就是三件事：看布局、对齐、和缓存打法。你只要在实践中多测多对比，就能积累出肌肉记忆。