The Surprising Performance Implications of .iterator()

This week I discovered a "gotcha" in the Java language that goes into the 'performance' pile, rather than the 'unusual behavior' pile. It has to do with iterators.

See I've been working on this implementation of Software Transactional Memory in Java, and the performance was pretty slow. Now I'm not really a run-time guy, so this fact normally wouldn't bother me, but it was slow enough that a static optimization that I developed was getting lost in the noise. So I busted out the old profiler to see what was slowing things down. I immediately discovered that our code was spending a lot of time iterating over sets, or at least that's how I first interpreted the results. And this made since to me. The run-time uses tons of sets; read sets, write sets, undo sets. And every time a transaction aborts or commits, we're iterating over lots of them, like so:

for( TxnRecord txn_rec : writeSet ) {
  // do something
}

Seems normal enough. So I replace the HashSet implementation with a LinkedHashSet, which should improve iteration performance. I was a little surprised when this improved the performance not one bit. Then I looked at the profiler results again and realized the following: It wasn't "next()" or "hasNext()" taking all the time, which would indicate slow iteration, it was the actual call to the "iterator()" method, which Java5's enhanced for loops call behind the scenes.

After investigating the implementation of LinkedHashSet I realized something surprising. For empty sets, a call to the "iterator()" method allocates at least two new objects, one for the new keySet of the underlying HashMap, and one for the iterator object itself. All this for an empty set. It turns out that my code was absolutely full of empty sets, since most objects aren't modified in a transaction and their write and undo sets are empty. If you have enough empty sets, this allocation adds up over time. By replacing the above code with:

if( !writeSet.isEmpty ) {
  for( TxnRecord txn_rec : writeSet ) {
    // do something
   }
}

The overall running time of the benchmark went from ~11secs to ~7secs!

This is bad, because iterating over empty collections should essentially have no run-time cost. Looking at the Java implementation, it would be easy to have some kind of singleton, "empty iterator" object that the HashSet's iterator would return if the set were empty. For example:

iterator() {
  if( size() == 0 ) return Collections.<Iterator<T>>emptyIterator();
  else return map.keySet().iterator(); // This is what it currently says.
}

This singleton iterator could then always return false when "hasNext" is called. The only reason why this might not be acceptable is if there is some rule about iterators needing to reflect subsequent "add" operations to their underlying collection, but honestly that would seem a little strange of a requirement. At the very least, the singleton iterator could hold a pointer to the original collection and continue to call size() after its creation...

Josh Block, are you listening?