RFR: 8373490: JFR Leak Profiler: path-to-gc-root very slow for large object arrays

[Erik Gahlin]

On Fri, 12 Dec 2025 07:36:57 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

> I see a steep performance decrease (as in: path-to-gc-root can hang for minutes or hours) with the JFR Leak Profiler under the following conditions:
> 
> 1) We have large object arrays on the heap
> 
> 2) We start with BFS, but at some point, we fallback to DFS. This happens when the BFS edge queue becomes too large (see https://github.com/tstuefe/jdk/blob/1bbbce75c5e68429c2a32519eb3c36d964dcdf57/src/hotspot/share/jfr/leakprofiler/chains/bfsClosure.cpp#L142-L144). This, in turn, is more likely to happen with large object arrays.
> 
> Both BFS and DFS are very fast on their own; when one enforces DFS (via the SkipBFS parameter), all is well. If BFS runs without DFS, all is well, too. The problem only occurs when mixing these two.
> 
> The problem is more likely with large object arrays on small heaps, since the size of the BFS edge queue is tied to 1/20 of the heap size. The problem can be provoked more easily by artificially decreasing the size of the BFS edge queue in the code.
> 
> In my tests (a modified variant of `TestJcmdDumpPathToGCRoots.java`), with a BFS edge queue size artificially reduced to 4 MB, I could reproduce the problem with an object array of 200k - 300k elements, with the following results:
> 
> - Object Array size of 200,000 elements: BFS only, all is well (~5 seconds)
> - Object Array size of 250,000 elements: BFS/DFS mixed, (~200 seconds)
> - Object Array size of 300,000 elements: BFS/DFS mixed, (~650 seconds)
> 
> The run time is the square of the array size, see explanation below. With the default edge queue size of 32MB, we only hit that DFS fallback path when processing arrays of >2mio, and for arrays as big as these, the search basically hangs forever.
> 
> Examining the problem more closely, I see:
> 
> - BFS search starts iterating over the object array. That many oops will saturate the queue. It will drop down to DFS for every single object element. That in itself is not the problem.
> 
> - It will then continue to process edges, and re-process the array oop over and over again: passing its oop down to `DFSClosure::find_leaks_from_edge` for every element inside this array. The effect is that, for an array of size N, we process that array oop N times. So the runtime will be O^2 with respect to the array size.
> 
> The reason for this is a missing mark check at the border between BFS and DFS. 
> 
> Tests:
> 
> - I provided a regression test that provokes the pathological behavior before the patch and is very quick to finish with the patch (TestJcmdDumpPathToGCRootsBFSDFS.java#bfsdfs...

Marked as reviewed by egahlin (Reviewer).

-------------

PR Review: https://git.openjdk.org/jdk/pull/28781#pullrequestreview-3571992566