Effective Concurrency: Prefer Using Active Objects Instead of Naked Threads

This month’s Effective Concurrency column, “Prefer Using Active Objects Instead of Naked Threads,” is now live on DDJ’s website.

From the article:

… Active objects dramatically improve our ability to reason about our thread’s code and operation by giving us higher-level abstractions and idioms that raise the semantic level of our program and let us express our intent more directly. As with all good patterns, we also get better vocabulary to talk about our design. Note that active objects aren’t a novelty: UML and various libraries have provided support for active classes. Some actor-based languages already have variations of this pattern baked into the language itself; but fortunately, we aren’t limited to using only such languages to get the benefits of active objects.

This article will show how to implement the pattern, including a reusable helper to automate the common parts, in any of the popular mainstream languages and threading environments, including C++, C#/.NET, Java, and C/Pthreads.

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

1 The Pillars of Concurrency (Aug 2007)

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

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

4 Apply Critical Sections Consistently (Nov 2007)

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

6 Use Lock Hierarchies to Avoid Deadlock (Jan 2008)

7 Break Amdahl’s Law! (Feb 2008)

8 Going Superlinear (Mar 2008)

9 Super Linearity and the Bigger Machine (Apr 2008)

10 Interrupt Politely (May 2008)

11 Maximize Locality, Minimize Contention (Jun 2008)

12 Choose Concurrency-Friendly Data Structures (Jul 2008)

13 The Many Faces of Deadlock (Aug 2008)

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

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

16 Writing a Generalized Concurrent Queue (Nov 2008)

17 Understanding Parallel Performance (Dec 2008)

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

19 volatile vs. volatile (Feb 2009)

20 Sharing Is the Root of All Contention (Mar 2009)

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

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

23 Eliminate False Sharing (May 2009)

24 Break Up and Interleave Work to Keep Threads Responsive (Jun 2009)

25 The Power of “In Progress” (Jul 2009)

26 Design for Manycore Systems (Aug 2009)

27 Avoid Exposing Concurrency – Hide It Inside Synchronous Methods (Oct 2009)

28 Prefer structured lifetimes – local, nested, bounded, deterministic (Nov 2009)

29 Prefer Futures to Baked-In “Async APIs” (Jan 2010)

30 Associate Mutexes with Data to Prevent Races (May 2010)

31 Prefer Using Active Objects Instead of Naked Threads (June 2010)

Effective Concurrency: Prefer Futures to Baked-In “Async APIs”

This month’s Effective Concurrency column, Prefer Futures to Baked-In “Async APIs”, is now live on DDJ’s website.

From the article:

When designing concurrent APIs, separate "what" from "how"

Let’s say you have an existing synchronous API function [called DoSomething]… Because DoSomething could take a long time to execute (whether it keeps a CPU core busy or not), and might be independent of other work the caller is doing, naturally the caller might want to execute DoSomething asynchronously. …

The question is, how should we enable that? There is a simple and correct answer, but because many interfaces have opted for a more complex answer let’s consider that one first.

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)

Eliminate False Sharing (May 2009)

Break Up and Interleave Work to Keep Threads Responsive (Jun 2009)

The Power of “In Progress” (Jul 2009)

Design for Manycore Systems (Aug 2009)

Avoid Exposing Concurrency – Hide It Inside Synchronous Methods (Oct 2009)

Prefer structured lifetimes – local, nested, bounded, deterministic (Nov 2009)

Prefer Futures to Baked-In “Async APIs” (Jan 2010)

Effective Concurrency: Avoid Exposing Concurrency – Hide It Inside Synchronous Methods

This month’s Effective Concurrency column, Avoid Exposing Concurrency – Hide It Inside Synchronous Methods, is now live on DDJ’s website.

From the article:

You have a mass of existing code and want to add concurrency. Where do you start?

Let’s say you need to migrate existing code to take advantage of concurrent execution or scale on parallel hardware. In that case, you’ll probably find yourself in one of these two common situations, which are actually more similar than different:

  • Migrating an application: You’re an application developer, and you want to migrate your existing synchronous application to be able to benefit from concurrency.
  • Migrating a library or framework: You’re a developer on a team that produces a library or framework used by other teams or external customers, and you want to let the library take advantage of concurrency on behalf of the application without requiring application code rewrites.

You have a mountain of opportunities and obstacles before you. Where do you start?

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)

Eliminate False Sharing (May 2009)

Break Up and Interleave Work to Keep Threads Responsive (Jun 2009)

The Power of “In Progress” (Jul 2009)

Design for Manycore Systems (Aug 2009)

Avoid Exposing Concurrency – Hide It Inside Synchronous Methods (Oct 2009)

VS2010 Beta 1 Now Available

For those of you who are interested in using or trying Microsoft development tools, I’m happy to report that Visual Studio 2010 Beta 1 is now available.

If you’re interested in:

Remember this is just a beta and not intended for production use, but there’s a lot of cool stuff to play around with and it should run fine side-by-side with VS2008. Feedback via forums or filing a bug/suggestion is always appreciated. Enjoy!

Effective Concurrency: Eliminate False Sharing

This month’s Effective Concurrency column, “Eliminate False Sharing”, is now live on DDJ’s website.

People keep writing asking me about my previous mentions of false sharing, even debating whether it’s really a problem. So this month I decided to treat it in depth, including:

  • A compelling and realistic example where just changing a couple of lines to remove false sharing takes an algorithm from zero scaling to perfect scaling – even when many threads are merely doing reads. Hopefully after this nobody will argue that false sharing isn’t a problem. :-)
  • How your performance monitoring and analysis tools do and/or don’t help you uncover the problem, and how to use them effectively to identify the culprit. Short answer: CPU activity monitors aren’t very helpful, but cycles-per-instruction (CPI) and cache miss rate measurements attributed to specific lines of source code are your friend.
  • The two ways to correct the code: Reduce the frequency of writes to the too-popular cache line, or add padding to move other data off the line.
  • Reusable code in C++ and C#, and a note about Java, that you can use to use padding (and alignment if available) to put frequently-updated objects on their own cache lines.

From the article:

In two previous articles I pointed out the performance issue of false sharing (aka cache line ping-ponging), where threads use different objects but those objects happen to be close enough in memory that they fall on the same cache line, and the cache system treats them as a single lump that is effectively protected by a hardware write lock that only one core can hold at a time. … It’s easy to see why the problem arises when multiple cores are writing to different parts of the same cache line… In practice, however, it can be even more common to encounter a reader thread using what it thinks is read-only data still getting throttled by a writer thread updating a different but nearby memory location…

A number of readers have asked for more information and examples on where false sharing arises and how to deal with it. … This month, let’s consider a concrete example that shows an algorithm in extremis due to false sharing distress, how to use tools to analyze the problem, and the two coding techniques we can use to eliminate false sharing trouble. …

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)

“Eliminate False Sharing” (May 2009)

Effective Concurrency: volatile vs. volatile

This month’s Effective Concurrency column, “volatile vs. volatile”, is now live on DDJ’s website and also appears in the print magazine. (As a historical note, it’s DDJ’s final print issue, as I mentioned previously.)

This article aims to answer the frequently asked question: “What does volatile mean?” The short answer: “It depends, do you mean Java/.NET volatile or C/C++ volatile?” From the article:

What does the volatile keyword mean? How should you use it? Confusingly, there are two common answers, because depending on the language you use volatile supports one or the other of two different programming techniques: lock-free programming, and dealing with ‘unusual’ memory.

Adding to the confusion, these two different uses have overlapping requirements and impose overlapping restrictions, which makes them appear more similar than they are. Let’s define and understand them clearly, and see how to spell them correctly in C, C++, Java and C# — and not always as volatile. …

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)

Effective Concurrency: Lock-Free Code — A False Sense of Security

DDJ posted the next Effective Concurrency column a couple of weeks earlier than usual. You can find it here: “Lock-Free Code: A False Sense of Security”, just went live on DDJ’s site, and also appears in the print magazine.
 
This is a special column in a way, because I rarely critique someone else’s published code. However, mere weeks ago DDJ itself published an article with fundamentally broken code that tried to show how to write a simplified lock-free queue. I corresponded with the author, Petru Marginean, and his main reviewer, Andrei Alexandrescu, to discuss the problems, and they have patched the code somewhat and added a disclaimer to the article. But the issues need to be addressed, and so Petru kindly let me vivisect his code in public in this column (and the next, not yet available, which will show how to do it right).
 
From the article:

[Lock-free code is] hard even for experts. It’s easy to write lock-free code that appears to work, but it’s very difficult to write lock-free code that is correct and performs well. Even good magazines and refereed journals have published a substantial amount of lock-free code that was actually broken in subtle ways and needed correction.

To illustrate, let’s dissect some peer-reviewed lock-free code that was published here in DDJ just two months ago …

I hope you enjoy it. (Note: Yes, the title is a riff on Tom Cargill’s classic article “Exception Handling: A False Sense of Security”, one of Scott Meyers’ five “Most Important C++ Non-Book Publications…Ever”.)
 
Finally, here are links to previous Effective Concurrency columns (based on the magazine print issue dates):
August 2007 The Pillars of Concurrency
September 2007 How Much Scalability Do You Have or Need?
October 2007 Use Critical Sections (Preferably Locks) to Eliminate Races
November 2007 Apply Critical Sections Consistently
December 2007 Avoid Calling Unknown Code While Inside a Critical Section
January 2007 Use Lock Hierarchies to Avoid Deadlock
February 2008 Break Amdahl’s Law!
March 2008 Going Superlinear
April 2008 Super Linearity and the Bigger Machine
May 2008 Interrupt Politely
June 2008 Maximize Locality, Minimize Contention
July 2008 Choose Concurrency-Friendly Data Structures
August 2008 The Many Faces of Deadlock
September 2008 “Lock-Free Code: A False Sense of Security”

Constructor Exceptions in C++, C#, and Java

I just received the following question, whose answer is the same in C++, C#, and Java.

Question: In the following code, why isn’t the destructor/disposer ever called to clean up the Widget when the constructor emits an exception? You can entertain this question in your mainstream language of choice:

// C++ (an edited version of the original code
// that the reader emailed me)
class Gadget {
   Widget* w;

public:
   Gadget() {
     w = new Widget();
     throw new exception();
     // … or some API call might throw
   };

   ~Gadget() {
      if( w != nullptr ) delete w;
   }
};

// C# (equivalent)
class Gadget : IDisposable {
   private Widget w;

   public Gadget() {
     w = new Widget();
     throw new Exception();
     // … or some API call might throw
   };

   public void Dispose() {
     // … eliding other mechanics, eventually calls:
     if( w != null ) w.Dispose();
     // or just “w = null;” if Widget isn’t IDisposable
   }
};

// Java (equivalent)
class Gadget {
   private Widget w;

   public Gadget() {
     w = new Widget();
     throw new Exception();
     // … or some API call might throw
   };

   public void dispose() {
     if( w != null ) w.dispose();
     // or just “w = null;” if Widget isn’t disposable

   }
};

Interestingly, we can answer this even without knowing the calling code… but there is typical calling code that is similar in all three languages that reinforces the answer.

Construction and Lifetime

The fundamental principles behind the answer is the same in C++, C#, and Java:

  1. A constructor conceptually turns a suitably sized chunk of raw memory into an object that obeys its invariants. An object’s lifetime doesn’t begin until its constructor completes successfully. If a constructor ends by throwing an exception, that means it never finished creating the object and setting up its invariants — and at the point the exceptional constructor exits, the object not only doesn’t exist, but never existed.
  2. A destructor/disposer conceptually turns an object back into raw memory. Therefore, just like all other nonprivate methods, destructors/disposers assume as a precondition that “this” object is actually a valid object and that its invariants hold. Hence, destructors/disposers only run on successfully constructed objects.

I’ve covered some of these concepts and consequences before in GotW #66, “Constructor Failures,” which appeared in updated and expanded form as Items 17 and 18 of More Exceptional C++.

In particular, if Gadget’s constructor throws, it means that the Gadget object wasn’t created and never existed. So there’s nothing to destroy or dispose: The destructor/disposer not only isn’t needed to run, but it can’t run because it doesn’t have a valid object to run against.

Incidentally, it also means that the Gadget constructor isn’t exception-safe, because it and only it can clean up resources it might leak. In the C++ version, the usual simple way to write the code correctly is to change the w member’s type from Widget* to shared_ptr<Widget> or an equivalent smart pointer type that owns the object. But let’s leave that aside for now to explore the more general issue.

A Look At the Calling Code

Next, let’s see how these semantics are actually enforced, whether by language rules or by convention, on the calling side in each language. Here are the major idiomatic ways in each language to use an Gadget object in an exception-safe way:

// C++ caller

{
  Gadget myGadget;
  // do something with myGadget
}

// C# caller

using( Gadget myGadget = new Gadget() )
{
  // do something with myGadget
}

// Java caller

Gadget myGadget = new Gadget();

try {
  // do something with myGadget
}
finally {
  myGadget.dispose();
}

Consider the two cases where an exception can occur:

  • What if an exception is thrown while using myGadget — that is, during “do something with myGadget”? In all cases, we know that myGadget’s destructor/dispose method is guaranteed to be called.
  • But what if an exception is thrown while constructing myGadget? Now in all cases the answer is that the destructor/dispose method is guaranteed not to be called.

Put another way, we can say for all cases: The destructor/dispose is guaranteed to be run if and only if the constructor completed successfully.

Another Look At the Destructor/Dispose Code

Finally, let’s return to each key line of code one more time:

// C++
      if( w != nullptr ) delete w;
// C#
     if( w != null ) w.Dispose();
// Java
     if( w != null ) w.dispose();

The motivation for the nullness tests in the original example was to clean up partly-constructed objects. That motivation is suspect in principle — it means the constructors aren’t exception-safe because only they can clean up after themselves — and as we’ve seen it’s flawed in practice because the destructors/disposers won’t ever run on the code paths that the original motivation cared about. So we don’t need the nullness tests for that reason, although you might still have nullness tests in destructors/disposers to handle ‘optional’ parts of an object where a valid object might hold a null pointer or reference member during its lifetime.

In this particular example, we can observe that the nullness tests are actually unnecessary, because w will always be non-null if the object was constructed successfully. There is no (legitimate) way that you can call the destructor/disposer (Furthermore, C++ developers will know that the test is unnecessary for a second reason: Delete is a no-op if the pointer passed to it is null, so there’s never a need to check for that special case.)

Conclusion

When it comes to object lifetimes, all OO languages are more alike than different. Object and resource lifetime matters, whether or not you have a managed language, garbage collection (finalizers are not destructors/disposers!), templates, generics, or any other fancy bell or whistle layered on top of the basic humble class.

The same basic issues arise everywhere… the code you write to deal with them is just spelled using different language features and/or idioms in the different languages, that’s all. We can have lively discussions about which language offers the easiest/best/greenest/lowest-carbon-footprint way to express how we want to deal with a particular aspect of object construction, lifetime, and teardown, but those concerns are general and fundamental no matter which favorite language you’re using to write your code this week.