Building a Flame Graph from a Set of Stack Samples

A folded stack file is the intermediate representation that every flame graph shares. One line per unique stack, the frames separated by semicolons from outermost to innermost, followed by a count. Building the graph from that file is a sequence of three operations, and each one has a convention baked into it that changes what the resulting picture asserts.

main;handle_request;parse_headers;memchr 412
main;handle_request;parse_headers;parse_field 87
main;handle_request;encode_response;writev 255
main;event_loop;poll 903

The fold step decides what a frame means

Producing folded lines from raw samples is where most of the ambiguity lives. A sample is a list of addresses innermost-first; the folded format is outermost-first and semicolon-joined, so the conversion reverses each chain. Samples whose stacks cannot be fully walked become shorter chains, and a truncated stack quietly merges into the parent’s subtree as if the missing frames did not exist. A sample from a thread whose stack consists of a single frame is indistinguishable from a sample of a program that really was executing at top level.

Frame naming determines whether the graph is legible or a wall of duplicates. Argument lists, return types, and template parameters create dozens of nodes that are the same code instantiated differently. Stripping arguments and template parameters collapses them, at the cost of hiding instantiation-specific problems. Mangling must be undone before stripping, or every C++ frame carries an encoded type name.

There is a second naming decision that matters more than it looks: whether the frame label carries the library or module, or only the function name. Two functions with the same name in different modules will either merge into one node or remain distinct, and merging them produces a node whose width is the sum of unrelated costs.

Merging is a trie, not a tree, and the difference is the point

The obvious data structure is a tree of distinct stacks. The flame graph instead merges by prefix: every stack is inserted into a trie whose nodes are (parent, frame) pairs, and each node’s count is the number of samples passing through it. Inserting s stacks of average depth d costs O(sd) node visits, and the resulting trie has one node per distinct prefix, not one per distinct stack.

The consequence is the central property of the visualisation. A node’s count is the total time in that frame regardless of what it called. A node that appears in many different call paths is drawn once, as wide as the sum of all paths through it. That makes the graph read as “this function consumed this fraction of samples”, which is a flat-profile statement, with the stack context available by reading upward. A strict call tree would instead draw the function once per caller, splitting its width; the graph would then answer “which caller made this expensive” more directly but would make the aggregate cost of the function hard to see at a glance.

Because counts are summed along prefixes, the root’s count equals the total sample count, and every level’s total equals the root’s total. Any node’s width as a fraction of the root is its share. That invariant breaks the moment stacks of different lengths are mixed: if some samples are missing frames, the depths differ and the invariant still holds arithmetically but no longer means what it appears to. Keeping all stacks at a uniform, complete depth is what makes the comparison between levels meaningful.

Sorting the children

Children are laid out left to right in sorted order, normally by name. Sorting is not cosmetic. It is what makes two graphs of the same program comparable: a node in the same position has the same name and roughly the same neighbours, so a difference between the two pictures appears as a changed width rather than as a rearranged set of rectangles. Without a stable sort, every regeneration moves the boxes and the eye cannot track them.

Sorting by width instead puts the largest child first and makes the hot paths easy to find, at the cost of stability across runs. A hybrid that sorts by width within a sorted-by-name parent gives both, but it produces a layout that flips whenever a width ordering changes, which is exactly the situation a comparison is trying to detect.

The other layout choice is the height. A fixed box height per level means a deep stack is drawn taller; a fixed total height means levels compress as depth grows. Compression keeps the image a constant size but makes deep stacks hard to read, and it forces a decision about what to do with stacks deeper than the available pixels: truncate at some depth, which hides cost, or merge the remainder into one line, which attributes it to a single arbitrary frame.

Width rounding and the smallest visible bar

Pixels quantise. A graph 1,200 pixels wide with 100,000 samples gives one pixel per 83 samples, so every node narrower than that is drawn as either zero or one pixel, and the choice is a rounding artefact. When many tiny nodes round up to one pixel each, the total drawn width exceeds the container and the layout must compensate, shifting every subsequent node. The errors accumulate along the row, so a node near the right edge can be displaced by several pixels relative to its true position.

The practical rule is that a flame graph resolves shares down to roughly the pixel width divided by total samples. A 3,000-sample profile cannot show anything narrower than about 0.1% even at full image width, and the sampling error at that count is far larger than the pixel resolution anyway. The graph is a display of counts that already carry the error discussed in sampling error; zooming into a narrow bar does not add information.

Reading downward versus reading across

The graph is usually described as being read top-down: the bottom row is the entry point, and each row above is a caller of the row below. That orientation makes the top edge the leaf functions, and a wide plateau at the top is where the CPU was at the sampled instants.

Reading upward answers a different question. Starting from a wide leaf and following its ancestors to the root identifies the call path that is responsible for it; though only if the propagation of a cost up the stack is done by eye. A function that is wide at its own node but has many parents shares its cost across them, and the graph does not divide the width among them. Determining which caller dominates requires either filtering the collapsed stacks by a predicate or using an inverted layout, where the tree is built from the leaf outward and the callers of a function appear as its children.

Inverted graphs are the right tool for “who calls this slow function”, and they are generated from the same folded data by reversing each stack before insertion. Because the merge is still by prefix, the inverted graph merges by suffix, and a function called from ten sites appears once with ten children. The arithmetic is identical; only the direction of the trie changes.

Colour, and what it does not encode

Colour in most implementations is arbitrary or derived from the frame name, chosen so that adjacent frames differ. It carries no measurement. A palette keyed to a category; kernel, user, library; carries one bit of classification, which is occasionally useful and never quantitative. Reading a graph for a colour gradient that is not there is a common misreading, and the fix is to keep colour deterministic from the name, so that the same frame is the same colour in two graphs.

A differential flame graph, by contrast, does encode data in colour: red for increased width and blue for decreased, with saturation proportional to the change. Its construction and its pitfalls are the subject of differential profiles, but one point belongs here: a differential graph must be laid out on the union of the two tries, with missing nodes counted as zero, or unchanged nodes shift position and the colour comparison becomes meaningless.

Implementing the build in a few dozen lines

import collections

def build_trie(path):
    """Fold a collapsed stack file into a prefix trie of counts."""
    root = {}
    with open(path) as fh:
        for line in fh:
            stack, _, count = line.rstrip("\n").rpartition(" ")
            if not count.isdigit():
                continue
            node = root
            for frame in stack.split(";"):
                node = node.setdefault(frame, {})
            node[""] = node.get("", 0) + int(count)  # leaf marker and count
    return root

def totals(node, out, prefix=()):
    """Annotate every node with the total count in its subtree."""
    leaf = node.pop("", 0)
    total = leaf
    for name in sorted(node):            # stable order = comparable layouts
        total += totals(node[name], out, prefix + (name,))
    out[prefix] = total
    return total

The "" key holds the self count, kept separate from child frames so a frame name can never collide with it in practice; the alternative is a wrapper object. Sorting at insertion time rather than at draw time yields the stable layout described above. Summing on a second traversal rather than during insertion keeps the fold linear in the number of stack lines and the totals linear in the number of nodes.

Two properties of this code are worth noticing because they carry over to any implementation. Memory is proportional to the number of distinct prefixes, not to the number of samples, so a million samples from a deep recursive program can produce a trie with a small number of nodes if the recursion path is uniform, and an enormous one if it is not. And the count at each node is a sum of integers, so no floating-point rounding enters the picture until the widths are computed at draw time.

Choosing between a graph and a table

A flame graph’s advantage is that it shows the whole call structure at once, including the deep, narrow paths that a top-ten list would omit. Its disadvantage is that it does not quantify precisely. When the question is “how much did this function cost”, a sorted table of self counts answers it with a number, and the graph answers with a width. When the question is “where in this tree is the cost concentrated”, the graph is the only practical form, because it preserves the hierarchy that a table flattens.

Both come from the same folded file, so the cost of producing both is one fold. The choice is presentational, and it should be made after the fold, not instead of it.