Tree implementation is very slow for large trees #4827

We have very deep and very wide flamegraphs for some services. Think 200 frames deep and 800k unique stacks with very long frame names. It can easily take 2.3s just to build a model.Tree instance.

Our stacks already come pre-optimized with interned strings:

type Stack struct {
	Frames []unique.Handle[string]
	Value  uint64
}

Playing around with different implementations, the following seems to be the winner:

type node struct {
	self  int64
	total int64
	edges []edge
}

type edge struct {
	name  unique.Handle[string]
	child *node
}

type Tree struct {
	root *node
}

func NewTree() Tree {
	return Tree{root: &node{}}
}

func (t *Tree) InsertStack(v int64, stack ...unique.Handle[string]) {
	if v <= 0 {
		return
	}

	n := t.root
	for _, s := range stack {
		n.total += v

		var child *node
		for _, edge := range n.edges {
			if edge.name == s {
				child = edge.child
				break
			}
		}

		if child == nil {
			child = &node{}
			n.edges = append(n.edges, edge{
				name:  s,
				child: child,
			})
		}

		n = child
	}

	n.total += v
	n.self += v
}

On my M3 Pro laptop:

• Baseline: 430ms
• Using map[unique.Handle[string]]: 340ms
• Optimized code above: 160ms

For the top 2.3s number we see in production we see a reduction to 0.5s. Here's a flamegraph to compare:

Currently we carry this implementation as a full replacement, but it would be nice if it was fast upstream instead. It's very possible that there's an even faster implementation, but it probably starts with unique.Handle[string] for frames too.