I had a crash reported for one of my Android applications. Thankfully that includes a stack trace, because I would never have found this bug without it. I learned something new about concurrently accessing an ArrayList.
What was the error?
java.lang.NullPointerException
How embarrassing.
|
1 2 3 4 5 6 7 8 9 |
while(mPendingPath.size() >= 3) { Vec3 a = mPendingPath.get(0); Vec3 b = mPendingPath.get(1); Vec3 c = mPendingPath.get(2); ... mSections.addAll(generateCurved(a, b, c)); ... mPendingPath.remove(0); } |
generateCurved threw the exception because argument “c” was null. Really? I put a null in a list? How embarrassing. Let’s see, where does that list get added-to…
|
1 |
mPendingPath.add(mMaze.resolvePosition(next)); |
Just this one place. resolvePosition has multiple implementations, but they all return directly from new, like so:
|
1 |
return new Vec3(p.x, p.y, p.z).scale(mSpacing).add(mSpatialOrigin); |
new is returning null? Can’t be, it’s not allowed to. Even if it did return null, how did that get past the calls to scale and add? Those return this, so there’s no way this expression comes out null. What the hell?
Whatever’s going on, surely it hinges on there being multiple threads accessing this list, but usually that kind of thing throws ConcurrentModificationException when it’s not done correctly. ConcurrentModificationException is not a good litmus test, though, as it actually has little to do with multithreading. You can get it thrown with a single thread; all you have to do is get an iterator, modify the collection, and then try to use the iterator. This will do the trick:
|
1 2 3 |
for(Object o : objectList) { objectList.clear() } |
The iterator is the essential ingredient, here. The broken code is not using iterators, so of course there is no ConcurrentModificationException, but if mPendingPath was mishandled I would expect to see an IndexOutOfBoundsException.
I recreated the problem under laboratory conditions. This reliably fails:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
final ArrayList list = new ArrayList(); timer_a.schedule(new TimerTask() { public void run() { if(list.size() < 1000) { list.add(new Object()); } } }, 1, 1); timer_b.schedule(new TimerTask() { public void run() { int n = list.size(); for(int i = 0; i < n; i++) { if(list.get(i) == null) { fail(); } } if(n > 0) { list.remove(0); } } }, 1, 1); |
An ArrayList is, underneath it all, an array. Obviously. That array sometimes needs to grow larger, so ArrayList will allocate a new, larger array and then copy the contents of the old array. Is that it? Am I catching it in the middle of copying to a new array? Nope, adding a call to ensureCapacity beforehand doesn’t fix it. I’m removing the first element, so am I catching it in the middle of shifting the other elements down? Nope, removing the last element instead doesn’t fix it, and synchronizing the add with the null search doesn’t fix it, either.
So ArrayList is explicitly writing nulls when elements are removed? Those elements fall out of the list’s range, so why bother?
Because of garbage collection.
ArrayList.remove looks like this:
|
1 2 3 4 5 6 7 8 9 10 11 |
public E remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } |
Damnit, ArrayList is explicitly writing nulls. I didn’t synchronize add with remove because rare off-by-one errors would be harmless in my application. I did not expect magically-appearing nulls. So. Fine then. I’ve synchronized them.
I’m still not totally sold on Java garbage collection. You aren’t required to handle deallocation, but on the other hand you don’t get to control deallocation, and you do still have to worry about memory management details and leaks and such.
