Measuring the Performance of Deterministic Exceptions

I have always been interested in Zero-Overhead Deterministic Exceptions from P0709, as they promised a nicer implementation model and they are much easier to integrate into JIT-compiled code. Some people forbid regular C++ exceptions, due to code size and performance concerns, which are concerns that P0709 explicitly wants to address. Unfortunately, there was no implementation available. But now, with LLMs, doing this kind of experiment is much more tractable. I basically gave the official P0709 specification to an LLM, and it built a first prototype in one shot. Admittedly my initial enthusiasm cooled down a bit after I found a lot of problems and corner cases, but after about one day of work I was able to build a reasonable prototype, which is something that would easily have taken me weeks or even months in the past. I tested it with complex code, and it handled everything fine, but note that it is still not production ready (e.g., Itanium ABI only).

That prototype now allows us to quantify the differences between exception implementations. P0709 describes two ways to implement them: Either pass a hidden pointer to an error state to all functions that are marked with throws (we call this strategy pointer here), or use the carry bit to indicate errors and pass the error itself in registers if the bit is set (we call this strategy carry). That is a very nifty approach suggested by Herb Sutter, but it somewhat clashes with some of the function epilogues (e.g., on Windows), and such a flag is not available on all platforms. We thus introduced a third variant register here that simply uses another unused caller-saved register as an error indicator, which is more portable. The classic C++ exception handling mechanism we call dynamic.

Microbenchmarks

We first run some microbenchmarks to see the overall effects. These over-emphasize the differences as the benchmarks basically do nothing besides function calls (ns per outer call):

Test	failures	dynamic	pointer	register	carry
int through 8 calls	0%	6.02	6.09	6.08	6.16
	1%	17.5	7.10	6.31	6.33
	10%	101	7.59	6.85	6.88
	50%	467	9.48	9.26	9.11
forwarding chain, 8 tail calls	0%	1.54	1.34	1.52	1.59
	50%	188	4.74	4.31	4.28
void through 4 calls	0%	3.00	3.09	3.05	3.06
	1%	9.82	3.33	3.32	3.31
16-byte struct (two registers)	0%	3.01	3.24	3.06	3.06
32-byte struct in memory	0%	5.40	6.06	5.75	5.44
	1%	11.3	6.03	5.60	5.43
	50%	314	6.26	5.93	5.92
pointer, single call	0%	0.75	0.95	0.75	0.75
	50%	188	3.66	3.29	3.08

We notice several things. First, the pointer strategy often has noticeable overhead due to additional memory instructions, and is inferior to the other two. register and carry are nearly identical, which, given the fragility of the carry approach, means that register seems to be the preferred choice. Compared to classical C++ exceptions, performance of register is within 1-2% on the happy path, where no exception occurs, and it is dramatically faster, up to orders of magnitude, if exceptions indeed occur.

A more realistic workload

These numbers over-inflate the differences because the functions do so little work. As a more plausible workload, we use RapidJSON and benchmark the performance on the nativejson-benchmark, optionally corrupting some inputs to trigger exceptions. RapidJSON can be configured to report failures by error codes instead of exceptions; we call that strategy codes here.

The full results are here; we show a selection below. What the numbers basically show is 1) deterministic exceptions with the register strategy have the same performance and the same code sizes as explicit error codes, 2) performance differences from traditional C++ exceptions are largely within the noise even on the happy path, and 3) in the case of errors they are vastly superior to traditional C++ exceptions.

Happy path: SAX parsing

MB/s, higher is better, best of 5 runs; in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
canada.json	1635.8	1606.6 (-1.8%)	1665.1 (+1.8%)	1606.1 (-1.8%)	1603.3 (-2.0%)
citm_catalog.json	2212.7	2216.0 (+0.1%)	2356.3 (+6.5%)	2206.3 (-0.3%)	2341.5 (+5.8%)
twitter.json	1365.2	1376.5 (+0.8%)	1425.4 (+4.4%)	1377.5 (+0.9%)	1472.0 (+7.8%)

Happy path: retired instructions per parse

Instructions (perf stat), lower is better; in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
sax canada.json	49555378	49903680 (+0.7%)	50294221 (+1.5%)	50850829 (+2.6%)	50738702 (+2.4%)
sax citm_catalog.json	20552806	20212949 (-1.7%)	20761272 (+1.0%)	20802928 (+1.2%)	20730816 (+0.9%)
sax twitter.json	11758968	11547972 (-1.8%)	11799096 (+0.3%)	11850736 (+0.8%)	11813765 (+0.5%)

Errors: small documents, a fraction of them corrupted

ns per document, lower is better, best of 5 runs; in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
0%	1726.1	1692.2 (-2.0%)	1729.3 (+0.2%)	1720.5 (-0.3%)	1721.0 (-0.3%)
1%	1707.3	1812.3 (+6.2%)	1703.3 (-0.2%)	1707.7 (+0.0%)	1713.9 (+0.4%)
10%	1600.8	1848.9 (+15.5%)	1597.3 (-0.2%)	1598.3 (-0.2%)	1614.3 (+0.8%)
50%	1256.5	1895.7 (+50.9%)	1263.6 (+0.6%)	1264.2 (+0.6%)	1275.3 (+1.5%)
100%	868.6	1934.7 (+122.7%)	871.8 (+0.4%)	869.3 (+0.1%)	882.1 (+1.6%)

Size of the parser

Bytes of all GenericReader functions, GenericDocument::ParseStream and parseSAX (into which parts of the parser are inlined); in parentheses: change relative to codes.

	codes	dynamic	pointer	register	carry
code	17191	18162 (+5.6%)	17540 (+2.0%)	17204 (+0.1%)	17289 (+0.6%)
unwind info	1292	1500 (+16.1%)	1340 (+3.7%)	1268 (-1.9%)	1248 (-3.4%)
exception tables	0	388	0	0	0
total	18483	20050 (+8.5%)	18880 (+2.1%)	18472 (-0.1%)	18537 (+0.3%)

Conclusion

Given that “exceptions” might not always be that exceptional (e.g., when parsing large amounts of user input), deterministic exceptions indeed seem to be a very good idea, and P0709 indeed should be adopted by the C++ standard. Not that this is likely to happen, given the lack of progress on this front, but now we at least have numbers to talk about.

Safe Optimistic Lock Coupling

As the number of CPU cores keeps growing, the scalability of concurrent data structures becomes increasingly important. A data structure that works fine on 4 cores can become a bottleneck on 32, not because of algorithmic limitations, but because of how it synchronizes access.

We illustrate that with a simple binary tree. Usually these data structures are protected by some kind of lock:

struct Node {
   mutex lock;
   
   key_type key;
   value_type value;
   Node* left, *right;
};
struct Tree {
   mutex lock;
   Node* root;
};

When searching a value, we can traverse the data structure, lock the parts of the data we are currently touching, and release locks when we are done (“lock coupling”):

option<value_type> Tree::lookup(key_type key) {
   lock.lock_shared();
   mutex* currentLock = &lock;
   Node* iter = root;
   option<value_type> result;
   while (iter) {
      if (key == iter->key) {
         result = iter->value;
         break;
      }
      Node* next = (key < iter->key) ? iter->left : iter->right;
      if (next) next->lock.lock_shared();
      currentLock->unlock();
      currentLock = next ? &next->lock : nullptr;
      iter = next;
   }
   currentLock->unlock();
   return result;
}

While conceptually simple, lock coupling has quite poor performance in practice. The problem is that it creates contention on the locks, in particular for the root node. Every lookup goes through the root node, thus the root node is constantly locked and unlocked. While there is no semantic contention between lookups, as all readers can read the root concurrently, there is physical contention on the lock itself, which limits scalability. This can be seen below, with concurrent lookups in a tree of 100,000 elements, executed on a 16-core / 32-thread 9950X3D.

Lookup scalability: no locking vs lock coupling

This contention problem can be solved by using Optimistic Lock Coupling, a synchronization technique where readers do not perform any writes. The key idea here is that writers lock as usual, and increase a version number when they are done updating. Readers read the version number before access, read the elements they are interested in, and then re-check the version number. If the version number changed (or the element is currently locked), the read fails and the reader tries again. In (slightly simplified) code it looks like this:

struct Node {
   version_lock lock;
   
   key_type key;
   value_type value;
   Node* left, *right;
};
struct Tree {
   version_lock lock;
   Node* root;
};

option<value_type> Tree::lookup(key_type key) {
   restart: lock_guard guard = lock.lock_optimistic();
   Node* iter = root;
   if (!guard.validate()) goto restart;
   option<value_type> result;
   while (iter) {
      auto currentKey = iter->key;
      if (!guard.validate()) goto restart;
      if (key == currentKey) {
         auto currentValue = iter->value;
         if (!guard.validate()) goto restart;
         result = currentValue;
         break;
      }
      iter = (key < currentKey) ? iter->left : iter->right;
      if (!guard.validate()) goto restart;
      auto nextGuard = iter->lock.lock_optimistic();
      if (!guard.validate()) goto restart;
      guard = nextGuard;
   }
   return result;
}

It is not that different from the classic lock coupling code above, except that we always have to check for concurrent writes before acting on the read values. The great benefit of this strategy is that the lookup code is purely read-only, which allows it to scale nicely with the number of cores:

Lookup scalability: all strategies

While Optimistic Lock Coupling offers excellent performance, it is a bit dangerous to use. If you act upon a value before validating, you effectively have a race condition in your code. In this small example it is clear when we have to validate, but in complex code fragments it is easy to forget to validate.

The best way to mitigate that is to get compiler support, by encoding the fact that we need to validate in the type system. We can achieve that by representing unvalidated values as a dedicated type, and having only the lock guard expose that value. Conceptually it looks like this (variants that validate multiple values omitted for simplicity):

template <class T>
class unvalidated {
   T value;
   friend class lock_guard;
};
class lock_guard {
   ...
   template <class T>
   optional<T> validate(unvalidated<T> value);
};

Basically we only allow access to the original value by validating, which makes that construct safe. But how do we ensure that code properly wraps everything in unvalidated<T>? By exposing only an optimistic view over the data. Conceptually we do the following:

struct Node {
   class OptimisticView;
   ... // as above
};
template <class T>
class OptimisticPtr
{
   T* rawPtr;
   public:
   // We cannot use operator-> here unfortunately due to C++ constraints
   typename T::OptimisticView data() const { return T::OptimisticView(rawPtr); }
};
// Exposes each member as unvalidated<T> value
class Node::OptimisticView {
   class Node* rawData;
   public:   
   unvalidated<key_type> key() { return unvalidated(atomic_ref(rawData->key).load(memory_order_relaxed)); }
   unvalidated<value_type> value() { return unvalidated(atomic_ref(rawData->value).load(memory_order_relaxed)); }
   unvalidated<OptimisticPtr<Node>> left() { return unvalidated(OptimisticPtr(atomic_ref(rawData->left).load(memory_order_relaxed))); }
   unvalidated<OptimisticPtr<Node>> right() { return unvalidated(OptimisticPtr(atomic_ref(rawData->right).load(memory_order_relaxed))); }
   unvalidated<lock_guard> lock() { return unvalidated(lock_guard(atomic_ref(rawData->lock).load(memory_order_seq_cst))); }
};

Note that the lock() accessor returns an unvalidated<lock_guard>: before we can hand off to the next node’s lock, we must first validate the current guard to ensure we actually read a valid lock. This ensures that lock acquisition itself is part of the validated chain.

With this design, the optimistic code only accesses data via an OptimisticPtr, which makes it impossible to access the data without prior validation. This greatly improves the robustness of the approach. It is a bit annoying that we have to manually implement accessor functions in the OptimisticView, but hopefully the compiler will do that in the future automatically.

Using these abstractions, our lookup code now becomes:

option<value_type> Tree::lookup(key_type key) {
   restart: lock_guard guard = lock.lock_optimistic();
   auto iterOpt = guard.validate(getRootOptimistic());
   if (!iterOpt) goto restart;
   OptimisticPtr<Node> iter = *iterOpt;
   option<value_type> result;
   while (iter) {
      auto currentKey = guard.validate(iter.data().key());
      if (!currentKey) goto restart;
      if (key == *currentKey) {
         auto currentValue = guard.validate(iter.data().value());
         if (!currentValue) goto restart;
         result = *currentValue;
         break;
      }
      auto next = guard.validate((key < *currentKey) ? iter.data().left() : iter.data().right());
      if (!next) goto restart;
      iter = *next;
      auto nextGuard = guard.validate(iter.data().lock());
      if (!nextGuard) goto restart;
      guard = *nextGuard;      
   }
   return result;
}

The code is nearly identical to the unsafe version above, but now it becomes impossible to forget to validate, as the compiler complains otherwise. This makes this highly attractive concurrency paradigm robust and easy to use for all kinds of data structures.

In summary, Optimistic Lock Coupling gives us near-lockfree read scalability while still supporting safe concurrent writes. And by encoding validation requirements in the type system, we get the performance benefits without sacrificing correctness. The compiler catches the mistakes that would otherwise become subtle race conditions at runtime.