[Bug]: Critical path is taxing on CPU when expanding span tags

[bobrik]

What happened?

We upgraded from v1.46 to v1.54 and some users noticed slowness when expanding tags. With some CPU tracing I was able to pinpoint #1871 as the culprit.

Steps to reproduce

1. Run Jaeger v1.54
2. Load a large trace
3. Try expanding/collapsing spans
4. Observe slowness

Expected behavior

Everything is snappy as it was.

Relevant log output

No response

Screenshot

Additional context

No response

Jaeger backend version

v1.54

SDK

No response

Pipeline

No response

Stogage backend

No response

Operating system

No response

Deployment model

No response

Deployment configs

No response

[MiirzaBaig]

Is it still on?
if yes would like to work on this!

[yurishkuro]

yes, there is an unfinished PR

[MiirzaBaig]

noted!

[BenzeneAlcohol]

This is happening because mergeChildrenCritialPath has a recursive function findAllDescendants that keeps calling descendents (children) of the span. In the wort case, each span could be checked once and hence the time complexity here is already O(n^2). And then filtering and merging adds some extra time.

We could simplify this by using a map, that stores the spans. This will take O(n) to create, but once created search operations would be processed in constant time. Now, using a stack we can push all the spans into the stack. If they have a child, they are pushed as well. In O(n) time we can evaluate the stack, and an O(m) time to filter and merge. Makes the time complexity better than the previous approach.

I can give a detailed explanation in the PR, if this idea sounds good and I can proceed.

cc: @yurishkuro

[yurishkuro]

@BenzeneAlcohol pre-building a map makes total sense. However, you may notice that we already build a tree when loading a trace (packages/jaeger-ui/src/selectors/trace.tsx). I would really like to have a way where that tree is not thrown away but reused for critical path and any other visitors. I think we keep rebuilding this tree multiple times for every trace.

[BenzeneAlcohol]

Yeah, I looked into it. I'll come up with an algo later today or tomorrow and post it here.