Parallel Iterator — Quick Start

Background on the Parallel Iterator’s motivation, with examples illustrating its features.

1. Motivation

1.1 Why parallel computing?

Parallel computing arrived on mainstream desktop systems as multi-core processors, because of the difficulty of maintaining improvements in uni-processor clock speed. Users see no performance improvement unless their applications are parallelised, and parallel programming is notoriously difficult — especially for correctness and high performance.

1.2 Object-oriented programming and (sequential) iterators

The Parallel Iterator focuses on object-oriented (OO) programming, since the most popular languages are OO, especially for general-purpose desktop applications. Iterative computations usually carry the lion’s share of computational load, often implemented with iterators:

Collection<File> elements = ...
Iterator<File> it = elements.iterator();
while (it.hasNext()) {
    File file = it.next();
    processFile(file);
}

This code uses only one thread — one core works while the others stay idle. To parallelise, developers must create threads and distribute elements among them, raising questions of scheduling policy, implementation, correctness, and performance. The simplest schemes tend to be least efficient; the most efficient tend to be complex and error-prone.

1.3 The Parallel Iterator

The Parallel Iterator is a thread-safe iterator shared among threads, with the underlying scheduling policy handled internally:

Collection<File> elements = ...
ParIterator<File> it = ParIteratorFactory.createParIterator(elements, threadCount);

// each thread does this
while (it.hasNext()) {
    File file = it.next();
    processFile(file);
} // implicit synchronization barrier

Unlike the standard sequential iterator, the Parallel Iterator is thread-safe, so all threads can share it. Its interface even extends the sequential Iterator interface.

The implicit barrier. Since threads share the iterator, none should proceed past the loop until all have finished, because code after the loop may rely on the completed results. A call to hasNext() blocks a thread until all others finish, after which false is returned to all threads so they break out together.

Atomicity of hasNext()/next(). The Parallel Iterator is fully thread-safe: if a thread receives true from hasNext(), an element is guaranteed reserved for it. Threads must continue iterating until they receive false; otherwise the iterator waits indefinitely. Early termination is still possible via the break mechanisms (section 2.4).

2. Parallel Iterator examples

2.1 Hello, World!

MainApp.java creates a collection, obtains a Parallel Iterator for it, starts a pool of worker threads, and joins them:

int threadCount = 2;
Collection<String> elements = getElements();
ParIterator<String> pi = ParIteratorFactory.createParIterator(elements, threadCount);

Thread[] threadPool = new WorkerThread[threadCount];
for (int i = 0; i < threadCount; i++) {
    threadPool[i] = new WorkerThread(i, pi);
    threadPool[i].start();
}
for (int i = 0; i < threadCount; i++) {
    threadPool[i].join();
}

Each WorkerThread loops on the shared iterator:

public void run() {
    while (pi.hasNext()) {
        String element = pi.next();
        System.out.println("Thread " + id + " got element: " + element);
    }
}

This example uses the default scheduling policy (dynamic, chunk size of one): elements are distributed one at a time as threads request them.

2.2 Scheduling policies

A scheduling policy determines how the iteration space is divided among threads into chunks. The chunk size controls how many iterations are reserved for a thread at a time. Supported policies:

• Static — all iterations assigned before the loop executes, either block (each thread gets one large chunk) or cyclic (chunks assigned round-robin).
• Dynamic — each thread requests a chunk at runtime.
• Guided — like dynamic, but chunk size decreases as iterations are distributed.

Choosing a policy matters: very fine-grained iterations suffer under dynamic scheduling with a chunk size of 1 (high synchronisation overhead — increase the chunk size); equal-sized iterations favour static scheduling (minimal distribution overhead); the guided schedule is a compromise that begins like static block and converges toward dynamic.

Changing the policy only requires changing the factory parameters:

ParIteratorFactory.createParIterator(elements, threadCount, ParIterator.Schedule.DYNAMIC, 3);
ParIteratorFactory.createParIterator(elements, threadCount, ParIterator.Schedule.STATIC);
ParIteratorFactory.createParIterator(elements, threadCount, ParIterator.Schedule.STATIC, 2);
ParIteratorFactory.createParIterator(elements, threadCount, ParIterator.Schedule.GUIDED, 1);

2.3 Reductions

For programs that share variables, mutual exclusion is needed for correctness, but fine-grained locking hurts performance. A reduction is the standard technique; PARCutils offers RedLib with ready-to-use reductions:

Collection<Integer> elements = ...
ParIterator<Integer> it = ParIteratorFactory.createParIterator(elements);
Reducible<Integer> localMin = new Reducible<Integer>(Integer.MAX);

while (it.hasNext()) {
    int v = it.next();
    if (v < localMin.get()) localMin.set(v);
}

int finalMin = localMin.reduce(new IntegerMinimum());

Reducible behaves like Java’s ThreadLocal, except reduce() combines all thread-local values into a final result. Custom reductions are defined by implementing the Reduction interface; they must be associative and commutative.

2.4 Early loop termination — parallel break semantics

A plain break is unsafe in parallel: its meaning is ambiguous, it can break correctness if a thread leaves while others run, and it can leave other threads waiting at the barrier. The Parallel Iterator instead provides:

• globalBreak() — all threads stop; each receives false from the next hasNext() and exits the loop together. Useful for parallel search or a user cancel.
• localBreak() — only the calling thread stops, releasing its reserved elements for other threads to process. It guarantees at least one thread remains to finish the elements (returning a boolean for whether the break succeeded).

2.5 Exception handling

Threads must catch exceptions within the scope of the Parallel Iterator; otherwise the other threads wait indefinitely. On catching an exception a thread may do nothing, localBreak(), or globalBreak(). The register(Exception) helper records the exception, the thread, and the iteration in a ParIteratorException for later inspection:

while (pi.hasNext()) {
    try {
        // ... work that may throw
    } catch (FileNotFoundException fe) {
        pi.register(fe);             // record only, keep going
    } catch (TooManyThreadsException te) {
        pi.register(te); pi.localBreak();   // this thread stops
    } catch (DiskFullException de) {
        pi.register(de); pi.globalBreak();  // all threads stop
    }
}

ParIteratorException[] piExceptions = pi.getExceptions();