Folded Stacks, Call Trees, and What Aggregation Destroys

A sample is a stack: a sequence of return addresses from the innermost frame outward. A profile is many such sequences, and the question of how to store them is the question of which questions the profile will be able to answer later. Two representations dominate, and they are not interchangeable.

The first keeps each distinct stack as a unit and counts how many samples had exactly that stack. Written as one line per stack with the frames joined by semicolons and the count at the end, this is the folded format. The second merges samples into a tree in which each node is a function at a particular call path and holds the count of samples that passed through it. Both are derived from the same samples; both lose different information.

The folded format and its one advantage

A folded stack is a complete path from root to leaf, and a folded file is a multiset of paths with counts:

main;serve;handle_request;parse_body;json_parse 1841
main;serve;handle_request;parse_body;read_chunk 302
main;serve;handle_request;write_response 77
main;gc_mark 1204

Each line is one distinct stack. The format is a lossless encoding of the sample set at stack granularity: every sample is represented, the multiplicity is exact, and no information about which frames occurred together is discarded. It is also the format a flame graph consumes directly, since the graph is built by inserting each line into a tree and then laying out the nodes by count.

The disadvantage appears when the data is queried rather than drawn. Answering “how much time is in json_parse regardless of caller” requires scanning every line and summing those that contain the frame, which is a linear pass over the number of distinct stacks. Answering “what are the top ten leaf functions” requires the same pass. For a single file this is cheap; for a store holding months of folded data across thousands of hosts, it is a scan per query.

Folded stacks also do not merge cheaply across differing depth limits. If one host captured thirty frames and another captured sixty, the folded lines have different lengths and the same logical stack appears twice, once truncated. The truncation is not marked, so the merged file double-counts and the resulting graph shows two branches where there is one call path.

The tree and what it buys

A call tree makes the aggregation explicit. Each node holds a function identity, a count of samples in which this function was on the stack at this position, and links to children. Inserting a sample is a walk from the root down the frames, incrementing each node. The tree is the folded data with shared prefixes factored out, which is why a program with a hundred thousand distinct stacks can have a tree with a few thousand nodes: the prefixes are shared.

The tree answers the aggregate questions directly. A node’s count is the number of samples whose stack passed through that call path, so “time in json_parse from any caller” is the sum over all nodes for that function. The total under a node is the inclusive time for that call path, and the difference between a node’s count and the sum of its children’s counts is the exclusive time, the samples that landed in that function and nowhere deeper.

The cost is a loss of correlation. A tree records, for each function, how many samples reached it under each caller, but not which combinations of sibling frames occurred in the same sample. Two different leaf functions called from the same parent are indistinguishable in the tree from two samples of one and zero of the other, as long as the parent counts match. The folded format preserves the joint distribution; the tree preserves only the marginals along paths.

That loss matters for questions of the form “is this cost correlated with that one”, and it does not matter for questions of the form “where is the time”, which is the question profiles are usually asked.

Inclusive time and the recursion trap

Inclusive time is the count at a node, and it is the number that drives most misreadings. A function that appears at many call paths has its inclusive time distributed across many nodes, so no single node looks large while the function is the largest consumer in aggregate. A function that is called once near the root has an inclusive count equal to the whole profile, which is true and useless.

Recursion breaks the arithmetic outright. A recursive function appears at several depths in the same stack, and each appearance increments a different node, so summing the nodes for that function counts the same sample several times. The usual fix is to count each function once per sample, attributing the sample to the shallowest or the deepest occurrence depending on the question, and to mark recursive nodes so that a reader knows the tree is not a partition.

Tail calls produce the opposite distortion. A tail-called function does not appear as a separate frame, so its inclusive time is folded into its caller’s and the tree shows a function that is doing more work than its code. Neither the tree nor the folded format can recover the missing level, because the return address was never pushed.

Merging across hosts and across time

The reason representation matters operationally is that a fleet-wide profile is a merge of many local profiles, and the merge operation must be associative and cheap.

Trees merge by adding corresponding nodes, which requires the trees to have the same shape, which requires the same root and the same path prefix for every node. Two trees from hosts with different entry points do not share a root, so the merged result needs a synthetic root, and the paths beneath it are unrelated. This is why fleet-wide trees are usually keyed by a stack trace identifier and merged at the leaf level rather than node by node: identical stacks produce identical identifiers regardless of which host produced them.

Folded data merges by concatenating lines and summing counts for identical lines, which is a sort-and-aggregate operation. It is associative and commutative, so partial merges can be done anywhere and combined later. The catch is that the lines must be byte-identical, which means the frames must be symbolized before merging or the addresses must be identical, and identical addresses across hosts require identical builds. A fleet running several builds of the same service produces several disjoint sets of stacks that look like different code paths.

Symbolizing before merging solves the identity problem and creates a size problem: the merged lines are now long strings, and the count of distinct lines is the count of distinct symbolized stacks, which is larger than the count of distinct address stacks because the same address can symbolize differently across builds. The practical arrangement is to symbolize locally, fold locally, and merge the folded lines centrally, accepting that the merge key is the symbolized path rather than the address.

Depth limits and the truncation bias

Every collection pipeline has a maximum stack depth, imposed by buffer size, by the unwinder’s cost budget, or by a deliberate cap to control cardinality. The cap is not neutral: truncating a stack removes the outermost frames, which are the ones shared by many paths, so the effect on the tree is to collapse distinct call paths into a common prefix and to make the remaining structure look more concentrated than it is.

A profile with a depth cap of thirty-two and an average true depth of forty loses the eight outermost frames, which is usually harmless because those frames are the runtime’s entry path. A profile with a cap of sixteen on the same workload loses the distinction between several entry paths and merges their counts under whatever frame landed at position sixteen. The graph then shows a large node with many children, and a reader cannot tell whether that node is genuinely expensive or is a truncation artifact.

The honest fix is to record the truncation. A marker frame inserted at the cut point, or a per-profile count of truncated samples, makes the artifact visible and lets a query exclude or account for it. Without the marker, the profile is internally consistent and quietly wrong in a way that favours whatever sits at the boundary.

Choosing between them

The two formats answer different questions, and a pipeline that needs both can carry both. Folded stacks are the right storage format when the queries are ad hoc, when merges must be done in arbitrary order, and when the consumer is a visualization that wants raw paths. Trees are the right in-memory format when the queries are aggregate, when the consumer needs inclusive and exclusive time per node, and when the profile must be compared against another profile node by node.

The conversion from folded to tree is cheap and lossy; the reverse is impossible. That asymmetry suggests storing folded data and building trees on demand, which is what most continuous profilers do, at the cost of a rebuild per query. The alternative, storing trees and losing the joint distribution, is cheaper per query and permanently forecloses the questions that need per-sample correlation.

Whichever is stored, the merge key determines whether fleet-wide aggregation works at all. That key, and the normalization needed to make stacks from different hosts comparable, is the next problem, treated in Merging Profiles Across a Fleet Without Losing the Tail.