Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
5  
Introducing concurrency in arbitary code is highly nontrivial, don't expect any compiler to do it. –  delnan Apr 23 '12 at 18:51
1  
Have a thread pool... –  user1249 Apr 23 '12 at 19:17
add comment

5 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment
  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).

share|improve this answer
add comment

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.

share|improve this answer
3  
If I have a data set with 10 million entries and I want to map some embarrassingly parallel O(1) operation (e.g. saturating each pixel of an raster image individually) over those values, the running time is O(1) -- after all, 10 million is just another constant -- but halving the runtime by using two threads for 5 million operations each, I'd say that makes a pretty significant difference. –  delnan Apr 23 '12 at 19:24
    
10 million hard-coded constants is an extremely unlikely use case and would constitute as an exception. However if it is a "data set" that you are mining somehow, I'd consider that "variable" for the purpose of my answer. If you wish you can edit my answer to change the wording, but I think I was clear enough. –  Bizorke Apr 23 '12 at 19:31
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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