Thread-safe Iterator wrapper

Question

Aside: This code assumes a class Option that can be Some or None to represent the presence (Some) or absence (None) of the value it contains. Haskell calls it Maybe.

Here is my first pass at wrapping Iterator in a thread-safe way:

public synchronized Option<T> nextBlocking() {
    return iter.hasNext() ? Option.of(iter.next())
                          : Option.none();
}

I don't like that it's synchronized - it requires locking in order to work across multiple threads. On the other hand, if we remove the word synchronized, one thread could call iter.hasNext() which returns true (e.g. for the last item in the Iterator), then a second thread calls iter.next() before the first thread does, using up that last item and causing the first thread to get a NoSuchElementException when it finally calls iter.next().

The following isn't going to win any object-oriented style points, but I think it mostly works around this issue in a non-blocking way:

public Option<T> nextNonBlocking() {
    try {
         return Option.of(iter.next());
    } catch (NoSuchElementException nsee) {
        if(iter.hasNext()) {
            // Oops, exception was thrown for reason other than end-of-iterator.
            // Rethrow that exception.
            throw nsee;
        }
    }
    return Option.none();
}

That could still fail if a nsee is thrown for some reason before end-of-iterator, then another thread reaches the true end-of-iterator before the first thread calls iter.hasNext(). While possible, this situation probably represents a coding failure in the underlying Iterable. It's very tempting to trade this tiny weakness for a non-blocking iterator wrapper.

Answer 1

Looking at your first code example, it's somewhat sensible. The synchronized method creates a "happens before" memory barrier, and as a result, all threads see the same version of the data at that point in the code.

There is a vulnerability in that code, though. The synchronized method means that your lock is publicly accessible. Anyone can synchronize on your wrapper, and create a conflicting lock, perhaps creating a "denial of service" situation, where you can never get in to your method because some other thread has your instance locked. This is rare, but it does happen in some programs.

About your second block of code.... this is just plain broken from a multi-threaded perspective:

public Option<T> nextNonBlocking() {
    try {
         return Option.of(iter.next());
    } catch (NoSuchElementException nsee) {
        if(iter.hasNext()) {
            // Oops, exception was thrown for reason other than end-of-iterator.
            // Rethrow that exception.
            throw nsee;
        }
    }
    return Option.none();
}

That code will seldom produce what you expect in an actual multi-threaded situation. For a start, it reverses the logic of the hasNext() and next() calls. You should call hasNext first. Secondly, in an actual multi-core, especially in a multi-memory-controller computer (multi-socket), you will run in to stale memory accesses. It is possible for all threads to iterate through all members of the iterator, as they will all be seeing different "caches" of the iterator.

The second block is just "plain wrong".

As an aside, Java 8 now has an Optional class. You should use it.

Answer 2

The whole idea of wrapping an iterator to be thread-safe seems a bit dubious to me. If this is supposed to be a (well-performing) producer-consumer thing, then you should model it as such, with a queue and all that. Otherwise you should try to avoid multithreading the iterator entirely.

If you cannot do that, at least use nextBlocking(), which does not require a link to this discussion in the code to be maintainable.

Answer 3

I just did some timings. When the methods process different underlying iterators, the blocking method works 4 times faster. Under heavy machine load, it works about 4.5 times faster.

I wrote a second speed test that had the two methods are fighting for access to the same underlying iterator. In that case, they process roughly the same number of items.

One time that I ran the second test, nextBlocking() threw a NoSuchElementException. Presumably for the reason that I outlined above. So if you are wrapping a shared iterator, you have to check for that exception. If you get to wrap your own new, private iterator from an Iterable, you can use the nextBlocking() method as is.

So I think that nextBlocking() is the clear winner if you can wrap a private iterator. nextNonBlocking() may be better if you can't. I think I just answered my own question, but since I went to the trouble of writing it up, I might as well post it and see what other ideas people may have about wrapping iterators.