This code calculates the factorial of a number on multiple threads. My issue: it is only a little bit faster than the sequential version of it (and I think I know why, I just can't find a way to solve this).

I use boost::multiprecision::cpp_int so the limits of default integers are not a problem, the size of integers is only limited by memory.

Only showing the relevant parts:

// ... other includes ...
#include <boost/multiprecision/cpp_int.hpp>

#define THREAD_COUNT 4
std::atomic<int> thread_num(1);         // global variable

// stuff...

void threaded_factorial(unsigned long long int num, boost::multiprecision::cpp_int& bigInt)
{
    int threadid = thread_num++;     // thread_num is atomic, so this is safe
    boost::multiprecision::cpp_int N = 1;
    for (unsigned long long int i = threadid; i <= num; i = i + THREAD_COUNT)
    {
        N *=(i);
        
    }
    
    std::lock_guard<std::mutex> lock(mu);      // race condition --> mutex needed
    bigInt *= N;
}

// more stuff ...

And the call of the function:

// ...

boost::multiprecision::cpp_int result = 1;
std::thread workers[THREAD_COUNT];

for (int i = 0; i < THREAD_COUNT; ++i)
{
    workers[i] = std::thread(threaded_factorial, num, std::ref(result));
}
for (int i = 0; i < THREAD_COUNT; ++i)
{
    workers[i].join();
}

// ...

The results seem correct, but as I said, this is not much faster than sequential code.

For example. The calculation of the factorial of 325253 took

• 67586 ms on 4 threads
• 76226 ms on a single thread

That is some really poor performance.

The reason, I think is that the for cycle in the threaded_factorial function roughly takes the same amount of time for each thread to complete, so when the std::mutex mu is locked, (THREAD_COUNT-1) threads have to wait for the one which locked the mutex.

This way, most of the work (by far the largest multiplications) are happening in a sequential manner, so the algorithm is really slow.

How can I work around this issue and make this work efficiently?

This code calculates the factorial of a number on multiple threads. My issue: it is only a little bit faster than the sequential version of it (and I think I know why, I just can't find a way to solve this).

I use boost::multiprecision::cpp_int so the limits of default integers are not a problem, the size of integers is only limited by memory.

Only showing the relevant parts:

// ... other includes ...
#include <boost/multiprecision/cpp_int.hpp>

#define THREAD_COUNT 4
std::atomic<int> thread_num(1);         // global variable

// stuff...

void threaded_factorial(unsigned long long int num, boost::multiprecision::cpp_int& bigInt)
{
    int threadid = thread_num++;     // thread_num is atomic, so this is safe
    boost::multiprecision::cpp_int N = 1;
    for (unsigned long long int i = threadid; i <= num; i = i + THREAD_COUNT)
    {
        N *=(i);
        
    }
    
    std::lock_guard<std::mutex> lock(mu);      // race condition --> mutex needed
    bigInt *= N;
}

// more stuff ...

And the call of the function:

// ...

boost::multiprecision::cpp_int result = 1;
std::thread workers[THREAD_COUNT];

for (int i = 0; i < THREAD_COUNT; ++i)
{
    workers[i] = std::thread(threaded_factorial, num, std::ref(result));
}
for (int i = 0; i < THREAD_COUNT; ++i)
{
    workers[i].join();
}

// ...

The results seem correct, but as I said, this is not much faster than sequential code.

For example. The calculation of the factorial of 325253 took

• 67586 ms on 4 threads
• 76226 ms on a single thread

That is some really poor performance.

The reason, I think is that the for cycle in the threaded_factorial function roughly takes the same amount of time for each thread to complete, so when the std::mutex mu is locked, (THREAD_COUNT-1) threads have to wait for the one which locked the mutex.

This way, most of the work (by far the largest multiplications) is happening in a sequential manner, so the algorithm is really slow.

How can I work around this issue and make this work efficiently?