Saturday, January 26, 2008

Anti-pattern: Concurrent Modification and endless recursive

Lately I bounced into a great open source library for a project I did. All worked great until I kicked few threads into the game and let the app run for dew days.
In this point I have to note that I'm using a quad core on Mac and the single Java process with its dozen threads did use all of them.
After some time I noticed a significant CPU load that I could locate using a profiling tool. It seemed like there were few methods particular where the CPU spent most of its time in, and the count of these method calls was few orders of magnitude larger then in normal execution. They all looked like that:

void myMethod(Set mySet) {
try {
//iterate over a mySet and do something about them
} catch(ConcurrentModificationException cme) {
myMethod();
}
}

If 100% of the time the iteration will throw a ConcurrentModificationException then we will have an out of memory exception due to endless recursive. It might not be the case here since after a while the method does succeed. The thread that changes mySet will be done with it. But if you wish to make sure your code will never have an endless recursive you must be aware of this pattern.

Even if you think something can't happen (like an endless recursive call in myMethod) you must have boundaries to the depth of the recursive calls. And since recursive calls have memory penalty, unless its part of the algorithm it might be better to avoid them and use a loop.

Few options to get around it:
1. Use this pattern
void myMethod(Set mySet) {
boolean done = false;
for(int i = 0; i < MAX_TRIALS; i++)
//iterate over a mySet and do something about them

done = true;
} catch(ConcurrentModificationException cme) {
//log about it and write the #of trial
//roll back if needed
Thread.yield(); //Let the other thread be done
continue();
}
/* If you got to this point then no exception was thrown
and no need to do another iteration*/
break;
}
if(!done) throw new CouldNotCompleteException(MAX_TRIALS);
}
Note: You might wish to make MAX_TRIALS configurable.
2. Use a data structure from java.util.concurrent
It might not be possible, but if it is then use it. The sync overhead is minimal so if that’s what holding you from doing it then do a benchmark.

3. Use java.util.concurrent.locks
If you have control on the access to mySet, check out the tools in java.util.concurrent.locks, they are very powerful and efficient. Java had gone a long way in regards of concurrency performance.

0 comments:

Creative Commons License This work by Eishay Smith is licensed under a Creative Commons Attribution 3.0 Unported License.