1024cores

When you protect an std::deque with a mutex you would need at least two atomic operations: to lock the queue before pushing, and to unlock the queue after pushing. Because you're using an std::deque it may need to allocate memory during a push, which would happen under the lock, which makes it more likely for a thread to suspend with the lock taken. While the queue is locked other threads will have to wait, possibly even suspend on a futex, and then the unlocking thread would have to wake another thread up.

The most expensive part of any mutex/futex is not locking, it's waking other threads up when the lock is contended. I'm actually surprised you only get 10 million messages per second, is that for a contended or an uncontended case? I would expect more, but it probably depends on the hardware a lot, these numbers are hard to compare.

My actor framework currently uses a lockfree intrusive mailbox [1]_, which consists of exactly two atomic exchange operations, so pushing a node is probably cheaper than with a mutex. But the nicest part about it is how I found a way to make it "edge triggered". A currently unowned (empty) queue is locked by the first push (almost for free, compared to a classic intrusive mpsc queue [2]_ the second part of push uses an exchange instead of a store), which may start dequeueing nodes or schedule it to an executor. The mailbox will stay locked until it is drained completely, after which it is guaranteed that a concurrent (or some future) push…

As far back as 2011, I was reading articles from this blog: https://www.1024cores.net/

I remember thinking: "That's crazy! One kilo-cores! They're processors, not memory!"

Then, almost immediately, it started sinking in that this is what Moore's law means. That yes, sooner or later, I'll be working on a single system with more than a thousand cores (or hardware threads) in it.

This behemoth of a server probably has 8 sockets and I'm guessing it is the size of half a rack or thereabouts.

An upcoming AMD EPYC processor is rumored to have 256 cores (512 threads), which means that a "normal sized" server will have 512c/1024t soon at a more reasonable cost: https://www.extremetech.com/computing/328692-future-256-core-amd-epyc-cpu-might-sport-remarkably-low-600w-tdp

Similarly, Intel is planning a processor with 288 cores within a year, although it may or may not have hyper-threading: https://www.anandtech.com/show/21276/intel-previews-sierra-forest-with-288-e-cores-announces-granite-rapids-d-for-2025-launch-at-mwc-2024

A challenge I like to pose to software developers is this: If you were given one of these servers, and you could install your software on it, would it get 100x faster for one user than a server with just 10 vCPUs?

This is interesting, but I don't really understand the differences with
the existing coroutine libraries like libtask, libconcurrency or libcoro.

Of course, it uses the longjmp/setjmp trick, as suggested by Dmitry Vyukov.

http://www.1024cores.net/home/lock-free-algorithms/tricks/fibers

However, I'm not sure of the benefit of this approach, compared to
writing a few lines of stack switching assembly code per architecture.
Especially, how portable are the implementations of longjmp and setjmp
across the multitude of C libraries and operating systems?

But more importantly, it doesn't seem to solve the two main issues
of coroutines libraries written in C that were already solved in Go:

- How does the stack can grow or shrink? (specifying the stack size
in the worse case scenario doesn't scale well)

- How can a coroutine be moved to another operating system thread
and back? (useful when blocking or when parallelism is needed)

I too am a beginner with concurrent programming—it's a difficult topic to get your head around at first. Some resources that I've found super helpful:

- Dmitry Vyukov's Lockless Algorithms: https://www.1024cores.net/home/lock-free-algorithms

- Jeff Preshing's blog (worth exploring all adjacent articles): https://preshing.com/20120612/an-introduction-to-lock-free-programming/

- Bartosz Milewski: https://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-ordering/

- Memory Barriers: a Hardware View for Software Hackers—P.McKenney: https://www.researchgate.net/publication/228824849_Memory_Barriers_a_Hardware_View_for_Software_Hackers

I hope you find some of these useful. I've re-read Paul McKenney's paper every 2-3 months in an attempt to get this stuff to stick! :)

Thanks for the link.

If you look at the implementation no thread is ever stopped from completing. If a producing thread was killed mid operation by another malicious thread then the stream is broken. Other threads are never blocked. Other writers can add via a finite number of steps and the stream will back pressure when flow control kicks in. The consumer is never blocked - it simply never sees more messages. The algorithm meets the definition.

Unless I missed it that paper does not not state that the algorithm must cope with a malicious thread to be wait-free.

Try applying your thinking to this other respected MPSC wait-free queue.

http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue

Russian intellectuals are extraordinary. This guy's predictions, "One Day in the Life of Ivan Denisovich", their rocket engines which were often developed by one guy with a slide rule.

I'm analysing Dimitry Vyukov bounded lockless mcpc queue: https://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue Every line is an exquisite optimisation, many taking hours to understand how they interact with the others. A true masterpiece that will only be appreciated by a few. (But probably used by many, as it's in Rust's std library now.)