C11/C++11 weak memory benchmarks

Question

Can anyone point to benchmark results comparing performance of C11/C++11 code using relaxed atomic operations (particularly memory_order_release and memory_order_acquire, but also memory_order_consume and memory_order_relaxed) versus the default memory_order_seq_cst? All architectures are of interest. Thanks in advance.

Minority

I daresay that performance does not matter so much as does correctness. You should use memory ordering to the semantics of your loads and stores correct, not use something different because it is maybe 3 cycles faster. OTOH, if you have no clue, stay with the default, which may be slightly slower (often isn't even), but is guaranteed to be correct. There's nothing more of a nightmare than "optimized" multithreaded code that's incorrect. – Ovi

The default sequentially consistent memory ordering is stricter than any of the others, so performance is the only reason to use weaker orderings. I know how to reason about correctness in either case, but the reasoning is more difficult for weaker orderings. In any event, it's not a question of 3 cycles; even on an i7, flushing the store buffer is typically tens of cycles (perhaps much more on older processors), and the difference between seq_cst and consume on ARM is much greater still. – Minority

It is hardly possible to get meaningful results from a benchmark. A single load/store is hardly measurable in a reliable way. Loading and storing the same value (or a set of values) many times without synchronization will only benchmark cache thrashing, but not the actual operation. Synchronizing will measure the synchronization primitive, which is ~1000X more expensive. That, and you really have no choice but to write correct code. If you need happens-before guarantee on some data, you cannot leave it out just because it would be faster. – Ovi

@Ovi there's nothing wrong with wanting to understand the performance of different approaches. That does not imply that you plan to sacrifice correctness. – Thurnau

@jalf: That is of course correct. Which still leaves the problem that it's pretty much impossible to measure this. How do you e.g. measure the impact of instruction reordering? Benchmarking such is simply not meaningful for a real program (only way I could imagine would be to use an existing real program, such as a database, and recompile this with stricter semantics, and stress-test / benchmark the application, and even then it's more than questionable whether this translates to a different application, since it may have entirely different access patterns). – Ovi

@Ovi is right that just banging on an atomic with multiple threads would just thrash the cache. But there are examples that don't thrash the cache. For example, I seem to recall that rewriting spinlock release to use a simple write on x86 (which is a release) instead of an interlocked store resulted in a measurable performance increase for Linux. Another example that I would expect to be measurable would traversing lockfree linked lists using consume on ARM. – Minority

In this talk of facebook engineering about the implementation of a atomic hashmap in their open-source library folly, they claim that they gained a performance boost of ~50% by using relaxed semantics. Nevertheless, they are also doing some other hacking, still it's an interesting talk and worth watching. facebook.com/… – Outspan

They're however using compare_exchange_strong as well as release in the critical part, not relaxed. Which is why it works. They're not just using relaxed. – Ovi

Checking the code, they are using both. github.com/facebook/folly/blob/master/folly/AtomicHashMap-inl.h – Outspan

The relevant slide is at the end of the talk, where the replaced a seq_cst load in find with an acquire load and got a 65% performance increase. This perf presumably came not at the instruction level (since any reasonable compiler for x86 will compile a load in the same way), but because the compiler was able to reorder things around it. This is a great example of why you need real benchmarks and not just cycle counts. – Minority

@Ovi sure, meaningfully benchmarking something like this is very very tricky. I'm just pointing out that asking about, and being interested in understanding, the performance aspects as well is certainly not irrelevant. – Thurnau

Answer 1

I did a bit of benchmarking on ARMv7, see https://github.com/reinhrst/ARMBarriers for the report, the slides for my talk at EuroLLVM, and the seqlock code I used.

Short story: in the seqlock code, the Acquire/Release function was about 40% faster than the sequentially consistent version.

Caper

The article is very nice. On the other hand, it seems to argue that the gap between sc and acq-rel is (at least in this example) purely due to lazy compilation, since with your proposed compiler passes in place, the gap above is essentially eliminated, right? – Minority

It's been a while since I dove into this, but as far as I recall the gap between sc and acq-rel is (in this example) due to missing compiler optimisations (before the patch mentioned in the GitHub repo was added to llvm), because in this example, in the ARM memory model, acq-rel gives you the same guarantees as sc (again: in the provided example, in the ARM memory model, pre-llvm-patch). In no way I'm trying to argue that sc and acq-rel should be equally fast in the general case. – Caper

Answer 2

This might not be the best solution but so far I have been using CDSChecker for some bench-marking in one of my projects. I have not yet used it on complete programs but more just on independent units.

Rescissory

CDSChecker isn't designed for benchmarking, just for exhaustive testing for correctness. CDSChecker provides no information about what the performance of your code will be. – Dyne

Answer 3

For a particular chunk of code (a work-stealing dequeue), I found a very nice paper that benchmarks a C11 version with weak atomics, with sc-atomics only, hand-optimized assembly, and an incorrect version using fully relaxed atomics. (By coincidence, a bug was later found in the C11 version by the aforementioned CDSChecker.) Similar examples are welcome.

Minority

Answer 4

The question as such doesn't make sense, and it's important to understand why.

An atomic operation is just a simple operation on a scalar object except that it can be used for inter thread communication; the ordering only affects what is guaranteed for other memory locations.

[Note: the standard text doesn't formally guarantees that, but it's meant to guarantee that, and a consistent approach to C/C++ thread semantics must be based on that.]

You can compare the speed of a multiplication and a cosine, but not compare the cost of outputting "hello world" and flushing cout. The flush on a stream or file doesn't have an intrinsic price tag: it relates to other operations.

You can't compare the speed of an operation that blocks until some previous operation is complete with one that doesn't.

Also, you can't benchmark in a vacuum. You need some workload, a pattern of operations.

You would need to learn a lot on modern CPU design, and by modern I mean anything that was invented in the last two decades. You have to have at least some idea of the complexity of a real CPU and the way it runs code, how multi core operates, and the general principles of memory caches, to even dream of designing a useful benchmark in the abstract.

Or, you could just write your program, and profile it to see if there is really an issue with atomic operations.

Bray