3
\$\begingroup\$

The following code is an experiment that I ran to play with the advantages of multi-threading in C++. Given a number 10000000000 it calculates how many numbers are even, divisible by 5, divisible by 8, divisible by 10 between the range 1 to 10000000000.

First, it runs single-threaded function followed by a multi-threaded function.

However, the problem with this is that results I got weren't as expected. It shows the multi-threading has no benefit at all. I am not even using mutexes but just multiple threads.

Compiler / IDE Used:

Microsoft Visual Studio 2019 Community Edition, C++17, x64 Release Build with /O2 Optimization.

Code:

#include <iostream>
#include <thread>
#include <chrono>
#include <string>
#include <vector>

#define CALC_NUMBER 10000000000ull

struct Counters {
    unsigned long long int CountDivTen = 0;
    unsigned long long int CountDivEight = 0;
    unsigned long long int CountDivFive = 0;
    unsigned long long int CountEven = 0;
};

Counters DivCounter;

// For multi-threading
std::vector<std::pair<unsigned long long, unsigned long long>> parts = {
    {1, 2500000000}, {2500000001, 5000000000}, {5000000001, 7500000000},    
    {7500000001, 10000000000}
};

// Multi-threading counters.
std::vector<Counters> MyCounters(4);


void SingleThreaded()
{
    std::chrono::high_resolution_clock::time_point StartTime = 
                         std::chrono::high_resolution_clock::now();

    for (unsigned long long x = 1; x <= CALC_NUMBER; ++x)
    {
        // Count the even number
        if ((x % 2) == 0)
            ++DivCounter.CountEven;

        // Count divisible by 5
        if ((x % 5) == 0)
            ++DivCounter.CountDivFive;

        // Count divisible by 8
        if ((x % 8) == 0)
            ++DivCounter.CountDivEight;

        // Count divisible by 10
        if ((x % 10) == 0)
            ++DivCounter.CountDivTen;
    }

    auto elapsed = std::chrono::high_resolution_clock::now() - StartTime;
    auto seconds = std::chrono::duration_cast<std::chrono::seconds>(elapsed).count();
    std::cout << "Time in seconds: " << seconds << std::endl;
}

void MultiThread_Merge(int index)
{
    for (unsigned long long x = parts[index].first; x <= parts[index].second; ++x)
    {
        // Count the even number
        if ((x % 2) == 0)
            ++MyCounters[index].CountEven;

        // Count divisible by 5
        if ((x % 5) == 0)
            ++MyCounters[index].CountDivFive;

        // Count divisible by 8
        if ((x % 8) == 0)
            ++MyCounters[index].CountDivEight;

        // Count divisible by 10
        if ((x % 10) == 0)
            ++MyCounters[index].CountDivTen;
    }
}

void DoThreadUsingMerge()
{
    // Start timer
    std::chrono::high_resolution_clock::time_point StartTime = 
                     std::chrono::high_resolution_clock::now();

    // Create four Threads
    std::vector<std::thread> MyThreads(4);

    // Create Threads
    for (size_t i = 0; i < MyThreads.size(); ++i) {

        MyThreads[i] = std::thread(MultiThread_Merge, i);
    }

    // Wait for all threads to finish.
    for (size_t i = 0; i < MyThreads.size(); ++i) {

        MyThreads[i].join();
    }

    // When threads are done, add up numbers.
    for (auto i : MyCounters)
    {
        // Add all the numbers.
        DivCounter.CountEven += i.CountEven;
        DivCounter.CountDivFive += i.CountDivFive;
        DivCounter.CountDivEight += i.CountDivEight;
        DivCounter.CountDivTen += i.CountDivTen;
    }

    // Stop timer and get time.
    auto elapsed = std::chrono::high_resolution_clock::now() - StartTime;
    auto seconds = std::chrono::duration_cast<std::chrono::seconds>(elapsed).count();
    std::cout << "Time in seconds: " << seconds << std::endl;
}

void DisplayCounters()
{
    std::cout << "Count divisible by 2: " << DivCounter.CountEven << std::endl;
    std::cout << "Count divisible by 5: " << DivCounter.CountDivFive << std::endl;
    std::cout << "Count divisible by 8: " << DivCounter.CountDivEight << std::endl;
    std::cout << "Count divisible by 10: " << DivCounter.CountDivTen << std::endl;
}


int main()
{
    std::cout << "Calculation number: " << CALC_NUMBER << std::endl;

    std::cout << "\n============================================\n";
    std::cout << "\nSingle-Threaded ..\n";

    SingleThreaded();

    DisplayCounters();

    // Reset for multi-thread
    DivCounter.CountEven = 0;
    DivCounter.CountDivFive = 0;
    DivCounter.CountDivEight = 0;
    DivCounter.CountDivTen = 0;

    std::cout << "\n============================================\n";
    std::cout << "\nMulti-Threaded (Merge) ..\n";

    DoThreadUsingMerge();
    DisplayCounters();

    system("pause");
}

Outputs:

Here's the output on 4 cores CPU, Windows 8.1 OS:

Calculation number: 10000000000

============================================

Single-Threaded .. Time in seconds: 36
Count divisible by 2: 5000000000
Count divisible by 5: 2000000000
Count divisible by 8: 1250000000
Count divisible by 10: 1000000000

============================================

Multi-Threaded (Merge) .. Time in seconds: 42
Count divisible by 2: 5000000000
Count divisible by 5: 2000000000
Count divisible by 8: 1250000000
Count divisible by 10: 1000000000
Press any key to continue . . .

Here's the output on 6 core CPU, Windows 10 OS:

Calculation number: 10000000000

============================================

Single-Threaded .. Time in seconds: 32
Count divisible by 2: 5000000000
Count divisible by 5: 2000000000
Count divisible by 8: 1250000000
Count divisible by 10: 1000000000

============================================

Multi-Threaded (Merge) .. Time in seconds: 45
Count divisible by 2: 5000000000
Count divisible by 5: 2000000000
Count divisible by 8: 1250000000
Count divisible by 10: 1000000000
Press any key to continue . . .

Results:

The results show that no matter how many times and regardless of number of cores, multi-threaded code doesn't benefit from threads.

Questions:

What's the reason that this code isn't behaving as expected? Did I just stumble upon some code which doesn't or cannot benefit from multi-threading?

Notes:

I also tried to increase the calculation number by 10x, 20x 30x so on.. but I didn't see any better performance.

\$\endgroup\$
  • \$\begingroup\$ You know that multithreading adds some overhead, no? \$\endgroup\$ – πάντα ῥεῖ Nov 3 at 11:10
  • 2
    \$\begingroup\$ Depends on more concrete context probably. \$\endgroup\$ – πάντα ῥεῖ Nov 3 at 11:12
  • 1
    \$\begingroup\$ Yes, the overhead is higher than the gain. \$\endgroup\$ – Mast Nov 3 at 12:56
  • 1
    \$\begingroup\$ I have a feeling codereview.SE is not actually the site you wanted to post this question on, as it seems you're mostly asking to gain understanding of why the code behaves this way. Maybe stackoverflow would be more fitting? \$\endgroup\$ – hoffmale Nov 3 at 22:59
  • 1
    \$\begingroup\$ Keeping the memory synced is probably forcing all the threads onto the same CPU so you get no gain from multithreading. Split the memory up so the work and memory can be distributed. \$\endgroup\$ – Martin York Nov 5 at 19:21
4
\$\begingroup\$

False sharing

struct Counters is smaller than a cache line. For a read-only data structure that would be fine, a "clean" copy of the data can be in the Shared state in a cache so it wouldn't matter if two or more cores wanted to have the same data. But here it's being used for many read/write/modify operations, and multiple cores are trying to jump on the same cache line - not the same data exactly, so it's not true sharing, the data is logically independent but since it's located in the same cache line, from the point of view of the hardware there is sharing: false sharing.

Padding out Counters to 64 bytes works .. to some extent. At least it will start to scale properly with thread count, but the code is still slow enough that I needed 4 threads before it overtook the single-threaded version.

Accidental pessimisation of the inner loop

From the point of view of the compiler, there are writes to (and reads from) shared memory. Maybe they are necessary, how would it know they're not? But we humans, with our whole-program reasoning skills, know most of them aren't necessary because the main thread waits for the workers to complete and then the results are collected, the partial counts are not observed along the way, so we can do this:

void MultiThread_Merge(int index)
{
    Counters local;
    for (unsigned long long x = parts[index].first; x <= parts[index].second; ++x)
    {
        // Count the even number
        if ((x % 2) == 0)
            ++local.CountEven;

        // Count divisible by 5
        if ((x % 5) == 0)
            ++local.CountDivFive;

        // Count divisible by 8
        if ((x % 8) == 0)
            ++local.CountDivEight;

        // Count divisible by 10
        if ((x % 10) == 0)
            ++local.CountDivTen;
    }

    MyCounters[index] = local;
}

And now it's fast.

\$\endgroup\$
  • \$\begingroup\$ "And now it's fast" - except it's still \$\mathcal{O}(n)\$ when it could be \$\mathcal{O}(1)\$ by simply using division (and thus not needing the multithreading overhead)... \$\endgroup\$ – hoffmale Nov 3 at 23:20
  • \$\begingroup\$ @hoffmale that's not the point of this question and you know it \$\endgroup\$ – harold Nov 3 at 23:21
  • \$\begingroup\$ If that isn't the point of the question, I strongly feel like this question doesn't belong on this site. \$\endgroup\$ – hoffmale Nov 3 at 23:32
  • \$\begingroup\$ @hoffmale then vote to close. By the way the program prints only constants (apart from the time) so no divisions would be necessary either, if you wanted to "optimally miss the point" you might as well hardcode the answer straight into the code. \$\endgroup\$ – harold Nov 3 at 23:40
  • \$\begingroup\$ @harold This has finally reduced the time by over 50%. Are you saying that its possible further optimize the code and reduce time by removing divisions? \$\endgroup\$ – cpx Nov 4 at 5:28
1
\$\begingroup\$

[I am writing this a separate answer as I have tested it now.]

I compiled your code and run the same test, with the same result. After some trying around, the problem seems to be that the four threads all access the same counting vector of struct (std::vector<Counters> MyCounters(4);).
I replaced the counter with a simple variable (unsigned long long int My1Counter;), and I get now a factor of 3.8 improvement for the multi-threaded run (this is still inside the dev environment, and the remaining .2 is probably the dev env eating a bit).

My guess is that the vector class is 'thread-safe', and therefore locks each time you access it from one of the threads, so the other three have to wait.
You can try a simple C-array to verify that, as it would not be implicitly thread-safe

\$\endgroup\$
  • \$\begingroup\$ As far as I knew, std::vector class wasn't thread safe. I'd like to verify that if they changed in C++17. So, I created C-style arrays instead of vectors and this time I got 36 with single thread and 34 with multi-thread function. I ran it outside the developer environment as well. \$\endgroup\$ – cpx Nov 3 at 17:50
  • \$\begingroup\$ I just confirmed there's nothing thread safe about a std::vector unless you use a std::mutex, Are you running the same compiler as mine on Windows? \$\endgroup\$ – cpx Nov 3 at 18:02
  • \$\begingroup\$ I have Windows 10, MS Visual Studio 2019 Community Edition, 16.3.7; C++ language standard is set to 'ISO C++17 Standard'; optimization is /O2. Try with the given My1Counter, that will of course ruin the count results, but you'll see that it works with a factor of N. I'm not really a SME for multi-threading; I learned it last week, and it worked for me. \$\endgroup\$ – Aganju Nov 3 at 18:58
0
\$\begingroup\$

You should definitely see a huge improvement, by a factor of nearly N.
The overhead that gets mentioned is in the microsecond range, and it is once per thread.

I have a similar example, where the runtime goes down by factors of 2, 4, 8, depending on the number of threads I start (up to the number of cores I have, of course).

I cannot tell you for sure why your example is not working; maybe the compiler was clever enough to run in multiple threads to begin with, or your executable does not get access to run more than one thread. Are you in a virtual machine maybe? Check int N = std::thread::hardware_concurrency() to see how many threads your program have access too.
I think your code is correct, and should work.

\$\endgroup\$
  • \$\begingroup\$ It's not a virtual machine. How would you roughly calculate the overhead for four threads? I see all four cores at 100% when I run it. \$\endgroup\$ – cpx Nov 3 at 15:38
  • 1
    \$\begingroup\$ I wouldn't know. But I see negligible overhead in my testing, less than a millisecond per thread (it's within the rounding error). I get 140.xxx seconds run-time with 1 thread, 35.xxx seconds with four threads, and the digits behind the comma are different every run. if I use 16 threads, I get 35.xxx too; if I use 128 threads, I get 35.xxx too. Your problem is not the overhead, it is either it runs both tests multithreaded, or it runs both times singlethreaded. \$\endgroup\$ – Aganju Nov 3 at 16:16
  • 1
    \$\begingroup\$ Try with commenting out three of the four divisions you do (so count only dividible by 2), so the compiler doesn't have an easy way to multithread on his own \$\endgroup\$ – Aganju Nov 3 at 16:16
  • 1
    \$\begingroup\$ Are you running it inside the development environment? (try standalone exe) What rights has the user you run with? (try with Admin account) \$\endgroup\$ – Aganju Nov 3 at 16:18
  • \$\begingroup\$ The hardware concurrency value is 4. I tried it running outside the IDE environment with admin rights. The result with single thread was 35 and 40 with multithreading. With only even number calculation it's 11 on single thread and 8 on multi-threading so it improves by about 30%. \$\endgroup\$ – cpx Nov 3 at 16:31
0
\$\begingroup\$

I do not have access to a Windows machine, but changing std::vector<Counters> MyCounters(4) to Counters MyCounters[4] doubles the performance of the code (my CPU is dual core), both when compiled with G++ and with Clang++.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.