C++11 get a task finished by one of two algorithms

Question

I have two algorithms to solve a task X ().

How can I get a thread started for algorithm 1 and a thread started for algorithm 2 and wait for the first algorithm to finish after which I kill the other one and proceed?

I have seen that join from std::thread will make me wait for it to finish but I can't do join for both threads, otherwise I will wait for both to complete. I want to issue both of them and wait until one of them completes. What's the best way to achieve this?

Answer 1

You can't kill threads in C++11 so you need to orchestrate their demise.

This could be done by having them loop on an std::atomic<bool> variable and getting the winner to std::call_once() in order to set the return value and flag the other threads to end.

Perhaps a bit like this:

std::once_flag once; // for std::call_once()

void algorithm1(std::atomic<bool>& done, int& result)
{
    // Do some randomly timed work
    for(int i = 0; !done && i < 3; ++i) // end if done is true
        std::this_thread::sleep_for(std::chrono::seconds(std::rand() % 3));

    // Only one thread gets to leave a result
    std::call_once(once, [&]
    {
        done = true; // stop other threads
        result = 1;
    });
}

void algorithm2(std::atomic<bool>& done, int& result)
{
    // Do some randomly timed work
    for(int i = 0; !done && i < 3; ++i) // end if done is true
        std::this_thread::sleep_for(std::chrono::seconds(std::rand() % 3));

    // Only one thread gets to leave a result
    std::call_once(once, [&]
    {
        done = true; // stop other threads
        result = 2;
    });
}

int main()
{
    std::srand(std::time(0));

    std::atomic<bool> done(false);

    int result = 0;

    std::thread t1(algorithm1, std::ref(done), std::ref(result));
    std::thread t2(algorithm2, std::ref(done), std::ref(result));

    t1.join(); // this will end if t2 finishes
    t2.join();

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

Answer 2

Firstly, don't kill the losing algorithm. Just let it run to completion and ignore the result.

Now, the closest thing to what you asked for is to have a mutex+condvar+result variable (or more likely two results, one for each algorithm).

Code would look something like

X result1, result2;
bool complete1 = false;
bool complete2 = false;

std::mutex result_mutex;
std::condition_variable result_cv;

// simple wrapper to signal when algoN has finished

std::thread t1([&]() { result1 = algo1();
                       std::unique_lock lock(result_mutex);
                       complete1 = true;
                       result_cv.notify_one();
                     });
std::thread t2([&]() { result2 = algo2();
                       std::unique_lock lock(result_mutex);
                       complete2 = true;
                       result_cv.notify_one();
                     });

t1.detach();
t2.detach();

// wait until one of the algos has completed
int winner;
{
  std::unique_lock lock(result_mutex);
  result_cv.wait(lock, [&]() { return complete1 || complete2; });
  if (complete1) winner=1;
  else           winner=2;
}

The other mechanisms, including the future/promise one, require the main thread to busy-wait. The only non-busy-waiting alternative is to move the post-success processing to a call_once: in this case the master thread should just join both children, and the second child will simply return when it finishes processing and realises it lost.