365

Let's say I have a 4-core CPU, and I want to run some process in the minimum amount of time. The process is ideally parallelizable, so I can run chunks of it on an infinite number of threads and each thread takes the same amount of time.

Since I have 4 cores, I don't expect any speedup by running more threads than cores, since a single core is only capable of running a single thread at a given moment. I don't know much about hardware, so this is only a guess.

Is there a benefit to running a parallelizable process on more threads than cores? In other words, will my process finish faster, slower, or in about the same amount of time if I run it using 4000 threads rather than 4 threads?

1
  • I appreciate your question very much, but I somehow do not understand how is your first assumption relevant to your question? namely this sentence: "each thread takes the same amount of time."
    – Dexter
    Commented Nov 30, 2020 at 20:23

13 Answers 13

334

If your threads don't do I/O, synchronization, etc., and there's nothing else running, 1 thread per core will get you the best performance. However that very likely not the case. Adding more threads usually helps, but after some point, they cause some performance degradation.

Not long ago, I was doing performance testing on a 2 quad-core machine running an ASP.NET application on Mono under a pretty decent load. We played with the minimum and maximum number of threads and in the end we found out that for that particular application in that particular configuration the best throughput was somewhere between 36 and 40 threads. Anything outside those boundaries performed worse. Lesson learned? If I were you, I would test with different number of threads until you find the right number for your application.

One thing for sure: 4k threads will take longer. That's a lot of context switches.

7
  • 29
    I think Gonzalo's answer is good. I'd just add that you should experiment and measure. Your program will differ from his, or mine, or anyone else's and only measurements of your own program's behaviour will answer your questions properly. The performance of parallel (or concurrent) programs is not an area where good conclusions can be drawn from first principles alone. Commented Nov 11, 2009 at 22:34
  • 7
    +1, +answer: it surprises me that having many more threads than cores results in better performance, although it makes some sense if more threads means larger chunk of time share compared to competing threads. It would be nice my application could detect differences in performance and automagically tune itself to the optimal number of threads.
    – Juliet
    Commented Nov 12, 2009 at 15:56
  • 14
    It shouldn't surprise you in a real world scenario. Threads block waiting for IO resources like disk access, network, etc. And also waiting for non IO resources like other threads to finish using shared variables. What you really want to achieve is the minimum number of threads such that at least one thread per core can always be running.
    – patros
    Commented Nov 12, 2009 at 17:44
  • 4
    1 thread per core is not the optimum. It needs to be slightly more, preferably twice that since this will allow another thread to run if a thread is temporarily blocked. Even if only on memory. This is more importnat if you have systems (P4,I7, Sun Rock etc) that feature SMT/HT) Commented Dec 31, 2009 at 13:54
  • 1
    Hence the "That is very likely not the case" in my answer. Finding the right number depends on the application and the architecture it runs on.
    – Gonzalo
    Commented Dec 31, 2009 at 15:21
158

I agree with @Gonzalo's answer. I have a process that doesn't do I/O, and here is what I've found:

enter image description here

Note that all threads work on one array but different ranges (two threads do not access the same index), so the results may differ if they've worked on different arrays.

The 1.86 machine is a macbook air with an SSD. The other mac is an iMac with a normal HDD (I think it's 7200 rpm). The windows machine also has a 7200 rpm HDD.

In this test, the optimal number was equal to the number of cores in the machine.

12
  • 20
    +1 for the graph. Clearly 1 thread per core is best, but it's interesting that the quad core system seems to not at higher thread numbers (<100 anyway) the way the others do. Commented Sep 28, 2012 at 16:30
  • 66
    -1 for the graph! Smooth curves through integer-valued x-coordinates? A wild jump from 1 2 3 to 10 20 30 to 50 100? And y-coordinates that are multiples of 10 plus 2 for good measure. This is Excel's doing, isn't it?
    – Spacedman
    Commented Dec 27, 2012 at 15:46
  • 6
    @Spacedman Yes it is. The smooth curves have a much nicer look IMHO. :D
    – mota
    Commented Dec 27, 2012 at 16:01
  • 32
    @PascalvKooten, The problem is not that it looks pretty, it's deceiving at first glance. First of all the y-axis starts at 42, exaggerating the apparent difference between the tested machines. Secondly, the weird progression of x-axis values suggest that 'time-taken' does not scale linearly with 'number of threads', this is especially true for the blue line. I think the problem others (including myself) have with it is that it misrepresents the data.
    – pauluss86
    Commented Dec 21, 2013 at 22:57
  • 24
    @Spacedman The critique on the graph is the most ridiculous thing I have come across in the last 24 hours. The graph helps. A lot. Period. Could it have been done better? No one cares. Smooth curve instead of discrete? That is your problem???? I assume, all of you would never include such a graph into their answer because you don't have the extra time/energy to make it look good. That is my point.
    – tyrex
    Commented Nov 17, 2014 at 1:59
58

I know this question is rather old, but things have evolved since 2009.

There are two things to take into account now: the number of cores, and the number of threads that can run within each core.

With Intel processors, the number of threads is defined by the Hyperthreading which is just 2 (when available). But Hyperthreading cuts your execution time by two, even when not using 2 threads! (i.e. 1 pipeline shared between two processes -- this is good when you have more processes, not so good otherwise. More cores are definitively better!) Note that modern CPUs generally have more pipelines to divide the workload, so it's no really divided by two anymore. But Hyperthreading still shares a lot of the CPU units between the two threads (some call those logical CPUs).

On other processors you may have 2, 4, or even 8 threads. So if you have 8 cores each of which support 8 threads, you could have 64 processes running in parallel without context switching.

"No context switching" is obviously not true if you run with a standard operating system which will do context switching for all sorts of other things out of your control. But that's the main idea. Some OSes let you allocate processors so only your application has access/usage of said processor!

From my own experience, if you have a lot of I/O, multiple threads is good. If you have very heavy memory intensive work (read source 1, read source 2, fast computation, write) then having more threads doesn't help. Again, this depends on how much data you read/write simultaneously (i.e. if you use SSE 4.2 and read 256 bits values, that stops all threads in their step... in other words, 1 thread is probably a lot easier to implement and probably nearly as speedy if not actually faster. This will depend on your process & memory architecture, some advanced servers manage separate memory ranges for separate cores so separate threads will be faster assuming your data is properly filed... which is why, on some architectures, 4 processes will run faster than 1 process with 4 threads.)

4
  • 5
    There are probably others, but the one I know of is the POWER processor from IBM. They had systems with 4 or 8 threads per processors. Now they can crank in more cores, so they offer 2 threads per core instead... Commented Oct 9, 2013 at 19:32
  • This is old, but most of Intel i5,i7 has multi thread cpu's like for example i7 cpu's usually have 4 cores, but 8 threads.
    – Edgar.A
    Commented Jun 25, 2015 at 17:55
  • 6
    Processors don't have threads. They have physical and logical cores. With hyperthreading, a single physical core functions as two logical cores. I had a tech that insisted that processors having threads was a real thing, so I drew a picture on the whiteboard of a processor with spindle of thread sticking out of it.
    – user562566
    Commented Aug 27, 2015 at 8:23
  • 2
    @TechnikEmpire Have a look at this intel.com/content/www/us/en/processors/core/… , maybe then you can contact intel and draw them threads too.
    – g7k
    Commented Oct 12, 2015 at 12:53
33

The answer depends on the complexity of the algorithms used in the program. I came up with a method to calculate the optimal number of threads by making two measurements of processing times Tn and Tm for two arbitrary number of threads ‘n’ and ‘m’. For linear algorithms, the optimal number of threads will be N = sqrt ( (mn(Tm*(n-1) – Tn*(m-1)))/(nTn-mTm) ) .

Please read my article regarding calculations of the optimal number for various algorithms: pavelkazenin.wordpress.com

3
  • 6
    Why is it downvoted ? I'm sorry but this is the best answer to this question. gonzalo addresses the bold part of the question, and pkazen addresses the title. Both answer are very useful, but pkazen answer is relevant because we have a systematic method to approximate the number of thread. He even gives the formula for linea algorithms.
    – tobiak777
    Commented May 8, 2015 at 11:34
  • 2
    I didn't downvote but if I did it would be on the basis that there is no real explanation as to why or how the optimal number of threads might be related to the complexity of the algorithm, save by reading the entire linked article, which is a long read (because of the complexity of the article). Beyond that, some aspects of the article are not clear to me, most importantly how the experimental results confirm the theory.
    – Codebling
    Commented Jan 23, 2018 at 19:12
  • 1
    Also, I believe this calculation assumes that you have an infinite number of CPU cores. While this is definitely valuable information, the question is referring to real machines with a small number of cores.
    – Navneeth
    Commented Apr 3, 2019 at 19:35
28

The actual performance will depend on how much voluntary yielding each thread will do. For example, if the threads do NO I/O at all and use no system services (i.e. they're 100% cpu-bound) then 1 thread per core is the optimal. If the threads do anything that requires waiting, then you'll have to experiment to determine the optimal number of threads. 4000 threads would incur significant scheduling overhead, so that's probably not optimal either.

11

I thought I'd add another perspective here. The answer depends on whether the question is assuming weak scaling or strong scaling.

From Wikipedia:

Weak scaling: how the solution time varies with the number of processors for a fixed problem size per processor.

Strong scaling: how the solution time varies with the number of processors for a fixed total problem size.

If the question is assuming weak scaling then @Gonzalo's answer suffices. However if the question is assuming strong scaling, there's something more to add. In strong scaling you're assuming a fixed workload size so if you increase the number of threads, the size of the data that each thread needs to work on decreases. On modern CPUs memory accesses are expensive and would be preferable to maintain locality by keeping the data in caches. Therefore, the likely optimal number of threads can be found when the dataset of each thread fits in each core's cache (I'm not going into the details of discussing whether it's L1/L2/L3 cache(s) of the system).

This holds true even when the number of threads exceeds the number of cores. For example assume there's 8 arbitrary unit (or AU) of work in the program which will be executed on a 4 core machine.

Case 1: run with four threads where each thread needs to complete 2AU. Each thread takes 10s to complete (with a lot of cache misses). With four cores the total amount of time will be 10s (10s * 4 threads / 4 cores).

Case 2: run with eight threads where each thread needs to complete 1AU. Each thread takes only 2s (instead of 5s because of the reduced amount of cache misses). With four cores the total amount of time will be 4s (2s * 8 threads / 4 cores).

I've simplified the problem and ignored overheads mentioned in other answers (e.g., context switches) but hope you get the point that it might be beneficial to have more number of threads than the available number of cores, depending on the data size you're dealing with.

10

4000 threads at one time is pretty high.

The answer is yes and no. If you are doing a lot of blocking I/O in each thread, then yes, you could show significant speedups doing up to probably 3 or 4 threads per logical core.

If you are not doing a lot of blocking things however, then the extra overhead with threading will just make it slower. So use a profiler and see where the bottlenecks are in each possibly parallel piece. If you are doing heavy computations, then more than 1 thread per CPU won't help. If you are doing a lot of memory transfer, it won't help either. If you are doing a lot of I/O though such as for disk access or internet access, then yes multiple threads will help up to a certain extent, or at the least make the application more responsive.

8

Benchmark.

I'd start ramping up the number of threads for an application, starting at 1, and then go to something like 100, run three-five trials for each number of threads, and build yourself a graph of operation speed vs. number of threads.

You should that the four thread case is optimal, with slight rises in runtime after that, but maybe not. It may be that your application is bandwidth limited, ie, the dataset you're loading into memory is huge, you're getting lots of cache misses, etc, such that 2 threads are optimal.

You can't know until you test.

4

You will find how many threads you can run on your machine by running htop or ps command that returns number of process on your machine.

You can use man page about 'ps' command.

man ps

If you want to calculate number of all users process, you can use one of these commands:

  1. ps -aux| wc -l
  2. ps -eLf | wc -l

Calculating number of an user process:

  1. ps --User root | wc -l

Also, you can use "htop" [Reference]:

Installing on Ubuntu or Debian:

sudo apt-get install htop

Installing on Redhat or CentOS:

yum install htop
dnf install htop      [On Fedora 22+ releases]

If you want to compile htop from source code, you will find it here.

3

The ideal is 1 thread per core, as long as none of the threads will block.

One case where this may not be true: there are other threads running on the core, in which case more threads may give your program a bigger slice of the execution time.

2
  • It depends on if you want the users background processes to run like crap while your application is running then. For that matter you could just set a real-time priority for each thread and get the maximum amount of power. But users like multitasking.
    – Earlz
    Commented Nov 11, 2009 at 22:35
  • 2
    Well, we're dealing with a magical ideally parallelizable application. If I ever created such a thing I would feel entitled to hog the CPU as much as I want.
    – patros
    Commented Nov 12, 2009 at 17:46
2

One example of lots of threads ("thread pool") vs one per core is that of implementing a web-server in Linux or in Windows.

Since sockets are polled in Linux a lot of threads may increase the likelihood of one of them polling the right socket at the right time - but the overall processing cost will be very high.

In Windows the server will be implemented using I/O Completion Ports - IOCPs - which will make the application event driven: if an I/O completes the OS launches a stand-by thread to process it. When the processing has completed (usually with another I/O operation as in a request-response pair) the thread returns to the IOCP port (queue) to wait for the next completion.

If no I/O has completed there is no processing to be done and no thread is launched.

Indeed, Microsoft recommends no more than one thread per core in IOCP implementations. Any I/O may be attached to the IOCP mechanism. IOCs may also be posted by the application, if necessary.

3
  • I do not know which Linux you're talking about, but my blocks until a connection arrives. I suggest you read a few things about select() and FD_SET() and similar functions/macros. Commented Dec 27, 2012 at 11:44
  • Ok, so there's no asynchronous form which returns immediately? Commented Dec 28, 2012 at 8:35
  • From the select() man page: timeout is an upper bound on the amount of time elapsed before select() returns. If both fields of the timeval structure are zero, then select() returns immediately. (This is useful for polling.) If timeout is NULL (no timeout), select() can block indefinitely. Commented Dec 29, 2012 at 1:10
0

speaking from computation and memory bound point of view (scientific computing) 4000 threads will make application run really slow. Part of the problem is a very high overhead of context switching and most likely very poor memory locality.

But it also depends on your architecture. From where I heard Niagara processors are suppose to be able to handle multiple threads on a single core using some kind of advanced pipelining technique. However I have no experience with those processors.

0

Hope this makes sense, Check the CPU and Memory utilization and put some threshold value. If the threshold value is crossed,don't allow to create new thread else allow...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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