2 ms·

If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, produc

by yason 9y ago

If the odds for contention are low then something like a futex is pretty snappy, too. Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer. I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.

banachtarski 9y ago
Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.
- gpderetta 9y ago
  Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
  - chriscappuccio 9y ago
    OpenBSD implements futex now, too. Major league userland responsiveness improvements for futex based mutexes.
gpderetta 9y ago
There are two-lock queues that allow consumers to mostly run independently from the producers while still using bog-standard locks. Still you are right that lock-free algos really shine in implementing message queues, but mostly because they can be implemented with fewer or cheaper memory operations, so even in the uncontended case, the lock-free queue can shave some cycles. > I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example. Yes, one huge advantage of lock free algorithms is that you can have read mostly data structures with no contentions between readers (most rw-lock implementations do require readers to write on some shared state).

by yason 9y ago

banachtarski 9y ago

Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.

gpderetta 9y ago
Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though. [1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
- chriscappuccio 9y ago
  OpenBSD implements futex now, too. Major league userland responsiveness improvements for futex based mutexes.

gpderetta 9y ago

There are two-lock queues that allow consumers to mostly run independently from the producers while still using bog-standard locks. Still you are right that lock-free algos really shine in implementing message queues, but mostly because they can be implemented with fewer or cheaper memory operations, so even in the uncontended case, the lock-free queue can shave some cycles. > I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example. Yes, one huge advantage of lock free algorithms is that you can have read mostly data structures with no contentions between readers (most rw-lock implementations do require readers to write on some shared state).