Dr. Dobb's Journal - December 2008 - (Page 47)

D12sutt_p3db 10/10/08 9:13 AM Page 47 Figure 2: Sample graph for measuring scalability of alternative algorithms for the same workload. Figure 1: Sample graph for measuring scalability of the same algorithm for different workloads. Assume that this code is entirely CPU-bound, and that the subcomputations really are independent and free of side effects on each other. Then we can get the answer faster on more cores by running the subparts in parallel. Here’s some pseudocode showing how to accomplish this using futures and the convenience of lambda functions, but with a common mistake: // Example 2 (flawed): Naïve parallel code for MyApp 2.0? // int NetSales() { // perform the subcomputations concurrently future wholesale = new thread( [] { CalcWholesale(); } ); future retail = new thread( [] { CalcRetail(); } ); future returns = new thread( [] { TotalReturns(); } ); // now block for the results return wholesale.value() + retail.value() – returns.value(); } one ready thread per core, and if there is more work than cores the pool naturally queues the work up and lets the machine concentrate on only as many tasks at a time as it has cores to perform. Here’s pseudocode for a revised version that uses pools instead: // Example 3 (better): Partly fixed parallel code for MyApp 2.0 // int NetSales() { // perform the subcomputations concurrently future wholesale = pool.run( [] { CalcWholesale(); } ); future retail = pool.run( [] { CalcRetail(); } ); future returns = pool.run( [] { TotalReturns(); } ); // now block for the results return wholesale.value() + retail.value() – returns.value(); } Seeing the words new Thread explicitly in code is often an indicator that code may not be as scalable as it could be. In most environments, it’s much less efficient to spin up a new thread for each piece of work than to run it on a thread pool: First, spinning up a new thread and throwing it away again each time incurs substantially more overhead than giving work to an existing pool thread. Second, spinning up a number of threads and turning them loose to fight for available cores via the operating system scheduler can cause needless contention when we spin up more work than there are cores currently available, which can happen not only on low-core hardware but also on many-core hardware if the application or the system happens to be doing a lot of other work at that moment. Both situations are different kinds of oversubscription, and some threads will have to incur extra context-switching to interleave on an available core. Instead, sharing the core by running one after the other would be both more efficient and more cache-friendly. Thread pools address these problems because a pool is designed to “rightsize” itself to the amount of hardware concurrency available on the machine. The pool will automatically try to maintain exactly The good news is that this can enable us to get the answer faster on more cores, at least up to three cores. But there are costs too: With today’s thread pools, we typically pay a tax of two context switches when we ship work over to a pool thread and then ship the result back. How can we reduce this cost? Reducing Context Switches We can eliminate some of the context switches by being smarter about the last line that combines the results, because just calling .value() three times may wake up the calling thread twice only to immediately have to sleep again; instead, use a “wait for a group of futures” facility if your futures library has one, as a well-written version can eliminate the needless wakeups. We can also avoid a switch by observing that the calling thread isn’t going to do anything anyway besides wait for the results, and so it’s often a good idea to keep the tail chunk of work and do it ourselves instead of needlessly idling the original thread. Example 4 shows both techniques in action: // Example 4: Improved parallel code for MyApp 2.0 // int NetSales() { // perform the subcomputations concurrently future wholesale = pool.run( [] { CalcWholesale(); } ); future retail = pool.run( [] { CalcRetail(); } ); int returns = TotalReturns(); // keep the tail work // now block for the results—-wait once, not twice December 2008 l www.ddj.com l Dr. Dobb’s Journal 47 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - December 2008

Dr. Dobb's Journal - December 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Conversations The Man Who Sold the Sky Performance on Rails LINQ-to-SQL and T-SQL A Remote Java RMI Registry Beyond B-Trees File Descriptors and Multithreaded Programs Effective Concurrency The Agile Edge Swaine's Flames

Dr. Dobb's Journal - December 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.