Flamegraph appears to be O(N^2) in complexity.

eclipse-tracecompass-incubator / org.eclipse.tracecompass.incubator

Eclipse Public License 2.0

2 stars 11 forks source link

Flamegraph appears to be O(N^2) in complexity. #9

Open MatthewKhouzam opened 5 months ago

MatthewKhouzam commented 5 months ago

The Incubator Flamegraph appears to be O(N2) in terms of complexity. Simple profiling showed the getNextFunction in callstack.java to be called over 4b times for a 5M event trace.

Potential solutions:

Do away with the querySingleState and replace it with a query2d and a cache.
Fix the algorithm to return to O(N)
Both!

bhufmann commented 5 months ago

Thanks for issue. Shouldn't be this issue be in the mainline eclipse-tracecompass after it was mainlined there?

MatthewKhouzam commented 5 months ago

I suspect it will. I wanted to investigate the issue before posting in main