rigtorp

You would use one of those approaches:

If you align and pad each slot there won't be any false sharing and the stream prefetcher can kick in if there's only one producer or consumer.

If you use bijective hashing you reduce false sharing without aligning and padding. This can save memory at the expense of the stream prefetcher never kicking in.

Interesting, of course many computations can be expressed as a graph. In the case of the bipartite graph we perform belief propagation on to decode LDPC where is the optimization from the distributive property? The parity matrix would typically be constructed so that there's few subexpression to factor out, to maximize the error correcting properties.

I agree both FFT and belief propagation can be expressed as message passing algorithms.

How is belief propagation used for decoding LDPC codes related to FFT?

I think it will be invalidated due to RFO when the reader reads the write index. Only when multiple readers reads the same cache line without any intervening write will the RFO heuristic be disabled.

It might also be better for performance since the two cores can RFO the buffer pointer cache lines from each other.

There might be an additional optimization in having the writer also cache it's write index on the cache line together with the read index cache. This way the writer would only do writes to the write index cache line. The hardware might be able to optimize this. I wonder how it interacts with UMWAIT on the latest cores.

You might need to add -fno-omit-frame-pointer to help ASAN unwind the stack.

The standard says that a thread must eventually terminate, do an atomic operation or do IO. So the while(lock.exchange(true)); loop is different.

Also keep in mind that C++11 specifies std::mutex::lock() to have acquire semantics and unlock() to have release semantics on the lock object. In order for std::mutex to actually work the reordering of m1.unlock(); m2.lock(); to m2.lock(); m1.unlock(); must be disallowed. But since m1 and m2 are separate objects m1.unlock() has no happens before relationship with m2.lock(). This seems to be a problem in the C++11 memory model. The arguments I have heard from some WG21 people is that there is no problem since transforming a wellformed terminating program into a non-terminating program is not allowed. I can't find the wording in the C++ standard that asserts this. But oh well, it works right now on gcc/llvm/msvc.