On Tue, 16 Apr 2002, Jack, Paul wrote: > Attached is a new List implementation inspired by > but faster than FastArrayList. From the javadoc:
Is there any external behavior difference between FastArrayList and your OptimizedFastArrayList (other than performance)? If so, can you explicitly specify the differences and why? If not, is there a reason not to just replace the existing FastArrayList with the faster implementation? > Read access to this list is not synchronized, but write > access is. To pull this trick off, the state of the list > is cloned during a write, the changes are applied to the > clone, and then the clone replaces the list's state. Read > operations use a local reference to the old state, and are > not adversely affected by a write. This is similar to > org.apache.commons.collections.FastArrayList. is it me, or does this behavior suffer from the double checked locking problem? While this isn't the exact same scenario (i.e. the double checking of a variable one in and one outside a synchronized block), I believe the situation is the same: it is possible that a non-synchronized read can see the cloned object before that cloned object is fully created. For more information on the double checked locking, see this excellent writeup: http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html Other writeups: http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html http://www.javaworld.com/javaworld/jw-05-2001/jw-0525-double.html The JSR for "fixing" the Java memory model: http://jcp.org/jsr/detail/133.jsp [Paul, I don't mean to pick on you about this. The existing Fast* classes suffer from the exact same problem] > However, since the list is backed by a dynamic array, *many > of the algorithms that alter the list already require that > the state be cloned*. For instance, to remove an element, > a new array must be allocated, and the elements from the old > array (minus the removed object) must be copied to the new > array. FastArrayList essentially performed the cloning twice: > It first clones the entire list, and then performs the costly > remove() operation on the copy. This implementation is > optimized such that a new array is only allocated once. > Assuming no monitor contention, this class should perform > similarly to java.util.ArrayList, except for the add(Object) > and set(int, Object) methods, which now perform in linear time. Actually, if the ArrayList implementeds were smart, they aren't "cloning" the array each time, they are just adding the element in an existing, but empty, slot in the array. That is, the underlying array is possibly larger than ArrayList.size(). An add(Object) only needs to duplicate the array if the existing array is full. An add(int, Object) may need to "move" elements, but shouldn't need to clone the entire array. The actual cloning of the array (to grow or shrink the size) can have an amortized constant time operation if the the array is doubled when a grow is required (and if you add in the shirnking, which I don't think the JDK impl does, you would halve the size of the array when it is 1/4 full). In your version, you may even be able to get rid of the single clone using a similar technique. For example, if you are adding to the end (add(Object)), if the array already has room for one more element, you could just increase the size and create a new State rather than a new State *and* a new array. When removing the last element, use the same array, but create a new State with the smaller size. I'm not sure if that really buys much though, as it requires excess memory for the empty array elements that are only used if an add operation occurs sometime in the future. Considering that the underlying ArrayList impl uses that memory anyway, I'm not sure this is that big of a deal when considered as a replacement of FastArrayList. regards, michael -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
