Effective Concurrency: The Many Faces of Deadlock

The latest Effective Concurrency column, “The Many Faces of Deadlock”, just went live on DDJ’s site, and also appears in the print magazine. From the article:

… That’s the classic deadlock example from college. Of course, two isn’t a magic number. An improved definition of deadlock is: “When N threads enter a locking cycle where each tries to take a lock the next already holds.”

“But wait,” someone might say. “I once had a deadlock just like the code you just showed, but it didn’t involve locks at all—it involved messages.” …
I hope you enjoy it.
 
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

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.

Research Firms Are Good At Research, Not Technology Predictions

This story has been picked up semi-widely since last night. I’m sure this Steven Prentice they quote is a fine (Gartner) Fellow, but really:

The computer mouse is set to die out in the next five years and will be usurped by touch screens and facial recognition, analysts believe.

Seriously, does anyone who uses computers daily really believe this kind of prediction just because someone at Gartner says so? Dude, sanity check: 1. What functions do you use your mouse for? 2. How many of those functions can be done by pointing at your screen or smiling at the camera: a) at all; and b) with equivalent high precision and low arm fatigue? Of course the mouse, including direct equivalents like the touchpad/trackpad, will be replaced someday. But to notice that people like to turn and shake their Wii controllers and iPhones and then make the leap to conclude that this will replace mice outright in the short term seems pretty thin even for Gartner.

When you read a report from Gartner, Forrester, IDC and their brethren research firms, remember that you’re either getting real-world data (aka research) or a single analyst’s personal predictions (aka crystal-ball gazing). Research firms are good at what they’re good at, namely research:

  • They’re “decent” at compiling current industry market data. Grade: A.
  • They’re “pretty okay” when they limit themselves to simple short-term extrapolation of that data, such as two-year projections of cost changes of high-speed networking in Canada or cell phone penetration in India. Grade: A-.

But when they try bigger technology movement predictions like “X will replace Y in Z years” they average somewhere around “spotty,” and on their off days they dip down into “I think you forgot to sanity check that sound bite” territory. It’s a pity that some venture capitalists take the research analysts’ word as gospel. Reliability of technology shift predictions: D+.

Kindling

Two weeks ago, I broke down and bought a Kindle. I like it:

  • It’s a good and well-designed reader, and the experience is much better than the other e-book reading I’ve done before on phones and PDAs. I like how when you bookmark a page, you can see it… the corner of the page gets a little dog-ear. [1]
  • It’s got a nice e-paper screen that uses ambient light, not backlight, which makes it readable anywhere just like a printed page — it’s even better, not worse, in direct sunlight.
  • It’s light and thin and sturdy. Sure beats carrying three or four books on a trip.
  • It has great battery life. I’ve only charged it once so far, when I first received it… since then I’ve had it for 11 days and read a full book and a half, and it still has 75% of its first charge left. (It helps that I turn the wireless off unless I’m actively using it.)
  • Fast, free wireless everywhere in the U.S., without computers or WiFi.

But today, it transformed my reading experience.

This morning, I was unsuspectingly reading my feeds in Google Reader as usual, blissfully unaware that the way I read books was about to change. Among other articles, I noticed that Slashdot ran a book review of Inside Steve’s Brain (that’s Jobs, not Wozniak or Ballmer). The review made me want to read the book. That’s when the new reality started, because I was interested in the book now, and had time to start reading it now:

  • Normally, I would have ordered it from Amazon and waited for it to arrive. But what usually happens then is that the book arrives a week later, and when it gets here I don’t have time to start it right away or I don’t quite feel like that kind of book just at the moment… and it goes on a shelf, with a 70% probability of being picked up at some point in the future.
  • Today, I searched for the book title on my Kindle, clicked “Buy”, and a few minutes later started reading Inside Steve’s Brain while eating lunch. [2]

That convenience isn’t merely instant gratification, it’s transformative. I suspect I’m going to be reading even more books now, even though I have a few little nits with the device, such as that the next and previous page buttons are a little too easy to press in some positions.

In other news, the Kindle also supports reading blogs and newspapers and some web surfing, but those are less compelling for me because I tend to do those things in the context of work, which means I’m already sitting at a computer with a bigger color screen and full keyboard. Maybe someday I’ll do it on e-paper. Until then, just living inside a virtual bookstore is plenty for me. Kindle + the Amazon Kindle store = iPod + iTunes for books. [3]

Here’s a useful summary article on Kindle features from a prospective user’s point of view.

Notes

1. The first two books I downloaded? The Design of Everyday Things, which was interestingly apropros to read on a new device like the Kindle with its nice dog-ear feedback and other well-designed features, and Foundation, which I hadn’t read in ages.

2. And it cost less than half what the dead-tree version would (though the latter was hardcover).

3. Caveat: I’m not actually an iPod owner, and I hate how Apple keeps insisting on installing iTunes on my computer just because I have Safari or QuickTime installed (mutter grumble evil product-tying monopolies mutter grumble :-) ). But apparently everyone else loves them, and they have indeed changed their industry.

Hungarian Notation Is Clearly (Good|Bad)

A commenter asked:

thread_local X tlsX; ??

Herb, I hope you aren’t backtracking on Hungarian Notation now that you work for Microsoft. Say it aint so…

It ain’t so. Besides, Microsoft’s Framework Developer’s Guide prominently intones: “Do not use Hungarian notation.”

Warts like “tls” and “i” are about lifetime and usage, not type. Here “tls” denotes that each thread gets its own copy of the value that is constructed and destroyed once per thread that uses it (lifetime) and doesn’t need to be synchronized using mutexes (usage). As another example of usage warts, I’ll also use “i” for a variable that’s used as an index or for iteration — and given that the “i” convention goes back to before BASIC, we shouldn’t try to pin the Hungarian tail on that donkey.

Having said that, though, many people have variously decried and defended different forms of Hungarian, and you may notice a pattern… they’re mostly:

Today, “Hungarian” nearly always means Systems Hungarian. The main trouble with Systems Hungarian comes from trying to embed information about a variable’s type into the variable’s name by prepending an encoded wart like the venerable sz, pach, ul, and their ilk. Although potentially helpful in a weakly-typed language like C, that’s known to be brittle and the prefixes tend to turn into lies as variable types morph during maintenance. The warting systems also don’t extend well to user-defined types and templates.

I’ve railed against the limitations and perils of Hungarian with Andrei Alexandrescu in our book C++ Coding Standards, where I made sure it was stated right up front as part of “Item 0: Don’t sweat the small stuff (or, Know what not to standardize)”:

Example 3: Hungarian notation. Notations that incorporate type information in variable names have mixed utility in type-unsafe languages (notably C), are possible but have no benefits (only drawbacks) in object-oriented languages, and are impossible in generic programming. Therefore, no C++ coding standard should require Hungarian notation, though a C++ coding standard might legitimately choose to ban it.

and with Jim Hyslop in our article “Hungarian wartHogs”:

“… the compiler already knows much more than you do about an object’s type. Changing the variable’s name to embed type information adds little value and is in fact brittle. And if there ever was reason to use some Hungarian notation in C-style languages, which is debatable, there certainly remains no value when using type-safe languages.”

There’s an amusing real-world note later in that article. I’ll pick up where the Guru is saying:

“I recall only one time when Hungarian notation was useful on a project. … One of the programmers on the project was named Paul,” the Guru explained. “Several months into the project, while still struggling to grow a ponytail and build his report-writing module, he pointed out that Hungarian notation had helped him find a sense of identity, for he now knew what he was…” She paused.

I blinked. It took me about ten seconds, and then I shut my eyes and grimaced painfully. “Pointer to array of unsigned long,” I groaned.

She smiled, enjoying my pain. “True story,” she said.

It is indeed a true story. I worked with him in 1993. The joke was bad then, too, but at least using Hungarian was more defensible because the project’s code was written in C. I found it handy at the time, but now that I work in more strongly typed languages I find the type-embedding version of Hungarian more actively harmful than actually useful.

You might call me a Hungarian emigrant, now living happily as an expat out in eastern C++ near the Isle of Managed Languages.

Trip Report: June 2008 ISO C++ Standards Meeting

The ISO C++ committee met in Sophia Antipolis, France on June 6-14. You can find the minutes here (note that these cover only the whole-group sessions, not the breakout technical sessions where we spend most of the week).

Here’s a summary of what we did, with links to the relevant papers to read for more details, and information about upcoming meetings.

Highlights: Complete C++0x draft coming in September

The biggest goal entering this meeting was to make C++0x feature-complete and stay on track to publish a complete public draft of C++0x this September for international review and comment — in ISO-speak, an official Committee Draft or CD. We are going to achieve that, so the world will know the shape of C++0x in good detail this fall.

We’re also now planning to have two rounds of international comment review instead of just one, to give the world a good look at the standard and two opportunities for national bodies to give their comments, the first round starting after our September 2008 meeting and the second round probably a year later. However, the September 2008 CD is “it”, feature-complete C++0x. The only changes expected to be made between that CD and the final International Standard are bug fixes and clarifications. It’s helpful to think of a CD as a feature-complete beta.

Coming into the June meeting, we already had a nearly-complete C++0x internal working draft — most features that will be part of C++0x had already been “checked in.” Only a few were still waiting to become stable enough to vote in, including initializer lists, range-based for loops, and concepts.

Of these, concepts is the long-pole feature for C++0x, which isn’t surprising given that it’s the biggest new language feature we’re adding to Standard C++. A primary goal of the June meeting, therefore, was to make as much progress on concepts as possible, and to see if it would be possible to vote that feature into the C++0x working draft at this meeting. We almost did that, thanks to a lot of work not only in France but also at smaller meetings throughout the winter and spring: For the first time, we ended a meeting with no known issues or controversial points in the concepts standardese wording, and we expect to “check in” concepts into the working draft at the next meeting in September, which both cleared the way for us to publish a complete draft then and motivated the plan to do two rounds of public review rather than one, just to make sure the standard got enough “bake time” in its complete form.

Next, I’ll summarize some of the major features voted into the draft at the June meeting.

Initializer lists

C++0x initializer lists accomplish two main objectives:

  • Uniformity: They provide a uniform initialization syntax you can use consistently everywhere, which is especially helpful when you write templates.
  • Convenience: They provide a general-purpose way of using the C initializer syntax for all sorts of types, notably containers.

See N2215 for more on the motivation and original design, and N2672 and N2679 for the final standardese.

Example: Initializing aggregates vs. classes

It’s convenient that we can initialize aggregates like this:

struct Coordinate1 {
  int i;
  int j;
  //…
};

Coordinate1 c1 = { 1, 2 };

but the syntax is slightly different for classes with constructors:

class Coordinate2 {
public:
  Coordinate2( int i, int j );
  // …
};

Coordinate2 c2( 1, 2 );

In C++0x, you can still do all of the above, but initializer lists give us a regular way to initialize all kinds of types:

Coordinate1 c1 = { 1, 2 };
Coordinate2 c2 = { 1, 2 }; // legal in C++0x

Having a uniform initialization syntax is particularly helpful when writing template code, so that the template can easily work with a wide variety of types.

Example: Initializing arrays vs. containers

One place where the lack of uniform initialization has been particularly annoying — at least to me, when I write test harnesses to exercise the code I show in articles and talks — is when initializing a container with some default values. Don’t you hate it when you want to create a container initialized to some known values, and if it were an array you can just write:

string a[] = { “xyzzy”, “plugh”, “abracadabra” };

but if it’s a container like a vector, you have to default-construct the container and then push every entry onto it individually:

// Initialize by hand today
vector<string> v;
v.push_back( “xyzzy” );
v.push_back( “plugh” );
v.push_back( “abracadabra” );

or, even more embarrassingly, initialize an array first for convenience and then construct the vector as a copy of the array, using the vector constructor that takes a range as an iterator pair:

// Initialize via an array today
string a[] = { “xyzzy”, “plugh”, “abracadabra” }; // put it into an array first
vector<string> v( a, a+3 ); // then construct the vector as a copy

Arrays are weaker than containers in nearly every other way, so it’s annoying that they get this unique convenience just because of their having been built into the language since the early days of C.

The lack of convenient initialization has been even more irritating with maps:

// Initialize by hand today
map<string,string> phonebook;
phonebook[ “Bjarne Stroustrup (cell)” ] = “+1 (212) 555-1212”;
phonebook[ “Tom Petty (home)” ] = “+1 (858) 555-9734”;
phonebook[ “Amy Winehouse (agent)” ] = “+44 20 74851424”;

In C++0x, we can initialize any container with known values as conveniently as arrays:

// Can use initializer list in C++0x
vector<string> v = { “xyzzy”, “plugh”, “abracadabra” };
map<string,string> phonebook =
  { { “Bjarne Stroustrup (cell)”, “+1 (212) 555-1212” },
    { “Tom Petty (home)”, “+1 (858) 555-9734” },
    { “Amy Winehouse (agent)”, “+44 99 74855424” } };

As a bonus, a uniform initialization syntax even makes arrays easier to deal with. For example, the array initializer syntax didn’t support arrays that are dynamically allocated or class members arrays:

// Initialize dynamically allocated array by hand today
int* a = new int[3];
a[0] = 1;
a[1] = 2;
a[2] = 99;

// Initialize member array by hand today
class X {
  int a[3];
public:
  X() { a[0] = 1; a[1] = 2; a[2] = 99; }
};

In C++0x, the array initialization syntax is uniformly available in these cases too:

// C++0x

int* a = new int[3] { 1, 2, 99 };

class X {
  int a[3];
public:
  X() : a{ 1, 2, 99 } {}
};

More concurrency support

Last October, we already voted in a state-of-the-art memory model, atomic operations, and a threading package. That covered the major things we wanted to see in this standard, but a few more were still in progress. Here are the major changes we made this time that relate to concurrency.

Thread-local storage (N2659): To declare a variable which will be instantiated once for each thread, use the thread_local storage class. For example:

class MyClass {
  …
private:
  thread_local X tlsX;
};
void SomeFunc() {
  thread_local Y tlsY;
  …
};

Dynamic initialization and destruction with concurrency (N2660) handles two major cases:

  • Static and global variables can be concurrently initialized and destroyed if you try to access them on multiple threads before main() begins. If more than one thread could initialize (or use) the variable concurrency, however, it’s up to you to synchronize access.
  • Function-local static variables will have their initialization automatically protected; while one thread is initializing the variable, any other threads that enter the function and reach the variable’s declaration will wait for the initialization to complete before they continue on. Therefore you don’t need to guard initialization races or initialization-use races, and if the variable is immutable once constructed then you don’t need to do any synchronization at all to use it safely. If the variable can be written to after construction, you do still need to make sure you synchronize those post-initialization use-use races on the variable.

Thread safety guarantees for the standard library (N2669): The upshot is that the answer to questions like “what do I need to do to use a vector<T> v or a shared_ptr<U> sp thread-safely?” is now explicitly “same as any other object: if you know that an object like v or sp is shared, you must synchronize access to it.” Only a very few objects need to guarantee internal synchronization; the global allocator is one of those, though, and so it gets that stronger guarantee.

The “other features” section below also includes a few smaller concurrency-related items.

More STL algorithms (N2666)

We now have the following new STL algorithms. Some of them fill holes (e.g., “why isn’t there a copy_if or a counted version of algorithm X?”) and others provide handy extensions (e.g., “why isn’t there an all_of or any_of?”).

  • all_of( first, last, pred )
    returns true iff all elements in the range satisfy pred
  • any_of( first, last, pred )
    returns true iff any element in the range satisfies pred
  • copy_if( first, last result, pred)
    the “why isn’t this in the standard?” poster child algorithm
  • copy_n( first, n result)
    copy for a known number of n elements
  • find_if_not( first, last, pred )
    returns an iterator to the first element that does not satisfy pred
  • iota( first, last, value )
    for each element in the range, assigns value and increments value “as if by ++value”
  • is_partitioned( first, last, pred )
    returns true iff the range is already partitioned by pred; that is, all elements that satisfy pred appear before those that don’t
  • none_of( first, last, pred )
    returns true iff none of the elements in the range satisfies pred
  • partition_copy( first, last, out_true, out_false, pred )
    copy the elements that satisfy pred to out_true, the others to out_false
  • partition_point( first, last, pred)
    assuming the range is already partitioned by pred (see is_partitioned above), returns an iterator to the first element that doesn’t satisfy pred
  • uninitialized_copy_n( first, n, result )
    uninitialized_copy for a known number of n elements

Other approved features

  • N2435 Explicit bool for smart pointers
  • N2514 Implicit conversion operators for atomics
  • N2657 Local and unnamed types as template arguments
  • N2658 Constness of lambda functions
  • N2667 Reserved namespaces for POSIX
  • N2670 Minimal support for garbage collection and reachability-based leak detection 
  • N2661 Time and duration support
  • N2674 shared_ptr atomic access
  • N2678 Error handling specification for Chapter 30 (Threads)
  • N2680 Placement insert for standard containers

Next Meeting

Although we just got back from France, the next meeting of the ISO C++ standards committee is already coming up fast:

The meetings are public, and if you’re in the area please feel free to drop by.