Saturday, 7 May 2011

An Immutable List in the JDK

It's quite strange that there is no immutable list class in the JDK, immutability is most likely the biggest part of any concurrent design.  It's well understood that an immutable object can be safely passed or accessed by other threads meaning that it is not necessary to lock.

It's not quite true that there is no immutable lists in the JDK, there is always the Collections#unmodifiableList method, return a wrapper around the supplied List that does not allow modification.  However, it is only a wrapper and the underlying data structure can be modified so there are no guarantees about immutability, only conventions which are only convention if you knew about it in the first place.  Or the guy before you did.

The problem with the unmodifiable list is that once you have it, there is no way to check if it is unmodifiable.  The implementation class, UnmodifiableList is package protected so it is not possible even to do an instanceof check.  I have found this to be a big source of inefficiency.  There is no way to check if the list is immutable so if you must have an immutable list you can "ask" via documentation that lists should be immutable or defensively copy the list.  Typically I would using defensive copying, because there is no way to know how the code is going to be used in the future and if the engineer is going to check the documentation.  I'm not even sure that it is a reasonable requirement to ask someone to check the small print for every method they use.

The fix for this is relatively easy and even doable without hacking the OpenJDK by using the -XbootClasspath command line option.  Using this you can specify the boot classes you want to load, by default its your JRE rt.jar.  If you modify some JDK classes you can specify that to be loaded first and then rt.jar so your modified classes will be first to load.

All that needs to be done as a starting point is to make the UnmodifiableList class public and make that the return type from Collections#unmodifiableList instead of List so we know what we're getting and other classes can pass it around also.  It doesn't fix the possibility of the data structure being modified but we're 80% of the way there for such a small change.  Because UnmodifiableList is still a List implementation all current code will still compile. 

Unfortunately it is not legal to deploy this change to a production system, it's only for fun.