4 ms·

> Going back to the original futuex paper in 2002, it was immediately clear that the futex was a huge improvement in highly concurrent environments. Just in tha

> Going back to the original futuex paper in 2002, it was immediately clear that the futex was a huge improvement in highly concurrent environments. Just in that original paper, their tests with 1000 parallel tasks ran 20-120 times faster than sysv locks.. I think this is a misunderstanding. The baseline isn’t sysv locks. The baseline isn’t even what Linux was doing before futexes (Linux had a very immature lock implementation before futexes). The baseline is all of the ways folks implement locks if they don’t have futexes, which end up having roughly the same properties as a futex based lock: - fast path that doesn’t hit kernel for either lock or unlock - slow path that somehow makes the thread wait until the lock is available using some kernel waiting primitive. The thing futexes improve is the size of the user level data structure that is used for representing the lock in the waiting state. That’s it. 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)

aktau 1y ago
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-periodically-hangs-at-futex-and-very-low-io-output https://stackoverflow.com/questions/32262946/java-periodical....
- pizlonator 1y ago
  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.
viega 1y ago
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.
- pizlonator 1y ago
  > 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
ibraheemdev 1y ago
> 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.
- pizlonator 1y ago
  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
  - ibraheemdev 1y ago
    > 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/739d370a809878e45021f6de21b32a0dba4520de/core/src/thread_parker/linux.rs#L64 https://github.com/Amanieu/parking_lot/blob/739d370a809878e4...
    - pizlonator 1y ago
      > 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.)

aktau 1y ago

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-periodically-hangs-at-futex-and-very-low-io-output https://stackoverflow.com/questions/32262946/java-periodical....

pizlonator 1y ago
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.

viega 1y ago

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.

pizlonator 1y ago
> 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

ibraheemdev 1y ago

> 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.

pizlonator 1y ago
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
- ibraheemdev 1y ago
  > 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/739d370a809878e45021f6de21b32a0dba4520de/core/src/thread_parker/linux.rs#L64 https://github.com/Amanieu/parking_lot/blob/739d370a809878e4...
  - pizlonator 1y ago
    > 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.)