grafana / grafana/pyroscope

Tree implementation is very slow for large trees

Open
#4,827 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
11.7k
Forks
802
Avg merge
1d 19h
Merged PRs (30d)
80

Description

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.

Image

Our stacks already come pre-optimized with interned strings:

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

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

```go
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:

Image

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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.