Stopping all threads when one of them is finished

Question

The goal is creating search method that returns the index of the needle found first over all search threads. And when one of them is finished, I need to stop all threads.

The logic is: there are 4 threads. First thread checks first %25 of the haystack, second thread checks %25-%50 of the haystack and so on.

I should stop as soon as one of them printed the text but I always get 4 output because all 4 of them finds needle in the haystack. However, I want only one output.

Example Output: (indexes below)

I found, it is: 622
I found, it is: 4072
I found, it is: 7519
I found, it is: 7264

Here is the SearcherThreat class the extends Thread

public class SearcherThread extends Thread {

// PROPERTIES
private int needle;
private int[] haystack;
private int start, end;

// CONSTRUCTOR
public SearcherThread(int needle, int[] haystack, int start, int end) {
    this.needle = needle;
    this.haystack = haystack;
    this.start = start;
    this.end = end;
}

@Override
public void run() {
    for (int i = start; i < end && !isInterrupted(); ++i) {
        if (haystack[i] == needle) {
            System.out.println("I found, it is: " + i);
            for (SearcherThread searcher : InterruptTest.searchers) {
                searcher.interrupt();
            }

        }
    }
}
}

And this is the class that contains main and threads

import java.util.ArrayList;
public class InterruptTest {

public static ArrayList<SearcherThread> searchers = new ArrayList<SearcherThread>();

public static void main(String[] args) throws InterruptedException {

    int itemCount = 10000;
    int[] haystack = new int[itemCount];
    int domainSize = 1000;
    for (int i = 0; i < itemCount; ++i)
        haystack[i] = (int) (Math.random() * domainSize);
    int needle = 10;

    int numThreads = 4;
    int numItemsPerThread = haystack.length / numThreads;
    int extraItems = haystack.length - numItemsPerThread * numThreads;
    for (int i = 0, start = 0; i < numThreads; ++i) {
        int numItems = (i < extraItems) ? (numItemsPerThread + 1) : numItemsPerThread;
        searchers.add(new SearcherThread(needle, haystack, start, start + numItems));
        start += numItems;
    }

    for (SearcherThread searcher : searchers)
        searcher.start();
}
}

Because your worker threads are not checking to see if they are interrupted. — Stephen C, Dec 30 '16 at 23:59
I may have found the answer here http://stackoverflow.com/questions/41389714/threading-search-for-a-value-and-stop-all-threads — funky-nd, Dec 30 '16 at 23:59
I check at this line: for (int i = start; i < end && !isInterrupted(); ++i) { — funky-nd, Dec 31 '16 at 00:00

Stephen C · Answer 1 · 2016-12-31T00:37:11.330

I got this output:

[stephen@blackbox tmp]$ java InterruptTest 
I found, it is: 855
I found, it is: 3051
[stephen@blackbox tmp]$ java InterruptTest 
I found, it is: 2875
I found, it is: 5008
I found, it is: 1081
I found, it is: 8527
[stephen@blackbox tmp]$ java InterruptTest 
I found, it is: 2653
I found, it is: 5377
I found, it is: 1092
[stephen@blackbox tmp]$ java InterruptTest 
I found, it is: 255
I found, it is: 9095
I found, it is: 6983
I found, it is: 3777

As you can see, the number of threads that is completing varies from one run to the next.

What we have here is a race. What is probably happening is that one thread completes and interrupts the other threads before they have been started. So they don't see the interrupt. The javadoc says:

"Interrupting a thread that is not alive need not have any effect."

Another possibility is that the interrupts are not propagating fast enough. Note that the javadoc does not say that an interrupt() is instantly visible to the interrupted thread.

I can't think of a solution to this that doesn't negate the benefits of multi-threading. On the other hand, in a real-world use-case:

You should be using a thread pool ... because thread creation is relatively expensive.
The threads should be doing more work.

If you measured the actual speedup you were getting in your current test, it is possibly negative.

In summary, in a more realistic test you should see the interrupts working most of the time. And that should be good enough. (It should not matter that occasionally threads are not interrupted fast enough to stop them finding secondary results.)

+1 Also, if you print a message after the interrupt has been sent and also print a message when the thread is interrupted, you will see that many times the threads _are_ interrupted but other times because of race conditions, either they find the needle too fast or the interrupt isn't immediate. — Gray, Dec 31 '16 at 18:30
Probably. However, you need to be a bit careful with adding trace prints. They can change the behavior of multi-threaded code — Stephen C, Jan 01 '17 at 01:08

score 1 · Answer 2 · answered Nov 07 '18 at 18:43

This is necro but this could help someone else out. You can use Java's built in Executors. With Java 8 it has

newCachedThreadPool()
newFixedThreadPool(int nThreads)
newSingleThreadExecutor()
etc

Here's an example of how you could write around your classes. I'm using the newFixedThreadPool(int nThreads) to match what you were doing in your code

import java.util.concurrent.Callable;

public class SearcherThread implements Callable<Object> {

// PROPERTIES
    private int needle;
    private int[] haystack;
    private int start, end;

// CONSTRUCTOR
    public SearcherThread(int needle, int[] haystack, int start, int end) {
        this.needle = needle;
        this.haystack = haystack;
        this.start = start;
        this.end = end;
    }


    @Override
    public Object call() throws Exception {
        for (int i = start; i < end ; ++i) {
            if (haystack[i] == needle) {
                return i;


            }
        }
        Thread.sleep(5000);
        return null;
    }
}

And the Test class

import java.util.ArrayList;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class InterruptTest {

    public static ArrayList<SearcherThread> searchers = new ArrayList<SearcherThread>();

    public static void main(String[] args) throws InterruptedException, ExecutionException {

        int itemCount = 10000;
        int[] haystack = new int[itemCount];
        int domainSize = 1000;
        for (int i = 0; i < itemCount; ++i)
            haystack[i] = (int) (Math.random() * domainSize);
        int needle = 10;

        int numThreads = 4;
        int numItemsPerThread = haystack.length / numThreads;
        int extraItems = haystack.length - numItemsPerThread * numThreads;
        for (int i = 0, start = 0; i < numThreads; ++i) {
            int numItems = (i < extraItems) ? (numItemsPerThread + 1) : numItemsPerThread;
            searchers.add(new SearcherThread(needle, haystack, start, start + numItems));
            start += numItems;
        }
        //Preferred to use Executors.newWorkStealingPool() instead
        ExecutorService executor = Executors.newFixedThreadPool(numThreads);
        executor.shutdown();//shutdown when done
        Object result = executor.invokeAny(searchers);//<------- right here lookie
        System.out.println("I found, it is: "+result);
    }
}

ExecutorService.invokeAny(List<Callable>) will run all the callable threads and get value of the first finished thread.

Stopping all threads when one of them is finished

2 Answers2