Why are 50 threads faster than 4?

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.

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.)

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 4Using 4 threadsreal    0m0.448suser    0m1.673ssys 0m0.004s[MatsP@linuxhost junk]$ time ./thread_speed -t 50Using 50 threadsreal    0m0.438suser    0m1.683ssys 0m0.008s[MatsP@linuxhost junk]$ time ./thread_speed -t 1Using 1 threadsreal    0m1.666suser    0m1.658ssys 0m0.004s[MatsP@linuxhost junk]$ time ./thread_speed -t 2Using 2 threadsreal    0m0.847suser    0m1.670ssys 0m0.004s[MatsP@linuxhost junk]$ time ./thread_speed -t 50Using 50 threadsreal    0m0.434suser    0m1.670ssys 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?