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).

Cryptanalysis

Can you modify the tasks? – Durrace

So you dont want to wait for threads A and B to complete before getting the valus??? and you want it when A is done youll get the value and vice versa? – Broch

The idea seems to be that if taskB finishes first, and is true, then you can short circuit and not wait for taskA to finish. – Durrace

Perhaps you could have the task that finishes first interrupt the other? – Cuthburt

I'm open to using different synchronization primitives - but I think I have to let the tasks complete because of the resources they use, even if after one task returns true the result of the second is no longer of interest. – Cryptanalysis

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.

Durrace

you should shutdown the executor service!! – Fieldfare

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();
            }

Roslynrosmarin

+1 - Cool! I haven't come across ExecutorCompletionService before. – Phonometer

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();
        }

Triumvir

Maybe this is inherent in the way it's set up, but how would you ensure isDone() would return true if you're signalling from inside the task? – Durrace

I'm a little unsure what you mean here. I would place this block at the very end of your call() method such that you explicitly know the callable has finished processing. – Triumvir

the get()of the tasks blocks until done. No need to wait explicitly, or what? – Fieldfare