Performance regression in OvershadowableManager

[jihoonson]

Affected Version

Since 0.16.

Description

OvershadowableManager was added in #7491 to manage all segments in the same time chunk. addChunk() is pretty slow when you have 1000+ segments per time chunk. Look at the below flame graph.

There are two slow parts in addChunk().

• It currently determines the state of the new atomicUpdateGroup by calling overshadows() against all existing segments. This stream contributes 77% to the total overhead. This should be fixed by navigating overlapping visible groups directly rather than iterating all visible groups.
• findLowestOverlappingEntry() contributes the remaining 23%. This is to skip non-overlapping entries in the map. This iteration is calling higherKey() to find the overlapping entries which traverses the tree from the root node every time.