A sampling profiler periodically captures the call stack of a running program. Each snapshot contains function names ordered from the root function to the function that is currently executing.

Given a sequence of stack snapshots, convert it into trace events that describe when each function was active.

Each trace event has the following form:

(start_time, end_time, function_name)

The interval uses inclusive-exclusive notation: [start_time, end_time).

Example

t = 0: ["main"]
t = 1: ["main", "foo"]
t = 2: ["main", "foo", "bar"]
t = 3: ["main", "foo"]
t = 4: ["main"]
t = 5: []

The expected trace events are:

(0, 5, "main")
(1, 4, "foo")
(2, 3, "bar")

main first appears at time 0 and disappears at time 5, so its interval is [0, 5). The same rule produces [1, 4) for foo and [2, 3) for bar.

Key Observation

Two consecutive snapshots usually share several frames near the root of the stack. Those shared frames are still active and should not generate new events.

The first position at which the snapshots differ separates the stack into three parts:

  1. The shared prefix contains functions that remain active.
  2. Frames after the shared prefix in the previous stack have finished.
  3. Frames after the shared prefix in the new snapshot have started.

The shared portion is the longest common prefix of the two stacks.

Approach

Maintain an active stack of (function_name, start_time) pairs.

For every snapshot:

  1. Compare the active stack with the new snapshot to find their longest common prefix.
  2. Pop every active frame after that prefix and emit its completed event.
  3. Push every new frame after the prefix with the current timestamp.

The input should end with an empty snapshot. If it does not, append one to close every function still active at the end.

Events are emitted when functions disappear, so sort them before returning chronological output.

Important Details

  • Sorting is required because nested functions finish before their callers, while the output must remain chronological.
  • Assume the snapshots end with []; otherwise, use snapshots.append([]) to close the remaining functions.
  • Recursive calls are handled correctly because frames are compared by both name and stack depth.

Python Solution

def profiler_to_trace_events(snapshots):
    result = []
    stack = []  # Current stack with (function_name, start_time) pairs

    if snapshots and len(snapshots[-1]) != 0:
        snapshots.append([])

    for t, snapshot in enumerate(snapshots):
        # Find longest common prefix between current stack and new snapshot
        i = 0
        while i < len(stack) and i < len(snapshot) and stack[i][0] == snapshot[i]:
            i += 1

        # Finished functions
        while len(stack) > i:
            func_name, start_time = stack.pop()
            result.append((start_time, t, func_name))

        # new functions
        for j in range(i, len(snapshot)):
            stack.append((snapshot[j], t))

    # Sort by start time for consistent output
    result.sort()

    return result

Complexity Analysis

Let n be the number of snapshots and d be the maximum stack depth.

  • Time complexity: O(n * d) in the worst case. Each snapshot may require comparing or updating up to d frames.
  • Space complexity: O(e + d), where e is the number of emitted trace events. The active stack uses at most d entries.

Follow-Up 1: Sampling Noise Filtering

Sampling profilers can briefly capture a noisy frame that does not represent a real stack transition.

t = 0: ["main", "foo", "bar"]
t = 1: ["main", "foo", "baz"]  # noise
t = 2: ["main", "foo", "bar"]

Question

How would you filter out short-lived frames that appear in only one sample?

Hint

Use hysteresis: do not immediately emit end/start events when the stack changes. Hold the change as pending and commit it only after the same new stack appears in two consecutive samples. If the confirmed stack returns first, discard the pending change as noise.

Analysis: Three States

  • Stable: the confirmed stack currently producing trace intervals.
  • Pending: an unconfirmed candidate stack and the time it first appeared.
  • Snapshot: the newest observation being compared with the other two states.

Each sample creates one of three situations:

  1. snapshot == stable: the candidate was a one-sample deviation, so clear pending.
  2. snapshot == pending: increment its count and commit it after the second consecutive observation.
  3. Otherwise: store snapshot as a new pending candidate with count 1.

Noise Position Cases

  • Beginning: with no confirmed stack, a one-sample initial candidate is replaced and never emitted. The first stack seen twice becomes stable, starting at its first observation.
  • Middle: once bar is stable, one baz sample becomes pending. When bar returns, the code clears baz without closing or reopening any frame. The example assumes the bar stack was confirmed before the noisy transition.
  • End: a final one-sample candidate remains unconfirmed and is ignored. The explicit terminal [] then closes the last stable stack at the final timestamp.

The filter intentionally delays confirmation by one sample but records a confirmed transition at pending_time, preserving its first observed boundary.

Python Solution

def profiler_to_trace_events_with_filtering(snapshots):
    result = []
    stack = []  # Confirmed stack: (function_name, start_time)

    pending = None
    pending_time = None
    pending_count = 0

    for time, snapshot in enumerate(snapshots):
        stable = [function_name for function_name, _ in stack]

        # The confirmed stack returned, so the pending change was noise.
        if snapshot == stable:
            pending = None
            pending_time = None
            pending_count = 0
            continue

        # The same candidate appeared again, so confirm it.
        if snapshot == pending:
            pending_count += 1

            if pending_count >= 2:
                prefix_length = 0
                while (
                    prefix_length < len(stack)
                    and prefix_length < len(snapshot)
                    and stack[prefix_length][0] == snapshot[prefix_length]
                ):
                    prefix_length += 1

                # Apply the transition at its first observed time.
                while len(stack) > prefix_length:
                    function_name, start_time = stack.pop()
                    result.append((start_time, pending_time, function_name))

                for function_name in snapshot[prefix_length:]:
                    stack.append((function_name, pending_time))

                pending = None
                pending_time = None
                pending_count = 0
        else:
            # Begin tracking a different possible transition.
            pending = list(snapshot)
            pending_time = time
            pending_count = 1

    # A final [] is an explicit end-of-stream marker, not noise.
    if snapshots and snapshots[-1] == []:
        final_time = len(snapshots) - 1
        while stack:
            function_name, start_time = stack.pop()
            result.append((start_time, final_time, function_name))

    result.sort()
    return result

Follow-Up 2: Streaming Samples

If snapshots arrive one at a time, preserve the active stack between calls. flush() returns only events completed since the previous flush; it does not close functions that are still active. End the stream with addSample(final_time, []).

Use minimal memory (no need store all snapshots like Q1) 

TraceEvent = tuple[int, int, str]


class SamplingProfiler:
    def __init__(self) -> None:
        self.stack: list[tuple[str, int]] = []
        self.completed: list[TraceEvent] = []

    def addSample(self, time: int, stack: list[str]) -> None:
        prefix_length = 0

        # Find the longest common prefix.
        while (
            prefix_length < len(self.stack)
            and prefix_length < len(stack)
            and self.stack[prefix_length][0] == stack[prefix_length]
        ):
            prefix_length += 1

        # Close functions that disappeared.
        while len(self.stack) > prefix_length:
            function_name, start_time = self.stack.pop()
            self.completed.append((start_time, time, function_name))

        # Start functions that appeared.
        for function_name in stack[prefix_length:]:
            self.stack.append((function_name, time))

    def flush(self) -> list[TraceEvent]:
        result = self.completed
        self.completed = []
        result.sort()
        return result

Streaming Complexity

Let d be the maximum stack depth and c the number of events returned by one flush.

  • addSample: O(d) worst-case time and O(d + c) retained space.
  • flush: O(c log c) time for sorting and O(c) space for the returned events; internal state retains only the active stack afterward.

Follow-Up 3: Multi-Threaded Stacks

A multi-threaded profiler receives an independent call stack for each thread.

t = 0
T1: ["main"]
T2: ["worker"]

t = 1
T1: ["main", "foo"]
T2: ["worker"]

t = 2
T1: ["main"]
T2: ["worker", "task"]

t = 3
T1: []
T2: []

Example output:
(1, 2, "foo", "T1")
(0, 3, "main", "T1")
(2, 3, "task", "T2")
(0, 3, "worker", "T2")

Key Change

Use a separate active stack for each thread. Each stack is compared only with the next snapshot from the same thread.

Python Solution

def profiler_to_trace_events(samples):
    result = []
    stacks = {}  # thread_id -> [(function_name, start_time)]

    for time, thread_samples in enumerate(samples):
        for thread_id, snapshot in thread_samples.items():
            stack = stacks.setdefault(thread_id, [])

            # Find longest common prefix
            i = 0
            while (
                i < len(stack)
                and i < len(snapshot)
                and stack[i][0] == snapshot[i]
            ):
                i += 1

            # Functions that ended
            while len(stack) > i:
                func_name, start_time = stack.pop()

                result.append(
                    (start_time, time, func_name, thread_id)
                )

            # Functions that started
            for j in range(i, len(snapshot)):
                stack.append((snapshot[j], time))

    return result

Events are returned in completion order. An omitted thread is not processed at that timestamp; an explicit [] closes its active frames.

Multi-Threaded Complexity

Let n be the number of timestamps, T the number of threads, d the maximum stack depth, and e the number of events.

  • Processing one thread sample takes O(d) time, for O(n * T * d) worst-case total time.
  • Active stacks use O(T * d) space, and the result uses O(e) space.