Skip to content

[FEATURE] 优化 import 路径数据结构,消除 segment/blocks 操作的 O(N²) 退化(子任务 #72-2) #74

Closed
1 of 1 issue completed

Description

@codeasier

功能描述

import 路径对每个 trace 事件倒序回放,每个 alloc 事件调用 attach_block、每个 free 调用 detach_block。当前实现中三处操作退化为 O(N),导致整体回放复杂度 O(N²),大快照(几十万事件)下 import 极慢。

本 issue 是 #72 的子任务,聚焦「数据结构替换」这一类问题。

使用场景

  • pt-snap import 大型 PyTorch 内存快照(事件数 ≥ 10w)
  • CI 批量导入多个快照

期望的实现方式

1. segment.blocks 列表插入/删除【严重】

snapshot_mutator.attach_block 用 segment.blocks.insert(insert_idx, block),detach_block 用 segment.blocks.remove(block)。N 个事件 → 最坏 O(N²)。

建议:用 sortedcontainers.SortedList 按 address 维护 blocks,插入/删除降到 O(log N)。

涉及代码:

  • src/pt_snap_cli/vendor/memsnapdump/simulate/snapshot_mutator.py:attach_block / detach_block
  • src/pt_snap_cli/vendor/memsnapdump/simulate/snapshot_lookup.py:find_block / find_gap_for_alloc_block(二分搜索逻辑可保留,但底层数据结构需配套替换)
  • src/pt_snap_cli/vendor/memsnapdump/simulate/snapshot_mutator.py:_shrink_segment / _split_segment_at / merge_mapped_segment(这些方法遍历 segment.blocks 重建列表,需配套适配新数据结构)

2. _insert_segment_sorted 每次重建 keys【中】

每次插入 segment 都重新构建 keys = [(seg.address, seg.stream) for seg in segments],再 bisect + 列表 insert,整体 O(N²)。

建议:维护一个独立的 sorted key 列表(在 DeviceSnapshot 上新增字段或在 AllocatorContext 中维护),避免每次重建;或同样改用 SortedList。

涉及代码:

  • src/pt_snap_cli/vendor/memsnapdump/simulate/snapshot_mutator.py:_insert_segment_sorted
  • src/pt_snap_cli/vendor/memsnapdump/base/entities.py:DeviceSnapshot(如新增字段)

3. alloc_or_map_segment 线性扫描找相邻 segment【中】

SimulatedCachingAllocator.alloc_or_map_segment 用 for i, seg in enumerate(segments) 线性扫描找左右相邻 segment,而同文件其他查找(如 find_overlapping_segment)已用二分。行为不一致且复杂度 O(N)。

建议:用二分定位到 new_segment.address 的位置后,向左右各扩展一格检查邻接关系,整体 O(log N)。

涉及代码:

  • src/pt_snap_cli/vendor/memsnapdump/simulate/simulated_caching_allocator.py:alloc_or_map_segment

注意事项

  • sortedcontainers 是纯 Python 库,无 C 扩展依赖,加入 pyproject.toml 的 dependencies 即可。
  • 替换 segment.blocks 时需同步检查所有读侧代码(find_block 的二分、_shrink_segment 的过滤重建、_split_segment_at 的遍历分类)。
  • Segment.blocks 的类型注解和序列化路径(如有)需配套更新。
  • 修改后需保证 vendor 目录的 ATTRIBUTION.md / LICENSE 一致性不被破坏(仅代码修改,不涉及 license)。

验收标准

  • segment.blocks 改用基于 SortedList(或等效结构)维护,插入/删除复杂度降到 O(log N)
  • _insert_segment_sorted 不再每次重建 keys 列表
  • alloc_or_map_segment 用二分定位相邻 segment,消除线性扫描
  • pyproject.toml 添加 sortedcontainers 依赖
  • 现有 vendor 测试全部通过
  • 新增基准:对 10w+ 事件的快照做 import 耗时对比,确认从 O(N²) 退化改善到接近 O(N log N)

父 issue

#72

Activity

  1. codeasier commented on Jul 27, 2026

    @codeasier
    OwnerAuthor

    代码已审查完毕。以下是对三个性能问题的逐一核实,以及一个必须优先解决的结构性问题。

    结构性前置问题:vendor 目录修改策略冲突

    本 issue 提议修改 6 个位于 src/pt_snap_cli/vendor/memsnapdump/ 下的文件。但该目录的 ATTRIBUTION.md 明确规定:

    Local modifications: None. Any local fix or workaround that the project needs should be applied in src/pt_snap_cli/core/snapshot_import_backend.py … not in this directory.

    直接改动 vendor 文件会破坏「字节等同于上游 pinned SHA」的同步策略,使未来 resync 从「clean replace」退化为逐文件 diff 合并。因此,无论下面的性能问题是否属实,正确的交付路径应是:

    1. 将修复提交到上游 codeasier/MemSnapDump,
    2. 更新 vendor pinned SHA 后 resync,
    3. 或在 ATTRIBUTION.md 的「Local modifications」一节显式记录本地修改及原因,并接受后续 resync 成本。

    本 issue 的实现方案需要先明确选择哪条路径。


    问题一:segment.blocks 插入/删除 — 复杂度定性有误,SortedList 方案有多个技术问题

    结论:存在开销,但严重程度被高估,且建议的方案不一定带来收益。

    复杂度分析

    attach_block 的 list.insert(insert_idx, block)(snapshot_mutator.py:21)与 detach_block 的 list.remove(block)(snapshot_mutator.py:43)单次代价是 O(k),其中 k = 该 segment 内的 block 数,而不是 N(全局事件数)。k 的上界是 segment.total_size / min_block_size,小池 segment 约 2MB / 512B = 4096,实际远小于此。所以整体是 O(N · k),把它记作 O(N²) 并标为【严重】并不准确 —— N 与 k 是两个独立量纲。

    更直接、成本更低的修复

    snapshot_lookup.find_block 已经返回 block_idx,free_block 拿到了这个 idx(simulated_caching_allocator.py:72),但 detach_block 没有接收它,而是用 list.remove(block) 逐元素调用 Block.__eq__(dataclass 生成的全字段比较)。把 idx 传入并改用 del segment.blocks[idx],即可直接消除这次线性扫描 —— 零新依赖,且顺带消除了「按值比较可能命中错误 block」的隐患。

    SortedList 方案的具体问题

    1. Block 是 @dataclass(未开 order=True),没有 __lt__,必须用 SortedKeyList(key=lambda b: b.address),不是直接 SortedList。
    2. attach_block 的签名接收 insert_idx,而该 idx 由 find_gap_for_alloc_block 在校验空隙可容纳该 block 后给出(snapshot_lookup.py:93-135)。改用 SortedList.add() 后位置自动确定,原有的空隙合法性校验语义需要整体重新设计,而不只是「配套替换底层结构」。
    3. _shrink_segment 两处 segment.blocks = [block for block in ...](snapshot_mutator.py:372、395)会把字段重置成 plain list,破坏类型一致性。
    4. _split_segment_at 用 blocks=[] 构造新 segment 后 append(snapshot_mutator.py:275、289、301、307),_merge_segments 与 merge_mapped_segment 用 target.blocks.append(block)(snapshot_mutator.py:235、117)—— 所有重建/追加路径都要配套改造,改动面比 issue 列出的更大。
    5. sortedcontainers 是纯 Python 实现,per-op 开销高于 C 层的 list.insert(memmove)。在 k 为几十到几百的量级上,替换后有实测变慢的风险。

    建议:本条改为「detach_block 接收 block index,用 del 替代 list.remove」,不引入 sortedcontainers。若后续 profile 证明 blocks 操作仍是热点,再单独评估数据结构替换。


    问题二:_insert_segment_sorted 每次重建 keys — 属实,且修复不需要新依赖

    已确认(snapshot_mutator.py:180-185):

    segments = snapshot.segments
    keys = [(seg.address, seg.stream) for seg in segments]
    idx = bisect.bisect_left(keys, (segment.address, segment.stream))
    segments.insert(idx, segment)

    每次插入都分配 S 个 tuple + 一个长度 S 的 list,累计 O(N · S) 的 Python 层分配开销。这是三条里最实在、ROI 最高的一条。

    更简单的修复:Python 3.10+ 的 bisect.bisect_left 支持 key= 参数,而项目已声明 requires-python = ">=3.10":

    idx = bisect.bisect_left(
        segments,
        (segment.address, segment.stream),
        key=lambda s: (s.address, s.stream),
    )
    segments.insert(idx, segment)

    零新依赖,改动局部,直接消除每次重建。不需要 SortedList,也不需要在 DeviceSnapshot 上新增字段(后者还会引入「字段与 segments 列表需保持同步」的新不变量,而 remove_segment、_merge_segments、_split_segment_at、_shrink_segment 都会直接改动 segments,同步点很多,容易出错)。

    顺带指出 issue 未覆盖的两处同类问题:

    • merge_mapped_segment 的 segments.index(new_segment)(snapshot_mutator.py:123)是 O(S) 线性扫描 + dataclass 全字段比较。_insert_segment_sorted 其实已经算出了这个 idx,让它返回即可。
    • remove_segment 的 snapshot.segments.remove(segment)(snapshot_mutator.py:82)同样是 O(S) 按值扫描,而调用方 free_segment 已持有 exist_seg_idx(simulated_caching_allocator.py:205)。

    问题三:alloc_or_map_segment 线性扫描 — 属实,但影响面有限且建议方案不完整

    已确认(simulated_caching_allocator.py:168-174):merge=True 路径确实全量扫描 segments,且不 early-break。

    两点需要修正

    1. 影响面:merge=True 仅由 segment_map / segment_unmap 事件触发(即启用 expandable segments 的场景)。非 expandable 工作负载完全走 merge=False 分支,不受影响。因此【中】这个定级在多数快照上偏高。
    2. 建议方案不正确:issue 写的「二分定位后向左右各扩展一格检查邻接关系」在多 stream 交织时会漏判。segments 按 (address, stream) 排序,而循环体第一行就是 if seg.stream != new_segment.stream: continue —— 紧邻位置上完全可能是其他 stream 的 segment,此时真正的同 stream 邻接段在更外侧。「扩展一格」无法保证正确性。

    建议:参照同目录下 snapshot_lookup._scan_overlapping_segments_for_stream(snapshot_lookup.py:29-49)已有的「向两侧持续扫描直到地址条件不再可能满足」模式来实现,而不是固定扩展一格。这样最坏情况仍受同地址区间内的 stream 数量影响,但正确性有保障。


    对验收标准的建议

    1. 先 profile 再改:当前验收标准把基准测试放在实现之后(「新增基准:对 10w+ 事件的快照做 import 耗时对比」)。仓库中目前没有 tests/perf/,也没有任何既有测量数据支撑「O(N²) 退化」这一判断。建议先在真实大快照上跑 cProfile / py-spy 确认热点分布,再决定改哪几处 —— 否则问题一有可能花较大改动换来零收益甚至负收益。
    2. pyproject.toml 添加 sortedcontainers 这条建议移除或推迟:问题二用标准库 bisect(key=) 即可解决,问题一的 del 方案也不需要它。为一个尚未实测的收益引入新运行时依赖不划算。
    3. 补充一条验收项:vendor 修改路径已按上游贡献 / ATTRIBUTION.md 记录二者之一处理完毕。

    小结

    子问题 是否属实 定级评估 建议方案
    1. segment.blocks 插入/删除 部分属实(O(N·k) 非 O(N²)) 【严重】偏高 改为 detach_block 用 index + del,不引入 SortedList
    2. _insert_segment_sorted 重建 keys 属实 【中】可上调,ROI 最高 bisect.bisect_left(key=...),零依赖
    3. alloc_or_map_segment 线性扫描 属实 【中】偏高(仅 expandable 场景) 二分 + 参照 _scan_overlapping_segments_for_stream 的向外扫描

    整体方向合理,但建议按上表收敛范围:优先交付问题二和问题一的轻量版本,问题三视 expandable segments 是否为目标场景决定,并在动手前补一次 profile 作为基线。最重要的是先确定 vendor 修改的交付路径。

  2. codeasier commented on Aug 6, 2026

    @codeasier
    OwnerAuthor

    实测数据记录:PR #82 合入后的 import 性能基线

    在 PR #82(perf: optimize snapshot replay lookups)合入 main 后,对 issue #72-2 的三处 O(N²) 退化做了同条件前后对比实测。以下为全部过程数据与结论。

    测试环境与硬件

    注意:以下数据仅在当前测试机上测得,作为本项目的描述性基线,不代表其他硬件的绝对值。

    项 值
    操作系统 Linux Mint 22.3(基于 Ubuntu 24.04 / Noble),内核 6.14.0-37-generic
    CPU Intel i7-12700(12 核 / 20 逻辑线程,P-core 最高 4.9GHz)
    内存 31 GiB(测试期间可用约 21–23 GiB)
    磁盘 NVMe(/ 与 /tmp 同盘,可用空间充足)
    Python 3.12.13(conda 环境 pt-snap)
    SQLite 3.53.2
    样本 snapshot_import_131k_sanitized.pickle(43,140,853 B,LFS oid 26b8d928…);snapshot_import_628k_sanitized.pickle(175,057,085 B,LFS oid 40634062…);snapshot_with_multi_devices.pkl
    对比版本 pre-#82 = 717e3ca(#81 合入后);post-#82 = dafaf4f(PR #82 合入后)
    测量方法 benchmarks/baseline_import.py,GNU /usr/bin/time -v;每次 1 次 warmup + 正式多次(8k/131k×5,628k×3)取中位数;RSS 为子进程峰值(LC_ALL=C 固定输出)

    导入总耗时对比(中位数、同机同脚本串行测量)

    样本 pre-#82 post-#82(当前 main) 提速
    8k(8,134 事件) 0.470s 0.270s 1.74x
    131k(131,283 事件) 13.450s 8.670s 1.55x
    628k(628,839 事件) 208.52s 41.42s 5.03x
    • 峰值 RSS 与 DB 大小两版一致:8k 55.5 MiB / 11.2 MiB;131k ≈1,259 MiB / 633.4 MiB;628k ≈4,950 MiB / 5,676.8 MiB。
    • 正确性逐项一致:quick_check=ok;trace 行数 8,134 / 131,283 / 628,839;block 行数 3,219 / 45,281 / 217,535;峰值 allocated/active/reserved 与代表查询结果在优化前后完全相同。

    分段计时(插桩逐阶段,628k 单次)

    阶段 pre-#82 post-#82 变化
    纯模拟(replay 事件分发) 211.706s 32.408s -179.3s(6.5x)
    事件批量写库(629 批 / 628,839 条) 7.201s 6.973s 基本持平
    块批量写库(218 批 / 217,535 条) 0.848s 0.690s 基本持平
    pickle 加载 0.561s 0.555s 持平
    SHA256 哈希(首次 + 落盘前复验) 0.199s 0.198s 持平
    建表 + 索引(空表) ≈0.000s ≈0.000s 持平(索引维护计入插入)
    元数据写入 0.471s 0.492s 持平
    合计 221.087s 41.426s 5.33x

    131k 样本分段:纯模拟 12.259s → 7.290s(1.68x),合计 14.011s → 8.903s(1.57x)。

    结论

    • 提速几乎全部来自回放「纯模拟」阶段,即 PR perf: optimize snapshot replay lookups #82 的二分定位相邻 segment、复用已发现下标(detach_block/remove_segment 传 idx)、_insert_segment_sorted 用 bisect(key=…) 不再重建 keys——与本 issue 的三处 O(N²) 热点一一对应。
    • 628k 收益(6.5x)远大于 131k(1.68x):O(N²) 项随事件数 N 平方放大,符合预期。
    • 写库批量插入路径基本不变(线性,预期内);pickle 加载本身很快(0.56s),高 RSS 来自解包后的完整对象图 + 回放结构,而非加载耗时。
    • 优化后纯模拟仍是最大单项(628k 占 78%、131k 占 82%,约 52µs/事件),可作为后续优化方向。

    备注

    • 本 issue 验收标准中的第一个「segment.blocks 改用 SortedList」未按原方案实施,而是采用更轻量的「find_block 已返回 idx → 直接 del segment.blocks[idx]」方案(见本 issue 审查评论),实测同样消除了该 O(N) 热点。
    • 顺带发现并修复了 benchmarks/baseline_import.py 对 GNU /usr/bin/time 输出中 ≥60s 时长(M:SS.ff 格式)的解析 bug(此前 628k 被误报为 ~39s,实为 ~209s);本数据为修复后重新测得。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions