IV：量化 C++ 开发、infra 题目和知识点

这组题来自一位第一次面量化方向的同学，岗位是 C++ 开发、交易系统开发和 infra，面的是几家传统量化私募和一家币圈量化。它的特点很集中：几乎不问项目，问答从 C++ 一路问到 CPU 和内核，手撕题没有一道是常见的算法题，全是并发和内存管理。 所以准备的重点不是刷题，而是把“这行代码在机器上发生了什么”讲清楚。

下面每道题写三样东西：考的是什么，答到哪一层算到位，本站哪里讲过。“待补”表示本站还没有对应的页面。

1. 问答题

1.1 C++ 语言：标准规定了什么，编译器借此做了什么

这一块问得很杂，从未定义行为（UB）到 C++26 的提案都有。它们背后是同一个问题：标准把某件事定为 UB，编译器就假设它永远不发生，并据此删代码、重排代码。 能把这一层讲出来，比背 UB 清单有用。

1.2 工具链：符号怎么找到，优化能跨多远

工具链的问题围绕两件事：链接器怎么把各个目标文件里的符号对上，优化能不能跨过编译单元的边界。

1.3 并发和体系结构：每个说法都要落到硬件

这是问得最多的一块。区别于一般后端面试的地方在于，每个并发问题都要讲到指令、缓存行和周期数，只说“加锁”“用原子变量”不够。

1.4 操作系统：用户态和内核态之间的代价

操作系统的题几乎都在问同一笔账：进一次内核、拷一次数据、缺一次页、错过一次 TLB 各要多少，以及怎么绕开。

1.5 性能测量和线程池

2. 手撕题

2.1 对象池：多线程分配，单线程回收

题目要求像 pmr 的 synchronized_pool_resource 那样：存储是一串大小翻倍的块（list<T[N]>，下一块是 2N），空闲槽用一个无锁的侵入式 LIFO 栈管理。

为什么这样设计。 块只追加、不搬家，已经分出去的对象地址一直有效；大小翻倍，扩容次数是对数级。空闲槽本身没在用，正好拿它的前 8 个字节存“下一个空闲槽”的指针，这就是侵入式：栈不需要额外的节点。

分配是从栈顶弹出：读 head 和 head->next，CAS 把 head 换成 next。回收只有一个线程，把槽压回栈顶。栈空时要扩容，这是慢路径，用一把互斥锁保护就够了，快路径仍然无锁。

追问几乎一定是 ABA：CAS 只比较值，head 从 X 变成别的、又变回 X，CAS 看不出来。线程 A 读到 head = X、next = Y 后被换下，别的线程拿走 X 和 Y、又把 X 还回来，A 回来 CAS 成功，栈顶却成了正被别人用着的 Y。解法是给 head 带一个版本号，每次修改加 1，CAS 同时比较下标和版本号（32 位下标加 32 位版本号打包进 64 位，或用 16 字节的 CAS）。内存序：弹出的 CAS 用 acquire，压入用 release，保证拿到槽的线程看得到上一个使用者写完的内容。

本站：内存池与分配器第 1 节讲池和空闲链表，5.3 有 ABA 的时刻表和无锁版本的完整代码。

2.2 优化 SPSC 场景下的移动平均

一个线程推价格，一个线程算最近 N 个价格的简单移动平均（SMA）。原实现用 mutex 加条件变量传数据，std::deque 存窗口，std::map 按品种查，每条消息 new / delete。逐项换：

• 队列：只有一个生产者和一个消费者，换成无锁环形队列。生产者只写尾、消费者只写头，两个下标放在不同缓存行上，用 acquire / release 同步，不需要锁也不需要进内核睡眠。见无锁队列。
• 窗口：定长的环形缓冲区，加上一个运行中的总和，新价格进来加上它、减去被挤出的那个，每次 O(1)。浮点数一直加减会累积误差，可以定期重算一次，或者价格用整数（最小变动单位）表示。
• 查找：std::map 是红黑树，每次查找都要跟着指针走好几层；换成哈希表，品种数固定时直接用数组按编号索引更好。
• 分配：换成 pmr 的内存池或启动时预分配，热路径上不再调 malloc。见内存池与分配器。
• 向量化：窗口重算这类循环可以用 #pragma clang loop vectorize(enable) 提示，前提是数据连续、对齐、指针之间不重叠。见 SIMD 向量化。

追问是“你怎么证明快了”，答案就是 1.5 节的微基准方法。

2.3 无锁哈希表

这道是币圈量化问的。思路是分片加 RCU：按哈希值的低几位分成若干片，每片单独处理，写和写之间的冲突被分散开；读的路径完全不加锁。

写者修改时不就地改，而是复制一份、改好，再用一次原子写把指针换过去。难点在于旧版本什么时候能释放：可能还有读者正拿着它。epoch（或 RCU）的办法是，读者进入时登记“我在第 e 代”，离开时注销；写者把旧版本挂上“第 e 代退休”的标签，等所有读者都离开了第 e 代，才真正释放。

追问是回收怎么做才平滑：不在写者线程里当场释放，而是把退休的对象放进队列，由后台线程批量释放，写路径上就没有长停顿。代价是某个读者迟迟不退出，会拖住整代的回收，内存会涨。另一种方案是 hazard pointer：读者登记的是具体指针，回收更精确，但每次读都要多一次写和一次内存屏障。

本站：待补。

2.4 并行化一个 DAG 调度器

给一个单线程的 DAG 调度器和一个线程池，要求并行化。基础是拓扑排序：入度为 0 的节点都已就绪，可以一起提交给线程池。 每个节点执行完，把它所有后继的入度原子减 1（fetch_sub），减到 0 的那个线程负责提交这个后继。最后用一个完成计数（或 std::latch）通知所有节点都已跑完。

两种提交方式的差别在关键路径：按层批量提交写起来简单，但同一层里最慢的节点会拖住下一层；完成一个就立刻提交它的后继，关键路径更短。节点很小的时候，调度本身的开销会超过计算，要把小节点合并。

本站：基础线程池见线程池和 future，DAG 调度待补。

2.5 用 futex 实现 mutex

这道追问最深。面试者的写法是两状态：锁字里存持有者的线程 id，空闲时是一个特殊值；加锁 CAS，失败先自旋一定次数，再 futex_wait 睡；解锁写回空闲值、futex_wake。它能用，但有一个问题：解锁时不知道有没有人在等，只能每次都调 futex_wake，而那是一次系统调用。

标准做法是三个状态（Drepper《Futexes Are Tricky》）：0 是没锁，1 是锁住且没人等，2 是锁住且可能有人等。

#include <atomic>
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>

static void futex_wait(std::atomic<int>* a, int val) {
    syscall(SYS_futex, reinterpret_cast<int*>(a), FUTEX_WAIT_PRIVATE, val, nullptr, nullptr, 0);
}
static void futex_wake(std::atomic<int>* a, int n) {
    syscall(SYS_futex, reinterpret_cast<int*>(a), FUTEX_WAKE_PRIVATE, n, nullptr, nullptr, 0);
}

class Mutex {
    std::atomic<int> s_{0};   // 0 没锁，1 锁住没人等，2 锁住可能有人等
public:
    void lock() {
        int c = 0;
        if (s_.compare_exchange_strong(c, 1, std::memory_order_acquire)) return;   // 快路径
        if (c != 2) c = s_.exchange(2, std::memory_order_acquire);
        while (c != 0) {
            futex_wait(&s_, 2);                          // 值仍是 2 才睡
            c = s_.exchange(2, std::memory_order_acquire);
        }
    }
    void unlock() {
        if (s_.fetch_sub(1, std::memory_order_release) != 1) {   // 原来是 2：可能有人在等
            s_.store(0, std::memory_order_release);
            futex_wake(&s_, 1);
        }
    }
};

没人抢的时候，加锁一次 CAS、解锁一次 fetch_sub，都不进内核。醒来的线程把状态设成 2 而不是 1，因为它不知道身后还有没有别人在等，宁可多唤醒一次也不能漏。要加自旋，就放在 exchange(2) 之前，循环里只读不写，读到 0 再 CAS。

内存序怎么分析：拿到锁的那次 CAS 或 exchange 用 acquire，释放锁的写用 release，这一对保证临界区里的读写不会越过加锁和解锁。futex 系统调用本身不承担 C++ 意义上的同步，同步全靠这个原子变量。futex_wait 在内核里会再检查一次“值是不是还是 2”，不是就立刻返回。这正是“先检查再睡”，防的是检查和睡下之间的那次唤醒被漏掉（epoll 里的等待队列是同一个道理）。

锁字里存线程 id 有什么用：能检查“解锁的是不是持有者”、支持递归锁和死锁诊断。Linux 的优先级继承锁（FUTEX_LOCK_PI）就要求锁字存持有者的 tid，再用一个最高位标记有人在等，内核据此把持有者的优先级临时提高。

公平性：futex_wake 唤醒一个线程，但它醒来之前，刚到的线程可能直接 CAS 成功插了队。这样吞吐高，等着的线程却可能一直抢不到。要公平，可以用 ticket lock（按号排队），或者解锁时把锁直接交给被唤醒的线程；排队锁 MCS 让每个等待者在自己的缓存行上自旋，核多的时候也不会集体抢同一行。glibc 的 mutex 默认不保证公平。

本站：自旋锁讲了 CAS、自旋和退避，线程同步讲了 mutex 的快路径和进内核睡。

3. 还没写的

按这组题，本站还缺这些：UB 和求值顺序的专题、模板和元编程、C++26 的 std::hive 和静态反射、LTO 和 LLVM 的优化阶段、协程的实现、一次系统调用的完整路径、io_uring、work stealing 线程池、无锁栈和 ABA、epoch 和 RCU 回收、DAG 调度器。最值得先补的是无锁栈加 ABA 和 epoch 回收：对象池和无锁哈希表两道手撕题都建在它们上面。futex 锁的代码已经在 2.5 节，单独成页时再补上测试。