parallel computation for an Iterator of elements in Java
- by Brian Harris
I've had the same need a few times now and wanted to get other thoughts on the right way to structure a solution. The need is to perform some operation on many elements on many threads without needing to have all elements in memory at once, just the ones under computation. As in, Iterables.partition is insufficient because it brings all elements into memory up front.
Expressing it in code, I want to write a BulkCalc2 that does the same thing as BulkCalc1, just in parallel. Below is sample code that illustrates my best attempt. I'm not satisfied because it's big and ugly, but it does seem to accomplish my goals of keeping threads highly utilized until the work is done, propagating any exceptions during computation, and not having more than numThreads instances of BigThing necessarily in memory at once.
I'll accept the answer which meets the stated goals in the most concise way, whether it's a way to improve my BulkCalc2 or a completely different solution.
interface BigThing {
int getId();
String getString();
}
class Calc {
// somewhat expensive computation
double calc(BigThing bigThing) {
Random r = new Random(bigThing.getString().hashCode());
double d = 0;
for (int i = 0; i < 100000; i++) {
d += r.nextDouble();
}
return d;
}
}
class BulkCalc1 {
final Calc calc;
public BulkCalc1(Calc calc) {
this.calc = calc;
}
public TreeMap<Integer, Double> calc(Iterator<BigThing> in) {
TreeMap<Integer, Double> results = Maps.newTreeMap();
while (in.hasNext()) {
BigThing o = in.next();
results.put(o.getId(), calc.calc(o));
}
return results;
}
}
class SafeIterator<T> {
final Iterator<T> in;
SafeIterator(Iterator<T> in) {
this.in = in;
}
synchronized T nextOrNull() {
if (in.hasNext()) {
return in.next();
}
return null;
}
}
class BulkCalc2 {
final Calc calc;
final int numThreads;
public BulkCalc2(Calc calc, int numThreads) {
this.calc = calc;
this.numThreads = numThreads;
}
public TreeMap<Integer, Double> calc(Iterator<BigThing> in) {
ExecutorService e = Executors.newFixedThreadPool(numThreads);
List<Future<?>> futures = Lists.newLinkedList();
final Map<Integer, Double> results = new MapMaker().concurrencyLevel(numThreads).makeMap();
final SafeIterator<BigThing> it = new SafeIterator<BigThing>(in);
for (int i = 0; i < numThreads; i++) {
futures.add(e.submit(new Runnable() {
@Override
public void run() {
while (true) {
BigThing o = it.nextOrNull();
if (o == null) {
return;
}
results.put(o.getId(), calc.calc(o));
}
}
}));
}
e.shutdown();
for (Future<?> future : futures) {
try {
future.get();
} catch (InterruptedException ex) {
// swallowing is OK
} catch (ExecutionException ex) {
throw Throwables.propagate(ex.getCause());
}
}
return new TreeMap<Integer, Double>(results);
}
}
