Start multiple threads and wait only for one to finish to obtain results

Question

Assuming I have the function double someRandomFunction(int n) that takes an integer and returns double but it's random in the sense that it tries random stuff to come up with the solution so even though you run the function with the same arguments, sometimes it can take 10 seconds to finish and other 40 seconds to finish.

The double someRandomFunction(int n) functions itself is a wrapper to a black box function. So the someRandomFunction takes a while to complete but I don't have control in the main loop of the black box, hence I can't really check for a flag variable within the thread as the heavy computation happens in a black box function.

I would like to start 10 threads calling that function and I am interested in the result of the first thread which finishes first. I don't care which one it's I only need 1 result from these threads.

I found the following code:

  std::vector<boost::future<double>> futures;
  for (...) {
    auto fut = boost::async([i]() { return someRandomFunction(2) });
    futures.push_back(std::move(fut));
  }

  for (...) {
    auto res = boost::wait_for_any(futures.begin(), futures.end());
    std::this_thread::yield();
    std::cout << res->get() << std::endl;
  }

Which is the closest to what I am looking for, but still I can't see how I can make my program to terminate the other threads as far as one thread returns a solution.

I would like to wait for one to finish and then carry on with the result of that one thread to continue my program execution (i.e., I don't want to terminate my program after I obtain that single result, but I would like to use it for the remaining program execution.).

Again, I want to start up 10 threads calling the someRandomFunction and then wait for one thread to finish first, get the result of that thread and stop all the other threads even though they didn't finish their work.

Answer 1

If the data structure supplied to the black-box has some obvious start and end values, one way to make it finish early could be to change the end value while it's computing. It could of course cause all sorts of trouble if you've misunderstood how the black-box must work with the data, but if you are reasonably sure, it can work.

main spawns 100 outer threads that each spawn one inner thread that calls the blackbox. The inner thread receives the blackbox result and notifies all waiting threads that it's done. The outer thread waits for any inner thread to get done and then modifies the data for its own blackbox to trick it to finish.

No polling (except for the spurious wakeup loops) and no detached threads.

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <vector>
#include <chrono>

// a work package for one black-box
struct data_for_back_box {
    int start_here;
    int end_here;
};

double blackbox(data_for_back_box* data) {
    // time consuming work here:
    for(auto v=data->start_here; v<data->end_here; ++v) {
        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
    // just a debug
    if(data->end_here==0) std::cout << "I was tricked into exiting early\n";
    return data->end_here;
}

// synchronizing stuff and result
std::condition_variable cv;
std::mutex mtx;
bool done=false;
double result;

// a wrapper around the real blackbox
void inner(data_for_back_box* data) {
    double r = blackbox(data);
    if(done) return; // someone has already finished, skip this result

    // notify everyone that we're done
    std::unique_lock<std::mutex> lock(mtx);
    result = r;
    done=true;
    cv.notify_all();
}

// context setup and wait for any inner wrapper
// to signal "done"
void outer(int n) {
    data_for_back_box data{0, 100+n*n};
    std::thread work(inner, &data);
    {
        std::unique_lock<std::mutex> lock(mtx);
        while( !done ) cv.wait(lock);
    }
    // corrupt data for blackbox:
    data.end_here = 0;
    // wait for this threads blackbox to finish
    work.join();
}

int main() {
    std::vector<std::thread> ths;

    // spawn 100 worker threads
    for(int i=0; i<100; ++i) {
        ths.emplace_back(outer, i);
    }

    double saved_result;
    {
        std::unique_lock<std::mutex> lock(mtx);
        while( !done ) cv.wait(lock);
        saved_result = result;
    } // release lock

    // join all threads
    std::cout << "got result, joining:\n";
    for(auto& th : ths) {
        th.join();
    }

    std::cout << "result: " << saved_result << "\n";
}