Skip to content

Commit 182b010

Browse files
reaperhulkclaudenedbat
authored
perf: resolve sysmon branch events lazily, one pair at a time (#2221)
* perf: resolve sysmon branch events lazily, one pair at a time On the first BRANCH_LEFT/RIGHT event of every code object, the sysmon core precomputed branch trails for every branch site in the code object: two full dis.get_instructions() decodes (branch_trails and always_jumps each built their own InstructionWalker), two trail walks per conditional jump, and re-registration of every trail under every offset it contains. On test-suite-shaped workloads — thousands of code objects, most branches executed a handful of times — this analysis dominates: branch mode on the pyca/cryptography suite (4,277 tests, 5,671 traced code objects) costs +35% vs +2% for line mode (issue #2172). But branch events are one-shot: each (site, direction) fires once and is then DISABLEd, so at most two pairs per branch site ever need resolving, and only for branches that actually execute. Replace the precompute with a BranchArcResolver that resolves each (source offset, destination offset) pair as it arrives, walking the raw co_code bytes from the destination — following unconditional jumps, skipping CACHE and EXTENDED_ARG, stopping at a new source line (arc), a return (arc to exit), or another branch possibility (no arc: that branch produces its own events). Lines come from the byte_to_line dict the tracer already builds, so nothing in the branch measurement path disassembles whole code objects any more. branch_trails(), always_jumps(), and InstructionWalker become unused and are removed. Computing jump targets needs the number of inline CACHE entries that follow the jump instruction (jump distances are measured from the end of the caches). Rather than reading opcode._inline_cache_entries — a private table whose shape has already changed once (list in 3.11, dict in 3.12) — the resolver counts the CACHE opcodes directly in co_code: exact by construction, self-consistent with the code object being walked, and no private API. Measured on the cryptography suite (Python 3.14.2, branch mode, wall time best of 3, base 35.44s): 47.90s (+35.2%) before, 38.33s (+8.2%) after; combined with the sysmon-multiline-map branch the overhead is at the run-to-run noise floor (~0-2%). Correctness verified by: coverage's own test suite under COVERAGE_CORE=sysmon on 3.14 (identical failure set to main, all environmental); resolving 17,445 (source, dest) pairs across 3,571 code objects identically to a dis-based reference implementation; and byte-identical 'coverage report' output on the cryptography suite (26,376 statements, 2,484 branches). The raw arc data differs by five arcs on that suite: the old code's byte_to_line fallback recorded arcs between two lines inside the same multi-line statement, which the resolver correctly attributes to the statement's first line; all five collapse to self-arcs at report time. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_0137DLbSXfm5v5bhCcz7xEKM * update changes --------- Co-authored-by: Claude <[email protected]> Co-authored-by: Ned Batchelder <[email protected]>
1 parent ee271ee commit 182b010

3 files changed

Lines changed: 110 additions & 177 deletions

File tree

‎CHANGES.rst‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,14 +30,16 @@ Unreleased
3030

3131
- A number of performance improvements thanks to Paul Kehrer, in pull requests
3232
`2213 <pull 2213_>`_, `2214 <pull 2214_>`_, `2215 <pull 2215_>`_, `2216
33-
<pull 2216_>`_, `2218 <pull 2218_>`_, and `2220 <pull 2220_>`_.
33+
<pull 2216_>`_, `2218 <pull 2218_>`_, `2220 <pull 2220_>`_, and `2221 <pull
34+
2221_>`_.
3435

3536
.. _pull 2213: https://github.com/coveragepy/coveragepy/pull/2213
3637
.. _pull 2214: https://github.com/coveragepy/coveragepy/pull/2214
3738
.. _pull 2215: https://github.com/coveragepy/coveragepy/pull/2215
3839
.. _pull 2216: https://github.com/coveragepy/coveragepy/pull/2216
3940
.. _pull 2218: https://github.com/coveragepy/coveragepy/pull/2218
4041
.. _pull 2220: https://github.com/coveragepy/coveragepy/pull/2220
42+
.. _pull 2221: https://github.com/coveragepy/coveragepy/pull/2221
4143
.. _pull 2224: https://github.com/coveragepy/coveragepy/pull/2224
4244

4345
.. start-releases

‎coverage/bytecode.py‎

Lines changed: 89 additions & 136 deletions
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,9 @@
55

66
from __future__ import annotations
77

8-
import collections
98
import dis
109
from collections.abc import Iterable, Mapping
1110
from types import CodeType
12-
from typing import Optional
1311

1412
from coverage.types import TArc, TLineNo, TOffset
1513

@@ -108,148 +106,103 @@ def op_set(*op_names: str) -> set[int]:
108106
"RETURN_GENERATOR",
109107
)
110108

111-
# Opcodes that do nothing.
112-
NOPS = op_set(
113-
"NOP",
114-
"NOT_TAKEN",
115-
)
116-
117-
118-
class InstructionWalker:
119-
"""Utility to step through trails of instructions.
120109

121-
We have two reasons to need sequences of instructions from a code object:
122-
First, in strict sequence to visit all the instructions in the object.
123-
This is `walk(follow_jumps=False)`. Second, we want to follow jumps to
124-
understand how execution will flow: `walk(follow_jumps=True)`.
125-
"""
126-
127-
def __init__(self, code: CodeType) -> None:
128-
self.code = code
129-
self.insts: dict[TOffset, dis.Instruction] = {}
110+
# CACHE doesn't exist in Python 3.10, but the branch resolver is only used
111+
# on 3.14+, so a placeholder value is fine.
112+
_CACHE = dis.opmap.get("CACHE", -1)
113+
_EXTENDED_ARG = dis.opmap["EXTENDED_ARG"]
130114

131-
inst = None
132-
for inst in dis.get_instructions(code):
133-
self.insts[inst.offset] = inst
115+
# All opcodes with a jump target.
116+
JUMPS = set(dis.hasjrel) | set(dis.hasjabs)
134117

135-
assert inst is not None
136-
self.max_offset = inst.offset
118+
# Opcodes that jump backwards.
119+
BACKWARD_JUMPS = {op for op in JUMPS if "JUMP_BACKWARD" in dis.opname[op]}
137120

138-
def walk(
139-
self, *, start_at: TOffset = 0, follow_jumps: bool = True
140-
) -> Iterable[dis.Instruction]:
141-
"""
142-
Yield instructions starting from `start_at`. Follow unconditional
143-
jumps if `follow_jumps` is true.
144-
"""
145-
seen = set()
146-
offset = start_at
147-
while offset < self.max_offset + 1:
148-
if offset in seen:
149-
break
150-
seen.add(offset)
151-
if inst := self.insts.get(offset):
152-
yield inst
153-
if follow_jumps and inst.opcode in ALWAYS_JUMPS:
154-
offset = inst.jump_target
155-
continue
156-
offset += 2
157121

122+
class BranchArcResolver:
123+
"""Resolve branch events to line arcs, one (source, dest) pair at a time.
158124
159-
TBranchTrailsOneSource = dict[Optional[TArc], set[TOffset]]
160-
TBranchTrails = dict[TOffset, TBranchTrailsOneSource]
125+
Branch events are one-shot (they are DISABLEd after firing), so each
126+
(source offset, destination offset) pair is resolved at most a couple of
127+
times per code object. Resolving pairs on demand is much cheaper than
128+
precomputing trails for every branch in the code object, most of which
129+
never fire. We walk the raw bytecode bytes so that we never need to
130+
disassemble whole code objects with `dis`.
161131
132+
To resolve one pair:
133+
starting from the destination, follow the trail of instructions (through
134+
unconditional jumps) until we reach an instruction on a new source line
135+
(giving us the arc), a return (an arc to leaving the code object), or
136+
another branch possibility (no arc: that branch will produce its own
137+
events).
162138
163-
def branch_trails(
164-
code: CodeType,
165-
multiline_map: Mapping[TLineNo, TLineNo],
166-
) -> TBranchTrails:
167139
"""
168-
Calculate branch trails for `code`.
169-
170-
`multiline_map` maps line numbers to the first line number of a
171-
multi-line statement.
172140

173-
Instructions can have a jump_target, where they might jump to next. Some
174-
instructions with a jump_target are unconditional jumps (ALWAYS_JUMPS), so
175-
they aren't interesting to us, since they aren't the start of a branch
176-
possibility.
177-
178-
Instructions that might or might not jump somewhere else are branch
179-
possibilities. For each of those, we track a trail of instructions. These
180-
are lists of instruction offsets, the next instructions that can execute.
181-
We follow the trail until we get to a new source line. That gives us the
182-
arc from the original instruction's line to the new source line.
183-
184-
"""
185-
the_trails: TBranchTrails = collections.defaultdict(lambda: collections.defaultdict(set))
186-
iwalker = InstructionWalker(code)
187-
for inst in iwalker.walk(follow_jumps=False):
188-
if not inst.jump_target:
189-
# We only care about instructions with jump targets.
190-
continue
191-
if inst.opcode in ALWAYS_JUMPS:
192-
# We don't care about unconditional jumps.
193-
continue
194-
195-
from_line = inst.line_number
141+
def __init__(
142+
self,
143+
code: CodeType,
144+
byte_to_line: Mapping[TOffset, TLineNo],
145+
multiline_map: Mapping[TLineNo, TLineNo],
146+
) -> None:
147+
self.code = code
148+
# co_code re-copies the bytes on each access, so fetch it once.
149+
self.co_code = code.co_code
150+
self.byte_to_line = byte_to_line
151+
self.multiline_map = multiline_map
152+
153+
def line_at(self, offset: TOffset) -> TLineNo | None:
154+
"""The source line of the instruction at `offset`, de-multilined."""
155+
line = self.byte_to_line.get(offset)
156+
if line is not None:
157+
line = self.multiline_map.get(line, line)
158+
return line
159+
160+
def resolve(self, source: TOffset, dest: TOffset) -> TArc | None:
161+
"""Turn a branch event's (source, dest) offsets into an arc, or None."""
162+
from_line = self.line_at(source)
196163
if from_line is None:
197-
continue
198-
from_line = multiline_map.get(from_line, from_line)
199-
200-
def add_one_branch_trail(
201-
trails: TBranchTrailsOneSource,
202-
start_at: TOffset,
203-
) -> None:
204-
# pylint: disable=cell-var-from-loop
205-
inst_offsets: set[TOffset] = set()
206-
to_line = None
207-
for inst2 in iwalker.walk(start_at=start_at, follow_jumps=True):
208-
inst_offsets.add(inst2.offset)
209-
l2 = inst2.line_number
210-
if l2 is not None:
211-
l2 = multiline_map.get(l2, l2)
212-
if l2 and l2 != from_line:
213-
to_line = l2
214-
break
215-
elif inst2.jump_target and (inst2.opcode not in ALWAYS_JUMPS):
216-
break
217-
elif inst2.opcode in RETURNS:
218-
to_line = -code.co_firstlineno
219-
break
220-
if to_line is not None:
221-
trails[(from_line, to_line)].update(inst_offsets)
222-
else:
223-
trails[None] = set()
224-
225-
# Calculate two trails: one from the next instruction, and one from the
226-
# jump_target instruction.
227-
trails: TBranchTrailsOneSource = collections.defaultdict(set)
228-
add_one_branch_trail(trails, start_at=inst.offset + 2)
229-
add_one_branch_trail(trails, start_at=inst.jump_target)
230-
the_trails[inst.offset] = trails
231-
232-
# Sometimes we get BRANCH_RIGHT or BRANCH_LEFT events from instructions
233-
# other than the original jump possibility instruction. Register each
234-
# trail under all of their offsets so we can pick up in the middle of a
235-
# trail if need be.
236-
for arc, offsets in trails.items():
237-
for offset in offsets:
238-
the_trails[offset][arc].update(offsets)
239-
240-
return the_trails
241-
242-
243-
def always_jumps(code: CodeType) -> dict[TOffset, TOffset]:
244-
"""Make a map of unconditional bytecodes jumping to others.
245-
246-
Only include bytecodes that do no work and go to another bytecode.
247-
"""
248-
jumps = {}
249-
iwalker = InstructionWalker(code)
250-
for inst in iwalker.walk(follow_jumps=False):
251-
if inst.opcode in ALWAYS_JUMPS:
252-
jumps[inst.offset] = inst.jump_target
253-
elif inst.opcode in NOPS:
254-
jumps[inst.offset] = inst.offset + 2
255-
return jumps
164+
return None
165+
co_code = self.co_code
166+
max_offset = len(co_code)
167+
byte_to_line = self.byte_to_line
168+
multiline_map = self.multiline_map
169+
offset = dest
170+
ext_arg = 0
171+
seen: set[TOffset] = set()
172+
while 0 <= offset < max_offset and offset not in seen:
173+
seen.add(offset)
174+
op = co_code[offset]
175+
if op == _CACHE:
176+
offset += 2
177+
continue
178+
if op == _EXTENDED_ARG:
179+
ext_arg = (ext_arg | co_code[offset + 1]) << 8
180+
offset += 2
181+
continue
182+
line = byte_to_line.get(offset)
183+
if line is not None:
184+
line = multiline_map.get(line, line)
185+
if line and line != from_line:
186+
return (from_line, line)
187+
if op in JUMPS:
188+
if op in ALWAYS_JUMPS:
189+
arg = ext_arg | co_code[offset + 1]
190+
# Jump distances are measured from the end of the
191+
# instruction's inline CACHE entries, which appear in
192+
# co_code as CACHE opcodes immediately following it.
193+
next_offset = offset + 2
194+
while next_offset < max_offset and co_code[next_offset] == _CACHE:
195+
next_offset += 2
196+
if op in BACKWARD_JUMPS:
197+
offset = next_offset - 2 * arg
198+
else:
199+
offset = next_offset + 2 * arg
200+
ext_arg = 0
201+
continue
202+
# Another branch possibility: it will get its own events.
203+
return None
204+
if op in RETURNS:
205+
return (from_line, -self.code.co_firstlineno)
206+
ext_arg = 0
207+
offset += 2
208+
return None

‎coverage/sysmon.py‎

Lines changed: 18 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020
from typing import Any, NewType, Optional, cast
2121

2222
from coverage import env
23-
from coverage.bytecode import TBranchTrails, always_jumps, branch_trails, bytes_to_lines
23+
from coverage.bytecode import BranchArcResolver, bytes_to_lines
2424
from coverage.debug import short_filename, short_stack
2525
from coverage.exceptions import NoSource
2626
from coverage.misc import isolate_module
@@ -177,17 +177,9 @@ class CodeInfo:
177177
file_data: TTraceFileData | None
178178
byte_to_line: dict[TOffset, TLineNo] | None
179179

180-
# Keys are start instruction offsets for branches.
181-
# Values are dicts:
182-
# {
183-
# (from_line, to_line): {offset, offset, ...},
184-
# (from_line, to_line): {offset, offset, ...},
185-
# }
186-
branch_trails: TBranchTrails
187-
188-
# Always-jumps are bytecode offsets that do no work but move
189-
# to another offset.
190-
always_jumps: dict[TOffset, TOffset]
180+
# Lazily-created resolver of branch events to arcs, created on the
181+
# first branch event in the code object.
182+
branch_resolver: BranchArcResolver | None
191183

192184

193185
class SysMonitor(Tracer):
@@ -374,8 +366,7 @@ def sysmon_py_start(self, code: CodeType, instruction_offset: TOffset) -> Monito
374366
tracing=tracing_code,
375367
file_data=file_data,
376368
byte_to_line=b2l,
377-
branch_trails={},
378-
always_jumps={},
369+
branch_resolver=None,
379370
)
380371
self.code_infos[id(code)] = code_info
381372
self.code_objects.append(code)
@@ -460,34 +451,21 @@ def sysmon_branch_either(
460451
code_info = self.code_infos[id(code)]
461452
# code_info is not None and code_info.file_data is not None, since we
462453
# wouldn't have enabled this event if they were.
463-
if not code_info.branch_trails:
454+
resolver = code_info.branch_resolver
455+
if resolver is None:
464456
if self.stats is not None:
465457
self.stats["branch_trails"] += 1
466-
multiline_map = self.get_multiline_map(code.co_filename)
467-
code_info.branch_trails = branch_trails(code, multiline_map=multiline_map)
468-
code_info.always_jumps = always_jumps(code)
469-
# log(f"branch_trails for {code}:\n{ppformat(code_info.branch_trails)}")
470-
added_arc = False
471-
dest_info = code_info.branch_trails.get(instruction_offset)
472-
473-
# Re-map the destination offset through always-jumps to deal with NOP etc.
474-
dests = {destination_offset}
475-
while (dest := code_info.always_jumps.get(destination_offset)) is not None:
476-
destination_offset = dest
477-
dests.add(destination_offset)
478-
479-
# log(f"dest_info = {ppformat(dest_info)}")
480-
if dest_info is not None:
481-
for arc, offsets in dest_info.items():
482-
if arc is None:
483-
continue
484-
if dests & offsets:
485-
code_info.file_data.add(arc) # type: ignore
486-
# log(f"adding {arc=}")
487-
added_arc = True
488-
break
489-
490-
if not added_arc:
458+
assert code_info.byte_to_line is not None
459+
resolver = code_info.branch_resolver = BranchArcResolver(
460+
code,
461+
code_info.byte_to_line,
462+
self.get_multiline_map(code.co_filename),
463+
)
464+
arc = resolver.resolve(instruction_offset, destination_offset)
465+
if arc is not None:
466+
code_info.file_data.add(arc) # type: ignore
467+
# log(f"adding {arc=}")
468+
else:
491469
# This could be an exception jumping from line to line.
492470
assert code_info.byte_to_line is not None
493471
l1 = code_info.byte_to_line.get(instruction_offset)

0 commit comments

Comments
 (0)