Retooling Exceptions for Parallelism

Exception handling is one of the big improvements of C++ over C. C code that checks for erroneous or unusual conditions is littered with tests for those conditions, making programs harder to read. Worse yet, the programmer might forget to check one of those conditions. Exceptions eliminated most of those problems, albeit opened up the new issue of exception safety.

Unfortunately, exceptions as practiced in C++ tend to force sequential execution of code. Consider:

    float a[N];
float b[N];
...
for( int i=0; i<N; ++i )
a[i] = f(b[i]);


If f has no side effects, this loop can be trivially parallelized while retaining the net effect of sequential execution. But if f throws an exception, the loop must terminate early, and is really a while loop as far as parallelization is concerned. Such a loop cannot be parallelized in a scalable way without resorting to speculative parallelization, which tends to be expensive in running time and/or complexity of implementation.
We’ve run into a similar issue while revising TBB’s concurrent_vector<T> while trying to make it completely exception safe. For a concurrent_vector<T> x, the call x.grow_by(n) should append n consecutive elements to x, and return the index of the first element appended. Multiple threads can invoke grow_by in parallel. But what happens if the constructor T() throws an exception for one of the threads? We now have a vector where some elements have been constructed and some have not.

One solution is to make an invocation of grow_by wait until the previous invocation completes. That’s what the 2006 beta version of concurrent_vector<T> did. But that turned out to be a big mistake, because it introduces a badly serializing bottleneck.

The root problem is that exceptions are modeled in C++ as alternative control flow. But another option is to model exceptions as alternative data values. Indeed, this is the way they started out in functional programming languages, e.g. Backus’ FP. A well known example of exceptions as alternative data values are the NaNs in IEEE arithmetic. We should investigate extending this model to C++. For example, we can define a class value_or_error<T> that represents a T or a special error value. Its constructor would never throw an exception. Here’s a sketch of what the class might look like:

    template<typename T>
class value_or_error {
public:
//! True if value() is okay to use
bool is_valid() const;
//! Reference to value. Valid only if is_valid() is true.
T& value() {
if(!is_valid()) throw some-kind-of-exception;
return reference-to-internal-value-of-type-T;
}
//! Const variant of above.
const T& value() const;
//! Default constructor
value_or_error() throw() {
try {
new( &internal-space-for-value ) T;
mark as valid
} catch (...) {
mark as invalid
}
}
~value_or_error() {
if( is_valid() )
&(internal-space-for-value)->~T();
}
... add other appropriate constructors and assignments...
};


A nice feature in this approach is that it automatically converts back to a control-flow exception if the client accesses value() without checking is_valid(). In that respect, it behaves somewhat like a signaling NaN in IEEE arithmetic. Getting back to concurrent_vector<T>, we can advise users to do one of three things:

    1. Ensure that T() does not throw an exception

    1. If not (1), ensure that ~T() works correctly on zeroed memory.

    1. If (1) and (2) are impractical, use a concurrent_vector<value_or_error<T>> instead of a concurrent_vector<T>.



I’d be interested to hear other people’s comments on the value_or_error
approach.

- Arch

For more complete information about compiler optimizations, see our Optimization Notice.