How to perform short-circuit evaluation in Java on two parallel threads that return boolean values?

Question

I'm looking for guidance for a problem logically equivalent to the following:

public boolean parallelOR() {
    ExecutorService executor = Executors.newFixedThreadPool(2);
    Future<Boolean> taskA = executor.submit( new SlowTaskA() );
    Future<Boolean> taskB = executor.submit( new SlowTaskB() );

    return taskA.get() || taskB.get(); // This is not what I want
    // Exception handling omitted for clarity
 }

The above construction gives the correct result but always waits for taskA to complete even if the result is already known since taskB has completed.

Is there a better construction which will allow a value to be returned if either of the threads returns true without waiting for the second thread to complete?

(The platform involved is Android, if that affects the result).

Answer 1

Here's an implementation of ParallelOr using ExecutorCompletionService. It waits on tasks until one returns true. If none do, it eventually returns false.

public class ParallelOr {

    static class LongTask implements Callable<Boolean> {

        private int milliseconds;
        private boolean val;

        public LongTask(int milliseconds, boolean val) {
            this.milliseconds = milliseconds;
            this.val = val;
        }

        @Override
        public Boolean call() throws Exception {
            try {
                Thread.sleep(milliseconds);
            } catch(Exception ex) {}
            return val;
        }
    }

    static boolean ParallelOr(List<Callable<Boolean>> tasks) {
        ExecutorService pool = Executors.newFixedThreadPool(tasks.size());
        ExecutorCompletionService<Boolean> completionService
                = new ExecutorCompletionService<Boolean>(pool);

        for(Callable<Boolean> task : tasks) {
            completionService.submit(task);
        }

        for(int i = 0; i < tasks.size(); i++) {
            try {
                Future<Boolean> result = completionService.take();
                if(result.get()) {
                    return true;
                }
            } catch (InterruptedException e) {
            } catch (ExecutionException e) {}
        }

        return false;
    }


    public static void main(String[] args) {
        ArrayList<Callable<Boolean>> tasks = new ArrayList<Callable<Boolean>>();

        tasks.add(new LongTask(1000, true));
        tasks.add(new LongTask(500, false));
        tasks.add(new LongTask(6000, false));

        boolean result = ParallelOr(tasks);

        System.out.println(result);
    }
}

Thanks to @Lav for pointing out the ExecutorCompleteionService class.

Answer 2

try Using ExecutorCompletionService ... something like

    ExecutorService pool = Executors.newFixedThreadPool(2);
    ExecutorCompletionService<Result> completionService = new ExecutorCompletionService<Result>(pool);
completionService.submit(new SlowTaskA());
completionService.submit(new SlowTaskB());
    Future<Result> future;
            try {
                future = completionService.take();
                Result currentResult=null;
                try {
                    currentResult = future.get();
                } catch (ExecutionException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
                // got the 1st result in obj currentResult, return true or obj
                return true;
            } catch (InterruptedException e1) {
                e1.printStackTrace();
            }

Answer 3

I think monitor logic might work nicely in this case, though it is dependent upon you being able to add alter the callables to receive a reference. It could look like this in the parallelOR() method:

ExecutorService executor = Executors.newFixedThreadPool(2);
    final Object monitor = new Object();
    Future<Boolean> taskA = executor.submit( new SlowTaskA(monitor) );
    Future<Boolean> taskB = executor.submit( new SlowTaskB(monitor) );
    Boolean ret = null,;
    try {
        loop:while(true){
            synchronized(monitor){
                monitor.wait();
            }
            if(taskA.isDone()){
                ret = taskA.get();
                if(ret.booleanValue()){
                    taskB.cancel(true); // If you can.
                    break loop;
                }
            }
            if(taskB.isDone()){
                ret = taskB.get();
                if(ret.booleanValue()){
                    taskA.cancel(true);
                    break loop;
                }
            }
            // Ifs in case of spurious wake-up
        }           
    } catch (InterruptedException | ExecutionException e) {
        e.printStackTrace();
    }

While at the end of the call() method in your callables you would have:

synchronized(monitor){
            monitor.notify();
        }