_remote_debugging: quadratic replay time for RLE records with alternating status
Chưa có ai nhận issue này.
- Ngôn ngữ chính
- Python
- Star
- 77.2k
- Fork
- 35.9k
- Chỉ số merge pull request
- Chỉ số pull request đang chờ
Mô tả
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
Hướng dẫn đóng góp
Bắt đầu từ đâu
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Hướng nghiên cứu
Bắt đầu từ profiling/sampling/binary_reader.py và entry point binary_reader_replay, sau đó xem xét PR được liên kết gh-152722. Tái hiện bằng profile có trạng thái xen kẽ được cung cấp và xác minh rằng việc phát lại vẫn tuyến tính theo số lượng sample, đồng thời giữ nguyên các sample và timestamp được phát lại.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Đánh giá
- Công nghệ
- c, python
- Lĩnh vực
- performance, tooling
- Loại issue
- Lỗi
- Độ khó
- 3/5
- Thời gian dự kiến
- 1-2 ngày
- Mức độ hoạt động
- Đình trệ
- Độ rõ ràng
- Đặc tả rõ ràng
- Mức phù hợp với người mới
- 25/100