186 lines
6.9 KiB
Markdown
186 lines
6.9 KiB
Markdown
# 压测方法与报告
|
||
|
||
[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
|
||
```
|
||
|
||
测量之间不要并发运行其它负载。绝对值随机器变化，结论应基于同一工具内的比值。
|