Prefer Structured Lifetimes: Local, Nested, Bounded, Deterministic
Herb Sutter is a bestselling author and consultant on software development topics, and a software architect at Microsoft. He can be contacted at www.gotw.ca.
There was a time when it was a novel idea that function calls should obey proper nesting, meaning that the lifetime of a called function should be a proper subset of the lifetime of the function that called it:
void f() {
//
g(); // jump to function g here and then
// return from function g and continue here!
//
}
"Eureka!" said Edsger Dijkstra. "Function g's execution occurs entirely within that of function f. Boy, that sure seems easier to reason about than jumping in and out of random subroutines with unstructured gotos. I wonder what to call this idea. There seems to be inherent structure to it. Hmm, I bet I could build a deterministic and efficient model of 'stack local variables' around it too and maybe I should write a letter" (I paraphrase.) [1]
That novel idea begat the discipline of structured programming. This was a huge boon to programming in general, because structured code was naturally localized and bounded so that parts could be reasoned about in isolation, and entire programs became more understandable, predictable, and deterministic. It was also a huge boon to reusability and a direct enabler of reusable software libraries as we know them today, because structured code made it much easier to treat a call tree (here, f and g and any other functions they might in turn call) as a distinct unit -- because now the call graph really could be relied upon to be a tree, not the previously usual plate of "goto spaghetti" that was difficult to isolate and disentangle from its original environment. The structuredness that let any call tree be designed, debugged, and delivered as a unit has worked so well, and made our code so much easier to write and understand, that we still apply it rigorously today: In every major language, we just expect that "of course" function calls on the same thread should still logically nest by default, and doing anything else is hardly imaginable.
That's great, but what does it have to do with concurrency?
A Tale of Three Kinds of Lifetimes
In addition to the function lifetimes we've just considered, Table 1 shows three more kinds of lifetimes -- of objects, of threads or tasks, and of locks or other exclusive resource access -- and for each one lists some structured examples, unstructured examples, and the costs of the unstructured mode.
For familiarity, let's start with object lifetimes (left column). I'll dwell on it a little, because the fundamental issues are the same as in the next two columns even though those more directly involve concurrency.
In the mainstream OO languages, a structured object lifetime begins with the constructor, and ends with the destructor (C++) or dispose method (C# and Java) being called before returning from the scope or function in which the object was created. The bounded, nested lifetime means that cleanup of a structured object is deterministic, which is great because there's no reason to hold onto a resource longer than we need it. The object's cleanup is also typically much faster, both in itself and in its performance impact on the rest of the system. [2] In all of the popular mainstream languages, programmers directly use structured function-local object lifetimes where possible for code clarity and performance:
- In some languages, we get to express the structured lifetime using a language feature, such as stack-based or by-value nested member objects in C++, and using blocks in C#.
- In other languages, we use a programming idiom or convention, such as the try/finally dispose pattern in Java, and explicit dispose-chaining (to have our object's dispose also call dispose on other objects exclusively owned by our object, the equivalent of by-value nested member objects) in both C# and Java.
Unstructured, non-local object lifetimes happen with global objects or dynamically allocated objects, which include objects your program may explicitly allocate on the heap and objects that a library you use may allocate on demand on your behalf. Even basic allocation costs more for unstructured, heap-based objects than for structured, stack-based ones. Objects with unstructured lifetimes also require more bookkeeping -- either by you such as by using smart pointers, or by the system such as with garbage collection and finalization. Importantly, note that C# and Java GC-time finalization [3] is not the same as disposing, and you can only do a restricted set of things in a finalizer. For example, in object A's finalizer it's not generally safe to use any other finalizable object B, because B might already have been finalized and no longer be in a usable state. Lest we be tempted to sneer at finalizers, however, note also that C++'s shutdown rules for global/static objects, while somewhat more deterministic, are intricate bordering on arcane and require great care to use reliably. So having an unstructured lifetime really does have wide-ranging consequences to the robustness and determinism of your program, particularly when it's time to release resources or shut down the whole system.
Speaking of shutdown: Have you ever noticed that program shutdown is inherently a deeply mysterious time? Getting orderly shutdown right requires great care, and the major root cause is unstructured lifetimes: the need to carefully clean up objects whose lifetimes are not deterministically nested and that might depend on each other. For example, if we have an open SQLConnection object, on the one hand we must be sure to Close() or Dispose() it before the program exits; but on the other hand, we can't do that while any other part of the program might still need to use it. The system usually does the heavy lifting for us for a few well-known global facilities like console I/O, but we have to worry about this ourselves for everything else.
This isn't to say that unstructured lifetimes shouldn't be used; clearly, they're frequently necessary. But unstructured lifetimes shouldn't be the default, and should be replaced by structured lifetimes wherever possible. Managing nondeterministic object lifetimes can be hard enough in sequential code, and is more complex still in concurrent code.
Concurrency Runtime (CRT): The Resource Manager
Managing processors, memory, and other resources
SIMD Parallism using Array Notation for C/C++
Parallel Composer 2011 brings array expressions to C and C++dBug: A C/C++ Tool for Systematic Evaluation of Distributed Systems
Array Building Blocks: A Flexible Parallel Programming Model for Multicore and Many-Core Architectures
- Quick Evaluation Guide: Locate a Hotspot and Optimize It
- Quick Evaluation Guide: Eliminate Memory Errors and Improve Program Stability
- Quick Evaluation Guides: Optimize an Existing Program by Introducing Parallelism
- Case Study RTT: Driving Automotive Design Innovation, Efficiency, and Cost Savings
- Case Study Sentinelle: Achieving Early and Accurate Detection of Cancer
- Intel Parallel Studio; Download the free eval today!
- Parallelism Breakthrough Video Series; Watch and learn more about Intel® Parallel Studio
- 2009 Intel Software Webinar Series; View On-Demand webinars
- Coding for Multi-core Processes; Intel® Compiler Pro eBook
- Performance Through Parallelism; Intel® Tuning for Vista eBook
- Intel® Software Network; Connect with developers and Intel engineers
-
September 13, 2010
The goal of the Third International Workshop on Parallel Programming Models and Systems Software for High-End Computing is to bring together researchers and practitioners in parallel programming models and systems software for high-end computing architectures. Please join us in a discussion of new ideas, experiences, and the latest trends in these areas at the workshop.
Parallel Architectures and Compilation Techniques
-
September 11-15, 2010
The International Conference on Parallel Architectures and Compilation Techniques (PACT) is a premier international forum for the presentation of research results in parallel computing. As a multi-disciplinary conference that brings together researchers from the hardware and software areas, PACT brings together researchers and practitioners in parallel systems to present ground-breaking research related to parallel systems ranging across instruction-level parallelism, thread-level parallelism, multiprocessor parallelism and large scale systems.
IDF2010
-
September 13-15, 2010
The Intel Developer Forum 2010 is your opportunity to collaborate with thousands of key industry players. Hear from more than 150 leading technology companies from around the world. Ask questions, get answers, experience live demonstrations, and more. Between the highly informative Keynotes, Technology and Industry Insights, Intel Fellows Live & Uncensored and Technical Sessions (including lectures, interactive panels, hands-on labs and Hot Topic Q&As), this year's IDF has everything you need to stay on top of the latest technology trends.
-
February 12-16, 2011
The Symposium on Principles and Practice of Parallel Programming is a forum for leading work on all aspects of parallel programming, including foundational and theoretical aspects, techniques, tools, and practical experiences. In the context of the symposium, "parallel programming" encompasses work on concurrent and parallel systems (multicore, multithreaded, heterogeneous, clustered systems, distributed systems, and large scale machines). Given the rise of parallel architectures into the consumer market (desktops, laptops, and mobile devices), PPoPP is particularly interested in work that addresses new parallel workloads, techniques and tools that attempt to improve the productivity of parallel programming, and work towards improved synergy with such emerging architectures.


