Notist
On this page
  1. 内容树遍历游标栈：实现与验证
  2. 结果
  3. 实现
  4. 回归覆盖
  5. 整站测量
  6. 探索记录与证据

内容树遍历游标栈：实现与验证

结果

基线提交：9a3c5f7bdaeaa8eca31b6160f140a8928704322c。分支：perf/descendants-iterator-stack。仅改变 Node::descendants 的遍历状态表示，没有合并调用方的扫描职责或修改树结构。

  • 工作区测试 847 项通过，无忽略项。

  • 51,739 页站点，18 次完整构建，全部 78,004 项输出的长度与 SHA-256 均与冻结基准一致。

  • 7 组交错 A/B 全部略快，配对 wall 变化的中位数为 -0.87%；不代表所有站点或交互操作的收益。

  • 独立父进程分配探针记录 malloc／calloc／realloc 成功调用合计减少 5,716,272 次，约 3.88%。

  • 峰值 RSS 基本不变；减少累计分配调用不等于降低存活内存。

实现

crates/notist-core/src/item.rs：

  • 保留先根、从左到右的深度优先顺序，返回原节点引用，根节点包含在内。

  • 当前层使用借用的孩子切片迭代器，不再一次把所有兄弟压入节点栈。

  • 遇到有孩子的节点，仅当父游标还有兄弟待访问时才保存父游标；单孩子链不需要保存祖先游标。

  • 待恢复游标使用 SmallVec，内联 8 项；超出容量后使用堆，不改成递归，不限制可遍历深度。

  • 构造及 next 路径标记 inline，让跨 crate 的调用方可以内联和消除不必要的状态搬运。

  • 对外方法签名、find、来源、字段、预算和节点身份语义不变。

空间由待恢复的分支深度决定，不随同一层的兄弟数量增长。内联容量没有宣称经过全局调优。smallvec 原已存在于 Cargo.lock；本次增加 notist-core 的直接依赖，没有升级其版本。

回归覆盖

crates/notist-core/src/item.rs 的 traversal_tests：

  • 混合树的先根顺序与引用身份，以及 find 的包含根／找不到行为。

  • 4,096 个兄弟的宽树保持顺序，游标栈不溢出内联存储。

  • 深度 4,096 的分支树触发堆回退，遍历本身无递归；测试清理也采用迭代方式，避免混入节点递归销毁问题。

  • 单节点只访问一次，多次调用耗尽迭代器保持 None。

crates/notist-core/tests/descendants_alloc.rs：

  • 独立测试二进制以线程局部开关记录 System 分配 API，仅测遍历，不包含树构造和销毁。

  • 单节点、4,096 个兄弟的浅树、嵌套链均为零分配；深度 128 的单孩子链也为零分配。

  • 深度 128 的分支树正常触发堆分配并访问所有节点。

全工作区命令：cargo test --workspace --locked --offline -j2 -- --test-threads=2。测试使用 CARGO_INCREMENTAL=0、CARGO_PROFILE_DEV_DEBUG=0、CARGO_PROFILE_TEST_DEBUG=0，以限制磁盘使用。磁盘不足导致的链接失败及冻结副本缺少 target 临时目录导致的失败日志均保留；补建空目录后完整重跑成功，没有跳过失败测试。

整站测量

基线使用既有冻结普通 release 二进制，候选由本次冻结源码、独立 Cargo target 构建。二者均使用 release、debug=1、incremental=0、jobs=2；计时版本无分配探针。独立站点副本，前后各预热一次；随后 7 对测量，每对交替运行顺序。输出核对在计时结束后执行。普通测量已有输出目录，发布主要比较产物，而非每轮首次写出站点；没有清空操作系统缓存。

指标，中位数

基线

游标实现

wall

8.3724 s

8.3257 s

user CPU

7.6654 s

7.5709 s

system CPU

1.0243 s

1.0218 s

maxrss

2,832,800 KiB

2,833,416 KiB

配对 wall 变化依次为 -1.022%、-1.091%、-1.215%、-0.541%、-0.869%、-0.795%、-0.061%。“配对比值中位数”和“两组中位数之比”是不同统计量，不混称。样本来自同一台机器的一轮局部实验，没有做独立机器重复。

独立分配诊断各运行一次，不纳入 wall 对比。包装器调用原 glibc allocator，只对指定 Rust 父进程启用，不统计扩展子进程及未拦截的对齐分配入口。

成功 API 调用

基线

游标实现

malloc + calloc + realloc

147,456,455

141,740,183

其中 realloc

14,726,628

13,541,263

这些是本次进程调用总数，不是存活对象数，也不表示每次 realloc 都物理复制；多线程通路的调用总量可能随运行有所波动。

探索记录与证据

最初“每层游标全部压栈”的候选同样减少分配，但整站配对中位数约慢 2.57%，没有以此作为最终实现。独立微探针支持继续减少游标维护工作；其合成树结果不替代整站验收，也不用于承诺各树形的加速。

最终证据目录：/tmp/opencode/notist-descendants-cursors-20261109。包含 run.py、manifest.json、sources/after、bin、logs、samples.json、allocations.json、summary.json 及全部输出清单。run.py 是这次已有冻结实验的续跑脚本，主动拒绝覆盖已记录的二进制或计时数据；不是对同一目录可反复执行的通用基准入口。初始候选及失败日志：/tmp/opencode/notist-descendants-20261109。基线二进制与证据：/tmp/opencode/notist-hotspots-9a3c5f7-20261109。

未测增量编辑、LSP／Worker 或其他站点；没有声称消除了所有树遍历分配，也没有实施重复扫描合并。