# 大型依赖图与边界输入测量

本页保留2026-10-16的首次测量。提供者索引和整目录检查的后续修复、2026-10-17数据及当前限制见 [查询性能记录](query-performance.md)。

测量日期：2026-10-16。平台：Windows x64，Intel Core Ultra 9 275HX；Python 3.9.12；MoonBit `0.10.14+7d59c7ec9`、moon `0.1.20260915`，native release 构建。

## 测量范围

`cmd/benchmark` 在内存生成四种确定的图：长链 `chain`、根包直接依赖所有叶子的 `wide`、多分支共享一个叶子的 `shared`，以及根包通过版本条件依赖虚拟包的 `virtual`。规模为100、500、1,000个包；另测5,000个包的长链。每个包有固定元数据和一组编译/链接参数。

每项分别测量输入生成与加载、依赖解析、编译参数收集、链尾路径、全部包的路径解释和整目录检查。使用固定工具链 `@bench.monotonic_clock_*` 计时，单位为微秒。除 `load` 外，耗时不含生成/加载、进程启动、文件 IO 或输出序列化；因此路径结果反映 CLI 解释所需的核心计算，不是完整命令的墙钟耗时。

每个样本启动一个新进程。普通图每项采样3次，报告中位数；遇到超时或进程失败时停止该项的后续采样，保留失败记录。峰值内存取各成功样本的最大工作集，涵盖整个进程，包括输入生成和加载。Windows 通过 `GetProcessMemoryInfo` 读取峰值，POSIX 使用单独测量进程的 `resource.getrusage`。这些数值不是核心库独占的分配量。

原始采样、错误、硬件信息和二进制 SHA-256 保存在 [测量数据](performance/windows-2026-10-16.json)。优化前核心为提交 `0392fb8`；测量适配程序是本轮新增。基线的全部路径操作逐包调用 `dependency_path`；优化后使用一次 `dependency_paths`，逐包调用 `path_to`，分别对应两版 CLI 的实际计算方式。

## 测量结果与修复

全部依赖路径的计算耗时，1,000个包，毫秒：

| 图形 | 优化前 | 优化后 |
| --- | ---: | ---: |
| 长链 | 2,380.93 | 14.86 |
| 宽图 | 542.93 | 1.63 |
| 共享叶子 | 737.10 | 2.72 |
| 虚拟包 | 超过30秒超时 | 357.36 |

长链约加速160倍。原实现为每个参数重做广度优先搜索，并为搜索到的每个节点复制整条路径。现在 `DependencyPaths` 只保存前驱标识符，CLI 每次解释建立一次索引，逐项还原路径。对直接包标识符，搜索和索引存储随图的节点/边增长；实际还原全部路径仍需要与路径总长度相应的工作量。虚拟包查找还有下面记录的扫描开销。

5,000包长链的优化前解析进程退出码为 `3221225725`，未返回有效结果。依赖解析已改为显式帧栈，优化后3次均成功，中位数12.66毫秒。四目标回归测试同时验证这个规模、依赖优先顺序以及循环/版本/缺失/私有字段诊断顺序。

同一规模下，单独查询链尾路径从250.94毫秒降到10.49毫秒，峰值工作集由217.11 MiB降到17.53 MiB。该项优化前为1次样本、优化后为3次样本，只作为这次故障调查的观察值；常规1,000包矩阵两版均为3次样本。

## 展开边界

对1,048,575、1,048,576和1,048,577个 ASCII 字符，分别测量变量替换和字面输入。前两个长度成功，超出上限时返回 `PC009`，6种情况各运行3次。此次观察到的中位数耗时约0.07–8.84毫秒，进程峰值工作集约11.5–20.5 MiB；没有调整既有上限。

上限按实现中的 UTF-16 字符单元计算；这里使用 ASCII，因此1,048,576个字符对应1 MiB文本。测量不把该限制推广为任意 Unicode 文本的字节上限。

## 复现

在固定版本工具链和 Python 3 环境中，从仓库根目录运行：

```sh
moon build --target native --release cmd/benchmark
python scripts/benchmark.py --binary _build/native/release/build/cmd/benchmark/benchmark.exe --output .tmp/performance.json
```

若平台产物名称为 `benchmark`，将 `--binary` 改为对应路径。默认执行四种图、三种规模、六种操作，每项3次；可以用 `--shapes`、`--sizes`、`--operations`、`--repeat`、`--timeout` 缩小范围。比如单独测量5,000包长链：

```sh
python scripts/benchmark.py --binary _build/native/release/build/cmd/benchmark/benchmark.exe --shapes chain --sizes 5000 --operations resolve path-last --repeat 3
python scripts/benchmark.py --binary _build/native/release/build/cmd/benchmark/benchmark.exe --shapes expansion --sizes 1048575 1048576 1048577 --operations expand-variable expand-literal --repeat 3
```

`python scripts/verify-performance.py` 自动构建并定位产物，执行1,000包四种图的解析/参数/路径检查、5,000包长链及展开边界。Windows 完整验证和 Ubuntu CI 都运行这条入口。规模、输出计数、路径长度、退出码和诊断是正确性断言；耗时仅记录，CI 不设绝对速度门槛。

本轮实现提交 `038b11c` 的 Ubuntu [CI 运行](https://github.com/xmyd0915/moonpkgconfig/actions/runs/38884224658) 已通过，包含上述工作负载、四目标70项逻辑测试和原有原生集成流程。

## 已知瓶颈与测量限制

`check_all` 仍对每个包分别解析可达图。1,000包长链本轮约459.68毫秒，优化前约387.10毫秒；显式帧栈修复深图故障，也增加了部分遍历开销。1,000包普通解析约2.54毫秒，优化前约1.83毫秒。本轮主要收益集中在解释路径与深图可靠性，普通查询和整目录检查的性能仍需继续优化。

虚拟包提供者仍按插入顺序扫描并解析 `Provides`。1,000虚拟包的普通解析约361.26毫秒、编译参数查询约735.86毫秒，仍有明显改进空间。后续应评估查询期间的提供者索引，并保持精确标识符优先、版本条件和插入顺序语义。

本轮图形为确定的合成输入，尚未代表所有真实构建系统。没有固定 CPU 频率或隔离后台负载；3次采样只适合发现大幅变化，不构成跨机器速度保证。完整路径的文本输出量、文件发现、文件读取和终端速度需要另外测量。