6 ms·

I have an Actor framework which uses a vanilla std::deque for method pointers, and to add messages to the queue, the locking technique is a Benaphore (the origi

I have an Actor framework which uses a vanilla std::deque for method pointers, and to add messages to the queue, the locking technique is a Benaphore (the original Futex, which uses an atomic and a locking primitive, with the twist that my locking primitive is a combo of spinlock/mutex based on retry count). Nothing special. Benchmarks show that very rarely does the message push function block, and the chance of an OS context switch is also very low, so even though occasionally we get a locked thread swapping out, it is so infrequent that it doesn't justify the lock-free algorithm cost. In a nutshell, non lock free queues are much faster than lock free queues, however you must be prepared to accept the very infrequent longer delay due to a context switch (where the lock is not available to anyone). My benchmarks show that the price is acceptable since so much more performance is available with non lock free queues. 10 million messages per second per work thread can be queued on modern hardware.

Y_Y 3y ago
With a post like this, however interesting, you really should link the code. Not only will it prove your claim, but others like me will find the idea intriguing and immediately want to see how it's done.
- smallstepforman 3y ago
  https://github.com/smallstepforman/Medo/tree/main/Actor https://github.com/smallstepforman/Medo/tree/main/Actor
enqk 3y ago
how do you deal with msvc's `std::deque`? (or maybe you're not using literal std::dequeue)
- OnionBlender 3y ago
  What is special about msvc's `std::deque`?
  - josefx 3y ago
    The memory chunks it allocates to store entries are so small that it ends up allocating one chunk for every element for almost every type. The result is a lot of allocation overhead, pointer indirection and various other things that are bad for performance.
  - nly 3y ago
    It's block size is something stupid like 16 bytes, so it effectively becomes a slower linked list.
    - dwattttt 3y ago
      See https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=108587 https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=10... which includes confirmation & a brief commentary of the tiny block size.
- HelloNurse 3y ago
  Whatever the issue is, they support Clang on linux, i.e. no MSVC standard library.
EliRivers 3y ago
My benchmarks show that the price is acceptable Well, except to people who have a hard requirement that there never be this unpredictable, infrequent longer delay you mention.
- Groxx 3y ago
  It's probably fair to claim that zero* game developers have this hard requirement. At best they have a strong desire which might be partially backed up by benchmarks and squinting hard enough. *: ignoring deliberately esoteric cases, like Doom on a hard real-time system.
  - EarthLaunch 3y ago
    It's a requirement for any game that needs a reliable frame rate. Unpredictable delays during frame rendering cause jank. (This is not to say the OP has any such issues in its context.)
    - deleted 3y ago
      [deleted]
    - electroly 3y ago
      This is usually called "soft realtime" -- you want it to be fast but it's not wrong if it misses deadlines. It doesn't violate correctness of the system to miss a deadline. In a "hard realtime" system, it is a fatal error if the system misses a deadline because correctness is violated. I presume this difference is what OP is talking about. Games are never hard realtime; missing frame deadlines reduces user experience but it doesn't break the game. Hard realtime is things like industrial motion control, automotive and aviation electronics, pacemakers, etc.
      - jefftk 3y ago
        > Games are never hard realtime Depends how high your standards are! One of the things that makes playing old games on the original hardware really satisfying is how consistent they are.
Phelinofist 3y ago
I agree, lock free is cool and all, but often times it is more complex and not every case justifies the increased complexity.
foota 3y ago
Aren't lock free data structures more about reducing the impact of contention than throughput under low contention?
- klodolph 3y ago
  Depends what you mean by “the impact of contention”. It is possible, if you build a lock-free system, to end up with threads that keep churning and never make forward progress.
- loeg 3y ago
  Lock free is kind of an overloaded term that can mean a variety of things depending on what the user is thinking. Usually the goal is being able to make forward progress even if one thread is context switched out by the OS scheduler, which might be called wait-free or non-blocking. Using mutexes (unless you can prevent OS scheduling, interrupts, etc) makes this property impossible to achieve. In general, MPSC queues are super fast and there's no real reason to prefer a locked queue.
  - adwn 3y ago
    > In general, MPSC queues are super fast and there's no real reason to prefer a locked queue. There's one significant advantage that a locked vector or deque has over MPSC/MPMC queues: the consumers can dequeue all messages in a single operation by locking the vector, swapping it with an empty vector (typically, that's just 3 words), and locking it again. That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Similarly, if the vector is empty, a producer can push any number of messages in a single, constant-time operation.
    - loeg 3y ago
      All true, although I would quibble with: > That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Not if the lock is blocked because one of the writers context switched out! The typical case is good, but the worst case is pretty bad.
samsquire 3y ago
Thank you for sharing this. Could you tell me if your 10 million figure includes batching or are they a loop that tries to enqueue as many items as possible?
rowanG077 3y ago
I gather from your comment that lock-free is actually the best choice for videogames. Where consistent frame timing should be paramount.
pramalhe 3y ago
[dead]
tialaramex 3y ago
> the original Futex The "Benaphore" was a pretty old idea, but the Futex isn't just "Oh it's a Benaphore but Linux" the essential trick is that you don't actually need a kernel object - your "locking primitive" at all, and that idea is where this goes from "Yeah, everybody knows that" to OK, our OS should add this feature ASAP. Instead of an OS synchronisation object which is used to handle conflicts, with the futex design the OS carries a list of address -> thread mappings. If a thread T is asleep on a futex at address X, the address X goes in the list pointing to thread T. When the OS is asked to wake the X futex, it walks the list and wakes T. The give away is the limits. For something like Benaphores you're constrained, these are a costly OS wide resource, I think BeOS only allowed 65536 per machine or something. But a Futex is just memory, so there's no reason to have any limit at all.
YZF 3y ago
It really depends on the specifics. If there's a lot of contention then performance will drop off a cliff. Even atomic instructions can become a bottleneck ( https://stackoverflow.com/q/2538070 https://stackoverflow.com/q/2538070 ). I think what you're observing, i.e. that in many cases just use a lock and don't worry about it (or your variation) is true. But there are certain applications/situations where you can do better. Having a consumer pull out everything from the queue with one locking operation and being careful with how you signal the consumer from the producer(s), assuming there's a signal, can also make the queue more efficient/have higher throughput (e.g. you shouldn't signal for every item you put in the queue, only when it becomes non-empty).
hoseja 3y ago
The problem with vanilla std::deque is that the only acceptable implementation is in clang libc++. On MSVC it's basically an overcomplicated linked list.
snaury 3y ago
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 will lock it. This enables very efficient wakeups (or even eliding them completely when performing symmetric transfer between actors). I actually get ~10 million requests/s in a single-threaded uncontended case (that's at least one allocation per request and two actor context switches: a push into the target mailbox, and a push into the requester mailbox on the way back, plus a couple of steady_clock::now() calls when measuring latency of each request and checking for soft preemption during context switches). Even when heavily contended (thousands of actors call the same actor from multiple threads) I still get ~3 million requests/s. These numbers may vary depending on hardware though, so like I said it's hard to compare. In conclusion it very much depends on how lockfree queues are actually used, and how they are implemented, they can be faster and more scalable than a mutex (mutex is a lockfree data structure underneath anyway). I'd agree with you in that mutexes are better when protecting complex logic or data structures however, because using lockfree interactions to make it "scalable" often makes the base performance so low, that you'd maybe need thousands of cores to justify the resulting overhead. .. [1] https://github.com/snaury/coroactors/blob/a599cc061d754eefea3d036df09de8dd7bf59e2e/coroactors/detail/intrusive_mailbox.h#L76 https://github.com/snaury/coroactors/blob/a599cc061d754eefea... .. [2] https://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue https://www.1024cores.net/home/lock-free-algorithms/queues/i...

Y_Y 3y ago

With a post like this, however interesting, you really should link the code. Not only will it prove your claim, but others like me will find the idea intriguing and immediately want to see how it's done.

smallstepforman 3y ago
https://github.com/smallstepforman/Medo/tree/main/Actor https://github.com/smallstepforman/Medo/tree/main/Actor

enqk 3y ago

how do you deal with msvc's `std::deque`? (or maybe you're not using literal std::dequeue)

OnionBlender 3y ago
What is special about msvc's `std::deque`?
- josefx 3y ago
  The memory chunks it allocates to store entries are so small that it ends up allocating one chunk for every element for almost every type. The result is a lot of allocation overhead, pointer indirection and various other things that are bad for performance.
- nly 3y ago
  It's block size is something stupid like 16 bytes, so it effectively becomes a slower linked list.
  - dwattttt 3y ago
    See https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=108587 https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=10... which includes confirmation & a brief commentary of the tiny block size.
HelloNurse 3y ago
Whatever the issue is, they support Clang on linux, i.e. no MSVC standard library.

EliRivers 3y ago

My benchmarks show that the price is acceptable Well, except to people who have a hard requirement that there never be this unpredictable, infrequent longer delay you mention.

Groxx 3y ago
It's probably fair to claim that zero* game developers have this hard requirement. At best they have a strong desire which might be partially backed up by benchmarks and squinting hard enough. *: ignoring deliberately esoteric cases, like Doom on a hard real-time system.
- EarthLaunch 3y ago
  It's a requirement for any game that needs a reliable frame rate. Unpredictable delays during frame rendering cause jank. (This is not to say the OP has any such issues in its context.)
  - deleted 3y ago
    [deleted]
  - electroly 3y ago
    This is usually called "soft realtime" -- you want it to be fast but it's not wrong if it misses deadlines. It doesn't violate correctness of the system to miss a deadline. In a "hard realtime" system, it is a fatal error if the system misses a deadline because correctness is violated. I presume this difference is what OP is talking about. Games are never hard realtime; missing frame deadlines reduces user experience but it doesn't break the game. Hard realtime is things like industrial motion control, automotive and aviation electronics, pacemakers, etc.
    - jefftk 3y ago
      > Games are never hard realtime Depends how high your standards are! One of the things that makes playing old games on the original hardware really satisfying is how consistent they are.

Phelinofist 3y ago

I agree, lock free is cool and all, but often times it is more complex and not every case justifies the increased complexity.

foota 3y ago

Aren't lock free data structures more about reducing the impact of contention than throughput under low contention?

klodolph 3y ago
Depends what you mean by “the impact of contention”. It is possible, if you build a lock-free system, to end up with threads that keep churning and never make forward progress.
loeg 3y ago
Lock free is kind of an overloaded term that can mean a variety of things depending on what the user is thinking. Usually the goal is being able to make forward progress even if one thread is context switched out by the OS scheduler, which might be called wait-free or non-blocking. Using mutexes (unless you can prevent OS scheduling, interrupts, etc) makes this property impossible to achieve. In general, MPSC queues are super fast and there's no real reason to prefer a locked queue.
- adwn 3y ago
  > In general, MPSC queues are super fast and there's no real reason to prefer a locked queue. There's one significant advantage that a locked vector or deque has over MPSC/MPMC queues: the consumers can dequeue all messages in a single operation by locking the vector, swapping it with an empty vector (typically, that's just 3 words), and locking it again. That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Similarly, if the vector is empty, a producer can push any number of messages in a single, constant-time operation.
  - loeg 3y ago
    All true, although I would quibble with: > That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Not if the lock is blocked because one of the writers context switched out! The typical case is good, but the worst case is pretty bad.

samsquire 3y ago

Thank you for sharing this. Could you tell me if your 10 million figure includes batching or are they a loop that tries to enqueue as many items as possible?

rowanG077 3y ago

I gather from your comment that lock-free is actually the best choice for videogames. Where consistent frame timing should be paramount.

pramalhe 3y ago

[dead]

tialaramex 3y ago

> the original Futex The "Benaphore" was a pretty old idea, but the Futex isn't just "Oh it's a Benaphore but Linux" the essential trick is that you don't actually need a kernel object - your "locking primitive" at all, and that idea is where this goes from "Yeah, everybody knows that" to OK, our OS should add this feature ASAP. Instead of an OS synchronisation object which is used to handle conflicts, with the futex design the OS carries a list of address -> thread mappings. If a thread T is asleep on a futex at address X, the address X goes in the list pointing to thread T. When the OS is asked to wake the X futex, it walks the list and wakes T. The give away is the limits. For something like Benaphores you're constrained, these are a costly OS wide resource, I think BeOS only allowed 65536 per machine or something. But a Futex is just memory, so there's no reason to have any limit at all.

YZF 3y ago

It really depends on the specifics. If there's a lot of contention then performance will drop off a cliff. Even atomic instructions can become a bottleneck ( https://stackoverflow.com/q/2538070 https://stackoverflow.com/q/2538070 ). I think what you're observing, i.e. that in many cases just use a lock and don't worry about it (or your variation) is true. But there are certain applications/situations where you can do better. Having a consumer pull out everything from the queue with one locking operation and being careful with how you signal the consumer from the producer(s), assuming there's a signal, can also make the queue more efficient/have higher throughput (e.g. you shouldn't signal for every item you put in the queue, only when it becomes non-empty).

hoseja 3y ago

The problem with vanilla std::deque is that the only acceptable implementation is in clang libc++. On MSVC it's basically an overcomplicated linked list.

snaury 3y ago

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 will lock it. This enables very efficient wakeups (or even eliding them completely when performing symmetric transfer between actors). I actually get ~10 million requests/s in a single-threaded uncontended case (that's at least one allocation per request and two actor context switches: a push into the target mailbox, and a push into the requester mailbox on the way back, plus a couple of steady_clock::now() calls when measuring latency of each request and checking for soft preemption during context switches). Even when heavily contended (thousands of actors call the same actor from multiple threads) I still get ~3 million requests/s. These numbers may vary depending on hardware though, so like I said it's hard to compare. In conclusion it very much depends on how lockfree queues are actually used, and how they are implemented, they can be faster and more scalable than a mutex (mutex is a lockfree data structure underneath anyway). I'd agree with you in that mutexes are better when protecting complex logic or data structures however, because using lockfree interactions to make it "scalable" often makes the base performance so low, that you'd maybe need thousands of cores to justify the resulting overhead. .. [1] https://github.com/snaury/coroactors/blob/a599cc061d754eefea3d036df09de8dd7bf59e2e/coroactors/detail/intrusive_mailbox.h#L76 https://github.com/snaury/coroactors/blob/a599cc061d754eefea... .. [2] https://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue https://www.1024cores.net/home/lock-free-algorithms/queues/i...