对齐、SoA 与数据布局 — 内存与性能

周一上午十点,你在国内某头部私募的成交分析(execution analytics)桌,昨夜成交回报落了一份 1M 条沪深300成分股的明细。组长要的不复杂:这一篮子今日的 VWAP(volume-weighted average price)是多少?你 30 行 C++17 写完,跑一遍 4.3 ms。下午组长又问:能不能把它压到 1 ms 以内——他想在分钟级用这个指标做实时风控。算法没动、数据没动、机器没换,你怎么再快三倍?

答案不在算法那一层,在数据布局(data layout)这一层。L1 教你装上了一组缓存延迟数字、装上了 perf 与 Google Benchmark。本课用同一根剖析器,把那 4.3 ms 压到大约 1.4 ms——不写一行 SIMD、不改算法,只重排你那条 struct Trade 在内存里的字节顺序,再把"一条记录对应一个对象"翻成"每个字段一根连续数组"。

对齐:硬件强制的字节起始位置

CPU 不在任意地址上读 64 位 double。x86_64 上一个 double 必须落在 8 字节倍数的地址,一个 int 必须落在 4 字节倍数,一个 8 字节指针必须落在 8 字节倍数。x86 上未对齐的 load 不会崩——硬件拆成两次 load 再合并——但比对齐 load 慢;ARM 的若干老核会直接 trap。C++ 在类型系统里把这条规则固化:alignof(T) 返回 T 的对齐要求,语言保证任何 T 类型对象的起始地址是 alignof(T) 的倍数。

由此两个直接结论。第一,alignof(T) 必然整除 sizeof(T)——否则 T[N] 的连续元素不可能全部对齐。第二,当你把字段塞进一个 struct,编译器会在字段之间和结构末尾插入填充字节(padding),以保持每个字段处在它的自然对齐位置。这件事在 struct Trade 上最有教学价值。

字段重排:零行为变化的最便宜优化

// Naive ordering: 24 bytes (11 bytes padding)
struct TradeNaive {
    char side;     // offset 0, then 7 bytes padding
    double price;  // offset 8
    int qty;       // offset 16, then 4 bytes trailing padding
};
static_assert(sizeof(TradeNaive) == 24);

// Reordered: largest-to-smallest; 16 bytes (3 bytes trailing padding)
struct Trade {
    double price;  // offset 0
    int qty;       // offset 8
    char side;     // offset 12, then 3 bytes trailing padding
};
static_assert(sizeof(Trade) == 16);

TradeNaive 是"按业务读起来顺手"的写法:方向在前、价居中、量在末。代价是 24 字节,其中 11 字节是空填充——46% 的内存被对齐规则吞掉。把 double price 提到最前、其后 int qty、最末 char side,总尺寸压回 16 字节、内存少占 33%,而对外可见的字段类型与语义一字未改。规则:字段按自然对齐从大到小排,通常就消灭了内部填充。

alignas(64):显式过对齐到缓存行

alignas(N) 是你显式告诉编译器"把这个类型的实例起始地址提到 N 的倍数"的语法。把它定在 64,意思是把对象按缓存行边界(cache-line boundary)对齐——意思是这个对象绝不会跨在两根缓存行上、一次 load 必定取完。

// Force this struct onto its own cache line so loads of `state` never straddle
// two lines, and so adjacent unrelated globals never share its line.
// Standard-blessed alternative (some libstdc++ versions report 128 here):
//   alignas(std::hardware_destructive_interference_size) struct HotState { ... };
alignas(64) struct HotState {
    double last_price;
    double rolling_mean;
    std::uint64_t tick_count;
};
static_assert(sizeof(HotState) == 24);
static_assert(alignof(HotState) == 64);

HotState 的有效载荷只有 24 字节,加 alignas(64) 后每个实例独占 64 字节(末尾 40 字节是浪费的内存)。代价是空间、收益是两件事:一,任何对 HotState 任意成员的 load 都只付一次缓存行取数;二,如果它是其缓存行上的第一个对象,硬件预取器对后续访问也能顺畅工作。规则:热路径上小于 64 字节的结构,padding 并 align 到 64。std::hardware_destructive_interference_size 是 C++17 在 <new> 里给的"线程间避免伪共享所需的最小间距"常量;x86_64 通常报 64,但部分 libstdc++ 因为相邻缓存行预取器(adjacent-line prefetcher)报 128。本课代码用字面 alignas(64) 保证在任何目标机器上都正确;线程间的伪共享(false sharing)本身,留给 3.4.4。

AoS 与 SoA:本模块最有杠杆的布局决定

std::vector<Trade> 是 C++ 的默认布局——内存里是 [Trade_0, Trade_1, Trade_2, ...] 连续排列,这种"对象数组"形式叫结构体数组(array of structures, AoS)。把它翻过来:每个字段单独一个 std::vector,N 条交易就变成"价格连续、数量连续、方向连续"的三条平行数组,这种形式叫数组结构体(structure of arrays, SoA)。

using TradeAoS = std::vector<Trade>;

struct TradeBatch {           // SoA form
    std::vector<double>    price;
    std::vector<int>       qty;
    std::vector<char>      side;
};

double vwap_aos(const TradeAoS& trades) {
    double num = 0.0;
    double den = 0.0;
    for (const auto& t : trades) {
        num += t.price * static_cast<double>(t.qty);
        den += static_cast<double>(t.qty);
    }
    return num / den;
}

double vwap_soa(const TradeBatch& tb) {
    double num = 0.0;
    double den = 0.0;
    for (std::size_t i = 0; i < tb.price.size(); ++i) {
        num += tb.price[i] * static_cast<double>(tb.qty[i]);
        den += static_cast<double>(tb.qty[i]);
    }
    return num / den;
}

哪个更快,完全取决于访问模式(access pattern)。AoS 在循环每次触碰一条记录的所有字段时更优——比如 if (t.side == 'B') notify_buyer(t.price, t.qty);:三个字段一起用,一根缓存行 load 把它们一起拽进来,顺手且贴合 OO 心智模型。SoA 在循环对很多记录只触碰一两个字段时更优——VWAP 的公式是

\text{VWAP} = \frac{\sum_{i} p_i \, q_i}{\sum_{i} q_i}

每次迭代只用 price 和 qty、完全用不上 side。AoS 路径上(sizeof(Trade) = 16)一根 64 字节缓存行装 4 条 trade、16 字节给 price、16 字节给 qty、剩下给 side 与填充——只有一半左右的字节在做有用功。SoA 路径上,计算 $\sum p_i q_i$ 那一半的循环里,一根缓存行装 8 个 double 价格或 16 个 int 数量,整根行 100% 都是循环要用的数据。同样的计算量,缓存占用降到原来的三分之一到四分之一;内循环也变成"连续 double"形态,第 4 课的自动向量化(auto-vectorization)正是吃这种形态。

工作例:1M 条 trade 的 VWAP

确定性初始化是让 cn 与 us 两套实现算出的 VWAP 数值按字节相同的前提——任何"我跑出 12.4571、对面跑出 12.4570"的差异都意味着布局优化破坏了语义,而不是数值精度问题。

static constexpr std::size_t N = 1'000'000;

void populate(TradeAoS& aos, TradeBatch& soa) {
    aos.resize(N);
    soa.price.resize(N);
    soa.qty.resize(N);
    soa.side.resize(N);
    for (std::size_t i = 0; i < N; ++i) {
        double p = 100.0 + 0.01 * static_cast<double>(i % 200);
        int    q = 100 * (static_cast<int>(i % 10) + 1);
        char   s = (i % 2 == 0) ? 'B' : 'S';
        aos[i] = Trade{p, q, s};
        soa.price[i] = p;
        soa.qty[i]   = q;
        soa.side[i]  = s;
    }
}

两套布局填的是完全相同的 1M 条 trade:价格在 100.00 到 101.99 之间循环 200 档,数量在 100 到 1000 之间循环 10 档,买卖方向 B / S 交替。把两个 VWAP 函数挂上 Google Benchmark:

static void BM_VWAP_AoS(benchmark::State& state) {
    TradeAoS aos; TradeBatch soa;
    populate(aos, soa);
    for (auto _ : state) {
        benchmark::DoNotOptimize(vwap_aos(aos));
    }
}
BENCHMARK(BM_VWAP_AoS);

static void BM_VWAP_SoA(benchmark::State& state) {
    TradeAoS aos; TradeBatch soa;
    populate(aos, soa);
    for (auto _ : state) {
        benchmark::DoNotOptimize(vwap_soa(soa));
    }
}
BENCHMARK(BM_VWAP_SoA);

BENCHMARK_MAIN();

在 L1 那台 Intel Xeon Gold 6342(Ice Lake-SP,单核锁定)上跑,AoS 路径大约 3–5 ms,SoA 路径大约 1–2 ms——SoA 比 AoS 快 2–4 倍。绝对值随宿主机漂移,比例在任何现代 x86 上稳定。要证明加速来自缓存而非测量伪影,把 L1 的工具拿来:

taskset -c 2 perf stat -e cache-misses,cache-references ./vwap_bench --benchmark_filter=BM_VWAP_AoS
taskset -c 2 perf stat -e cache-misses,cache-references ./vwap_bench --benchmark_filter=BM_VWAP_SoA

AoS 路径的 cache-misses / cache-references 比例通常是 SoA 路径的 2 到 3 倍。这个差就是 SoA 加速的全部出处——不是魔法。

操作规则与下一课

AoS 仍是合理默认:它和"一条 trade 一个对象"的 OO 心智模型对齐,写起来快、读起来顺。把代码翻成 SoA 必须三件事同时成立:(a) 热循环只触碰一部分字段、(b) 剖析器说瓶颈是缓存、(c) 结构足够大,使一根缓存行里没用的字段占了一半以上。决策是局部的——同一个程序,订单入库路径完全可以保留 std::vector<Trade>(因为每条入库都用上三个字段),分析路径(VWAP / 成交量 / 波动率)单独维持一个 TradeBatch 投影。这正是国内 quant 桌订单簿核心的实际做法:撮合循环只读价格列,插入与撤单循环只动数量列,完整的 Level 记录只在打印订单簿快照时才被需要;SoA 在这里不是"高级写法",是被访问模式逼出来的形状。

本课没写一行 SIMD——那是第 4 课的任务。但 SoA 是 SIMD 的前提:自动向量化、__restrict__、<immintrin.h> 里的 AVX2 内循环都要求"一段连续 double 在一段连续内存里",而你刚刚把数据布成了这个形状。第 3 课先去处理 std::vector<double> 自己捅出来的那一刀:1M 条 trade 的 SoA 数组本身要走 new / delete,而在更高频的工作流里——比如每个 tick 创建一个生命期只有几微秒的暂存数组——ptmalloc2 那 20–30 ns 的快路径就成了新的瓶颈。下一课用 arena 与 pool 分配器把它压到 1–2 ns。

练习

Exercise

(a) 用 g++ -std=c++17 -O2 -g vwap_bench.cpp -lbenchmark -lpthread -o vwap_bench 编译上面的"两个 struct / 两个 VWAP"工作例,然后跑 ./vwap_bench,读出 BM_VWAP_AoS 与 BM_VWAP_SoA 的每迭代纳秒数。SoA 应当只占 AoS 的 30%–50%(即 2–3 倍加速)。(b) 把 struct Trade 改回朴素字段顺序(char side; double price; int qty; —— sizeof 从 16 跳到 24),重跑基准。AoS 路径应进一步变慢,SoA 路径不变。一句话说明为什么 SoA 路径对 AoS 的字段顺序不敏感。(c) 运行 taskset -c 2 perf stat -e cache-misses,cache-references ./vwap_bench --benchmark_filter=BM_VWAP_AoS 与同样针对 BM_VWAP_SoA 的一遍,计算两个版本的缓存未命中率(cache-misses / cache-references),写下 AoS 与 SoA 的未命中率比值。(d) 把两个函数算出的 VWAP 值 printf 出来,确认它们是按字节相同的两个 double。

提示

SoA 的 vwap_soa 直接读 tb.price 与 tb.qty 两条独立数组,根本不接触 struct Trade——struct 的字段顺序与填充和 SoA 的内循环没有任何关系,所以重排 Trade 只影响 AoS 路径。

提示

AoS 路径每根 64 字节缓存行装 4 条 Trade(每条 16 字节),只有 12 字节(price 8 + qty 4)是 VWAP 真正要的;SoA 路径每根缓存行 100% 都是 price 或 qty,因此把 AoS 的 cache-miss 率推到 SoA 的 2–3 倍。