Print permutation of {0, 1, 2, 3} by multithread program (C++)

Question

I want print a permutation of {0, 1, 2, 3} set by a multithread program written in C++11.

The source code is this:

#include <iostream>
#include <stdio.h>
#include <thread>
#include <vector>
#include <chrono>

using namespace std;


void func(int index);

int main()
{
    vector<thread> threads;

    for (int i = 0; i < 4; i++)
    {
        auto var = [&]()
        {
            return func(i);
        };

        threads.push_back(thread(var));
    }

    for (auto& thread : threads)
        thread.join();
}

void func(int index)
{
    cout << index;

    for (int i = 0; i < 10000; i++);
}

I expect in output a permutation of 0123, but I receive weird results, like these:

0223

0133

0124

I don't understand this weird behaviour, in particualar I cannot explain the presence of number 4.

Probably this is a beginner's mistake, I thanks anyway everybody will help me.

Answer 1

You are capturing i by reference:

    auto var = [&]()
    {
        return func(i);
    };

As such, when the thread that gets eventually started gets kicked off and going, it does not have an actual copy, the value of i that it has at this moment, but it has only a reference to i.

Which was probably incremented, once or twice now. If you consider that a reference is really just an ordinary pointer with a thin layer of makeup on top of it, you should be able to figure this out on your own. The thread gets a pointer to i, which, who knows how many times it could've been incremented, by the time the thread gets going.

And, technically, since i could've even gone out of scope here, if the for loop terminated before the thread started executing, this is undefined behavior.

Answer 2

You're invoking undefined behaviors in three ways:

Firstly, you're capturing the value of a stack variable by reference rather than by value, so when the thread starts it will call the lambda and use the then-current value of i rather than the value at the time of capture.

[edit: No-longer true as of C++11] Second is the thread-safety of cout.

The third is an assumption of the order in which the threads execute which is not guaranteed. [edit:] This includes not only the order in which they start but in which they access cout to write their output.

But do you need to solve the order of execution?

If you do, then instead of passing the values to the threads, put them into a queue and give the threads access to the queue.

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

class LockedQueue {
    std::queue<int> queue_;
    mutable std::mutex mutex_;
public:
    LockedQueue() = default;

    // these don't have to be deleted, but you'd have to decide whether or
    // not each operation needed to invoke a lock, and in the case of operator=
    // you have two mutexes to contend with.
    LockedQueue(const LockedQueue&) = delete;
    LockedQueue(LockedQueue&&) = delete;
    LockedQueue& operator=(const LockedQueue&) = delete;
    LockedQueue& operator=(LockedQueue&&) = delete;

    void push(int value) {
        std::lock_guard<std::mutex> lock(mutex_);
        queue_.push(value);
    }
    int pop() {
        std::lock_guard<std::mutex> lock(mutex_);
        int value = queue_.front();
        queue_.pop();
        return value;
    }
    bool empty() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return queue_.empty();
    }
};

void func(LockedQueue& work, LockedQueue& results);

int main()
{
    LockedQueue work, results;
    std::vector<std::thread> threads;

    for (int i = 0; i < 4; i++)
    {
        work.push(i);
        threads.emplace_back(func, std::ref(work), std::ref(results));
    }

    for (auto& thread : threads)
        thread.join();

    while (!results.empty()) {
        int i = results.pop();
        std::cout << i;
    }
}

void func(LockedQueue& work, LockedQueue& results)
{
    int index = work.pop();
    using namespace std::chrono_literals;
    std::this_thread::sleep_for(1s);
    results.push(index);
}

http://ideone.com/7G0JEO

We are still not guaranteed to get our results back in-order: it's quite possible that the thread that takes 0 off the queue is then pre-empted and doesn't execute again until 1, 2 and 3 have had their results pushed onto the result queue.