Bubble sort in parallel

Question

I have done bubble sort algorithm on a vector that is filled with randomly generated values. Bubble sort is actually done with the odd-even transposition method:

#include <iostream>
#include <algorithm>
#include <vector>
#include <random> 
#include <thread>
#include <mutex>

void fill_with_random(std::vector<int> &vec)
{
    constexpr int lower_bound = 1;
    constexpr int upper_bound = 100;

    std::random_device rnd_device;
    std::mt19937 mersenne_engine(rnd_device());

    std::uniform_int_distribution<int> distribution(lower_bound, upper_bound);

    auto generator = std::bind(distribution, mersenne_engine);
    std::generate(vec.begin(), vec.end(), generator);
}

bool is_odd(int number)
{
    return number % 2 != 0;
}

int main(int argc, char *argv[])
{
    constexpr size_t vector_size = 10;

    std::mutex mutex;

    std::vector<int> vec(vector_size);
    fill_with_random(vec);

    std::cout << "Normal vector: ";
    for (auto item : vec)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;

    for (size_t i = 0; i < vector_size; i++)
    {
        std::vector<std::thread> threads;
        if (is_odd(i))
        {
            for (size_t j = 1; j < vector_size / 2 + vector_size % 2; j++)
            {
                size_t second = 2 * j;
                size_t first = second - 1;

                threads.emplace_back(
                    [&vec, first, second, &mutex]()
                    {
                        if (vec[first] > vec[second])
                        {
                            std::lock_guard<std::mutex> lock(mutex);
                            std::iter_swap(vec.begin() + first, vec.begin() + second);
                        }
                    }
                );
            }
        }
        else
        {
            for (size_t j = 0; j < vector_size / 2; j++)
            {
                size_t first = 2 * j;
                size_t second = first + 1;

                threads.emplace_back(
                    [&vec, first, second, &mutex]()
                    {
                        if (vec[first] > vec[second])
                        {
                            std::lock_guard<std::mutex> lock(mutex);
                            std::iter_swap(vec.begin() + first, vec.begin() + second);
                        }
                    }
                );
            }
        }

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

    std::cout << "Sorted vector: ";
    for (auto item : vec)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;

    return 0;
}

Next to a style review, please check functionality of the algorithm itself.

Have you tried to test it? Just use std::is_sorted() on your vector. You could write a loop that would check vectors up to certain size. — Incomputable
– Incomputable, Commented Jun 5, 2018 at 18:47

Toby Speight · Accepted Answer · 2024-02-02 15:36:32Z

General review

We're missing an include of <functional>, needed for std::bind(). This would be easier to spot if standard headers were included in alphabetical order.

It's strange that we have a named function for is_odd(), yet the sort function is just inlined into main(), making it harder to independently reason about.

is_odd() takes an int as argument, but we call it with a std::size_t. That's easily avoidable.

main() doesn't use argc or argv, so we should use the version that takes no arguments.

Algorithm

We create as many threads as we have vector elements, but on most platforms, threads are a scarce resource, and we're likely to throw std::system_error when no more can be created. Typically this will be when the collection contains a few hundred to a few thousand elements, which is not a large number.

All the threads lock on the same mutex, which could be very highly contended, even when the actual values being touched are completely separate. It's not clear that the locking is sufficient, given that the comparison is done without holding the lock.

Instead of manually joining threads, use std::jthread; then simply destructing the vector of threads will cause them all to be joined.

G. Sliepen · Accepted Answer · 2024-02-03 15:49:19Z

Make it more generic

Your code lives mostly in main(), and can only sort one std::vector<int>. What if you want to sort a std::array<int> or a std::vector<float>? What if you want to sort more than once?

First, make this into a proper function, that takes a reference to a std::vector<int> as the input:

void parallel_bubble_sort(std::vector<int>& vec) {
    …
}

Then consider that nothing in your algorithm really depends on the type of the vector, or even whether it is a std::vector to begin with. You can therefore very easily turn your function into a template:

template<typename T>
void parallel_bubble_sort(T& vec) {
    …
}

And now it works on all kinds of things! Well, things that have operator[], are supported by std::iter_swap() and that contain values that you can compare with >.

Ideally, you make the interface of your sorting function look exactly like that of std::ranges::sort(). The big advantage you get then is that everywhere you could use std::ranges::sort(), you can use your sorting algorithm instead, without having to change anything else in the code.

Inefficient use of threads

The only thing you are doing inside each thread is comparing just two values and maybe swapping them. But starting and stopping threads is not free, and the overhead of that is much more than the time it takes to do the comparison and swapping. So the runtime of your algorithm is dominated by the main thread just managing the other threads. Your code will be faster if you just use a single thread!

To make better use of threads, first ensure that you don't spawn more threads than the number of available CPU cores. You can use std::thread::hardware_concurrency() to check how many threads can actually run in parallel. Each thread should then process more than one pair at a time.

Second, keep the threads alive. The issue is then how to synchronize them. C++20 introduced std::barrier, and that is exactly the right solution for your problem. If you can't use C++20 yet, then you can implement your own using std::mutex and std::condition_variable, or use an external library such as Boost.

Your code should then look a bit like:

template<typename T>
void parallel_bubble_sort(T& vec) {
    std::size_t n_threads = std::thread::hardware_concurrency();
    std::vector<std::jthread> threads;
    std::barrier barrier(n_threads);

    for (std::size_t i = 0; i < n_threads; ++i) {
        threads.emplace_back([&](std::size_t thread_id) {
            // Calculate thread-specific variables
            …

            for (/* outer loop from 0 to vec.size() */) {
                 if (/* odd */) {
                     …
                 } else {
                     …
                 }

                 barrier.arrive_and_wait();
            }
        }, i);
    }
}

greybeard · Accepted Answer · 2024-02-02 21:13:57Z

The odd-even transposition sort deserves to be in an entity of its own; documented, at that.

As Toby Speight points out, All the threads lock on the same mutex
- without need: all "odd accesses" may occur in parallel, as well as all "even" ones. Writing to one&the same vector, it's just that even accesses may begin only when odd ones are done, and vice-versa.

Coming to think of it, odd-even transposition sort looks a worthy target for tinkering with synchronisation.
Using a thread pool should help against creating inconveniently many threads. I don't know what the favourite mechanism to use thread pools is in C++ - std::async?

Trying to simplify thread creation:

    for (size_t level = 0; level < vector_size; level++)
    {
        std::vector<std::jthread> threads;
        for (size_t lo = level%2, hi ; (hi = lo + 1) < vector_size ; lo += 2)
        {
            threads.emplace_back(
                    [&vec, lo, hi]()
                    {
                        if (vec[lo] > vec[hi])
                        {
                            std::iter_swap(vec.begin() + lo, vec.begin() + hi);
                        }
                    }
                );
        }
    }

(I think of odd-even transposition sort in terms of a sorting network from 2-sorters.
As long as hi always is lo+1, its claim to usefulness is low, as a thread parameter, too.)

Cris Luengo · Accepted Answer · 2024-02-04 15:16:49Z

One point I haven’t seen addressed in the other answers: your loop structure

for (size_t i = 0; i < vector_size; i++)
{
    if (is_odd(i))
    { odd_code }
    else
    { even_code }
}

can be much more simply be written as

for (size_t i = 0; i < vector_size; i += 2)
{
    odd_code
    even_code
}

There is no need to test whether the loop index is even or odd because these two conditions always alternate. But you might now do even_code one time more than in the original code, if the array length is odd.

I have the impression you need to run the two sets of comparisons N-1 times each, not N/2 as you do. I’m not sure, do test your code to see if it leaves the array sorted. Regular bubble sort must run at most N-1 times, and it does N-1 comparisons per iteration. Your code does N iterations with N/2 or N/2-1 comparisons per iteration. Therefore it is doing too few comparisons.

I think you need to run the odd/even pair N-1 times:

for (size_t i = 0; i < vector_size - 1; ++i)
{
    odd_code
    even_code
}

The inner loops are also more complex than they need to be:

for (size_t j = 1; j < vector_size / 2 + vector_size % 2; j++)
{
    size_t second = 2 * j;
    size_t first = second - 1;

You should loop to vector_size in steps of two instead:

for (size_t j = 1; j < vector_size; j += 2)
{
    size_t second = j;
    size_t first = second - 1;

For the “even” comparisons, simply make the loop start at 2.

For the odd-length case, we just need a if (at_end) break; between odd_code and even_code, of course. — Toby Speight
– Toby Speight, Commented Feb 4, 2024 at 16:25
@TobySpeight Yes, but I argue that you need to run the two as a pair, to get one complete bubble sort iteration. I might be wrong about that, but it is the reason I didn’t want to discuss how to exactly replicate OP’s result. — Cris Luengo
– Cris Luengo, Commented Feb 4, 2024 at 17:47

Stack Exchange Network

Bubble sort in parallel

4 Answers 4

General review

Algorithm

Make it more generic

Inefficient use of threads

You must log in to answer this question.

Hot Network Questions

Bubble sort in parallel

4 Answers 4

General review

Algorithm

Make it more generic

Inefficient use of threads

You must log in to answer this question.

Related

Hot Network Questions