RFR: 8263561: Re-examine uses of LinkedList

Maurizio Cimadamore mcimadamore at openjdk.java.net
Fri May 21 23:20:04 UTC 2021

On Fri, 21 May 2021 14:22:47 GMT, Daniel Fuchs <dfuchs at openjdk.org> wrote:

>> The usage of `LinkedList` is senseless and can be replaced with either `ArrayList` or `ArrayDeque` which are both more compact and effective.
>> jdk:tier1 and jdk:tier2 are both ok
> I don't remember all the comments you have received in this thread but have you verified that arbitrarily changing `LinkedList` into `ArrayList` in these classes is not going to significantly increase the footprint in the case where lists are empty or contain only one or two elements?
> I am not convinced that a global replacement of  `LinkedList` by `ArrayList` is necessarily good - even though I agree that `ArrayList` is generally more efficient.

I second the footprint concerns from @dfuch. I've seen with first hand cases where widespread uses of array lists for holding 1-2-3 elements (e.g. think of a graph where each node might only have a very small number of outgoing edges) lead to massive memory over-utilization. If the average size is known, at the very least I'd argue to replace with an array list which is sized correctly.

And, all this said, the general assumption implied in this PR which linked lists are just to be avoided doesn't match my experience. If you want a "pay only as much memory as you use" data structure, you don't care about random access (e.g. all accesses are linear walks), a linked list is a perfectly fine choice. If there are use cases in the JDK where a LinkedList is used in places where it shouldn't be, then obviously _those cases_ should be replaced.


PR: https://git.openjdk.java.net/jdk/pull/2744

More information about the net-dev mailing list