java - threading: search for a value and stop all threads

Question

I need to implement a search method that will search through haystack and return first founded index of needle.

static int search(T needle, T[] haystack, int numThreads)

My question: How can I stop all threads if one of the thread finds result?
For example: I am searching for 5, I have 10 numbers in array such that [2, 4, 5, 6, 1, 4, 5, 8, 9, 3] and there are 2 threads. So first thread will look for first part [0 - 5), second thread will search other part [5 - 10). If thread 2 starts firstly and finds result quicker than other thread, it should return 6 and terminate thread 1 and 2.

Answer 1

The classic way of doing this is to simply have shared data between the threads so that they can communicate with each other. In other words, initialise some flag value to "not found" before starting the threads.

Then, when the threads are running, they process elements in the array until either their elements are exhausted, or the flag value has been set to "found".

In pseudo-code, that would be something like:

main():
    global array = createArray(size = 10000, values = random)
    global foundIndex = -1
    global mutex = createMutex()

    startThread(id = 1, func = threadFn, param = (0, 4999))
    startThread(id = 2, func = threadFn, param = (5000, 9999))

    waitFor(id = 1)
    waitFor(id = 2)

    print("Result is ", foundIndex)

threadFn(first, last):
    for index in first through last inclusive:
        if userSpecifiedCheckFound(array[index]):
            mutex.lock()
            if foundIndex == -1:
                foundIndex = index
            mutex.unlock()
            return

        mutex.lock()
        localIndex = foundIndex
        mutex.unlock()
        if localIndex != -1:
            return

You can see from that that each instance of the function will set the shared data and return if it finds a value that matches whatever criteria you're looking for. It will also return (without setting the shared data) if another thread has already set the shared data, meaning it can exit early if another thread has already found something.

Just keep in mind that the shared data, foundIndex in this case, needs to be protected from simultaneous changes lest it become corrupted. In the pseudo-code, I've shown how to do that with low-level mutual exclusion semaphores.

---

In Java, that means using synchronized to achieve the same effect. By way of example, the following code sets up some suitable test data so that the sixteenth cell of the twenty-cell array will satisfy the search criteria.

It then runs two threads, one on each half of the data, until it finds that cell.

public class TestProg extends Thread {
  // Shared data.

  static int [] sm_array = new int[20];
  static int sm_foundIndex = -1;

  // Each thread responsible for its own stuff.

  private int m_id, m_curr, m_last;
  public TestProg(int id, int first, int last) {
    m_id = id;
    m_curr = first;
    m_last = last;
  }

  // Runnable: continue until someone finds it.

  public void run() {
    // Try all cells allotted to thread.

    while (m_curr <= m_last) {
      System.out.println(m_id + ": processing " + m_curr);

      // If I find it first, save and exit.

      if (sm_array[m_curr] != 0) {
        synchronized(this) {
          if (sm_foundIndex == -1) {
            sm_foundIndex = m_curr;
            System.out.println(m_id + ": early exit, I found it");
            return;
          }
        }
      }

      // If someone else finds it, just exit.

      synchronized(this) {
        if (sm_foundIndex != -1) {
          System.out.println(m_id + ": early exit, sibling found it");
          return;
        }
      }

      // Kludge to ensure threads run side-by-side.

      try { Thread.sleep(100); } catch(Exception e) {}

      m_curr++;
    }
  }

  public static void main(String[] args) {
    // Create test data.

    for (int i = 0; i < 20; i++) {
      sm_array[i] = 0;
    }
    sm_array[15] = 1;

    // Create and start threads.

    HelloWorld thread1 = new HelloWorld(1, 0, 9);
    HelloWorld thread2 = new HelloWorld(2, 10, 19);
    thread1.start();
    thread2.start();

    // Wait for both to finish, then print result.

    try {
      thread1.join();
      thread2.join();
      System.out.println("=> Result was " + sm_foundIndex);
    } catch(Exception e) {
      System.out.println("Interrupted: " + e);
    }
  }
}

The output of that code (although threading makes it a little non-deterministic) is:

1: processing 0
2: processing 10
1: processing 1
2: processing 11
1: processing 2
2: processing 12
1: processing 3
2: processing 13
1: processing 4
2: processing 14
1: processing 5
2: processing 15
2: early exit, I found it
1: processing 6
1: early exit, sibling found it
=> Result was 15