3、数据局部性原理：时间局部性与空间局部性
各位同学，今天我们来聊一个非常实在的话题——数据局部性。说实话，我在做回测系统优化之前，对这东西的理解也就停留在「CPU缓存那点事」上。直到有一次，我负责的一个日频回测系统，跑一次全市场回测要整整47分钟。我当时就纳闷了：逻辑明明很简单，为什么这么慢？
后来一分析，发现罪魁祸首就是数据访问模式。嗯，今天我们就来彻底搞明白这件事。
3.1 什么是时间局部性与空间局部性？
先看两个核心概念。说白了，它们描述的是程序访问内存的「规律性」。
- 时间局部性：如果一个数据被访问了，那么它在不久的将来很可能再次被访问。
- 空间局部性：如果一个数据被访问了，那么它附近的数据也很可能被访问。
举个例子你就明白了。你写一个循环：
for (int i = 0; i < 1000000; i++) {
sum += prices[i];
}
这里 prices[i] 被顺序访问，相邻地址的数据连续读取——这就是空间局部性。而 sum 变量每次循环都被累加——这就是时间局部性。
你想想看，CPU的L1缓存才多大？32KB左右。如果数据访问没有局部性，缓存命中率会低得可怜，CPU大部分时间都在等内存。我见过一个极端案例，某团队的回测引擎因为数据布局问题，缓存缺失率高达40%，性能直接腰斩。
3.2 回测场景下的局部性分析
好，理论说完了。我们来看看回测系统里最典型的两种遍历方式。
3.2.1 逐K线遍历
这是最自然的做法。你有一根K线，然后检查所有信号是否触发：
// 伪代码：逐K线遍历
for each bar in bars:
for each strategy in strategies:
if strategy.should_enter(bar):
execute_order(strategy, bar)
这种模式有什么特点？
- 空间局部性极好：因为
bar的数据是连续存储的，顺序读取时CPU预取器能完美工作。 - 时间局部性一般：每个
bar只被访问一次，不会重复读。
我个人习惯用这种模式做日频回测。数据量不大，逻辑简单，缓存友好度很高。
3.2.2 逐信号遍历
另一种常见做法是：先遍历所有信号，再去找对应的K线数据：
// 伪代码：逐信号遍历
for each signal in signals:
bar = get_bar_by_timestamp(signal.timestamp)
if bar is not None:
execute_order(signal, bar)
这里问题就来了。
- 空间局部性极差：信号的时间戳是乱序的，你一会儿读第1000根K线，一会儿读第5根，CPU预取器完全失效。
- 时间局部性也很差：每根K线可能只被访问一次，而且访问间隔很大。
我在项目中遇到过这样一个场景：一个高频回测系统，信号数量是K线数量的10倍。用逐信号遍历，回测时间从2分钟暴涨到18分钟。为什么？因为每次 get_bar_by_timestamp 都是一次随机内存访问，缓存命中率不到10%。
避坑指南：我曾经天真地以为「反正数据都在内存里，怎么访问不都一样？」结果被现实狠狠教育了一顿。内存随机访问和顺序访问的延迟差距，可以轻松达到10倍以上。尤其是在多策略并行回测时，逐信号遍历会让你的缓存变成摆设。
3.3 如何利用局部性提升性能？
知道了问题，解决方案就清晰了。核心思路就一句话：让数据访问模式匹配硬件的工作方式。
3.3.1 数据重排：按时间序存储
把信号也按时间排序，然后和K线数据一起顺序遍历：
// 优化后：双指针顺序遍历
sort_signals_by_time(signals)
i = 0
for each bar in bars:
while i < signals.length and signals[i].timestamp <= bar.timestamp:
if signals[i].should_enter(bar):
execute_order(signals[i], bar)
i++
这样，K线数据和信号数据都是顺序访问的。缓存命中率从10%直接飙升到95%以上。我在一个实盘回测系统中应用了这个优化，回测时间从47分钟降到了6分钟。嗯，你没看错，7.8倍的提升。
3.3.2 结构体布局：SoA vs AoS
另一个容易被忽视的点是结构体布局。假设你有这样的数据结构：
// AoS（Array of Structs）—— 不推荐
struct Bar {
double open;
double high;
double low;
double close;
long volume;
};
Bar bars[1000000];
如果你只遍历 close 价格，那么 open、high、low、volume 都会被加载到缓存行里，但根本用不上。这就是缓存污染。
改成SoA（Struct of Arrays）就好多了：
// SoA（Struct of Arrays）—— 推荐
struct Bars {
double* open;
double* high;
double* low;
double* close;
long* volume;
};
这样遍历 close 时，只有 close 数组被加载到缓存，其他字段不会干扰。我记得有一次优化一个多因子回测系统，仅仅把AoS改成SoA，性能就提升了3倍。说白了，就是让缓存只做有用功。
个人经验：如果你在写回测引擎，建议一开始就用SoA布局。虽然代码写起来稍微麻烦一点，但后期优化空间大得多。我见过太多项目，AoS写到一半想改SoA，结果重构成本高得吓人。
3.4 知识体系总览
下面这张图总结了本章的核心逻辑。我建议你仔细看看，尤其是「数据重排」和「结构体布局」这两条路径，它们是最容易出效果的地方。
3.5 小结
今天的内容其实就三个要点：
- 时间局部性和空间局部性是硬件友好的访问模式，违背了就要付出代价。
- 逐K线遍历天然具有空间局部性，而逐信号遍历则相反。能用前者就别用后者。
- 数据重排和SoA布局是两个立竿见影的优化手段。我建议你在设计阶段就考虑进去，而不是等性能出问题了再回头改。
好了，这一章就到这里。记住：让数据访问模式去适应硬件，而不是让硬件来迁就你的代码。这是性能优化的底层逻辑。
公众号:蓝海资料掘金营，微信deep3321