search

grafana / pyroscope

Continuous Profiling Platform. Debug performance issues down to a single line of code
https://grafana.com/oss/pyroscope/
GNU Affero General Public License v3.0
9.87k stars 585 forks source link

Improve tree insertion performance #787

Closed abeaumont closed 1 year ago

abeaumont commented 2 years ago

Currently, tree insertion keeps track of children nodes in a sorted slice and new children nodes are inserted in order. The complexity of insertion is thus O(n) in the worst case. Switching to a balanced binary search tree, this operation could become O(log n), so this should be, in theory, an improvement.

As discussed in https://github.com/pyroscope-io/pyroscope/pull/773#discussion_r794604814, tree insertion is in the hot path, making this potential improvement interesting to scale the number of applications.

Rperry2174 commented 1 year ago

we've made a lot of improvements here going to close this -- we can re open with more specific task if needed