Hacker News Reader

If you baseline against what people do when they skip builtin locks, then yes, that's spot on.

Though, I was more coming from the assumption that most people are really learning about the primitives that are going to be there, and they're going to be reaching for in the real world.

So I was thinking more, "what does my language's standard library provide", which has mostly moved from sysv (or worse, sure) -> futex.

It's true though, there have been some recent defections to custom waiting. I haven't looked at any of the well-used parking lot implementations in any depth.

It's a bit of a tangent, but obviously, such constructs can be done completely in userland if you're running your own scheduler. But I assume most of them are not, so if they're not using a futex, I'd assume they're instead writing to a blocking FD and managing their own queues?

If so, how much of a win is that, really? I'm surprised it'd be worth the effort.

> If you baseline against what people do when they skip builtin locks, then yes, that's spot on.

No idea what you mean by "builtin locks".

For example, the best baseline at the time futexes were introduced would have been MS's CRITICAL_SECTION, which was:

- Builtin in the sense that it shipped with the OS and part of that OS's standard library.

- Not a kernel call except on slow paths.

Prior to futexes, LinuxThreads already provided a lock implementation in pthread_mutex that was better than sysv, just worse than CRITICAL_SECTION, and worse than the futex-based one. But that old implementation already achieved the no-kernel-call fast path.

Also worth noting that today, the fastest widely available lock impl is MS's SRWLock, which obviously isn't futex based. So it's not like futexes are even the best

> So I was thinking more, "what does my language's standard library provide", which has mostly moved from sysv (or worse, sure) -> futex.

No, it hasn't. Before and after futexes, folks use pthread_mutex. Before and after futexes, pthread_mutex was faster than sysv. Before and after futexes, pthread_mutex was not based on sysv.

> It's a bit of a tangent, but obviously, such constructs can be done completely in userland if you're running your own scheduler. But I assume most of them are not, so if they're not using a futex, I'd assume they're instead writing to a blocking FD and managing their own queues?

Both ParkingLot and thin locks bottom out in a lock-and-condition-variable-per-thread implementation (or semaphore-per-thread if that's what the OS has). Then the lock and condition variable (or semaphore) may or may not use futexes.

> If so, how much of a win is that, really? I'm surprised it'd be worth the effort.

Portability. If you build a fast lock implementation on futexes, then it won't work on all OSes. You could get it to be portable to different OSes by virtue of the fact that the major OSes these days provide futex-like primitives, but even then, you'd be in a world of hurt because the details are different.

But ParkingLot can be built out of pthread_mutex/pthread_cond so it'll work well on any POSIX

> And futexes aren’t the only way to get there. Alternatives:

> - thin locks (what JVMs use)

> - ParkingLot (a futex-like primitive that works entirely in userland and doesn’t require that the OS have futexes)

Worth nothing that somewhere under the hood, any modern lock is going to be using a futex (if supported). futex is the most efficient way to park on Linux, so you even want to be using it on the slow path. Your language's thread.park() primitive is almost certainly using a futex.

ParkingLot just uses pthread mutex and cond.

Sure that uses futex under the hood, but the point is, you use futexes on Linux because that’s just what Linux gives you

> ParkingLot just uses pthread mutex and cond.

That's interesting, I'm more familiar with the Rust parking-lot implementation, which uses futex on Linux [0].

> Sure that uses futex under the hood, but the point is, you use futexes on Linux because that’s just what Linux gives you

It's a little more than that though, using a pthread_mutex or even thread.park() on the slow path is less efficient than using a futex directly. A futex lets you manage the atomic condition yourself, while generic parking utilities encode that state internally. A mutex implementation generally already has a built-in atomic condition with simpler state transitions for each thread in the queue, and so can avoid the additional overhead by making the futex call directly.

[0]: https://github.com/Amanieu/parking_lot/blob/739d370a809878e4...

> It's a little more than that though, using a pthread_mutex or even thread.park() on the slow path is less efficient than using a futex directly.

No, it absolutely isn’t.

The dominant cost of parking is whatever happens in the kernel and at the microarchitectural level when your thread goes to sleep. That cost is so dominant that whether you park with a futex wait or with a condition variables doesn’t matter at all.

(Source: I’ve done that experiment to death as a lock implementer back when I maintained Jikes RVM’s thin locks and then again when I wrote and maintained ParkingLot.)

Thanks for that reference. Do you know if the JVM still uses thin locks? Did they migrate to thin locks? I ask because I found a 9 year old reference with a JVM calling futex: https://stackoverflow.com/questions/32262946/java-periodical....

OpenJDK has used thin locks since back when it was called HotSpot.

The fact that the JVM is hanging in futexes doesn’t meant anything for the purpose of this discussion. Futexes are _the_ OS locking primitive on Linux so I would expect modern JVM thin locks to bottom out in a futex syscall. That doesn’t mean that the JVM is “using” futexes in the sense of the original post.