在 low-latency C++ 中,效能瓶頸往往不在於程式做了多少計算,而在於 CPU 為了取得資料究竟付出了多少成本。當多個 thread 同時存取資料時,我們通常會先思考如何避免 lock、如何降低 contention,或如何讓資料結構更有效率。但在更底層的硬體層級,還有一個更根本的問題:這份資料究竟屬於哪一個 thread?
如果不同 thread 頻繁修改彼此需要的資料,即使它們沒有共享同一把 lock,仍然可能因為 cache coherence、cache line bouncing、false sharing,甚至 NUMA 等因素產生額外成本。因此,Data Ownership 不只是軟體設計上的概念,也可以成為連結 C++ 資料結構與 CPU memory hierarchy 的一種思維模式。接下來,我們將從不同角度重新討論資料結構的設計,以及不同 thread 之間究竟應該共享多少資料。
1. Thread Execution —— 資料的歸屬
情況 1 —— Thread-local ownership:
Thread 0
ㅤ└── OrderBook A
Thread 1
ㅤ└── OrderBook B
Thread 2
ㅤ└── OrderBook C
情況 2 —— Shared ownership:
Thread 0 ─┐
Thread 1 ─┼── shared OrderBook
Thread 2 ─┘
前者讓每個 OrderBook 的 mutable state 由單一 thread 負責修改,因此可以大幅減少跨 thread 的 synchronization。這種設計通稱可以大幅降低:
這也是為什麼很多 high-performance system 會採取 single-writer principle,讓某一份 mutable data 儘可能只有一個 thread 負責修改。
2. Memory Hierarchy —— 資料離 CPU 有多遠
CPU 存取資料的成本並不只取決於資料本身,而與資料位於 memory hierarchy 的哪一層高度相關。一般而言,越靠近 execution core 的儲存層級容量越小,latency 也會越低;而較大的 cache 與 DRAM 則提供更大的容量,但通常需要付出更高的存取成本。
因此,Low-Latency C++ 的設計不只是考慮需要多少記憶體,更需要考慮資料是否能被有效地留在較快的 cache 中,以及 CPU 是否能以較少的 memory access 取得所需資料。這也是 cache localit 與 data layout 會如此重要的原因。
3. NUMA —— 當一台機器不再只有一種 RAM
當系統進入 multi-socket server:
CPU 0
ㅤ├── L1/L2
ㅤ├── L3
ㅤ└── Memory 0
CPU 1
ㅤ├── L1/L2
ㅤ├── L3
ㅤ└── Memory 1
這時 CPU 0 → Memory 0 和 CPU 0 → Memory 1 成本可能不同,這就是 Non-Uniform Memory Access (NUMA) 的觀念 —— 不只是單純思考 data 放在哪裡,還要考量到跟哪個 CPU 在一起。
於是前兩篇文提到的 DOD 又可以延伸成:
Data Layout → Data Placement → CPU Affinity → NUMA Locality
4. DOD 與 Ownership
Data-Oriented Design
│
┌─────────┼─────────┐
↓ ↓ ↓
Access Pattern Data Layout Data Ownership
│ │ │
↓ ↓ ↓
Hot / Cold AoS / SoA Thread Local
│ AoSoA Single Writer
↓ │ │
Working Set ↓ ↓
│ Cache Coherency
↓ │ │
Cache ↓ ↓
Locality SIMD False Sharing
│ │ │
└─────────┼─────────┘
↓
Memory Hierarchy
↓
Cache / TLB / NUMA
↓
CPU Microarchitecture
↓
┌─────┴──────┐
↓ ↓
Throughput Latency
│ │
└─────┬──────┘
↓
Profiling
↓
Measurement