RFR: 8369039: JDK-8348611 caused regression in Javac-Hot-Generate [v3]

[Jan Lahoda]

On Wed, 8 Oct 2025 13:23:18 GMT, Claes Redestad <redestad at openjdk.org> wrote:

>> src/jdk.compiler/share/classes/com/sun/tools/javac/code/LintMapper.java line 180:
>> 
>>> 178: 
>>> 179:         final LintRange rootRange;                              // the root LintRange (covering the entire source file)
>>> 180:         final List<Span> unmappedDecls = new LinkedList<>();    // unmapped top-level declarations awaiting attribution
>> 
>> LinkedList has a ton of nodes, which translate to extra object headers, forward/backward pointers, and worse cache locality. To add N items, it requires O(N) allocations. In contrast, ArrayList requires O(log(N)) allocations (resizing) and is almost always better.
>
> @archiecobbs measured a win. I haven't seen it in profiles but it could be that the code in `afterAttr` contribute to the case for `LinkedList` as it is set up to remove matching item from the list, likely at an early index. Which is one of the few things a `LinkedList` actually does better than an `ArrayList`.

While I agree `ArrayList`s are often better, @archiecobbs measured the `LinkedList`s perform better here, as @cl4es says.

I am not quite clear why linked lists are faster, but it might be many of the lists are either empty (all the `children` of the leaf `LintRange` instances will be empty lists, I think, and an empty `LinkedList` is, I think, cheaper than an empty `ArrayList`), and some of them will have only a few entries (like the `unmappedDecls` list here: AFAIK, this has one entry for each top-level declaration, and hence is highly unlikely to have more than 2 entries - one for the package clause, and one for the top-level class). If `ArrayList`s with substantial number of entries are only a small minority, it might explain why the use of `LinkedList`s leads to better results.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/27651#discussion_r2413937369