# 第 29 章实验：精确计数器 vs 近似计数器

对应 OSTEP 第 29 章《基于锁的并发数据结构》的 Figure 29.2（一把锁的精确计数器）、
Figure 29.4（近似计数器 / sloppy counter），重做 Figure 29.5（线程数扫描）和 Figure 29.6（阈值 S 扫描）两个实验。

## 怎么跑

```bash
cd labs/29-lock-data-structures
make            # 编译出 counters 和 counters-nopad
./counters      # 完整实验，约 2~3 秒
./counters-nopad            # 同样的实验，但 local[] 不做缓存行填充（原书写法）
./counters precise 4 1000000        # 单独跑：4 线程 × 100 万次，精确计数器
./counters approx  4 1000000 1024   # 单独跑：近似计数器，S = 1024
```

编译参数：`gcc -O2 -Wall -pthread`。

## 程序做了什么

- `precise_t`：`value` + 一把 `pthread_mutex_t`，每次 `increment()` 都加锁、`value++`、解锁（Figure 29.2）。
- `approx_t`：每个 CPU 一个局部计数器 `local[i]` 和局部锁，外加全局计数器 `global` 和全局锁 `glock`。
  线程 `id` 更新 `local[id % NUMCPUS]`；局部值 ≥ 阈值 S 时拿全局锁，把局部值加到全局并清零（Figure 29.4）。
  `get()` 只读 `global`，所以是**近似**值。
- `NUMCPUS` 在运行时用 `sysconf(_SC_NPROCESSORS_ONLN)` 取本机在线逻辑 CPU 数（本机 WSL2 下为 16）。
- 每个配置跑 3 次取中位数，计时用 `clock_gettime(CLOCK_MONOTONIC)`。

实验一：每线程 100 万次递增，线程数取 1/2/4/8/16，比较两种计数器的总耗时（S=1024）。
实验二：固定 4 线程，S 取 1,2,4,…,1024，看近似计数器的耗时和 `get()` 的滞后量。

## 该观察到什么

1. **精确计数器随线程数变慢**：1 个线程最快；线程越多，所有线程都在抢同一把锁、同一条缓存行，
   总耗时反而上升（原书 iMac 上 2 线程就超过 5 秒；现代 glibc 的 futex 互斥锁快得多，但趋势相同）。
2. **近似计数器几乎"完美扩展"**：线程数翻倍、总工作量翻倍，耗时基本不变——各线程主要只碰自己的局部计数器。
3. **S 越小越慢、越准；S 越大越快、越不准**。`get()` 的滞后 = 各局部计数器里还没转移的余数之和，
   上界是 `NUMCPUS × (S−1)`（原书粗略说"至多 CPU 数 × S"）。例如 4 线程、每线程 100 万次、S=1024：
   `1000000 mod 1024 = 576`，所以滞后 `4 × 576 = 2304`。
4. **`counters-nopad` 对比**：原书的 `int local[NUMCPUS]` 让多个局部计数器挤在同一条 64 字节缓存行里，
   不同 CPU 仍在争抢同一条缓存行（伪共享，false sharing），扩展性明显变差。本程序默认给每个局部计数器单独一条缓存行。

## 注意

- 线程没有绑核，操作系统可能把两个线程调度到同一个物理核的两个超线程上，或者来回迁移，所以数字会抖动。
- 本机是 8 核 16 线程（超线程），16 个线程时两个超线程共享一个物理核的执行单元，扩展性会打折扣。
- 你的机器上数字会不同；看趋势，不要看绝对值。