Multi-threading in C++, “do” and “don’t”. (part 1- try lock free design)

In general multi threading can be really hard, and it is kind of milestone for many people to get know how to deal with multiple threads and not go into some really hard to debug problems. This is my short guideline how to write multi threaded programs in modern c++ …

Think about problem you are trying to solve, and choose a proper design …

All of problems that requires multiple threads can be solved using three designs:

• lock free design
• single locking design
• continuous locking design

It would be an ideal if we could live in a non locking world, but even in functional programming world you need to preserve a state of a program, as you do not want to create copies of copies of copies each time that you need to deal with data…

Lock Free Design

There are a problems that can be solved in a non locking manner. In simple terms you just split data into smaller chunks, and you process data separately. “Look up” is such a simple problem.

    std::queue<std::future<std::string>> tasks;
    for (const auto &entry : fs::directory_iterator(path)) {
            tasks.push(std::async(&bruteforce_with_dict, hash, entry.path()));
    }

This is a little bit over simplified, but in general true … 1) you may want to schedule only as many tasks at once as many CPU cores you have.

auto processor_count = std::thread::hardware_concurrency();
    std::queue<std::future<std::string>> tasks;
    for (const auto &entry : fs::directory_iterator(path)) {
        if (tasks.size() > processor_count) {
            auto word = tasks.front().get();
            tasks.pop();
            if (not word.empty())
                return word;
        } else {
            tasks.push(std::async(&bruteforce_with_dict, hash, entry.path()));
        }
    }

2) when you find the results, you can stop running new tasks, and let to finish tasks that are ongoing.

while (not tasks.empty()) {
        auto word = tasks.front().get();
        tasks.pop();
        if (not word.empty())
            return word;  
    }
    return {};

You may want to cancel remaining tasks, but this would require some thread synchronization.

Single Lock Design

For a problems that you partition your input, and then you are processing partial results to heave overall result. You do not care about how many threads you can serve at once, you need to process all the partitions, so just leave that to yous system scheduler. You also do not need to cancel anything, because you need to get all the partial results. And this is your single point of synchronization, waiting until everything is done.

    std::queue<std::future<std::string>> tasks;
    for (const auto &entry : fs::directory_iterator(path)) {
        tasks.push(std::async(&bruteforce_with_dict, hash, entry.path()));
    }

    std::vector<std::string> results;
    while (not tasks.empty()) {
        tasks.front.wait();
        results.push_back(tasks.front.get());
        tasks.pop();
    }

So this is my first guideline: “Try to go lock free, or single lock design”

A little bit of discussion:

Lets assume you want to count passwords that did not fit the hash. Nothing easier, just declare a counter. unsigned int word_counter = 0; or even better std::atomic<unsigned int> word_counter = 0; and pass reference into task… But then you will have thread lock every word iteration.

What I would suggest, is to count words per task, return a std::tuple within a std::feature;.

Footnote:

For “Continuous Locking Design” you need to wait until next Monday.

For compilable code of “password bruteforcer” XD, go to my github.

With best regards.
Michal.