pyroscope icon indicating copy to clipboard operation
pyroscope copied to clipboard

Improve tree insertion performance

Open abeaumont opened this issue 4 years ago • 0 comments

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.

abeaumont avatar Feb 01 '22 16:02 abeaumont