GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — _remote_debugging: quadratic replay time for RLE records with alternating status · Issue #152721 · python/cpython

_remote_debugging: quadratic replay time for RLE records with alternating status #152721

New issue
Copy link
New issue
Copy link
Closed
#152722
Closed
_remote_debugging: quadratic replay time for RLE records with alternating status#152721
#152722
Copy link
Labels
extension-modulesC modules in the Modules dirC modules in the Modules dirtopic-profilingtype-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

Description

@tonghuaroot
tonghuaroot
opened on Jul 1, 2026
Issue body actions

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-152721: Fix quadratic RLE replay time in the profiling binary reader #152722
  • [3.15] gh-152721: Fix quadratic RLE replay time in the profiling binary reader (GH-152722) #158850
Reacted by Maurycy Pawłowski-Wieroński

Activity

  1. StanFromIreland
    added
    type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error
    extension-modulesC modules in the Modules dirC modules in the Modules dir
    on Jul 1, 2026
  2. tonghuaroot
    added a commit that references this issue on Jul 2, 2026

    pythongh-152721: Clarify the batch-list comment

    beb5980
  3. serhiy-storchaka
    added
    topic-profiling
    on Jul 3, 2026
  4. pablogsal
    added 2 commits that reference this issue on Oct 5, 2026

    pythongh-152721: Test replay batches beyond the RLE limit

    e3327f5

    gh-152721: Fix quadratic RLE replay time in the profiling binary read…

    e4a2473
  5. pablogsal
    closed this as completedin #152722on Oct 5, 2026
  6. pablogsal
    added 3 commits that reference this issue on Oct 5, 2026

    [3.15] gh-152721: Fix quadratic RLE replay time in the profiling bina…

    ebaca2a

    Revert "[3.15] pythongh-152721: Fix quadratic RLE replay time in the …

    80eb57e

    [3.15] Restore deferred backports for 3.15.1, including GH-158874 (#1…

    4ceb3fa
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

    extension-modulesC modules in the Modules dirC modules in the Modules dirtopic-profilingtype-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      You are visitor 01402503 — GeezerVison does not store the pages you look up.
      Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.