# 查询索引与整目录检查优化

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

本轮继续处理 [首次大图测量](performance.md) 中的提供者扫描和整目录重复遍历。优化前核心为提交 `fc96813`；同机重新测量100、500、1,000包的四种图、六种操作，每项3次。时间为核心操作中位数，不含输入生成/加载、文件 IO、进程启动或输出序列化。峰值工作集涵盖整个独立进程。

原始采样、环境、二进制校验值和补充场景保存在 [测量数据](performance/windows-2026-10-17-queries.json)。四种普通图的生成方式沿用原基准；新增 `broken` 图仅在长链末尾增加一个缺失依赖。

## 同机结果

1,000包的耗时，毫秒：

| 操作 | 优化前 | 优化后 | 本次观察 |
| --- | ---: | ---: | ---: |
| 有效长链整目录检查 | 370.78 | 1.62 | 约229倍 |
| 虚拟包图解析 | 279.43 | 2.84 | 约98倍 |
| 虚拟包图编译参数查询 | 556.72 | 3.48 | 约160倍 |
| 虚拟包图整目录检查 | 279.56 | 2.71 | 约103倍 |
| 宽图整目录检查 | 1.69 | 1.50 | 小幅变化 |
| 共享叶子整目录检查 | 3.73 | 1.84 | 约2倍 |

5,000包有效长链的解析中位数为11.33毫秒，整目录检查为10.82毫秒，均完成并得到正确结果。新增索引会占用额外内存：1,000虚拟包编译参数查询的峰值工作集约由9.83 MiB增至10.19 MiB。内存数据是进程最大工作集，不能解释成索引自身的准确分配量。

## 提供者索引与查询缓存

`QueryContext` 只在单次公开操作中存在。遇到首个虚拟包请求时，按包插入顺序解析所有 `Provides`，按虚拟名建立有序候选列表；同一操作的后续请求只检查该名称的候选。编译/链接参数收集中的诊断遍历和参数遍历共用这个上下文，依赖字段也只解析一次。

匹配规则保持原有合同：精确包标识符优先，精确包版本不满足时不会退回虚拟提供者；同名候选选第一个满足要求的声明。未带版本的 `Provides` 不产生可用虚拟版本，非法字段整体忽略，范围比较继续使用既有 pkgconf 3.0.7 比较矩阵。

缓存不存入 `PackageSet`，下一次调用重新建立。因此添加包或修改调用方持有的文档后，后续查询可见新内容；无虚拟请求时不建立提供者索引。单次冷查询仍承担一次索引成本，不能保证所有小查询都提速。

## 整目录检查

先用显式栈识别依赖全部有效、无循环、且可达子图没有 `Conflicts` 字段的包。这些包作为任何根都不会产生诊断，可以复用判定，不必逐根重走完整可达图。普通有效图的依赖字段和边各检查一次，临时缓存随节点、边和提供者声明数量增长。

任何缺失依赖、版本问题、循环、非法依赖字段或冲突字段都会使相关根进入原有的完整诊断遍历。冲突依赖当前根实际选中的包集合，不能把整个目录当成一个共同根。问题根仍按插入顺序遍历，诊断按首次出现顺序去重；共享上下文只复用依赖步骤和提供者索引。

新增8个逻辑测试覆盖候选顺序、非法声明、精确名优先、后续包/文档修改、公开/私有参数顺序、每根独立冲突、循环与错误顺序、非法字段及5,000包目录检查。与原测试合计78项，四目标均通过。

实现提交 `37c38ff` 的 Ubuntu [CI 运行](https://github.com/xmyd0915/moonpkgconfig/actions/runs/39003870216) 已通过，包含78项四目标测试、26个大图/边界工作负载、38项 pkgconf 差分及真实 zlib/libpng 集成。

## 问题图的边界

长链末尾存在缺失依赖时，100、500、1,000包整目录检查分别约需1.70、40.81、124.95毫秒。每次结果均精确保留一条去重后的 `PC015`，不把失败包标为有效。

问题根、循环根和含冲突字段的根仍可能反复遍历共同子图，最坏情况仍有平方级工作量；大量诊断的去重也没有在本轮重写。对这些分支，没有宣称消除全部重复遍历。真实构建目录的读取与完整 CLI 墙钟耗时仍需另外评估。

## 复现

```sh
moon build --target native --release cmd/benchmark
python scripts/benchmark.py --binary _build/native/release/build/cmd/benchmark/benchmark.exe --repeat 3 --output .tmp/query-performance.json
python scripts/benchmark.py --binary _build/native/release/build/cmd/benchmark/benchmark.exe --shapes broken --sizes 100 500 1000 --operations resolve check --repeat 3
python scripts/benchmark.py --binary _build/native/release/build/cmd/benchmark/benchmark.exe --shapes chain --sizes 5000 --operations resolve check --repeat 3
```

若平台产物名为 `benchmark`，调整 `--binary`。`python scripts/verify-performance.py` 会自动定位构建产物，并检查四种1,000包图的目录结果、5,000包长链及1,000包缺失依赖图；原有参数、路径和展开边界检查继续执行。CI 验证结果正确性，记录耗时，不使用绝对速度门槛。

本轮未固定 CPU 频率或隔离后台负载，3次采样仅反映当前环境。普通图两版均从新进程开始，计时范围相同；补充问题图和5,000包目录检查只报告本轮值，没有对应基线比值。