Why are 50 threads faster than 4?

Question

DWORD WINAPI MyThreadFunction(LPVOID lpParam) {
    volatile auto x = 1;
    for (auto i = 0; i < 800000000 / MAX_THREADS; ++i) {
        x += i / 3;
    }
    return 0;
}

This function is run in MAX_THREADS threads.
I have run the tests on Intel Core 2 Duo, Windows 7, MS Visual Studio 2012 using Concurrency Visualizer with MAX_THREADS=4 and MAX_THREADS=50.
test1 (4 threads) completed in 7.1 seconds, but test2 (50 threads) completed in 5.8 seconds while test1 has more context switches than test2.
I have run the same tests on Intel Core i5, Mac OS 10.7.5 and got the same results.

Answer 1

I decided to benchmark this myself on my 4-core machine. I directly compared 4 threads with 50 threads by interleaving 100 tests of each. I used my own numbers so that I had a reasonable execution time for each task.

The result was as you described. The 50-thread version is marginally faster. Here is a box plot of my results:

Why? I think this comes down to the thread scheduling. The task is not complete until all threads have done their work, and each thread must do a quarter of the job. Because your process is being shared with other processes on the system, if any single thread is switched out to another process, this will delay the entire task. While we are waiting for the last thread to finish, all other cores are idle. Note how the time distribution of the 4-thread test is much wider than the 50-thread test, which we might expect.

When you use 50 threads, each thread has less to do. Because of this, any delays in a single thread will have a less significant effect on the total time. When the scheduler is busy rationing cores out to lots of short threads, a delay on one core can be compensated by giving these threads time on another core. The total effect of latency on one core is not as much of a show-stopper.

So it would seem that in this case the extra context-switching is not the biggest factor. While the gain is small, it appears to be beneficial to swamp the thread scheduler a little bit, given that the processing is much more significant than the context-switching. As with everything, you must find the correct balance for your application.

---

[edit] Out of curiosity I ran a test overnight while my computer wasn't doing much else. This time I used 200 samples per test. Again, tests were interleaved to reduce the impact of any localised background tasks.

The first plot of these results is for low thread-counts (up to 3 times the number of cores). You can see how some choices of thread count are quite poor... That is, anything that is not a multiple of the number of cores, and especially odd values.

The second plot is for higher thread-counts (from 3 times the number of cores up to 60).

Above, you can see a definite downward trend as the thread-count increases. You can also see the spread of results narrow as the thread-count increases.

In this test, it's interesting to note that the performance of 4-thread and 50-thread tests were about the same and the spread of results in the 4-core test was not as wide as my original test. Because the computer wasn't doing much else, it could dedicate time to the tests. It would be interesting to repeat the test while placing one core under 75% load.

And just to keep things in perspective, consider this:

---

[Another edit] After posting my last lot of results, I noticed that the jumbled box plot showed a trend for those tests that were multiples of 4, but the data was a little hard to see.

I decided to do a test with only multiples of four, and thought I may as well find the point of diminishing returns at the same time. So I used thread counts that are powers of 2, up to 1024. I would have gone higher, but Windows bugged out at around 1400 threads.

The result is rather nice, I think. In case you wonder what the little circles are, those are the median values. I chose it instead of the red line that I used previously because it shows the trend more clearly.

It seems that in this particular case, the pay dirt lies somewhere between 50 and 150 threads. After that, the benefit quickly drops away, and we're entering the territory of excessive thread management and context-switching.

The results might vary significantly with a longer or shorter task. In this case, it was a task involving a lot of pointless arithmetic which took approximately 18 seconds to compute on a single core.

By tuning only the number of threads, I was able to shave an extra 1.5% to 2% off the median execution time of the 4-thread version.

Answer 2

It all depends on what your threads are doing.

Your computer can only concurrently run as many threads as there are cores in the system. This includes virtual cores via features like Hyper-threading.

CPU-bound

If your threads are CPU-bound, (meaning they spend the vast majority of their time doing calculations on data that is in memory), you will see little improvement by increasing the number of threads above the number of cores. You actually lose efficiency with more threads running, because of the added overhead of having to context-swtich the threads on and off the CPU cores.

I/O-bound

Where (#threads > #cores) will help, is when your threads are I/O-bound, meaning they spend most of their time waiting on I/O, (hard disk, network, other hardware, etc.) In this case, a thread that is blocked waiting on I/O to complete will be pulled off the CPU, and a thread that is actually ready to do something will be put on instead.

The way to get highest efficiency is to always keep the CPU busy with a thread that's actually doing something. (Not waiting on something, and not context-switching to other threads.)

Answer 3

I took some code that I had "laying about" for some other purposes, and re-used it - so please beware that it's not "pretty", nor is supposed to be a good example of how you should do this.

Here's the code I came up with (this is on a Linux system, so I'm using pthreads and I removed the "WINDOWS-isms":

#include <iostream>
#include <pthread.h>
#include <cstring>

int MAX_THREADS = 4;

void * MyThreadFunction(void *) {
    volatile auto x = 1;
    for (auto i = 0; i < 800000000 / MAX_THREADS; ++i) {
        x += i / 3;
    }
    return 0;
}


using namespace std;

int main(int argc, char **argv)
{
    for(int i = 1; i < argc; i++)
    {
    if (strcmp(argv[i], "-t") == 0 && argc > i+1)
    {
        i++;
        MAX_THREADS = strtol(argv[i], NULL, 0);
        if (MAX_THREADS == 0)
        {
        cerr << "Hmm, seems like end is not a number..." << endl;
        return 1;
        }       
    }
    }
    cout << "Using " << MAX_THREADS << " threads" << endl;
    pthread_t *thread_id = new pthread_t [MAX_THREADS];
    for(int i = 0; i < MAX_THREADS; i++)
    {
    int rc = pthread_create(&thread_id[i], NULL, MyThreadFunction, NULL);
    if (rc != 0)
    {
        cerr << "Huh? Pthread couldn't be created. rc=" << rc << endl;
    }
    }
    for(int i = 0; i < MAX_THREADS; i++)
    {
        pthread_join(thread_id[i], NULL);
    }
    delete [] thread_id;
}

Running this with a variety of number of threads:

MatsP@linuxhost junk]$ g++ -Wall -O3 -o thread_speed thread_speed.cpp -std=c++0x -lpthread
[MatsP@linuxhost junk]$ time ./thread_speed -t 4
Using 4 threads

real    0m0.448s
user    0m1.673s
sys 0m0.004s
[MatsP@linuxhost junk]$ time ./thread_speed -t 50
Using 50 threads

real    0m0.438s
user    0m1.683s
sys 0m0.008s
[MatsP@linuxhost junk]$ time ./thread_speed -t 1
Using 1 threads

real    0m1.666s
user    0m1.658s
sys 0m0.004s
[MatsP@linuxhost junk]$ time ./thread_speed -t 2
Using 2 threads

real    0m0.847s
user    0m1.670s
sys 0m0.004s
[MatsP@linuxhost junk]$ time ./thread_speed -t 50
Using 50 threads

real    0m0.434s
user    0m1.670s
sys 0m0.005s

As you can see, the "user" time stays almost identical. I actually tries a lot of other values too. But the results are the same so I won't bore y'all with a dozen more that show almost the same thing.

This is running on a quad core processor, so you can see that the "more than 4 threads" times show the same "real" time as with "4 threads".

I doubt very much there is anything different in how Windows deals with threads.

I also compiled the code with a #define MAX_THREADS 50 and same again with 4. It gave no difference to the code posted - but just to cover the alternative where the compiler is optimizing the code.

By the way, the fact that my code runs some three to ten times faster indicates that the originally posted code is using debug mode?

Answer 4

I did some tests a while ago on Windows, (Vista 64 Ultimate), on a 4/8 core i7. I used similar 'counting' code, submitted as tasks to a threadpool with varying numbers of threads, but always with the same total amount of work. The threads in the pool were given a low priority so that all the tasks got queued up before the threads, and timing, started. Obviously, the box was otherwise idle, (~1% CPU used up on services etc).

8 tests,
400 tasks,
counting to 10000000,
using 8 threads:
Ticks: 2199
Ticks: 2184
Ticks: 2215
Ticks: 2153
Ticks: 2200
Ticks: 2215
Ticks: 2200
Ticks: 2230
Average: 2199 ms

8 tests,
400 tasks,
counting to 10000000,
using 32 threads:
Ticks: 2137
Ticks: 2121
Ticks: 2153
Ticks: 2138
Ticks: 2137
Ticks: 2121
Ticks: 2153
Ticks: 2137
Average: 2137 ms

8 tests,
400 tasks,
counting to 10000000,
using 128 threads:
Ticks: 2168
Ticks: 2106
Ticks: 2184
Ticks: 2106
Ticks: 2137
Ticks: 2122
Ticks: 2106
Ticks: 2137
Average: 2133 ms

8 tests,
400 tasks,
counting to 10000000,
using 400 threads:
Ticks: 2137
Ticks: 2153
Ticks: 2059
Ticks: 2153
Ticks: 2168
Ticks: 2122
Ticks: 2168
Ticks: 2138
Average: 2137 ms

With tasks that take a long time, and with very little cache to swap out on a context-change, the number of threads used makes hardly any difference to the overall run time.

Answer 5

The problem you encounter is tighly bound to the way you are subdividing the workload of your process. In order to make an efficient use of a multicore system on a multitasking OS, you must ensure that there will always be remaining work for all the cores as long as possible during your process lifetime.

Consider the situation where your 4 threads process executes on 4 cores, and because of the system load configuration, one of the cores manages to finish 50% faster than the others: for the remaining process time, your CPU will only be able to allocate 3/4 of its processing power to your process, since there's only 3 threads remaining. In the same CPU load scenario, but with many more threads, the workload is split in many more subtasks which can be distributed more finely between the cores, all other things being equal (*).

This example illustrate that the timing difference is not actually due to the number of threads, but rather to the way the work has been divided, which is much more resilient to an uneven availability of cores in the later case. The same programme built with only 4 threads, but where the work is abstracted to a series of small tasks pulled by threads as soon as they are available would certainly produce similar or even better results on average, even though there would be the overhead of managing the tasks queue.

The finer granularity of a process task set gives it better flexibility.

---

(*) In the situation of a highly loaded system, the many threads approach might not be as beneficial, the unused core being actually allocated to other OS process, hence lightening the load for the three others cores still possibly used by your process.