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.

Here's my widely used implementation of this approach in C++: https://github.com/rigtorp/MPMCQueue

That looks like a rewrite of my earlier work: https://rigtorp.se/ringbuffer/

Better to use the Gmail API to incrementally backup your mail: https://github.com/rigtorp/gmbackup

I have a tool that saves each mail as a single file using the Gmail API: https://github.com/rigtorp/gmbackup

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.

I have something similar but in C++: https://github.com/rigtorp/c2clat

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

You're incorrect, garbage collection would be the biggest problem for that use case. You have to be really careful even with your C/C++ code, warming up the branch predictor between packets etc, see my article for some pitfalls: https://rigtorp.se/virtual-memory/

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.

There's even more discussion on the lock memory ordering on Stackoverflow: https://stackoverflow.com/questions/61299704/how-c-standard-...

Taking a lock only needs to be an acquire operation and a compiler barrier for other lock operations. Using seq_cst or acq_rel semantics is stronger than needed. From my reading and discussions with people from WG21 the current argument for why taking a lock only requires acq semantics is that a compiler optimization that transforms a non-deadlocking program into a potentially deadlocking program is not allowed. There's an interesting twitter thread where we discuss this I can't find anymore :(.

Yes that's right!

Well isn't that just a normal lock/mutex of the "lightweight" type (only enter kernel on contention)?

You cannot use that in non-preemptible context.

Deploy to production :).

You can use a model checker that understands C++11 memory model.

His rant only applies to preemptible threads. If you don't have preemptible threads spinlocks works great. The linux kernel uses them in non-preemptible contexts.

It's nonsense to do this when you can be preempted. But you can run one thread per core and avoid preemption. You can tune the linux kernel to avoid almost all preemption, due to TLB shootdowns etc: https://rigtorp.se/low-latency-guide/

I now think it's actually this part of the standard that prevents it: http://eel.is/c++draft/intro.multithread#intro.progress-7

Basically a compiler can not optimize a non-deadlocking program into a potentially deadlocking one.

Yes this re-ordering can cause a deadlock. But it's not an allowed optimization to change a non-deadlocking program into a potentially deadlocking program, so this reordering can not happen. (http://eel.is/c++draft/intro.multithread#intro.progress-7)

You can still get this deadlock if you actually write the code like that: lock1.lock(); lock2.unlock();

I think reitzensteinm was referring to the actual data inside the ring. There is a false sharing problem there particularly for the MPMC type ring buffer like disruptor. The solution is to pad each data slot in addition to the read and write indices. I do this in my MPMC ring buffer queue: https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...

You can align and pad each ring buffer slot to the cache line size. Example https://github.com/rigtorp/MPMCQueue/blob/master/include/rig...

Ringbuffers and thread-per-core architecture is great for low latency transaction processing systems, like exchanges and trading systems.

Sometimes you don't have time to do things perfectly and might use a spinlock when initializing some cache on first use... Only light contention, not great not, not terrible :).

I've written some on this topic. Start here https://rigtorp.se/virtual-memory/ , there is more on similar stuff on my website.

Yes, I've done this using libFuzzer. Supply custom mutation and crossover functions that generates interesting floating point numbers. Then let the coverage guided fuzzer exercise your code. https://rigtorp.se/fuzzing-floating-point-code/

All loads and stores are atomic. I'm also pretty sure ARM has coherent caches. What ARM does allow is for CPUs to optimize the order it loads and stores from cache as opposed to x86 TSO guarantee. DMB barrier instruction on ARM allows you to control how L/S may be reordered. Both x86 and ARM have special types of memory regions such as uncachable memory, but that's not something you are going to see outside of kernel space.

As I understand 'full task-isolation mode' will prevent compaction, completely disable vmstat timer etc. So it provides additional isolation. Since you already switched into kernel mode, might as well deliver a signal to let you know it happened. If the signal is masked there should be no overhead at all except a branch to check the signal mask.

There was also this recent patch https://lwn.net/Articles/816211/ to deal with kthread affinities. Even with isolcpus I find I still need to run pgrep -P 2 | xargs -i taskset -p -c 0 {} and deal with the workqueues.

Have you tried "A full task-isolation mode for the kernel": https://lwn.net/Articles/816298/ ?

Running only a single thread per core, I see no difference between SCHED_FIFO vs SCHED_OTHER. Except SCHED_FIFO can cause lockups if running 100% since cores are not completely isolated (ie vmstat timer and some other stuff).

Yes, it's annoying you cannot disable compaction. There is also work on pro-active compaction now: https://nitingupta.dev/post/proactive-compaction/