20.7 C++ 量化面试专题

C++ 量化面试不是语法竞赛。面试官真正关心的是：你能否在延迟、吞吐、正确性和可维护性之间做出可解释的取舍。一个会写 std::thread 却说不清数据竞争的人，通常不如一个能画出 happens-before 关系、再选择最简单同步原语的人。

概念详解

C++ vs Python：为什么高性能量化岗位必考 C++

Python 适合研究迭代、数据分析和策略编排；C++ 适合行情接入、订单管理、撮合、定价内核和低延迟执行。面试差异不在“哪门语言更高级”，而在资源控制粒度。

维度	Python 面试常问	C++ 面试常问	量化场景
内存	对象引用、NumPy 视图	生命周期、RAII、对齐、分配器	行情对象是否触发堆分配
并发	多进程、asyncio、GIL	线程、原子、内存序、无锁结构	行情线程到策略线程的传递
性能	向量化、批处理、JIT	cache、分支、SIMD、系统调用	单条订单尾延迟
错误模型	异常、动态类型	UB、悬空引用、数据竞争	偶发错误是否可重现
数据结构	dict、deque、heapq	布局、迭代器失效、复杂度常数	订单簿价格档与订单队列
测试	单元测试、属性测试	sanitizer、benchmark、并发压力	正确性与 P99 延迟同时验证

高质量开场

“我会先确认目标是吞吐还是尾延迟、生产者和消费者数量、能否阻塞、容量是否有界，再决定用 mutex、SPSC ring buffer 还是 MPMC queue。”

多线程与同步原语

std::thread 启动后必须 join() 或 detach()，否则可连接线程析构时会调用 std::terminate()。C++20 的 std::jthread 能在析构时请求停止并等待线程结束，更适合有明确 owner 的后台任务。

#include <thread>
#include <vector>

std::vector<int> values(1'000'000, 1);
long long left = 0, right = 0;
std::thread t1([&] { for (int x : values) left += x; });
std::thread t2([&] { for (int x : values) right += x; });
t1.join();
t2.join();

上例没有数据竞争：两个线程写不同标量，主线程在 join() 后读取；但两线程都遍历全部数据，造成重复计算。面试中应先检查正确性和任务划分，再讨论并行加速；join() 让线程完成 happens-before 主线程继续执行。

mutex 适合临界区短、竞争可控、正确性优先的场景。用 RAII 管理锁：

#include <mutex>
#include <unordered_map>

std::mutex mutex;
std::unordered_map<int, long> positions;

void add_position(int symbol, long delta) {
    std::lock_guard<std::mutex> lock(mutex);
    positions[symbol] += delta;
}

std::scoped_lock 可一次获取多把锁并避免常见锁序死锁。不要仅凭“读多写少”换成 shared_mutex，共享锁的管理成本与写者饥饿必须实测。

condition_variable 用于等待状态变化，不是事件计数器。等待必须由同一 mutex 下的谓词保护，以应对虚假唤醒：

std::unique_lock<std::mutex> lock(mutex);
cv.wait(lock, [&] { return stopped || !queue.empty(); });
if (stopped && queue.empty()) return;
auto task = queue.front();
queue.pop();

生产者应在锁内修改 queue 或 stopped，解锁后 notify_one()／notify_all()。谓词决定是否继续，通知只负责唤醒重新检查。

atomic 保证单个原子对象的操作不可撕裂，却不能自动保护“现金减少、持仓增加”这类跨变量不变量：

std::atomic<long> sequence{0};
long next_sequence() {
    return sequence.fetch_add(1, std::memory_order_relaxed);
}

序列号只要求唯一递增且不发布其他数据时，relaxed 足够；若原子标志表示“普通数据已就绪”，则需要 acquire-release 或锁。

四类并发故障

故障	定义	量化系统例子	处理方式
死锁	各线程循环等待对方持有的资源	风控锁与订单锁获取顺序相反	固定锁顺序、scoped_lock、缩小临界区
活锁	线程都在运行，但互相礼让而无进展	两个重试循环不断撤回 CAS	随机退避、有界重试、仲裁者
饥饿	某线程长期得不到资源	高频读锁让写线程无法更新配置	公平队列、限制读批次、专用线程
优先级反转	高优先级线程等待低优先级线程持锁	执行线程等待日志线程占用共享锁	避免共享锁、优先级继承、异步日志

死锁的 Coffman 四条件是互斥、占有且等待、不可抢占、循环等待。破坏任一条件都可避免死锁；工程上最常用的是统一锁顺序。

内存模型：回答 happens-before，而不是背枚举值

C++ 原子内存序常见选择：

• memory_order_relaxed：只保证该原子操作不可撕裂及其修改顺序，不建立跨变量同步。
• memory_order_release：其前的写入不能被重排到 release 之后。
• memory_order_acquire：其后的读取不能被重排到 acquire 之前。
• memory_order_acq_rel：用于同时读写的原子操作，如成功的 read-modify-write。
• memory_order_seq_cst：除 acquire-release 语义外，所有 seq_cst 操作进入单一全局顺序。

经典发布模式：

#include <atomic>
#include <cassert>

int payload = 0;
std::atomic<bool> ready{false};

void producer() {
    payload = 42;
    ready.store(true, std::memory_order_release);
}

void consumer() {
    while (!ready.load(std::memory_order_acquire)) {
    }
    assert(payload == 42);
}

消费者的 acquire 读取到生产者的 release 值后，payload = 42 happens-before 消费者读取 payload。若两处都改成 relaxed，读取普通变量 payload 就没有同步保证。

性能优化：从数据移动开始

低延迟优化的优先级通常是：测量 → 算法 → 数据布局 → 分配 → 同步 → 指令级优化。直接写 SIMD 往往不是第一步。

Cache line 与 false sharing

两个线程频繁写各自独立计数器，如果计数器在同一 cache line，会因一致性协议反复争夺该行。

#include <atomic>
#include <cstddef>

struct alignas(64) Counter {
    std::atomic<long> value{0};
};

Counter market_data_count;
Counter order_count;

64 是常见 cache line 大小，但生产代码应依据目标硬件和 std::hardware_destructive_interference_size。过度 padding 会增加内存占用和 cache miss。

Branch prediction

分支是否昂贵取决于可预测性。订单类型若高度稳定，分支预测可能很好；若方向近乎随机，错误预测会冲刷流水线。优化前要用硬件性能计数器确认 branch-miss，而不是把所有 if 改成位运算。

SIMD

SIMD 适合连续、同构、无依赖计算，如批量 Greeks、收益归一化和风控限额检查。前提是数据连续、对齐合理、尾部处理正确。结构数组 AoS 便于对象建模，数组结构 SoA 往往更利于向量化。

布局	示例	优势	劣势
AoS	vector<Quote>	单对象访问自然	批量读取单字段会带入无关数据
SoA	prices[]、sizes[]	连续字段利于 SIMD	对象一致性维护更复杂

典型算法题清单

按岗位选择训练顺序

订单簿无锁队列内存池LRU Cache

勾选题目，查看第一步提醒。

题目	必须先问	目标复杂度	高频追问
Order Book	价格精度、撮合规则、撤单方式	加单 $O(\log L)$，档内 FIFO	如何做到按订单号 $O(1)$ 撤单
SPSC Queue	单／多生产者、容量、阻塞	入队出队 $O(1)$	wrap-around 与 ABA 是否相关
Memory Pool	对象大小是否固定、线程模型	分配释放 $O(1)$	对齐、析构、跨线程归还
LRU Cache	get 是否更新 LRU、返回语义	get／put 平均 $O(1)$	锁粒度、迭代器失效
Singleton	生命周期、初始化失败处理	首次初始化一次	静态初始化线程安全起始版本
Timer Wheel	时间精度、取消定时器	插入／触发近似 $O(1)$	时钟跳变和漂移

数学原理

Amdahl 定律与线程上限

若程序串行比例为 $s$，使用 $N$ 个线程的理论加速比为：

$$Speedup(N)=\frac{1}{s+\frac{1-s}{N}}$$

即使有无限线程，加速比上限也是 $1/s$。当串行比例为 $5\mathrm{\%}$ 时，上限为 20 倍；盲目从 32 线程加到 64 线程不会翻倍。

CPU-bound 与 I/O-bound 的线程估算

CPU 密集型任务可从“可用物理核心数”起步，并为 OS、行情接入、风控或其他关键线程预留核心。I/O 密集型任务可粗略用：

$$N_{threads}\approx N_{cores}\left(1+\frac{W}{C}\right)$$

其中 $W$ 是等待时间，$C$ 是计算时间。该式只是初始配置，最终必须以吞吐、P50／P99／P99.9 延迟、上下文切换和 CPU 利用率验证。

Little 定律

稳定系统中：

$$L=\lambda W$$

若每秒到达 100000 条消息，平均系统停留时间为 $50\mu s$，则系统内平均有 5 条消息。该关系可用于检查队列长度、批处理规模和延迟测量是否自洽。

无锁不等于 wait-free

• Blocking：线程可能因锁或系统调用暂停。
• Lock-free：系统整体持续进展，但某个线程可能饥饿。
• Wait-free：每个线程在有限步骤内完成操作。

面试中说“用了 CAS，所以是 lock-free”不充分。需要说明失败重试是否可能无限、内存回收是否安全，以及算法面对抢占线程能否整体进展。

Python实战

C++ 代码无法在 Pyodide 中直接编译执行，因此本节用 Python 对线程预算和数据结构不变量做可运行验证；完整 C++ 实现用于白板和本地编译练习。

用 Amdahl 定律评估线程预算

PYTHON13 行 · 471 B

📄此处有展示代码13 行 · 471 B展开 ▼

from __future__ import annotations


def amdahl_speedup(serial_fraction: float, threads: int) -> float:
    if not 0.0 <= serial_fraction <= 1.0:
        raise ValueError("serial_fraction 必须在 0 到 1 之间")
    if threads < 1:
        raise ValueError("threads 必须为正整数")
    return 1.0 / (serial_fraction + (1.0 - serial_fraction) / threads)


for n in [1, 2, 4, 8, 16, 30, 32, 64]:
    print(f"threads={n:>2}, speedup={amdahl_speedup(0.08, n):.2f}x")

▶ 点击展开可浏览运行结果

线程数  理论加速比  新增线程边际收益
     1        1.00            1.0000
     2        1.85            0.8519
     4        3.23            0.6396
     8        5.13            0.3985
    16        7.27            0.1973
    24        8.45            0.1174
    30        9.04            0.0855
    32        9.20            0.0778
    48       10.08            0.0413
    60       10.49            0.0285

结论：先保留行情、OS 和风控所需核心，再用基准测试决定线程数。

解释输出时要强调：这是计算上限，不包含锁竞争、cache miss、NUMA、超线程、调度和热节流。

用模型测试 LRU 不变量

PYTHON37 行 · 1.0 KB

📄此处有展示代码37 行 · 1.0 KB展开 ▼

from collections import OrderedDict


class ReferenceLRU:
    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity 必须为正")
        self.capacity = capacity
        self.data: OrderedDict[str, int] = OrderedDict()

    def get(self, key: str) -> int | None:
        if key not in self.data:
            return None
        self.data.move_to_end(key, last=False)
        return self.data[key]

    def put(self, key: str, value: int) -> None:
        if key in self.data:
            del self.data[key]
        self.data[key] = value
        self.data.move_to_end(key, last=False)
        if len(self.data) > self.capacity:
            self.data.popitem(last=True)

    def assert_invariants(self) -> None:
        assert len(self.data) <= self.capacity
        assert len(self.data) == len(set(self.data))


cache = ReferenceLRU(2)
cache.put("A", 1)
cache.put("B", 2)
assert cache.get("A") == 1
cache.put("C", 3)
assert cache.get("B") is None
cache.assert_invariants()
print(list(cache.data.items()))

▶ 点击展开可浏览运行结果

[('C', 3), ('A', 1)]

该 Python 模型可作为 C++ 实现的 oracle。生成随机操作序列，同时喂给 Python 参考模型和 C++ 被测实现，比只写几个固定用例更容易发现淘汰顺序错误。

实战题：线程安全 LRU Cache

设计采用 std::list 维护新旧顺序，std::unordered_map 保存键到链表迭代器。所有会读取或改变这两个容器的操作由同一把 mutex 保护。

#include <cstddef>
#include <list>
#include <mutex>
#include <optional>
#include <stdexcept>
#include <unordered_map>
#include <utility>

template <class Key, class Value>
class ThreadSafeLRU {
public:
    explicit ThreadSafeLRU(std::size_t capacity) : capacity_(capacity) {
        if (capacity == 0) throw std::invalid_argument("capacity must be positive");
    }

    std::optional<Value> get(const Key& key) {
        std::lock_guard lock(mutex_);
        auto it = index_.find(key);
        if (it == index_.end()) return std::nullopt;
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }

    void put(Key key, Value value) {
        std::lock_guard lock(mutex_);
        if (auto it = index_.find(key); it != index_.end()) {
            it->second->second = std::move(value);
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        items_.emplace_front(std::move(key), std::move(value));
        index_[items_.front().first] = items_.begin();
        if (items_.size() > capacity_) {
            index_.erase(items_.back().first);
            items_.pop_back();
        }
    }

private:
    using Entry = std::pair<Key, Value>;
    using Iterator = typename std::list<Entry>::iterator;
    const std::size_t capacity_;
    std::mutex mutex_;
    std::list<Entry> items_;
    std::unordered_map<Key, Iterator> index_;
};

复杂度：平均 get 与 put 为 $O(1)$。关键追问是返回值生命周期：这里返回副本，锁释放后安全；若返回引用或指针，另一线程可能立刻淘汰元素，接口就不安全。

实战题：多线程单例

C++11 起，函数内局部静态变量的初始化由语言保证线程安全，Meyers Singleton 是首选简洁答案。

class RiskConfig {
public:
    static RiskConfig& instance() {
        static RiskConfig config;
        return config;
    }

    RiskConfig(const RiskConfig&) = delete;
    RiskConfig& operator=(const RiskConfig&) = delete;

private:
    RiskConfig() = default;
};

不要手写未经同步的“双重检查锁定”。如果必须显式控制一次初始化，可使用 std::call_once 与 std::once_flag。还要主动讨论单例的测试隔离和隐藏依赖问题；“线程安全”不代表“架构合理”。

算法题：有界 SPSC lock-free queue

#include <array>
#include <atomic>
#include <cstddef>
#include <optional>


template <class T, std::size_t Capacity>
class SPSCQueue {
    static_assert(Capacity >= 2);

public:
    bool push(const T& value) {
        const auto tail = tail_.load(std::memory_order_relaxed);
        const auto next = increment(tail);
        if (next == head_.load(std::memory_order_acquire)) {
            return false;
        }
        buffer_[tail] = value;
        tail_.store(next, std::memory_order_release);
        return true;
    }

    std::optional<T> pop() {
        const auto head = head_.load(std::memory_order_relaxed);
        if (head == tail_.load(std::memory_order_acquire)) {
            return std::nullopt;
        }
        T value = buffer_[head];
        head_.store(increment(head), std::memory_order_release);
        return value;
    }

private:
    static constexpr std::size_t increment(std::size_t value) {
        return (value + 1) % Capacity;
    }

    std::array<T, Capacity> buffer_{};
    alignas(64) std::atomic<std::size_t> head_{0};
    alignas(64) std::atomic<std::size_t> tail_{0};
};

该实现只适用于单生产者、单消费者，并牺牲一个槽位区分空与满。把它直接用于 MPMC 是错误的。若 T 的复制可能抛异常或对象生命周期需要手工管理，还需扩展设计。

算法题：价格优先、时间优先订单簿骨架

#include <cstdint>
#include <deque>
#include <functional>
#include <map>
#include <optional>

struct Order {
    std::uint64_t id;
    int price_ticks;
    int quantity;
};

class OrderBook {
public:
    void add_bid(Order order) {
        bids_[order.price_ticks].push_back(order);
    }

    void add_ask(Order order) {
        asks_[order.price_ticks].push_back(order);
    }

    std::optional<Order> best_bid() const {
        if (bids_.empty()) return std::nullopt;
        return bids_.begin()->second.front();
    }

    std::optional<Order> best_ask() const {
        if (asks_.empty()) return std::nullopt;
        return asks_.begin()->second.front();
    }

private:
    std::map<int, std::deque<Order>, std::greater<int>> bids_;
    std::map<int, std::deque<Order>, std::less<int>> asks_;
};

这是可解释骨架，不是完整撮合引擎。完整答案还要处理部分成交、撤单索引、自成交规则、序列号、快照恢复和整数 tick。若要求按订单号 $O(1)$ 撤单，可在稳定节点容器上增加 order_id → iterator 索引。

算法题：固定块内存池的接口设计

面试中先定义约束：对象固定大小、池生命周期覆盖对象、单线程还是多线程、耗尽后返回空还是回退到堆。

#include <cstddef>
#include <memory>
#include <new>
#include <vector>

class FixedBlockPool {
public:
    FixedBlockPool(std::size_t block_size, std::size_t count)
        : block_size_(block_size < sizeof(Node*) ? sizeof(Node*) : block_size),
          storage_(std::make_unique<std::byte[]>(block_size_ * count)) {
        for (std::size_t i = 0; i < count; ++i) {
            release(storage_.get() + i * block_size_);
        }
    }

    void* acquire() noexcept {
        if (!free_) return nullptr;
        Node* node = free_;
        free_ = free_->next;
        return node;
    }

    void release(void* memory) noexcept {
        auto* node = static_cast<Node*>(memory);
        node->next = free_;
        free_ = node;
    }

private:
    struct Node { Node* next; };
    std::size_t block_size_;
    std::unique_ptr<std::byte[]> storage_;
    Node* free_ = nullptr;
};

该简化版本是单线程、未完整处理超对齐类型。高质量回答会明确这些边界，而不是声称它是通用分配器。

常见误区

误区	为什么错	面试中的修正表达
线程数永远等于核心数	忽略任务类型、预留核心和超线程	给初始值，再用基准测试决定
atomic 让一切线程安全	跨变量不变量仍可能破坏	画出共享状态与同步边界
lock-free 一定比 mutex 快	CAS 竞争和回收成本可能更高	先测竞争度与尾延迟
volatile 用于线程同步	C++ volatile 不建立 happens-before	使用 atomic 或 mutex
默认用 seq_cst 就完成分析	可能正确但无法证明设计理解	先说明同步关系，再选内存序
detach 可避免 join 阻塞	生命周期和退出顺序失控	用 jthread、stop token 或明确 owner
shared_mutex 读多就快	共享锁也有争用和饥饿	基于读写比例做 benchmark
padding 越多越好	增加 footprint 和 cache miss	只隔离高频写热点
benchmark 只看平均延迟	平均值掩盖抖动	报 P50、P99、P99.9 和最大值
微秒计时一次就可信	冷启动、频率变化和噪声很大	预热、重复、固定环境、统计分布
返回 cache 内对象引用	解锁后可能被并发淘汰	返回副本或设计受控访问器

未定义行为

数据竞争本身就是 Undefined Behavior，不是“偶尔读到旧值”。一旦存在 UB，编译器无需保留程序员直觉中的执行顺序。

小测验

题目 1

在 32 核机器上，合理的线程数是多少？
假设你要为实时定价任务设置工作线程，但尚未获得任务的等待比例、NUMA 拓扑和延迟目标。最佳回答是什么？

• AA. 固定为 32，因为一核一线程永远最优
• BB. 固定为 64，因为每个核心都有两个硬件线程
• CC. 没有固定答案；先分类负载、预留核心，再基准测试
• DD. 固定为 1，因为多线程一定引入抖动

💡查看答案与解析展开 ▼

正确答案：C

线程数取决于负载类型、NUMA 拓扑与延迟目标，没有固定答案。CPU-bound 可从略低于物理核心数（如 28—30，为 OS、行情、风控预留核心）起测，做了 CPU affinity 或服务独占才可测 32；I／O-bound 可以超过核心数。判据是吞吐、P99／P99.9 尾延迟、上下文切换、cache miss 与功耗的实测对比。A 错：一核一线程忽略了 OS 与关键服务也要占用 CPU。B 错：64 假设超线程给出线性加速，实际远非线性。D 错：单线程最稳定，但没有证据表明它满足吞吐目标。

面试官继续追问时怎么答？

CPU-bound、无共享状态的批计算，可从 28—30 个线程起测，为 OS、行情和风控预留核心；若做了 CPU affinity 或服务独占，可测试 32。I／O-bound 可以超过核心数。需要比较 16、24、28、30、32、48、64 等配置的吞吐、P99.9、上下文切换、cache miss 与功耗，而不是只看平均耗时。

实战练习

以下题目可直接用于 60—90 分钟模拟面试。每题先澄清约束，再写不变量和复杂度，最后编码。

题目	时限	主任务	必答追问
并发计数器	10 分钟	用 mutex、atomic、thread-local reduction 实现	fetch_add(relaxed) 何时足够
死锁排查	12 分钟	为 OrderBook／RiskBook 画 wait-for graph 并修复	scoped_lock 如何避免死锁
内存序	15 分钟	证明 ready 发布模式的 happens-before	多生产者时 bool 是否足够
False Sharing	10 分钟	设计硬件计数器实验并解释 padding	vector::reserve 是否有帮助
Order Book	35 分钟	新增、撤单、部分成交、best bid／ask	如何按订单号平均 $O(1)$ 撤单
SPSC Queue	25 分钟	用 $2^k$ 环形数组实现 push／pop	非平凡析构类型如何处理
Memory Pool	25 分钟	固定大小对象池与耗尽策略	跨线程释放如何影响 locality
线程安全 LRU	30 分钟	实现 get／put／size 并压力测试	linearization point 在哪里
Singleton	10 分钟	Meyers Singleton，再改依赖注入	为什么后者更容易测试
性能分析	15 分钟	平均延迟下降但 P99.9 恶化时决策	上线前还需要哪些数据

Order Book 验收条件：价格用整数 tick；相同价格按 sequence 成交；空档位及时删除；订单数量不得为负；快照回放结果确定。

C++ 知识图谱

并发正确性

thread／jthread → mutex／condition_variable → atomic → happens-before → lock-free 进展保证。

内存与生命周期

RAII → smart pointer → 对齐 → allocator／memory pool → 迭代器与对象失效。

低延迟性能

基准测量 → cache line／NUMA → branch prediction → SIMD → P99／P99.9 尾延迟。

交易数据结构

Order Book → SPSC Queue → LRU Cache → Timer Wheel → 快照与确定性回放。

展开节点，并为每条路径准备“定义—代码—量化场景—测试”四层回答。

典型题目自评清单

检查项	未达标	达标标准
需求澄清	直接编码	说明线程模型、容量、阻塞与生命周期
正确性	只跑 happy path	写出不变量、边界和并发测试
复杂度	只说大 O	同时讨论分配、cache 和常数项
内存模型	只背术语	能画 happens-before
性能	凭直觉优化	有基线、分位数和硬件计数器
工程性	代码能编译即可	RAII、明确 ownership、可停止、可测试

延伸阅读

1. Anthony Williams，C++ Concurrency in Action：线程、同步原语与 C++ 内存模型。
2. Scott Meyers，Effective Modern C++：移动语义、智能指针和并发条款。
3. Jeff Preshing，Preshing on Programming：acquire-release、无锁结构与内存序文章。
4. Agner Fog，Optimizing Software in C++：处理器、cache、分支与 SIMD 优化手册。
5. Martin Thompson，Mechanical Sympathy：硬件友好的低延迟系统设计。
6. C++ Core Guidelines：资源管理、并发和性能的工程准则。

本章要点

1. C++ 量化面试考察的是资源、并发和延迟取舍，而不只是语法熟练度。
2. mutex 是正确且常用的默认方案；无锁结构必须先明确 SPSC／MPSC／MPMC 和进展保证。
3. acquire-release 的核心是建立 happens-before，memory order 选择必须服务于同步证明。
4. cache line、false sharing、分支预测和 SIMD 都需要由测量驱动，不能凭口号优化。
5. 32 核机器没有固定“正确线程数”，应按负载、预留核心、NUMA 和尾延迟实测。
6. Order Book、SPSC Queue、Memory Pool、线程安全 LRU 和 Singleton 是可直接复用的高频练习。
7. 性能验收必须同时看正确性、吞吐和 P99／P99.9 尾延迟。