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).
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.
Activity
pythongh-152721: Clarify the batch-list comment
pythongh-152721: Test replay batches beyond the RLE limit
gh-152721: Fix quadratic RLE replay time in the profiling binary read…
[3.15] gh-152721: Fix quadratic RLE replay time in the profiling bina…
Revert "[3.15] pythongh-152721: Fix quadratic RLE replay time in the …
[3.15] Restore deferred backports for 3.15.1, including GH-158874 (#1…