Given an event stream containing enter X and exit X, rebuild the active invocation stack. Every exit corresponds to the latest enter that has not yet been closed. After each event, produce the active stack as a tuple, then combine adjacent equal tuples into one record carrying its run length or duration.
compress_trace(events)
The usual stack layout compares frames from the root toward the leaf. Reverse that viewpoint: compare stacks beginning at the leaf and moving toward the root, so leaf-side additions and removals can still be grouped when the calling chain changes. Explain how this reverses the matching procedure.
Assume a profiler records only the final m frames of a stack. Its hidden leading portion is unavailable, and the value of m is not known. Using only those observed suffixes, merge neighboring samples whenever they might describe one underlying logical stack. A commonly expected approach scans the suffix representation with two pointers or a sliding window. Be prepared to list the special cases caused by recursive invocations.
N repeated frames with one frame. Preserve timestamps so this reduction is limited by elapsed time rather than merely by the number of samples.struct Sample {
double ts; // input timestamps are in ascending order
std::vector<std::string> stack; // outermost (for example, "entry") -> innermost
};
struct Event {
std::string kind; // either "start" or "end"
double ts;
std::string name;
};
// Core behavior: compare adjacent samples and produce start/end changes.
compress_trace(events)
// - Leave frames that remain active in the last sample without emitted closing "end" records.
// - Handle recursion correctly: repeated names at separate depths are separate frames;
// Debounced variation: produce a start/end only after a frame occurs at the SAME stack
// location (identical parents and depth) for N successive samples. A mismatch clears
// its run; disjoint runs must never be combined.
compress_trace(events)
// The reset behavior is the frequent failure point:
// t=3 ["root","load"], t=4 ["root","load","parse"] -> root and load continue their runs.
// t=3 ["root","load"], t=4 ["worker","load","root"] -> root and load runs clear; every
// frame from t=3 closes before the replacement stack begins.
// A start timestamp may be taken from either the first or the Nth qualifying sample,
// provided that the same convention is used for every frame.