constructive nonconformist

Party Like It's 1993

Revised editions of two significant programming books are due this May.

• The C++ Programming Language, 4th Edition (updated for C++11)


• Advanced Programming in the UNIX Environment, 3rd Edition

Takes me back to 1993 — in a good way.

Defensive Threading

Designing and writing multi-threaded code is hard. Threading adds a debilitating amount of complexity to the Von Neumann architecture and, despite 50+ years of theory and implementation, the threading support in most programming languages is low level, the equivalent of malloc rather than GC managed memory.

If you’re a developer and you approach threading with trepidation then here are some experience tested guidelines and techniques that I try to follow. The overall strategy is to reduce the surface area for bugs and to increase the maintainability of the code. These are not hard and fast rules. It’s important to be pragmatic and to adjust for the specific situation.

But first, please note that I’m no expert. I’m sharing what I’ve learned and I know I’m not done learning. If this post helps you, I want to know. If you think I’ve got something wrong, I want to know. Thank you.

Avoid sharing data.

Sharing data between threads is the most common source of threading bugs. By definition many of the nastiest threading bugs can only occur when data is shared. Safely sharing data requires synchronization either in the form of a lock or an atomic primitive. Getting the synchronization right is not always easy. Avoid sharing data and the threading bug potential goes way down. As a bonus, the code can potentially run faster because the possibility of synchronization contention is eliminated.

It may seem that without sharing data, threads are pretty useless. Not so. But this is a case where you need to be willing and able to trade space for speed and safety. Give a thread it’s own private copy of everything it may need, let the thread run to completion (‘wait’ or ‘join’ on the thread), and then collect the results of it’s computations.

Avoid sharing logging.

Logging is data. See above. Sometimes the messages generated on a thread need to be reported more or less immediately. But if a delay can be tolerated, a thread can have it’s own private log that gets collected after the thread has run to completion.

When you must share, prefer lighter weight synchronization mechanisms.

I didn’t understand lock-free threading until I understood that lock-free doesn’t mean no synchronization mechanisms at all.

Under Windows the Interlocked* APIs represent atomic operations implemented by specific processor instructions. Critical sections are implemented via the interlocked functions. The interlocked functions and the critical section on Windows and the equivalent on other platforms are generally the lightest weigh synchronization mechanisms.

Technically the interlocked functions are not locks, they are hardware implemented primitives. But colloquially developers will speak of ‘locks’ and mean the whole set of synchronization mechanisms, hence my confusion over lock-free threading.

Having said that I will now forgo rigor and refer to all synchronization mechanisms as ‘locks’ because it’s pithier.

Use the smallest number of locks possible.

Don’t treat locks like magic pixie dust and sprinkle them everywhere. Synchronization locks provide safety but at a cost in performance and a greater potential for bugs. Yes, it’s kind of paradoxical.

Hold locks for the shortest length of time possible.

A critical section, for an example, allows only one thread to enter a section of code at a time. The longer the execution time of the section, the longer the window for other threads to box car up waiting for entry.

If there are values that can be computed before entering a critical section, do so. Only the statements that absolutely must be protected should be within the section.

Sometimes a value needs to be retrieved from a synchronized source, used as part of a computation, and a product of the computation needs to be stored to a synchronized destination. If the whole operation does not need to be atomic then, despite the desire to minimize locks, two independent synchronization locks could be better than one. Why? Because the source and destination are decoupled and the combined lock hold time is reduced because only the source read and the destination write are covered.

Be DRY - Don’t Repeat Yourself.

Always a good policy, being DRY has special importance with threaded code. There should be only one expression or implementation of any given synchronized operation. Every thread should be executing the same code to ensure that the operation is performed consistently.

Design to ensure that every acquisition of a lock is balanced by a release of the lock.

Take advantage of the RAII pattern or the dispose pattern or whatever is appropriate to the language and platform. Don’t rely on the developer (even when the developer is yourself) to remember to explicitly add every release for every acquisition.

Finish the threads you start.

Don’t fire and forget. Wait or join and clean up your threads and their resources.

Don’t let threads you created outlive the primary thread in the process. Some platforms have the unfortunate design of performing runtime set up and initialization, calling the the program code, and then tearing down and de-initializing on the primary thread. Other threads that may still be running after the primary thread exits may fail when the runtime is pulled out from underneath them.

Don’t kill a thread. That will leave data in an undeterminable state. If appropriate implement a way to signal your thread to finish.

Don’t get focused on locking the data when it’s the operation that needs to be synchronized.

It’s easy to get fixated on the shared data but often times the design is better served by paying more attention to the shared operations.

Avoid nested locks.

Acquiring lock A and then lock B in one part of the code and elsewhere acquiring lock B and then lock A is asking for a deadlock. No-one sets out to write a deadlock. But sometimes the code isn’t exactly what was intended or a change is made and the impact of the change isn’t fully understood. If locks are never nested then the potential for this kind of deadlock just doesn’t exist.

If locks must be nested then alway acquire the locks in the same order and always release the locks in the same opposite order. And be DRY about it.

Avoid method calls within a lock.

This may seem aggressively limiting but method implementations can change and introduce new issues like unwanted nested locks. Keeping method calls out of the scope of locks reduces coupling and the potential for deleterious side effects.

(I think of this one as following in the spirit of LoD.)

Encapsulate intermediate values.

Avoid creating inconsistent state in shared data. Operations that create intermediate values shouldn’t be performed in situ on shared objects or data structures. Use local temporaries for intermediate values. Only update the shared data with the end products of a operation.

Be careful of using the double check lock pattern.

It’s a wonderful idea that’s so clever that’s it’s broken in many languages and runtime platforms.

Where the DCLP is not just inherently broken and can be used, it still needs to be implemented correctly. Mark the variable under test as ‘volatile’ (or the closest equivalent) so that the language compiler doesn’t optimize away one of the two checks. Don’t operate directly on the variable under test. Use a temporary to hold intermediate values and wait to assign to the variable under test until the new state is fully computed.

The DCLP is often used for one time or rare initializations.

Don’t lock the ‘this’ pointer.

If there are member functions of an object that need to synchronize, create a private member variable that is used as the lock target rather than locking on ‘this’. In addition to encapsulating the locking, using a private member guards against potential issues where a framework, library, or runtime may be performing synchronization by using the ‘this’ pointer.

Explain your code.

Leave comments for yourself and the next person.

Strive to make the design grokkable.

The original design and implementation can be bug free but if the design is hard to understand and follow, bugs can be introduced in maintenance cycles. Even if you are the only developer who may ever touch the code, remember that the details of the design that are so crystal clear in your mind today will get supplanted by tomorrow’s events and miscellany like … Squirrel!

Encapsulating a Thread in a C++ Object

It’s a frequently asked question in C++ forums and newsgroups. Try to create a thread and pass an instance member function of a C++ class as the thread start routine and the compiler balks. What is the compiler complaining about? How can a thread be run within an instance of a class?

Block Comment Quick Trick

Sometimes it’s useful to be able to quickly add or remove a section of code. Some languages have preprocessors that can help but here’s a ‘stupid’ comment trick to achieve the same.

C-style syntax languages (e.g. C, C++, Java, JavaScript, C#) support single line comments with ‘//’ and block comments with a ‘/*’ and ‘*/’ pair. The trick is that single line comments can be used to comment out block comments.

So here’s a commented out code block:

/*

    var lorem = 'ipsum';

    ...

//*/



Note the ‘//’ for a single line comment in front of the block comment terminator. The block can be uncommented with a single keystroke, by adding a ‘/’ before the block start.

//*

    var lorem = 'ipsum';

    ...

//*/



Too Many Abstractions?

I want to tell a story about a software engineer named Bob. Bob is not his real name.¹ Bob is not even a real individual. He’s a composite and a straw man.

Bob the software engineer says “there’s too many abstractions.” It’s a common criticism from Bob when he reviews code or code designs. He’s not applying a YAGNI or KISS principle. He’s not diagnosing an incorrect or poorly implemented abstraction. It’s something else.

Bob is a veteran software engineer. His formative professional experience was probably writing C code but he has long since transitioned to C++. He thinks he made the jump pretty well. He uses classes and considers his code to be objected-oriented. He appreciates the ability of a C++ class to colocate data and the functions that operate on the data.

If you ask Bob what he means by ‘too many abstractions’, he’ll explain that every abstraction has a cost. More abstractions mean more classes and more function calls and more overhead. He doesn’t like adaptors, decorators, or functors. He believes deep layers of abstraction are inherently too expensive.

This ‘abstraction is too expensive’ idea is curious for a software engineer engaged in true object-oriented design because object-oriented design fundamentally assumes that abstraction is cheap.

Unsurprisingly Bob doesn’t write object-oriented code. What he writes is tightly coupled procedural code wrapped in monolithic class definitions and he doesn’t understand the difference. This is not an OO versus procedural argument. Bob is creating bad code that abuses multiple paradigms. The point is he believes he is writing object-oriented code, yet he can’t grasp and truly leverage OOP because he can’t get pass the overhead issue.

OOP isn’t about optimizing for the machine; it’s about optimizing the construction and maintenance of the software. Quality and time-to-market are prioritized ahead of raw execution speed. Software that’s super fast but wrong and delivered late is worthless.

A good object-oriented design is an investment. The return on that investment is flexible, adaptable software that’s easy to repair, refactor, and extend.

OOP is not perfect and it’s not the only way to achieve adaptable software. But it is Bob’s professed paradigm and he’s failing to realize some of OOP’s most significant potential benefits. In essence Bob is attempting to practice OOP without embracing objects.

¹How did I pick the name Bob? Some strange synaptic cross between Microsoft Bob and Bob the Builder.

Speaking of Microsoft and children’s programming: Do the rolling green hills in Windows XP’s default desktop background image remind anyone else of Teletubbies?

RAII in C++

[This post was revised on May 23, 2005.]

Resource Acquisition Is Initialization
I first learned about the “Resource acquisition is initialization” (RAII) technique from Bjarne Stroustrup’s The C++ Programming Language (3rd Edition). RAII changed the way I write C++ code.

The meaning behind the phrase “Resource acquisition is initialization” is that acquiring a resource is performed by constructing an appropriate object. The object manages the lifetime of the resource and the object’s destructor ensures the resource is ‘un-acquired’.

A resource, for the purposes of this discussion, is something that must be explicitly acquired and released. For example, heap memory acquired by newand released by delete is a resource.

Managing the lifetime of a resource can be difficult. RAII’s power and simplicity comes from making managing the lifetime of a resource the same as managing the lifetime of an object. Managing object lifetimes is comparatively easy. The language is designed for managing objects and RAII objects are often local automatics.

Deterministic Destruction
C++ guarantees an object’s destructor will be executed when the object either goes out of scope or is deleted. Because destruction depends on either scope or when delete is invoked, it can be known when an object will be destructed. This is termed “deterministic destruction.”

Not all languages provide deterministic destruction and it’s usually essential for RAII. Why? Resources are limited and have temporal constraints. A resource that is both scarce and in high demand can’t be lazily released.

Without deterministic destruction an object that wraps a resource should expose a cleanup method and consumers of the object are responsible for calling that method. This is a very useful pattern (sometimes referred to as the “dispose pattern”) but it isn’t RAII and it introduces problems that RAII doesn’t suffer. First, because cleanup is separated from destruction, the object must guard against cleanup being performed more than once and against other methods being called after cleanup has been performed. Second, the abstraction created by the class type is compromised by requiring external knowledge that something within needs cleanup.

One-Stage Versus Two-Stage Construction
The Microsoft Foundation Class Library (MFC) is heavily invested in two-stage construction. Two-stage construction is when an object’s constructor does little or nothing and a consumer of the object must call a separate initialization method before the object is usable.

MFC uses two-stage construction because MFC was designed before exceptions became a standard part of the language. Prior to exceptions there was no mechanism for a constructor to signal a failure. Therefore it was prudent to never perform an action that could fail in a constructor.

C++ was standardized six years ago and Standard C++ includes exceptions and defines semantics for constructors that throw.

I favor one-stage construction. I want to make my job easier. I want to minimize the number of methods on a class and I want to minimize the opportunities for silly mistakes like forgetting to call an initialization method.

Two-stage done right would guard against attempts to use the object in an un-initialized state. (I want my objects to tell me when I’m being a bozo.) But guarding against un-initialized use adds complexity. (MFC classes don’t guard but also generally have no encapsulation.)

With one-stage construction the constructor either successfully creates and fully initializes the object or there is no object. It’s not possible to have an object (that enforces invariants) in an unusable state.

Exceptions And Exception Safety
There are some who will question how one-stage construction can make things easier since it depends on using exceptions and exceptions are notoriously dangerous when thrown through code that is not exception safe.

I have a short smart-alecky answer: Exception unsafe code hurts, so stop writing it.

A longer answer is probably worthy of its own blog post but the essential issue is that exceptions contaminate a codebase. If the potential for exceptions exists in a codebase (in the present or in the future) it’s prudent to assume that an exception could happen nearly anywhere and nearly all code should be written to defend against exceptions.

Exceptions are not evil and there are plenty of ways that don’t involve exceptions to create buggy leaky code. However the presence of exceptions does impact how code should be written. The good news is that most of the techniques for writing exception safe code are good practices in their own right. Which comes back to the topic at hand: RAII is indispensable for ensuring resources are not leaked when an exception is thrown and the stack is unwound.

RAII is DRY
RAII supports the DRY principle. DRY stands for “Don’t Repeat Yourself.” (See my previous post: constructive nonconformist: A Single Point of Correctness.)

An RAII class provides a single expression of how to correctly acquire and release a given resource. Creating an instance of an RAII object can replace copying and pasting boiler plate code for acquisition and release. In this way RAII protects against programmer error and reduces code clutter.

RAII Example
RAII may sound great in concept but “the proof of the pudding is in the eating.” So the following is a concrete example of using RAII.

To support critical sections, the Microsoft Windows Win32 API includes a specialized critical section synchronization object. A CRITICAL_SECTION struct must be initialized before use and deleted after use by the InitializeCriticalSection() and DeleteCriticalSection() APIs respectively. This fits the resource usage pattern of an RAII class.

Here’s an RAII class for wrapping a CRITICAL_SECTION:

class CriticalSection
{
public:
    CriticalSection()
        { ::InitializeCriticalSection(&m_rep); }
    ~CriticalSection()
        { ::DeleteCriticalSection(&m_rep); }
    
    void Enter()
        { ::EnterCriticalSection(&m_rep); }
    void Leave()
        { ::LeaveCriticalSection(&m_rep); }
    
private:
    // copy ops are private to prevent copying
    CriticalSection(const CriticalSection&);
    CriticalSection& operator=(const CriticalSection&);
    
    CRITICAL_SECTION m_rep;
};


Copying a CriticalSection object doesn’t make sense so copying is disallowed. See constructive nonconformist: Disallowing Copying in a C++ Class for details.

Another RAII class can be used to create a critical section synchronization lock.

class CSLock
{
public:
    CSLock(CriticalSection& a_section)
        : m_section(a_section) { m_section.Enter(); }
    ~CSLock()
        { m_section.Leave(); }
    
private:
    // copy ops are private to prevent copying
    CSLock(const CSLock&);
    CSLock& operator=(const CSLock&);
    
    CriticalSection& m_section;
};


Together the CriticalSection and CSLock classes can be used to synchronize thread access to the state of an object:

class Example
{
public:
    bool Process( … );
    
    …
    
private:
    CriticalSection m_criticalsection;
    
    …
};
    
bool Example::Process( … )
{
    CSLock lock(m_critsection);
    
    // do some stuff
    …
}


Only one thread at a time may acquire a critical section object. A second thread entering Example::Process() will block on the construction of the lock object until the first thread exits the function. If an exception is thrown in or through Example::Process() the lock object will still release.

By wrapping the raw Win32 structs and APIs, the RAII classes in this example allow coding at a higher level of abstraction.

Related Reading
Programming with Exceptions By Bjarne Stroustrup
Stroustrup: C++ Style and Technique FAQ: Why doesn’t C++ provide a “finally” construct?
Abstraction and Efficiency, A Conversation with Bjarne Stroustrup, Part III

Disallowing Copying in a C++ Class

How would you design a C++ class so that objects of that class type can’t be copied? Why would you want objects that can’t be copied?

I have asked many people those two questions. For a long time those two questions were part of my standard repertoire of interview questions for candidates for positions requiring knowledge of C++. Most of the people I asked did not have ready answers. That was okay. The intent was to see how the candidate would approach solving the problem and how much knowledge of construction and assignment in C++ the candidate possessed.

How To
To prevent copying, a C++ class needs to declare a copy constructor and an assignment operator (operator=). At face value it’s counter-intuitive. To prevent copying, declare a copy constructor?

By default C++ allows copying. For any class that doesn’t declare its own, the C++ compiler will provide a default copy constructor and a default assignment operator. No good for a ‘no copy’ class.

Declare a copy constructor and an assignment operator so the compiler won’t provide the default versions but make both methods private and don’t provide implementations.

If an external non-friend function or class method calls the copy constructor or the assignment operator, compilation will fail because the methods are private. Friends and methods of the same class can call privates but compilation will still fail because the copy constructor and assignment operator are declared but not defined. (Intentionally declaring but not defining a method is sometimes termed “poisoning a method.”)

Example
class NoCopy
{
public:
    …
private:
    // copy ops are private to prevent copying
    NoCopy(const NoCopy&); // no implementation
    NoCopy& operator=(const NoCopy&); // no implementation
    …
};

Why
Why would copying be disallowed? The motivations can be generalized as either logical or pragmatic.

Logical is when copying doesn’t make sense for the class type or model.

A class type that implements the Singleton design pattern is an example. A singleton should disallow copying by definition.

Another example might be a class type that wraps an external resource that has no copy semantics. For instance a class designer could decide that it is not meaningful for an object that wraps a thread to support copying.

A pragmatic motivation is when copy support doesn’t violate the class type’s logic but a decision is made to not allow copying anyway. This could be an exercise of the YAGNI principle. Or it could be based on knowledge that a copy operation for the given class type is very expensive and should be prohibited.

Class Design
A C++ class design is not complete if copying hasn’t been considered. Do the default copy constructor and assignment operator provide the correct copy behavior? Probably not if the class has any data members that are pointers. And if not, decide to either implement correct copying or disallow copying. Don’t leave a time bomb for the next programmer.

Unlike C++, Java requires an explicit decision to implement copying rather than providing a default that can be wrong. But objects in Java are all references and the ability to copy is actually rarely needed.

The Java experience can be emulated in C++ by preferring to pass objects by reference and const reference. Objects that are never passed by value can pragmatically disallow copying.

XML on Mac OS X

Mac OS X 10.3 (‘Panther’) includes the Gnome libxml2 library.

Related Reading
Mac OS X: System Overview: Application Technologies
The XML C parser and toolkit of Gnome