RFR JDK-7143928 : (coll) Optimize for Empty ArrayList and HashMap

Martin Buchholz martinrb at google.com
Wed Mar 27 05:18:26 UTC 2013

This adds an extra field to every ArrayList - a tax paid by every carefully
constructed ArrayList so that sloppy instances can get away with their
sloppiness, which is pretty distasteful.  If I was going to "spend" an
extra field of ArrayList, it would be to implement a circular array like
ArrayDeque and have O(1) deletion of element 0.

An alternative is to make elementData null when there are no elements.  We
can then reuse the size field for initialCapacity.  Yes, it's true that you
then have to introduce more null checks into the code, but hotspot will
likely do that anyways in the jitted code, and elide them if you provide
them, so cost of the null checks may be zero or even negative!

Much more difficult would be the alternative of automatically snipping the
tail (as with trimToSize) of any inactive ArrayList occasionally, e.g.
after a gc cycle.

More information about the core-libs-dev mailing list