python / python/cpython

_remote_debugging: quadratic replay time for RLE records with alternating status

未关闭
#152,721 0 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看

还没有人认领这个 Issue。

extension-modules topic-profiling type-bug
主要语言
Python
星标
77.2k
派生
35.9k
PR 合并指标
PR 指标待抓取

描述

Bug report

Bug description

The binary profile reader in _remote_debugging (used by python -m profiling.sampling replay and --diff-flamegraph) reconstructs
run-length-encoded (STACK_REPEAT) samples in binary_reader_replay. On every
status change within a repeat record it allocates a fresh timestamp list sized to
the whole remaining sample count (PyList_New(count - i)) and later trims it with
PyList_SetSlice. When the per-sample status byte alternates, this allocates and
trims an ~count-sized list for every sample, so replaying a single repeat record
is O(count**2) in time.

count is bounded only by the file size (remaining_data / 2), so a large but
otherwise valid .pyb file reaches the quadratic regime. Memory stays bounded;
only CPU time is unbounded (a ~2 MB profile takes minutes, and it scales
quadratically from there).

Reproducer

import os, tempfile, time
from _remote_debugging import (
    FrameInfo, LocationInfo, ThreadInfo, InterpreterInfo, THREAD_STATUS_HAS_GIL,
)
from profiling.sampling.binary_collector import BinaryCollector
from profiling.sampling.binary_reader import BinaryReader

class NullCollector:
    def collect(self, samples, timestamps): pass
    def export(self, filename): pass

def timed(n):
    fn = tempfile.mktemp(suffix=".pyb")
    frame = FrameInfo(("rle.py", LocationInfo((1, 1, 0, 0)), "f", None))
    writer = BinaryCollector(fn, 1000, compression="none")
    for i in range(n):
        status = THREAD_STATUS_HAS_GIL if i % 2 else 0
        interp = InterpreterInfo((0, [ThreadInfo((1, status, [frame]))]))
        writer.collect([interp], timestamp_us=1000 + i)   # same stack -> one repeat record
    writer.export(None)
    t0 = time.perf_counter()
    with BinaryReader(fn) as reader:
        reader.replay_samples(NullCollector())
    os.unlink(fn)
    return time.perf_counter() - t0

for n in (50_000, 100_000, 200_000):
    print(n, f"{timed(n):.2f}s")
# Doubling n roughly quadruples the time (quadratic).

Expected behavior

Replay time should be linear in the number of samples. The list for each
status run should be built to its exact length (e.g. PyList_New(0) +
PyList_Append) instead of over-allocating to the remaining count and trimming
per status change.

Linked PRs
  • gh-152722

贡献指南

打开贡献指南

从这里开始

  1. 先读完整个 Issue,再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库,在一个分支上完成修改。
  4. 提交 Pull Request,并在描述里引用这个 Issue 编号。

调研方向

从 profiling/sampling/binary_reader.py 和 binary_reader_replay 入口点开始,然后审查关联的 PR gh-152722。使用提供的交替状态 profile 进行复现,并验证 replay 相对于 sample 数量仍保持线性,同时保留 replay 的 sample 和时间戳。

由索引模型根据 Issue 内容生成。

评估

技术栈
c, python
领域
performance, tooling
Issue 类型
缺陷
难度
3/5
预计耗时
1-2 天
活跃度
停滞
描述清晰度
描述清楚
新手友好度
25/100

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。