Tree implementation is very slow for large trees
- 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.
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:
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.