python / python/cpython

_remote_debugging: quadratic replay time for RLE records with alternating status

オープン
#152,721 コメント 0 件 リアクション 1 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

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. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

調査の方向性

profiling/sampling/binary_reader.py と binary_reader_replay エントリーポイントから始め、リンクされている PR gh-152722 を確認します。提供されたステータス交互プロファイルで再現し、再生がサンプル数に対して線形のままであり、再生されたサンプルとタイムスタンプが保持されることを検証します。

索引モデルが issue の本文から書いたものです。

評価

技術スタック
c, python
領域
performance, tooling
issue の種類
バグ
難易度
3/5
見積もり時間
1〜2日
活発さ
停滞
明瞭さ
明確に書かれている
初心者へのやさしさ
25/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。