5 ms·

I updated my comment. The fastest impl, parking_lot, appears to be a ground up atomic based mutex that doesn’t rely on pthread at all.

ww520 7y ago
It seems to be doing similar logic. 1. Does a CAS with compare_exchange_weak() at line 69. 2. Then call lock_slow() at line 72 to do spinlocking (Guh!). 3. The call to parking_lot_core::park() at line 256 seems to sleep wait.
- bluejekyll 7y ago
  Yes. I just meant to say that it’s not a pthread based implementation, potentially making it more portable.
  - asveikau 7y ago
    The P in pthread is the P from Posix which stands for portable. Now, the "zero syscalls for uncontended pthread mutices via futex" optimization is Linux specific and may not be replicated elsewhere. Or it may. It's not Posix, but I know for instance win32 critical sections look a lot like spinlocks when not contended but do syscalls to block, which sounds a lot like a futex. So that would put that technique as dating to the 1990s at the latest. Futex landed in 2002.
    - bluejekyll 7y ago
      > The P in pthread is the P from Posix which stands for portable. What’s your point here? Posix is portable across posix compliant systems, it is not portable beyond that. There are many systems that are posix, but Rust targets more than that.
      - asveikau 7y ago
        Avoiding pthreads because they aren't portable and replacing them with a spinlock sounds a little bit like madness, that was my point. What is the non-posix target you have in mind? Windows? Seems like conditionally compiling against either pthreads or win32 critical section [or anything else] is a feasible thing and reasonable action. Maybe even the spinlock as a last resort.
- acqq 7y ago
  So this it acquires fully in userspace if there's no contention, it even spins if there is contention, and then if that wasn't enough it lets the thread sleep with the timeout. Which matches the description of that library: https://github.com/Amanieu/parking_lot https://github.com/Amanieu/parking_lot "This library provides implementations of Mutex, RwLock, Condvar and Once that are smaller, faster and more flexible than those in the Rust standard library" "Uncontended lock acquisition and release is done through fast inline paths which only require a single atomic operation. Microcontention (a contended lock with a short critical section) is efficiently handled by spinning a few times while trying to acquire a lock. The locks are adaptive and will suspend a thread after a few failed spin attempts." The only thing that I'm missing is how often the sleeping threads wake, as a bad constant can increase the CPU use.
  - ww520 7y ago
    Ah, thanks for the info. I would imagine the unlocking call would wake up the sleeping thread so it won't keep waking up periodically. The user-mode only implementation sounds interesting. The only downside is it won't work with inter-process locking.
    - deleted 7y ago
      [deleted]
  - temac 7y ago
    Does it really sleep for a specified period instead of doing directed wake-ups? If so that's very far from ideal...
    - bdash 7y ago
      No, a thread that fails to acquire the mutex sleeps until the thread that is releasing the mutex explicitly wakes it. On Linux this is achieved via FUTEX_WAIT / FUTEX_WAKE.
  - AstralStorm 7y ago
    How does it know that said critical section is short? Guessing? Likely a hard linear-quadratic expanding threshold. They tend to waste a lot of CPU power in specific algorithms. There are better, more intrusive ways of solving this problem on language level.

ww520 7y ago

It seems to be doing similar logic. 1. Does a CAS with compare_exchange_weak() at line 69. 2. Then call lock_slow() at line 72 to do spinlocking (Guh!). 3. The call to parking_lot_core::park() at line 256 seems to sleep wait.

bluejekyll 7y ago
Yes. I just meant to say that it’s not a pthread based implementation, potentially making it more portable.
- asveikau 7y ago
  The P in pthread is the P from Posix which stands for portable. Now, the "zero syscalls for uncontended pthread mutices via futex" optimization is Linux specific and may not be replicated elsewhere. Or it may. It's not Posix, but I know for instance win32 critical sections look a lot like spinlocks when not contended but do syscalls to block, which sounds a lot like a futex. So that would put that technique as dating to the 1990s at the latest. Futex landed in 2002.
  - bluejekyll 7y ago
    > The P in pthread is the P from Posix which stands for portable. What’s your point here? Posix is portable across posix compliant systems, it is not portable beyond that. There are many systems that are posix, but Rust targets more than that.
    - asveikau 7y ago
      Avoiding pthreads because they aren't portable and replacing them with a spinlock sounds a little bit like madness, that was my point. What is the non-posix target you have in mind? Windows? Seems like conditionally compiling against either pthreads or win32 critical section [or anything else] is a feasible thing and reasonable action. Maybe even the spinlock as a last resort.
acqq 7y ago
So this it acquires fully in userspace if there's no contention, it even spins if there is contention, and then if that wasn't enough it lets the thread sleep with the timeout. Which matches the description of that library: https://github.com/Amanieu/parking_lot https://github.com/Amanieu/parking_lot "This library provides implementations of Mutex, RwLock, Condvar and Once that are smaller, faster and more flexible than those in the Rust standard library" "Uncontended lock acquisition and release is done through fast inline paths which only require a single atomic operation. Microcontention (a contended lock with a short critical section) is efficiently handled by spinning a few times while trying to acquire a lock. The locks are adaptive and will suspend a thread after a few failed spin attempts." The only thing that I'm missing is how often the sleeping threads wake, as a bad constant can increase the CPU use.
- ww520 7y ago
  Ah, thanks for the info. I would imagine the unlocking call would wake up the sleeping thread so it won't keep waking up periodically. The user-mode only implementation sounds interesting. The only downside is it won't work with inter-process locking.
  - deleted 7y ago
    [deleted]
- temac 7y ago
  Does it really sleep for a specified period instead of doing directed wake-ups? If so that's very far from ideal...
  - bdash 7y ago
    No, a thread that fails to acquire the mutex sleeps until the thread that is releasing the mutex explicitly wakes it. On Linux this is achieved via FUTEX_WAIT / FUTEX_WAKE.
- AstralStorm 7y ago
  How does it know that said critical section is short? Guessing? Likely a hard linear-quadratic expanding threshold. They tend to waste a lot of CPU power in specific algorithms. There are better, more intrusive ways of solving this problem on language level.