Why calling future.get() retrieved from async leads to unexpected output order

Question

Consider the following code:

#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <future>

std::mutex mutex;

int generate()
{
    static int id = 0;
    std::lock_guard<std::mutex> lock(mutex);
    id++;
    std::cout << id << '\n';
    return id;
}

int main()
{
    std::vector<std::future<int>> vec;
    std::vector<int> result;
    for(int i = 0; i < 10; ++i)
    {
        vec.push_back(std::async(std::launch::async,generate));
    }
    for(int i = 0; i < 10; ++i)
    {
        result.push_back(vec[i].get());
    }
    std::cout << "\n result:";
    for(const auto res : result)
    {
        std::cout << res << " ";
    }
}

Which produces following output:

1
2
3
4
5
6
7
8
9
10

 result:1 2 3 6 4 5 7 8 9 10

As you can see, the output inside generate() function has correct (from 1 to 10) order. But when iterating over the result vector I'm getting different order each run. Why is this happening and how can I synchronize such code?

Answer 1

What you're seeing in the final output is the order in which the threads produced their results.

Consider these three threads as a simplified version:

          +- -+   +- -+    +- -+
Thread    | 1 |   | 2 |    | 3 |
          +- -+   +- -+    +- -+
Result    |   |   |   |    |   |
          +- -+   +- -+    +- -+

Now, no matter which order these execute and acquire the mutex in, the output will be

1 2 3

because id is static, and the first "locker" increments it and prints "1", then the second increments it and prints "2", and so on.

Let's assume that Thread 3 gets the mutex first, then 1, then 2.

That leads to this situation:

          +- -+   +- -+    +- -+
Thread    | 1 |   | 2 |    | 3 |
          +- -+   +- -+    +- -+
Result    | 2 |   | 3 |    | 1 |
          +- -+   +- -+    +- -+

And when you print the results in "vector order", you will see

2 3 1

If you want threads to execute in some predetermined order, you need to synchronize them further.

Answer 2

If you resolve the future right away, then it will be in sequence. For example:

#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <future>

std::mutex mutex;

int generate()
{
    static int id = 0;
    std::lock_guard<std::mutex> lock(mutex);
    id++;
    std::cout << id << '\n';
    return id;
}

int main()
{
    std::vector<std::future<int>> vec;
    std::vector<int> result;
    for(int i = 0; i < 10; ++i)
    {
        int result = std::async(std::launch::async,generate).get();
        result.push_back(result);
    }
    std::cout << "\n result:";
    for(const auto res : result)
    {
        std::cout << res << " ";
    }
}