What is the minumum code/operations to have in a separate thread?

Question

I understand that threading is needed to get the maximum performance out of today's multicore processors but starting a thread is rather costly so you can't put every single calculation that can be done in parallel in an own thread. For example

answer = new thread(plus(1,2)) + new thread(plus(3,4))

will run much slower than the simple single-threaded

answer = 1+2+3+4

but if plus was some really complicated calculation the threaded variant might be faster.

Now to the questions

• Are there any convention or standards about what the minimum length of code, operations or execution time that are defendable to put in its own thread?
• Do I even have to worry about this or are the compiler/processor so smart that they do all the work for me?

The reason I ask this question is that I saw an implementation of quicksort that started a new thread for every recursive call ending up with (n²) threads and there many of this threads just returned some value.

Answer 1

when parallelizing there are 3 different timings to take into consideration

1. the serial time: this is the time spent doing stuff that cannot be parallelized and where you cannot get below (getting the input, writing the output)

2. the parallel time: this is the part where you can parallelize, this you can get down to 0 by throwing more processors at it

3. overhead: the time spent communicating between processes/threads, this is very dependent on the algorithm used and the distribution of the work

basically you can add threads until the overhead becomes too big compared to actual gain from parallelization there are formulas for that

but really this is a job for profiling as every algorithm is different

Answer 2

1. There are no conventions, every program is a different story, there is no quick and dirty rule that will let you skip the "careful planning" part.

2. Unfortunately no. To take advantage of threads you have to use them manually. However, there are languages or libraries that facilitate this e.g. a construct that runs a loop in parallel (but you still have to make sure that it makes sense).

Answer 3

If you're only creating a couple of threads, the overhead is negligible. So in your example, answer = new thread(plus(1,2)) + new thread(plus(3,4)) is roughly equivalent to answer = 1+2+3+4 (as long as you're not running this multiple times). This operation runs in a constant number of instructions so there is really no need to thread.

Threading is more appropriate when you are performing calculations on large (variable) sets of data where the running time for the algorithm is not constant. For any such calculation, your aim should be to have all cores at 100% over the duration of the calculation, so that there is no need to create 8000 threads to sort a list. Create one thread per processor and divide the work evenly.

Answer 4

Multithreading is not only about performance. It's also about user-experience. One of the main reasons to use multithreading is for applications to remain responsive. You wouldn't want your browser to become totally unresponsive until your next webpage has loaded.

So those situations need their own metric.

Answer 5

While a lot dependson your actual tools, the following guideline from Intel's TBB documentation may givea useful ballpark figure:

A rule of thumb is that grainsize iterations of operator() should take at least 10,000-100,000 instructions to execute.

TBB is not exactly heavyweight.