# 压测方法与报告

[English](./bench.md) | 简体中文

本文件记录压测的方法学与实测数据，使他人能够复现并判断结论是否可信。

## 方法学

### 三种测量，分别回答不同问题

| 工具 | 回答的问题 |
| --- | --- |
| `bench` | 单次调用有多快 |
| `bench_scale` | 成本随规模如何增长 |
| `bench_parallel` | 多个核心能省多少 |

三者都在 `apsis-rs` 门面中，以 example 形式提供，release 模式运行：

```bash
cargo run --release -p apsis-rs --features full --example bench
cargo run --release -p apsis-rs --features full --example bench_scale
cargo run --release -p apsis-rs --features full --example bench_parallel
```

### 三条原则

**无预热。** 每项测量前不丢弃任何一次调用。首次调用会付出惰性分配与缓存的代价，
而调用方等待的正是这个代价，把它藏在一次被丢弃的运行里，等于报告了一个没有人
真正等待过的数字。因此 `bench_scale` 同时给出**冷启动**与**稳态**两列。

**取多次最优。** 串行基线跑若干次取最快。调度抖动只会让某一次变慢，不会让所有
次都变慢；取最快得到的是干净的信号，而不是被邻居进程污染的下界。`bench_parallel`
用这一方式。

**报告每单位成本。** 绝对值随机器变化，`ns per unit` 不变。看后者才能判断复杂度
是否正确。

### 复杂度判据

对输入规模 n，`ns per unit` 恒定即 O(1) 每单位（线性总时间）；`ns per unit`
按 n 的幂增长即该幂次的总复杂度。指数由相邻两点的比值取对数得到。

## 测量环境

| 项 | 值 |
| --- | --- |
| CPU | AMD Ryzen 7 8845HS（8 核 16 线程） |
| 内存 | 28 GB |
| 工具链 | rustc 1.98.1，release |
| 依赖 | 无第三方，基准为 example |

绝对值只在本机有意义。跨机器比较应看同一工具的**比值**。

## 结果一：单次调用

| 路径 | 每次调用 |
| --- | --- |
| Hermite 星历插值查询 | 24.3 ns |
| TEME 到地固系旋转 | 26.8 ns |
| 开普勒根数转状态 | 38.1 ns |
| 地固系转大地坐标 | 50.1 ns |
| 链路预算 C/N0 | 60.6 ns |
| SGP4 传播（历元后 30 分） | 248.7 ns |
| 可见性搜索（120 样本） | 7.49 μs |
| 规划 60 个任务（1 资源） | 239 μs |

星历查询比它所替代的 SGP4 传播快约十倍，这正是 `apsis-ephemeris` 存在的理由：
一次建表、多次查询时，插值远便宜于传播。

## 结果二：规模扫描

### 星座一日传播（60 秒步长，1441 样本/星）

| 星数 | 冷启动 | 稳态 | 每样本 |
| --- | --- | --- | --- |
| 24 | 8.7 ms | 8.7 ms | 252 ns |
| 240 | 80.5 ms | 80.0 ms | 231 ns |
| 1008 | 339.5 ms | 339.5 ms | 234 ns |
| **2016** | 679.4 ms | 679.4 ms | 234 ns |

**每样本成本恒定（增长指数 0.00）**，即 SGP4 单次传播是 O(1)，总时间线性于星数。
两千余星的一日覆盖约 0.7 秒。冷启动与稳态几乎相同，说明该路径没有显著的
一次性分配。

### 可见性搜索（单站，每轨 2 小时）

| 轨数 | 每星 |
| --- | --- |
| 8 | 7.3 μs |
| 128 | 7.3 μs |

**恒定（增长指数 0.00）**，每条轨道独立，线性于星数。

### 拓扑构建与路由（4500 km 链路）

| 星数 | 每星 | 增长指数 |
| --- | --- | --- |
| 8 | 237 ns | — |
| 64 | 2.2 μs | 1.07 |
| 120 | 5.7 μs | 1.52 |
| 300 | 33.0 μs | 1.93 |
| **600** | **182.6 μs** | 2.47 |

**约 O(n²)**。每星成本随星数增长，指数从 1 升到 2.5。成因是几何判定本身
就是全对检查：n 颗星有 n² 对要判断。并行扫描证实瓶颈在此。

### 任务规划（单资源，50 长优先级链）

| 任务数 | 每任务 | 增长指数 |
| --- | --- | --- |
| 60 | 4.5 μs | — |
| 200 | 16.0 μs | 1.05 |
| 1000 | 108.4 μs | 1.33 |
| **2000** | **314.1 μs** | 1.54 |

**约 O(n²)，大 n 时趋向 O(n)**。贪心放置本质上按时间序逐个安排，每次放置
都要与已放置的 placement 比较，故二次是算法本身而非实现缺陷。

## 结果三：并行扫描

### 传播（按卫星分块）

| 星数 | 1 线程 | 2 | 4 | 8 | 16 | 最佳加速 |
| --- | --- | --- | --- | --- | --- | --- |
| 550 | 184 ms | 1.96× | 3.83× | 6.86× | 8.12× | 8.12× (16) |
| 1000 | 336 ms | 1.89× | 3.73× | 6.49× | 8.24× | 8.24× (16) |
| 2000 | 671 ms | 1.89× | 3.74× | 6.61× | 7.93× | 7.93× (16) |

**传播是 embarrassingly parallel**：每个卫星独立，2 至 8 线程接近线性。
16 线程效率降到约 0.5，即超线程带来争用。**推荐 8 线程**（效率约 0.85），
或 16 线程换取更高绝对吞吐。

### 可见性搜索

| 轨数 | 1 线程 | 4 | 8 | 16 | 最佳加速 |
| --- | --- | --- | --- | --- | --- |
| 64 | 0.47 ms | 2.74× | 2.68× | 1.87× | 2.74× (4) |
| 256 | 1.95 ms | 3.52× | 4.36× | 5.27× | 5.27× (16) |

**小规模加速有限**，因为线程启动的固定开销在小工作量上占主导。256 轨约 5.3×。

### 拓扑构建（阶段拆分）

| 星数 | 可见性（可并行） | 边折叠（串行尾部） | 最佳加速 |
| --- | --- | --- | --- |
| 120 | 0.31 ms | 0.30 ms | 1.37× |
| 300 | 1.93 ms | 3.84 ms | 1.72× |

**该路径并行收益有限**。300 星时串行的边折叠占 3.84 ms，是可并行部分的两倍，
故总时间最多加速约 1.7 倍，远不及数值内核的接近线性。根因是 `add_edge` 查重时
线性扫描已有边，使插入本身成为 O(n³)。

## 结论

| 路径 | 复杂度 | 并行性 | 实用规模表现 |
| --- | --- | --- | --- |
| SGP4 传播 | O(1)/样本 | 优秀，16 线程 ~8× | 2016 星一日 0.68 s；16 线程 85 ms |
| 星历插值查询 | O(log n) | 随传播 | 24 ns/次 |
| 可见性搜索 | O(1)/星 | 良好，16 线程 ~5× | 256 轨 0.37 ms |
| 坐标与链路 | O(1) | 不必并行 | 27 至 61 ns |
| 任务规划 | ~O(n²) | 串行 | 2000 任务 0.63 s |
| 拓扑构建 | ~O(n²) | 收益有限（串行尾部主导） | 600 星 110 ms |

**要点**

1. **数值内核是线性且高度可并行的。** 两千余星的一日轨道预测单线程 0.68 秒，
   16 线程 85 毫秒。
2. **星历插值比传播快十倍**，密集查询场景应先用传播建表再插值。
3. **两个组合算法受限于算法而非并行度**：任务规划是贪心的固有二次，拓扑构建的
   边插入查重是二次的平方，后者并行化最多只能加速约 1.7 倍。欲再提升需改算法。
4. **传播推荐 8 线程**：并行效率约 0.85，16 线程因超线程争用降至约 0.5。

## 复现

```bash
# 全部门禁，确保测量的是正确代码
cargo test --workspace --all-features

# 三种测量
cargo run --release -p apsis-rs --features full --example bench
cargo run --release -p apsis-rs --features full --example bench_scale
cargo run --release -p apsis-rs --features full --example bench_parallel
```

测量之间不要并发运行其它负载。绝对值随机器变化，结论应基于同一工具内的比值。