Actually it makes sense, if you manually force the code to use only 4 threads it will take more time to finish that in the case when you let the compiler split the work for you.
On a given machine there are hundreds of threads running concurrently, the OS will let them run in time slices on the available hardware. Using the same number of threads as the number of available processors does not mean your code will be faster than when you use a larger number of threads. Obviously this is OS and compiler dependent.
It does reduce thread switching overhead considerably, usually resulting in less time spent storing and retrieving thread contexts and more time spent actually processing the thread.
It's possible on newer intel hardware we've reached the stage where context switching is no longer much of a cost I guess...
> Actually it makes sense, if you manually force the code to use only 4 threads it will take more time to finish that in the case when you let the compiler split the work for you.
While I think this is correct, I think your reasoning is off. And as far as I know, the compiler does not do anything clever here (unlike in some smarter, less mainstream languages) and you're just launching a huge number of threads.
If you use only 4 threads in a similar manner in a loop, the problem is that the background threads finish and the CPU is idle while the serial loop that creates the threads is occupied by creating and launching the threads and there are not enough threads to keep the cpu busy. (edit: this is more likely about waiting for I/O, see below).
If you're truly CPU bound, you will not gain from having a lot more threads than CPU cores (* ~1.5 for hyperthreads). If your threads are waiting for I/O, adding more will cause the OS to switch to an available thread but you gain more by using asynchronous I/O functions (like aio and epoll or kqueue, which you won't find an abstraction for in C++ stdlib). The way the code in the blog works is actually spending a whole lot of good cpu cycles for doing context switching from one thread to another and wasting a lot of memory for maintaining threads that wait for disk I/O.
What you can't see from the tutorial source is what the worker actually does (make_perlin_noise), I assume that function also does the writing to disk which would explain why you benefit from launching a huge number of threads. On the other hand, your memory use is completely unacceptable with this solution.
You should try this: split the number of images evenly and make each thread compute a number of images. Launch roughly as many threads as there are cpu cores and do not make the threads wait for disk I/O. You should see performance go up and memory use go down.
One of the patterns I've used before is to use thread pools rather than starting and stopping threads all the time. Each thread in the pool can be passed a list of the tasks it needs to do, or grab tasks from a central list as it finishes a previous one.
Then after a few runs you can tune the pool size so that you get the most out of the machine. Obviously there are still gains to be made by switching to async io, avoiding any serial choke points etc, and keeping the pool size small, but it seems to be a decent approach.
This very much depends on what the threads are doing. Like some others have mentioned, threads are sometimes an abstraction of context and sometimes a CPU. THere is no pat answer -- unless you're doing only one kind of thing -- if you're all IO bound or all CPU bound, the answer is obvious, otherwise...
I worked on a platform that could have 200+ threads running through it, but in areas of the code where it mattered, only NCPU+epsilon threads were allowed to do intense CPU-bound work. Doing this, as you might expect, improves performance substantially when the system is loaded, while at the same time allowing one to use threads as an abstraction of context in the non-CPU bound areas of the code.
My thoughts exactly. Unless you use a language with cheap and fast green threads that multiplex on OS threads (like Haskell), you should use a number of threads that is roughly in the same order of magnitude as the number of CPU cores + hyper threads.
I am very surprised by the fact that there was any speedup at all and not surprised that the parallel version used 200x (!!) memory.
On the other hand, this is probably one of those thing that was done for demonstration purposes, not really something you'd do on practice.
Btw. is async a part of C++11 standard at all? I thought it was omitted from the standard but may be still implemented by some compilers/stdlibs. Does every async call start a new thread and why?
std::async is included in the C++11 standard. The number of threads that async will use is implementation dependent, I bet on Windows with VS2012 you will see a different number of threads. You could force async to run asynchronously or in a lazy evaluation mode using launch policies.
> Unless you use a language with cheap and fast green threads that multiplex on OS threads (like Haskell), you should use a number of threads that is roughly in the same order of magnitude as the number of CPU cores + hyper threads.
The optimal number of threads per core is workload and machine dependent, but rarely is that number 1 per hardware thread[1]. For maximum CPU utilization and computational efficiency, you need multiple software threads per hardware thread so that the OS always has a thread ready to go when another thread blocks or the CPU has an unused component. How much the threads block and what parts of the CPU the exercise is the workload-dependent part. Ideally, the number of threads would be a tunable performance parameter.
As an example of this, I recently wrote some math-heavy code to transform the cells of a matrix by a particular transfer function. Each cell calculation was independent, so I parallelized them. The most efficient parallelization for my 6-core AMD processor turned out to be 6 threads per core.
[1] The main exception I can think of is when running multiple applications in parallel that in turn parallelize their work.
> The optimal number of threads per core is workload and machine dependent, but rarely is that number 1 per hardware thread.
This is exactly why I said it should be in the same order of magnitude, not exactly the same. Definitely not 250+ threads on a dual core. It might make sense to add a few more threads to keep the CPU busy if one or more of the threads will have to wait.
I'm sorry, but if your "math-heavy" code performs better when oversubscribed, then it is a massively suboptimal implementation. As a performance-oriented mathematical library developer, with colleagues at many of the major supercomputing centers and vendors, oversubscription is a hazard that we guard against on CPU architectures because it is always slower. Many supercomputing environments use a kernel that does not even support over-subscription.
Note that GPUs are different in the sense that over-decomposition is necessary to cover latency, but even there, you generally get better performance at lower occupancy due to better register reuse. SMT CPU systems, most notably, Blue Gene/Q, often require use of multiple hardware threads per core to cover instruction latency and keep the prefetcher busy (due to allocation of outstanding requests). This is not over-subscription because those are bonified hardware threads.
Threads are for context switching. Can you switch context faster in code than the hardware can do it? Why would you think that?
If there is significant context with synchronization points, then threads are appropriate. This can occur in message-passing systems - its about all that happens in fact.
I'm not sure what the OP was doing (I should have read that first) but I just wanted to chime in and defend the use of threads where appropriate. In particular, where its algorithmically matched and where 'doing it yourself' would add more overhead.
> Threads are for context switching. Can you switch context faster in code than the hardware can do it? Why would you think that?
This code is using a whole bunch of threads that are waiting for disk I/O. You can do that faster than with threads using asynchronous I/O routines provided by your OS. E.g. aio(7) in POSIX.
That is very unfortunate, but sometimes performance goes over portability. I think it was a major omission to leave out async I/O abstractions from C11 and C++11 standard libraries.
But you can't do much with only the standard library anyway. In addition to async filesystem i/o, it's completely lacking network sockets (async or otherwise) and other important, almost standard functionality. And besides, aio is a POSIX standard, so it should be fairly widely supported. With POSIX aio + Win32 async i/o you should get quite good portability.
And in any case, it's just a bad idea to have a ton of threads waiting for synchronous I/O completion. If using async i/o is out of the question, use a thread pool to keep your resource consumption sane.
Thread pools require tuning. That means you can get it wrong, or what was right on one platform is later wrong on another. In any case, you have to burn human resources making it right.
Again, why is it a bad idea to use threads? Your OS doesn't feel any pain, its quite willing to support 100's of threads. While async i/o is cool, if the i/o context of each thread is quite different then again you're 'manually' handling context when fielding async, which can be worse in terms of hardware caches etc. associated with the thread that fields the async call.
Historically it has been bad to use a heck of a lot of threads because you add a lot of context switching overhead that you could otherwise avoid, as the OS tries to schedule everything to get some time and thus spends some cycles suspending and restoring active threads. If you have many hundreds of threads then this will involve fetching thread contexts from main memory (it may even with a few, I'm not sure on this). So the theory is that if don't absolutely need all of these things to run concurrently then you can design your workload to use these cycles instead of wasting them on switching back and forth, and get your work done faster.
I'm sure that hardware and operating systems are designed with this in mind and the effect is reduced, but it's still going to be a factor.
And I know we all have machines with gigabytes and gigabytes of RAM these days, but limiting the number of threads used is going to have a huge effect on memory footprint, which is still important in a lot of places (embedded/mobile etc).
Thread pools can/could be written to auto-tune, depending on the nature of the workload. The human is only comparing times over multiple runs, you can do this programmatically though this is more coding overhead. It does need to tune to the specific machine though, as all sorts of factors will affect the result. I'm not going to pretend they're a panacea but they can still be useful as they provide flexibility and a way around the context-switch costs.
EDIT - Also thread pools don't require tuning, and are not even necessary at all in this situation, people (self included) are just reacting to the idea of throwing orders of magnitude more threads at a system than it has processors, and expecting optimal results.
Thread switch time does not scale to the # of threads involved. Switching between 100 threads each blocked on i/o is exactly as efficient time-wise as switching between two threads ping-ponging the same i/o.
Memory footprint is somewhat applicable - often each has a (virtual) megabyte stack. So in 32-bit address mode you could run out of virtual memory!
> Thread switch time does not scale to the # of threads involved.
True, but the number of context switches does increase and that in turn decreases the ratio of useful work vs. context switch overhead.
Also the secondary costs of context switching, like flushing caches increase. If there are hundreds of threads, the chances that a thread is woken up with warm caches decreases.
Well, getting 1.7x speedup on a dual core box isn't so bad and makes some sense. Showing at least the context switching isn't crippling, if you can cope with the memory overhead.
Anthony William's book "C++ Concurrency in Action" gave me the impression that implementations of std::async would stop spawning new threads at some implementation defined limit based on harware concurrency levels. Instead, delay execution or switch to serial for extra tasks.
The "fade", "grad" and the "lerp" are written as member functions (so there is some "this" pushing), yet there is no need for so. There might be some speedup (overall) inlining them.
The author claimed it's straight JAVA translation from Ken Perlin's code, yet he managed to drop the "static" for the above three functions.
EDIT: Some more problems.
Since perlin noise is perfect candidate for data-parallel split, it would much more efficient to split the job where instead of creating one image / thread, you split one image among all threads and process them individually.
This way memory usage is reduced - e.g. you are processing one image, not N. For very big images it might be even more efficient to limit processing of one thread to a 16x16 or 256x1 image blocks.
There is another Java->C++ problem with the code in this case - since you instantiate the p[] array (not static again), this means that each worker would have it's own array, hence wasting L1 cache (the p[] data is all the same).
Overall this task is more suited for OpenMP (data-parallel), than the async stuff (but thanks for demonstrating it, I was not familiar)
28 comments
[ 3.0 ms ] story [ 61.9 ms ] threadThis is a great example of how you shouldn't run things in parallel. Running 280 Threads on 2-4 cores machine makes no sense at all.
On a given machine there are hundreds of threads running concurrently, the OS will let them run in time slices on the available hardware. Using the same number of threads as the number of available processors does not mean your code will be faster than when you use a larger number of threads. Obviously this is OS and compiler dependent.
It's possible on newer intel hardware we've reached the stage where context switching is no longer much of a cost I guess...
While I think this is correct, I think your reasoning is off. And as far as I know, the compiler does not do anything clever here (unlike in some smarter, less mainstream languages) and you're just launching a huge number of threads.
If you use only 4 threads in a similar manner in a loop, the problem is that the background threads finish and the CPU is idle while the serial loop that creates the threads is occupied by creating and launching the threads and there are not enough threads to keep the cpu busy. (edit: this is more likely about waiting for I/O, see below).
If you're truly CPU bound, you will not gain from having a lot more threads than CPU cores (* ~1.5 for hyperthreads). If your threads are waiting for I/O, adding more will cause the OS to switch to an available thread but you gain more by using asynchronous I/O functions (like aio and epoll or kqueue, which you won't find an abstraction for in C++ stdlib). The way the code in the blog works is actually spending a whole lot of good cpu cycles for doing context switching from one thread to another and wasting a lot of memory for maintaining threads that wait for disk I/O.
What you can't see from the tutorial source is what the worker actually does (make_perlin_noise), I assume that function also does the writing to disk which would explain why you benefit from launching a huge number of threads. On the other hand, your memory use is completely unacceptable with this solution.
You should try this: split the number of images evenly and make each thread compute a number of images. Launch roughly as many threads as there are cpu cores and do not make the threads wait for disk I/O. You should see performance go up and memory use go down.
Then after a few runs you can tune the pool size so that you get the most out of the machine. Obviously there are still gains to be made by switching to async io, avoiding any serial choke points etc, and keeping the pool size small, but it seems to be a decent approach.
I worked on a platform that could have 200+ threads running through it, but in areas of the code where it mattered, only NCPU+epsilon threads were allowed to do intense CPU-bound work. Doing this, as you might expect, improves performance substantially when the system is loaded, while at the same time allowing one to use threads as an abstraction of context in the non-CPU bound areas of the code.
I am very surprised by the fact that there was any speedup at all and not surprised that the parallel version used 200x (!!) memory.
On the other hand, this is probably one of those thing that was done for demonstration purposes, not really something you'd do on practice.
Btw. is async a part of C++11 standard at all? I thought it was omitted from the standard but may be still implemented by some compilers/stdlibs. Does every async call start a new thread and why?
The optimal number of threads per core is workload and machine dependent, but rarely is that number 1 per hardware thread[1]. For maximum CPU utilization and computational efficiency, you need multiple software threads per hardware thread so that the OS always has a thread ready to go when another thread blocks or the CPU has an unused component. How much the threads block and what parts of the CPU the exercise is the workload-dependent part. Ideally, the number of threads would be a tunable performance parameter.
As an example of this, I recently wrote some math-heavy code to transform the cells of a matrix by a particular transfer function. Each cell calculation was independent, so I parallelized them. The most efficient parallelization for my 6-core AMD processor turned out to be 6 threads per core.
[1] The main exception I can think of is when running multiple applications in parallel that in turn parallelize their work.
This is exactly why I said it should be in the same order of magnitude, not exactly the same. Definitely not 250+ threads on a dual core. It might make sense to add a few more threads to keep the CPU busy if one or more of the threads will have to wait.
I'm sorry, but if your "math-heavy" code performs better when oversubscribed, then it is a massively suboptimal implementation. As a performance-oriented mathematical library developer, with colleagues at many of the major supercomputing centers and vendors, oversubscription is a hazard that we guard against on CPU architectures because it is always slower. Many supercomputing environments use a kernel that does not even support over-subscription.
Note that GPUs are different in the sense that over-decomposition is necessary to cover latency, but even there, you generally get better performance at lower occupancy due to better register reuse. SMT CPU systems, most notably, Blue Gene/Q, often require use of multiple hardware threads per core to cover instruction latency and keep the prefetcher busy (due to allocation of outstanding requests). This is not over-subscription because those are bonified hardware threads.
What happens during a cache miss? Does the thread block?
If there is significant context with synchronization points, then threads are appropriate. This can occur in message-passing systems - its about all that happens in fact.
I'm not sure what the OP was doing (I should have read that first) but I just wanted to chime in and defend the use of threads where appropriate. In particular, where its algorithmically matched and where 'doing it yourself' would add more overhead.
This code is using a whole bunch of threads that are waiting for disk I/O. You can do that faster than with threads using asynchronous I/O routines provided by your OS. E.g. aio(7) in POSIX.
But you can't do much with only the standard library anyway. In addition to async filesystem i/o, it's completely lacking network sockets (async or otherwise) and other important, almost standard functionality. And besides, aio is a POSIX standard, so it should be fairly widely supported. With POSIX aio + Win32 async i/o you should get quite good portability.
And in any case, it's just a bad idea to have a ton of threads waiting for synchronous I/O completion. If using async i/o is out of the question, use a thread pool to keep your resource consumption sane.
Again, why is it a bad idea to use threads? Your OS doesn't feel any pain, its quite willing to support 100's of threads. While async i/o is cool, if the i/o context of each thread is quite different then again you're 'manually' handling context when fielding async, which can be worse in terms of hardware caches etc. associated with the thread that fields the async call.
Historically it has been bad to use a heck of a lot of threads because you add a lot of context switching overhead that you could otherwise avoid, as the OS tries to schedule everything to get some time and thus spends some cycles suspending and restoring active threads. If you have many hundreds of threads then this will involve fetching thread contexts from main memory (it may even with a few, I'm not sure on this). So the theory is that if don't absolutely need all of these things to run concurrently then you can design your workload to use these cycles instead of wasting them on switching back and forth, and get your work done faster.
I'm sure that hardware and operating systems are designed with this in mind and the effect is reduced, but it's still going to be a factor.
And I know we all have machines with gigabytes and gigabytes of RAM these days, but limiting the number of threads used is going to have a huge effect on memory footprint, which is still important in a lot of places (embedded/mobile etc).
Thread pools can/could be written to auto-tune, depending on the nature of the workload. The human is only comparing times over multiple runs, you can do this programmatically though this is more coding overhead. It does need to tune to the specific machine though, as all sorts of factors will affect the result. I'm not going to pretend they're a panacea but they can still be useful as they provide flexibility and a way around the context-switch costs.
EDIT - Also thread pools don't require tuning, and are not even necessary at all in this situation, people (self included) are just reacting to the idea of throwing orders of magnitude more threads at a system than it has processors, and expecting optimal results.
Memory footprint is somewhat applicable - often each has a (virtual) megabyte stack. So in 32-bit address mode you could run out of virtual memory!
True, but the number of context switches does increase and that in turn decreases the ratio of useful work vs. context switch overhead.
Also the secondary costs of context switching, like flushing caches increase. If there are hundreds of threads, the chances that a thread is woken up with warm caches decreases.
Anthony William's book "C++ Concurrency in Action" gave me the impression that implementations of std::async would stop spawning new threads at some implementation defined limit based on harware concurrency levels. Instead, delay execution or switch to serial for extra tasks.
The author claimed it's straight JAVA translation from Ken Perlin's code, yet he managed to drop the "static" for the above three functions.
EDIT: Some more problems.
Since perlin noise is perfect candidate for data-parallel split, it would much more efficient to split the job where instead of creating one image / thread, you split one image among all threads and process them individually.
This way memory usage is reduced - e.g. you are processing one image, not N. For very big images it might be even more efficient to limit processing of one thread to a 16x16 or 256x1 image blocks.
There is another Java->C++ problem with the code in this case - since you instantiate the p[] array (not static again), this means that each worker would have it's own array, hence wasting L1 cache (the p[] data is all the same).
Overall this task is more suited for OpenMP (data-parallel), than the async stuff (but thanks for demonstrating it, I was not familiar)
https://github.com/sol-prog/async_tutorial/blob/master/ppm.c...
Three calls to ostream::write() for each and every pixel. oof.