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.

5 comments

Top
anonymous's picture

The functional programming language Haskell has the "Maybe" monad which can be "Just x" or "Nothing". I'm not sure anything really useful can be done by code in C++/Java if information about an exception was captured and stored instead of "Nothing".

If it is possible to design value_or_error such that whenever it participates in a computation, it propagates itself. For example, evaluating a function f : T -&gt; U on a value_or_error&lt;T&gt; should yield a value_or_error&lt;U&gt;. Basically the idea is to not have to check for error at every step of the computation and only examine the final result after all parallel computations have finished.

Using your NaN analogy, this would correspond to declaring that any expression involving an NaN value will result in an NaN.

Arch D. Robison (Intel)'s picture

Thanks for the pointer to the Boost optional<T>. It sounds a lot like the .NET Nullable (http://msdn2.microsoft.com/en-us/library/1t3y8s4s(VS.80).aspx) type. It's very similar to what I had in mind, except for exception semantics. optional<T> propgates exceptions from T(), whereas value_or_error captures the exception.

anonymous's picture

The idea is elaborated in boost, please see
http://boost.org/libs/optional/doc/optional.html

Arch D. Robison (Intel)'s picture

Good point. We ought to retain some information about the cause of the exception. Java has an advantage here for implementing this feature because everything is passed by pointer. With C++, we need to copy the exception, and there's no standard way to clone an exception object, though I believe the subject has come up on the C++ 200x committee.

If the exception is derived from std::exception, we could record the value of std::exception::what()and its typeid. The ISO C++ standard seems silent on the lifetime of the C-style string returned by std::exception::what(). I'm wondering if it's safe to just remember the pointer and use it later?

We should avoid dynamic allocation of memory to do this recording - out of memory is a typical cause of an exception.

anonymous's picture

this seems neat to me as a pragmatic solution for the concurrent scenario ;)

my only suggestion is that rather than a 'mark as error' you could store the original exception (in Java at least, I'm not sure how this works in c++), and have the exception that is thrown on access chain the original exception

that way you don't lose the ability to determine where something went wrong post-mortem

Add a Comment

Have a technical question? Visit our forums. Have site or software product issues? Contact support.