Multi-threaded array comparison - Pushing events to a thread?

Question

I have a simple multi threading problem (in Java). I have 2 sets of 4 very large arrays and I have 4 threads, 1 for each array in the set. I want the threads, in parallel, to check if both sets, if their arrays have identical values. If one of the values in one of the arrays does not match the corresponding index value in the other array, then the two sets are not identical and all threads should stop what they are doing and move on to next 2 sets of 4 very large arrays. This process continues until all the pairs of array sets have been compared and deemed equal or not equal. I want all the threads to stop when one of the threads finds a mis-match. What is the correct way to implement this?

Answer 1

Here's one simple solution, but I don't know if it's the most efficient: Simply declare an object with a public boolean field.

public class TerminationEvent {
    public boolean terminated = false;
}

Before starting the threads, create a new TerminationEvent object. Use this object as a parameter when you construct the thread objects, e.g.

public class MyThread implements Runnable {
    private TerminationEvent terminationEvent;
    public MyThread(TerminationEvent event) {
        terminationEvent = event;
    }
}

The same object will be passed to every MyThread, so they will all see the same boolean.

Now, the run() method in each MyThread will have something like

if (terminationEvent.terminated) {
    break;
}

in the loop, and will set terminationEvent.terminated = true; when the other threads need to stop.

(Normally I wouldn't use public fields like terminated, but you said you wanted efficiency. I think this is a bit more efficient than a getter method, but I haven't tried benchmarking anything. Also, in a simple case like this, I don't think you need to worry about synchronization when the threads read or write the terminated field.)

Answer 2

Stopping other threads are usually done through the use of interrupts. Java threads do no longer use Thread.stop() because this was seen as unsafe in that it unlocks all monitors held by the thread, possibly leading to other threads being able to view objects in an inconsistent state (Ref: http://docs.oracle.com/javase/1.5.0/docs/guide/misc/threadPrimitiveDeprecation.html). The threads are not "stopped" as such, but are commonly used to set a flag false:

The thread should check the interrupted flag (infrequently) before performing computations:

if (Thread.interrupted()) {
    throw new InterruptedException();
}

Answer 3

Use a volatile variable to set the abort condition. In your check loop that is run by all threads, let those threads check a number N of values uninterrupted so they don't have to fetch the volatile too often, which may be costly compared to the value match test. Benchmark your solution to find the optimum for N on your target hardware.

Another way would be to use a ForkJoin approach where your result is true if a mismatch was found. Divide your array slices down to a minimum size similar to N.