This month’s Effective Concurrency column, “Use Thread Pools Correctly: Keep Tasks Short and Nonblocking”, is now live on DDJ’s website.

From the article:

… But the thread pool is a leaky abstraction. That is, the pool hides a lot of details from us, but to use it effectively we do need to be aware of some things a pool does under the covers so that we can avoid inadvertently hitting performance and correctness pitfalls. Here’s the summary up front:

1. Tasks should be small, but not too small, otherwise performance overheads will dominate.

2. Tasks should avoid blocking (waiting idly for other events, including inbound messages or contested locks), otherwise the pool won’t consistently utilize the hardware well — and, in the extreme worst case, the pool could even deadlock.

Let’s see why. …

I hope you enjoy it. Finally, here are links to previous Effective Concurrency columns:

The Pillars of Concurrency (Aug 2007)

How Much Scalability Do You Have or Need? (Sep 2007)

Use Critical Sections (Preferably Locks) to Eliminate Races (Oct 2007)

Apply Critical Sections Consistently (Nov 2007)

Avoid Calling Unknown Code While Inside a Critical Section (Dec 2007)

Use Lock Hierarchies to Avoid Deadlock (Jan 2008)

Break Amdahl’s Law! (Feb 2008)

Going Superlinear (Mar 2008)

Super Linearity and the Bigger Machine (Apr 2008)

Interrupt Politely (May 2008)

Maximize Locality, Minimize Contention (Jun 2008)

Choose Concurrency-Friendly Data Structures (Jul 2008)

The Many Faces of Deadlock (Aug 2008)

Lock-Free Code: A False Sense of Security (Sep 2008)

Writing Lock-Free Code: A Corrected Queue (Oct 2008)

Writing a Generalized Concurrent Queue (Nov 2008)

Understanding Parallel Performance (Dec 2008)

Measuring Parallel Performance: Optimizing a Concurrent Queue (Jan 2009)

volatile vs. volatile (Feb 2009)

Sharing Is the Root of All Contention (Mar 2009)

Use Threads Correctly = Isolation + Asynchronous Messages (Apr 2009)

“Use Thread Pools Correctly: Keep Tasks Short and Nonblocking” (Apr 2009)

Now that I’m over the icky flu that forced me to postpone the seminar two weeks ago, I’m happy to say that we have new dates: Effective Concurrency (Europe) will be held on May 27-29, 2009, in Stockholm, Sweden. I’ll cover the following topics:

• Fundamentals: Define basic concurrency goals and requirements • Understand applications’ scalability needs • Key concurrency patterns
• Isolation — Keep work separate: Running tasks in isolation and communicate via async messages • Integrating multiple messaging systems, including GUIs and sockets • Building responsive applications using background workers • Threads vs. thread pools
• Scalability — Re-enable the Free Lunch: When and how to use more cores • Exploiting parallelism in algorithms • Exploiting parallelism in data structures • Breaking the scalability barrier
• Consistency — Don’t Corrupt Shared State: The many pitfalls of locks–deadlock, convoys, etc. • Locking best practices • Reducing the need for locking shared data • Safe lock-free coding patterns • Avoiding the pitfalls of general lock-free coding • Races and race-related effects
• High Performance Concurrency: Machine architecture and concurrency • Costs of fundamental operations, including locks, context switches, and system calls • Memory and cache effects • Data structures that support and undermine concurrency • Enabling linear and superlinear scaling
• Migrating Existing Code Bases to Use Concurrency
• Near-Future Tools and Features

I hope to see some of you there!

This month’s Effective Concurrency column, “Use Threads Correctly = Isolation + Asynchronous Messages”, is now live on DDJ’s website.

From the article:

Explicit threads are undisciplined. They need some structure to keep them in line. In this column, we’re going to see what that structure is, as we motivate and illustrate best practices for using threads — techniques that will make our concurrent code easier to write correctly and to reason about with confidence.

I hope you enjoy it. Finally, here are links to previous Effective Concurrency columns and the DDJ print magazine issue in which they first appeared:

The Pillars of Concurrency (Aug 2007)

How Much Scalability Do You Have or Need? (Sep 2007)

Use Critical Sections (Preferably Locks) to Eliminate Races (Oct 2007)

Apply Critical Sections Consistently (Nov 2007)

Avoid Calling Unknown Code While Inside a Critical Section (Dec 2007)

Use Lock Hierarchies to Avoid Deadlock (Jan 2008)

Break Amdahl’s Law! (Feb 2008)

Going Superlinear (Mar 2008)

Super Linearity and the Bigger Machine (Apr 2008)

Interrupt Politely (May 2008)

Maximize Locality, Minimize Contention (Jun 2008)

Choose Concurrency-Friendly Data Structures (Jul 2008)

The Many Faces of Deadlock (Aug 2008)

Lock-Free Code: A False Sense of Security (Sep 2008)

Writing Lock-Free Code: A Corrected Queue (Oct 2008)

Writing a Generalized Concurrent Queue (Nov 2008)

Understanding Parallel Performance (Dec 2008)

Measuring Parallel Performance: Optimizing a Concurrent Queue (Jan 2009)

volatile vs. volatile (Feb 2009)

Sharing Is the Root of All Contention (Mar 2009)

Use Threads Correctly = Isolation + Asynchronous Messages (Apr 2009)

This month’s Effective Concurrency column, “Sharing Is the Root of All Contention”, is now live on DDJ’s website.

This article aims to address the root cause behind some frequently made assertions: Statements like “locks kill scalability” and “CAS kills scalability” are mostly true but focus on symptoms rather than causes; and others such as “reader/writer mutexes are great for scalability” at minimum need some heavy qualification.

From the article:

Quick: What fundamental principle do all of the following have in common?

• Two children drawing with crayons.
• Three customers at Starbucks adding cream to their coffee.
• Four processes running on a CPU core.
• Five threads updating an object protected by a mutex.
• Six threads running on different processors updating the same lock-free queue.
• Seven modules using the same reference-counted shared object.

Answer: In each case, multiple users share a resource that requires coordination because not everyone can use it simultaneously — and such sharing is the root cause of all resulting contention that will degrade everyone’s performance. (Note: The only kind of shared resource that doesn’t create contention is one that inherently requires no synchronization because all users can use it simultaneously without restriction, which means it doesn’t fall into the description above. For example, an immutable object can have its unchanging bits be read by any number of threads or processors at any time without synchronization.)

In this article, I’ll deliberately focus most of the examples on one important case, namely mutable (writable) shared objects in memory, which are an inherent bottleneck to scalability on multicore systems. But please don’t lose sight of the key point, namely that "sharing causes contention" is a general principle that is not limited to shared memory or even to computing.

The Inherent Costs of Sharing

Here’s the issue in one sentence: Sharing fundamentally requires waiting and demands answers to expensive questions. …

Aside: This will be in the first electronic-only Dr. Dobb’s Report, and I’m going to have to get used to Dobb’s being electronic-only. One consequence of this change that I just discovered today is that an article can go online hours after I correct the proofs. That may seem like it shouldn’t be surprising in the days of blogs, but a magazine isn’t (or at least wasn’t) like a blog. When I wrote for magazines like C++ Report in the late 1990s, the time between submitting the final column manuscript and seeing it in print was about two to three months, depending on the magazine. Since the mid-2000s with Dobb’s, it’s been only one month from proofs to print — and Dobb’s could have posted the online versions even sooner, but held them back to be semi-synced with the print magazine. Now that the print constraint has disappeared, apparently I can (and, today, did) start work on a Friday morning to find the Dobb’s proofs I corrected the night before already on the web. Nifty. (And thanks again, Deirdre!)

I hope you enjoy it. Finally, here are links to previous Effective Concurrency columns and the DDJ print magazine issue in which they first appeared:

The Pillars of Concurrency (Aug 2007)

How Much Scalability Do You Have or Need? (Sep 2007)

Use Critical Sections (Preferably Locks) to Eliminate Races (Oct 2007)

Apply Critical Sections Consistently (Nov 2007)

Avoid Calling Unknown Code While Inside a Critical Section (Dec 2007)

Use Lock Hierarchies to Avoid Deadlock (Jan 2008)

Break Amdahl’s Law! (Feb 2008)

Going Superlinear (Mar 2008)

Super Linearity and the Bigger Machine (Apr 2008)

Interrupt Politely (May 2008)

Maximize Locality, Minimize Contention (Jun 2008)

Choose Concurrency-Friendly Data Structures (Jul 2008)

The Many Faces of Deadlock (Aug 2008)

Lock-Free Code: A False Sense of Security (Sep 2008)

Writing Lock-Free Code: A Corrected Queue (Oct 2008)

Writing a Generalized Concurrent Queue (Nov 2008)

Understanding Parallel Performance (Dec 2008)

Measuring Parallel Performance: Optimizing a Concurrent Queue (Jan 2009)

volatile vs. volatile (Feb 2009)

Sharing Is the Root of All Contention (Mar 2009)

A number of people have asked whether I will be teaching my Effective Concurrency seminar in Europe. The answer is yes:

Effective Concurrency (Europe) will be held on March 16-18, 2009, in Stockholm, Sweden. This is my only public European seminar in 2009. I’ll cover the following topics:

• Fundamentals: Define basic concurrency goals and requirements • Understand applications’ scalability needs • Key concurrency patterns
• Isolation — Keep work separate: Running tasks in isolation and communicate via async messages • Integrating multiple messaging systems, including GUIs and sockets • Building responsive applications using background workers • Threads vs. thread pools
• Scalability — Re-enable the Free Lunch: When and how to use more cores • Exploiting parallelism in algorithms • Exploiting parallelism in data structures • Breaking the scalability barrier
• Consistency — Don’t Corrupt Shared State: The many pitfalls of locks–deadlock, convoys, etc. • Locking best practices • Reducing the need for locking shared data • Safe lock-free coding patterns • Avoiding the pitfalls of general lock-free coding • Races and race-related effects
• High Performance Concurrency: Machine architecture and concurrency • Costs of fundamental operations, including locks, context switches, and system calls • Memory and cache effects • Data structures that support and undermine concurrency • Enabling linear and superlinear scaling
• Migrating Existing Code Bases to Use Concurrency
• Near-Future Tools and Features

I hope to see some of you there!

Lest people get the wrong idea, I enjoy reading Jeff Atwood’s blog and agree with much of what he writes so entertainingly and provocatively. So far I’ve only responded when I strongly felt differently about something, which has been a grand total of twice now.

So let me also offer an example of something I wholeheartedly agree with. Yesterday, Jeff cited what is also my own favorite Programming Pearls figure:

Despite the enduring wonder of the yearly parade of newer, better hardware, we’d also do well to remember my all time favorite graph from Programming Pearls:

Everything is fast for small n.

Spot on. If you’re a professional programmer and haven’t read Programming Pearls yet, “run don’t walk” to your bookstore of choice.

Incidentally, just to tie this in to parallel computing as well, Jeff’s article also cites a nice graph of optimizations that improved NDepend:

Patrick Smacchia’s lessons learned from a real-world focus on performance is a great case study in optimization.

Patrick was able to improve nDepend analysis performance fourfold, and cut memory consumption in half. As predicted, most of this improvement was algorithmic in nature, but at least half of the overall improvement came from a variety of different optimization techniques.

As I’ve said many times, measure twice, optimize once: Know when and where to optimize. Profilers are your friend. As Patrick writes:

When it comes to enhancing performance there is only one way to do things right: measure and focus your work on the part of the code that really takes the bulk of time, not the one that you think takes the bulk of time.

And of course, in our ever-more-multicore world, the contribution of parallelization gain will continue to grow and dominate the optimization of CPU-bound code. But as Patrick also notes, realizing that gain is not always trivial:

While we get the 15% gain from between 1 and 2 processors, the gain is almost zero between 2 and 4 processors. We identified some potential IO contentions and memory issues that will require more attention in the future. This leads to another lesson: Don’t expect that scaling on many processors will be something easy, even if you don’t share states and don’t use synchronization.