Author Archives: Scott

Concurrency is an Atomic Operation

Our architect came into my office recently with a conundrum.  We’d recently jumped into concurrency as part of a performance-tuning overhaul.  After some profiling, we identified a few hotspots in program initialization and in paths that need to maintain user-responsiveness.  The solution was deceptively simple:  adopt a parallel for-each in place of the existing sequential for-each.  After debugging the thread-unsafe parts of the legacy code invoked from the parallel for-each, we achieved success.  Or so we thought.  It turns out that ensuring thread-safety along all code paths executed from the parallel for-each, through the course of routine maintenance, is a challenging task.  Another programmer on the team later made an innocent change to the code invoked by the parallel for-each, introducing a race condition.  It wasn’t clear whose responsibility this was – the breaking change could have been arbitrarily distant from the parallel for-each.

 

In functional languages, immutability and pure functions (non side-effecting) are core concepts.  Many argue that these lead to code that is easier to reason about, and that concurrency is nearly a natural consequence.  As Herb Sutter says, “shared state leads to contention”.  The corollary is that avoiding shared state can eliminate concurrency concerns (the idea behind lock-free algorithms).  Sharing of state occurs not just in obvious places, like global variables.  It also occurs in local mutable variables (or members), which are within scope for more than one thread of execution.

 

The problem is that idiomatic C++ is littered with such mutable state and side-effecting functions.  I say “idiomatic” and not “legacy” C++.  In this new world order of threading support in the STL, it is oh-so-easy to manage threads – their creation, synchronization, invocation, etc.  What’s lacking is a best practice for ensuring that the code executed by threads is safe.  Some C++ shops have adopted a pure functional style of programming to ensure thread safety.  This is noble and impressive, but in my view impractical.  Such code may be thread-safe itself, but must still interface with other C++ code (libraries) which is still idiomatic and thus, not thread-safe.  How is thread-safety to be achieved then?  The fact that even the venerable go-to collection class, vector, must essentially be rewritten is instructive.

 

The architect concluded that we had two options:  roll back all concurrency work, or train all the developers on staff to be aware of threading and to write ALL of their code to be thread-safe.  The former was not an option – we had crossed the Rubicon.  In the end, we identified two techniques to achieve the latter:  (1) a “top down” (from the parallel for-each) analysis of const correctness; and (2) a “bottom up” analysis of “mutable correctness” (synchronizing access to shared state).  But the lesson for us was that with concurrency, you cannot “buy it by the yard” or delegate the responsibility to the local subject matter expert.  In other words, the move to concurrency in an organization must be atomic.  In that sense, as Sutter has also said, the free lunch is still over.

C++ and Beyond

Grove Park Inn

Grove Park Inn

Hello fellow travelers, and welcome to the inaugural post of my blog!  I thought it would be appropriate to begin it with a review of the C++ and Beyond 2012 conference, hosted by industry luminaries Scott Meyers, Herb Sutter, and Andrei Alexandrescu.  This year’s conference was held August 5-8 in the historic Grove Park Inn in Asheville, NC.  Attendance was limited to 120, which encouraged a more intimate, communal experience.  Speakers and attendees shared meals together, and Meyers even led a few hiking excursions around the grounds of the Inn.

An Expected Template

Most, but not all, of the content focused on C++11 features.  Alexandrescu did not fail to deliver a few templated novelties, such as his Expected<T> , a C++ variation on the Maybe Monad, and an alternative to the traditional, but mutually-exclusive, error propagation techniques of function returns and exceptions.  He also introduced ScopeGuard11, a C++11 upgrade to his popular ScopeGuard template, enabling an RAII-patterned transaction technique for invoking arbitrary blocks of logic comprising action, continuation, rollback, and commit operations.

Fast Code

Alexandrescu also presented two sessions on writing fast code.  Some of the techniques were quite novel, such as strength reduction (substituting cheaper operations or lighter-weight data types).  I resonated with the emphasis on mathematical analysis in fine-tuning algorithms, such as the use of injection to substitute two comparisons for one, and the observation that because addition is associative, and thus inherently parallelizable, accumulating algorithms should leverage it whereever possible.

Parallelism

A fair amount of time was devoted to techniques for optimizing code for ILP (instruction-level parallelism), whether in concurrent applications or single-threaded ones.  I use the term “optimizing” loosely, as the techniques were really aimed at encouraging parallel execution among the ALUs within a single core, which occurs “beneath” the level of the program code.  I had mixed feelings about this part of the session.  I was impressed by Alexandrescu’s rigorous scientific method in approaching the problem, inspiring me to do likewise.  I also took note of his “questioning authority” – in this case the established itoa function, which turns out to have rather mediocre performance.  My concern was with the techniques used to optimize this code for faster execution on a single proc.  While effective, I felt the focus meandered a bit from C++, and especially idiomatic C++.

Blocking Matters

Sutter’s focus was primarily on concurrency features in C++11.  His thorough and insightful treatment of atomics, async, and non-blocking alternatives to thread synchronization (such as message queues) provided a practicum in writing idiomatic concurrent C++11.  He also tantalized with promises of future language (or library) support for non-blocking sync constructs, such as a “then” method for invoking continuations on a future.  Sutter even hinted that a monadic style of async programming might be in the wings, taking inspiration from C#’s “await” keyword.

A New Community

Sutter devoted some time to advocating for the ongoing renaissance in C++ – specifically, community.  His call to action included a centralized source of reference materials, style guidelines, FAQs, and increased availability to, and transparency of, the C++ standardization process.  This is an exciting development, for a language that, to outside appearances, has byzantine control structures, and which has the reputation for being unfriendly to beginners.

Universal References

Meyers never fails to impress me with his keen insight and ability to clearly articulate the thorniest and murkiest of subjects.  Probably the greatest single value of the conference for me was Meyers’ concept of a Universal Reference.  The ambiguous nature of T&&, which can “collapse down” to either an lvalue reference or an rvalue reference, can make template code (even more) challenging to understand and maintain.  In his excellent article on rvalue references, Microsoft’s Stephan T. Lavavej hints at this ambiguity:  “In templates, things that look like rvalue references aren’t necessarily so.”  Meyers resolves the confusion by coining the term Universal Reference to capture the dual nature of T&& in situations where T is deduced.  An aptly-named construct can do more to clarify a subject than an essay of explanation.

An Effective Excerpt

Meyers concluded with a few bits of advice on C++11, which will no doubt find their way into his next edition of Effective C++, for which he also solicited input from attendees.  One of his “gotchas” (capturing member data by reference, as default behavior) even got the attention of Sutter, who proposed a breaking change to correct it.

Summary

The three speakers are outstanding in both technical acumen and presentation skills, which made this conference one of the best I’ve attended.  In addition, the banter between them was entertaining and lively, particularly in panel discussions.  C++ is a thriving, evolving language thanks in large part to advocates like these.