7 ms·

Thanks for writing this up -- I'll be coming back to it when I need to implement mutexes. As an aside -- it would be interesting to see what the analog on Win

Thanks for writing this up -- I'll be coming back to it when I need to implement mutexes. As an aside -- it would be interesting to see what the analog on Windows is. I know from experience the platform-provided mutex implementation on win32 is horrendously slow, and it would be nice to know if it's even possible on that platform to implement a 'real' mutex that doesn't suck. Anyone know of a reference implementation of mutexes on Windows?

johncolanduoni 3y ago
it’s called WaitOnAddress: https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96265 https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96...
- atq2119 3y ago
  That blog slightly misrepresents futex. Or perhaps it's outdated. It's written as if futexes can only be used with a 1/0/negative protocol, but that's not true. The values used are up to user space.
  - firstlink 3y ago
    Indeed, in another article Chen actually explicitly claims that msft invented (what we understand to be) futexes and that Linux switched their futex syscall from semaphores to futexes by copying windows. It is truly a wildly incorrect and implausible view of history.
mastax 3y ago
I don't know if this is the "best" recommendation, but it's the one I know. https://crates.io/crates/parking_lot https://crates.io/crates/parking_lot IIRC the only platform specific part is the thread parking logic, so I'd assume it's pretty fast on Windows in the common case.
- thayne 3y ago
  The rust standard library has incorporated a lot of parking_lot. On platforms that have futex-like primatives (like linux and windows) it uses those. But I think it uses a parking lot implementation if the OS doesn't support such an operation.
moonchild 3y ago
Refer to 'futexes are tricky', which shows how to build a mutex with a futex—<https://www.akkadia.org/drepper/futex.pdf https://www.akkadia.org/drepper/futex.pdf>—windows futexes are named WaitOnAddress, WakeByAddressSingle, and WakeByAddressAll. (That said, I think I heard somewhere that windows mutexes are decent now?)
overthrow 3y ago
Windows has an analogue to futexes called WaitOnAddress.[1] Zig's stdlib claims SRW locks are faster than a futex-based implementation.[2] But the futex-based implementation a few lines down that should run fine on Windows since it uses the cross-platform futex abstraction, so it wouldn't be hard to benchmark. [1]: https://learn.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress https://learn.microsoft.com/en-us/windows/win32/api/synchapi... [2]: https://github.com/ziglang/zig/blob/295b8ca467da36cd1066395e7f50b6245f456573/lib/std/Thread/Mutex.zig#L118 https://github.com/ziglang/zig/blob/295b8ca467da36cd1066395e...
asveikau 3y ago
It's worth noting that EnterCriticalSection on Windows already doesn't enter the kernel on the non-contended case. So very often these are used instead of the mutex kernel object.
userbinator 3y ago
The Win32 mutex is slow because it's also usable across processes. If you don't need cross-process sync, you should really be using a Critical Section instead. The kernel-level interface, which is largely undocumented, is I believe either an Event object or a Keyed Event on later versions. There's some interesting related discussion on that here: https://microsoft.public.win32.programmer.kernel.narkive.com/2F2a5Nin/question-about-win32-critical-section-implementation https://microsoft.public.win32.programmer.kernel.narkive.com... Anyone know of a reference implementation of mutexes on Windows? Look in the WINE source.
spacechild1 3y ago
> I know from experience the platform-provided mutex implementation on win32 is horrendously slow Sorry, but this sounds like FUD to me. First off, there is no single Win32 mutex implementation. The Win32 'Mutex' object is indeed heavy weight, but it is meant for inter-process synchronization. For thread synchronization you would rather use 'CriticalSection' or 'SRWLOCK'; they both avoid calling into the kernel in the uncontended case. SRWLOCK in particular is very fast.

johncolanduoni 3y ago

it’s called WaitOnAddress: https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96265 https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96...

atq2119 3y ago
That blog slightly misrepresents futex. Or perhaps it's outdated. It's written as if futexes can only be used with a 1/0/negative protocol, but that's not true. The values used are up to user space.
- firstlink 3y ago
  Indeed, in another article Chen actually explicitly claims that msft invented (what we understand to be) futexes and that Linux switched their futex syscall from semaphores to futexes by copying windows. It is truly a wildly incorrect and implausible view of history.

mastax 3y ago

I don't know if this is the "best" recommendation, but it's the one I know. https://crates.io/crates/parking_lot https://crates.io/crates/parking_lot IIRC the only platform specific part is the thread parking logic, so I'd assume it's pretty fast on Windows in the common case.

thayne 3y ago
The rust standard library has incorporated a lot of parking_lot. On platforms that have futex-like primatives (like linux and windows) it uses those. But I think it uses a parking lot implementation if the OS doesn't support such an operation.

moonchild 3y ago

Refer to 'futexes are tricky', which shows how to build a mutex with a futex—<https://www.akkadia.org/drepper/futex.pdf https://www.akkadia.org/drepper/futex.pdf>—windows futexes are named WaitOnAddress, WakeByAddressSingle, and WakeByAddressAll. (That said, I think I heard somewhere that windows mutexes are decent now?)

overthrow 3y ago

Windows has an analogue to futexes called WaitOnAddress.[1] Zig's stdlib claims SRW locks are faster than a futex-based implementation.[2] But the futex-based implementation a few lines down that should run fine on Windows since it uses the cross-platform futex abstraction, so it wouldn't be hard to benchmark. [1]: https://learn.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress https://learn.microsoft.com/en-us/windows/win32/api/synchapi... [2]: https://github.com/ziglang/zig/blob/295b8ca467da36cd1066395e7f50b6245f456573/lib/std/Thread/Mutex.zig#L118 https://github.com/ziglang/zig/blob/295b8ca467da36cd1066395e...

asveikau 3y ago

It's worth noting that EnterCriticalSection on Windows already doesn't enter the kernel on the non-contended case. So very often these are used instead of the mutex kernel object.

userbinator 3y ago

The Win32 mutex is slow because it's also usable across processes. If you don't need cross-process sync, you should really be using a Critical Section instead. The kernel-level interface, which is largely undocumented, is I believe either an Event object or a Keyed Event on later versions. There's some interesting related discussion on that here: https://microsoft.public.win32.programmer.kernel.narkive.com/2F2a5Nin/question-about-win32-critical-section-implementation https://microsoft.public.win32.programmer.kernel.narkive.com... Anyone know of a reference implementation of mutexes on Windows? Look in the WINE source.

spacechild1 3y ago

> I know from experience the platform-provided mutex implementation on win32 is horrendously slow Sorry, but this sounds like FUD to me. First off, there is no single Win32 mutex implementation. The Win32 'Mutex' object is indeed heavy weight, but it is meant for inter-process synchronization. For thread synchronization you would rather use 'CriticalSection' or 'SRWLOCK'; they both avoid calling into the kernel in the uncontended case. SRWLOCK in particular is very fast.