Profiler Stack Samples

A sampling profiler hands you periodic call-stack snapshots. Turn them into trace events, then into call records, a total/self time profile, a merged call tree, and finally folded flamegraph output that survives sampling gaps.

Step 1 — Stack sample events

A profiler periodically records snapshots of a program's call stack. Each snapshot is a (timestamp, stack) pair, where the stack is listed outermost frame first.

Convert the snapshots into a sequence of trace events.

def convert_stack_samples_to_events(samples: List[Tuple[int, List[str]]]) -> List[List]

A call emits a start event when it appears at a stack depth where it was not present in the previous snapshot.
A call emits an end event when it was present at some depth in the previous snapshot but is no longer present at that same depth in the current snapshot.
A frame only continues if every frame above it also continues: once depth d changes, everything below it ends too.
At the same timestamp, emit all end events first, deepest frame to shallowest; then all start events, shallowest to deepest.
Do not emit end events for frames still active in the final snapshot.
Recursive calls at different depths are different active calls.

Each event is a list [kind, timestamp, name].

samples = [
    (4,  ["entry"]),
    (6,  ["entry", "parse"]),
    (9,  ["entry", "parse", "tokenize"]),
    (11, ["entry", "render"]),
]

convert_stack_samples_to_events(samples)
# [["start", 4,  "entry"],
#  ["start", 6,  "parse"],
#  ["start", 9,  "tokenize"],
#  ["end",   11, "tokenize"],
#  ["end",   11, "parse"],
#  ["start", 11, "render"]]

entry gets no end event: it is still on the stack in the last snapshot.