14 ms·

Author of the original WTF::ParkingLot here (what rust’s parking_lot is based on). I’m surprised that this only compared to std on one platform (Linux). The m

Author of the original WTF::ParkingLot here (what rust’s parking_lot is based on). I’m surprised that this only compared to std on one platform (Linux). The main benefit of parking lot is that it makes locks very small, which then encourages the use of fine grained locking. For example, in JavaScriptCore (ParkingLot’s first customer), we stuff a 2-bit lock into every object header - so if there is ever a need to do some locking for internal VM reasons on any object we can do that without increasing the size of the object

nextaccountic 11mo ago
How can a parking_lot lock be less than 1 byte? does this uses unsafe? Rust in general doesn't support bit-level objects unless you cast things to [u8] and do some shifts and masking manually (that is, like C), which of course is wildly unsafe for data structures with safety invariants
- Conscat 11mo ago
  This article elaborates how it works.
  - scottlamb 11mo ago
    Unhelpful response. This cuongle.dev article does not answer nextaccountic's question, and neither do the webkit.org articles that describe the parking lot concept but not this Rust implementation. The correct answer appears to be that it's impossible: `parking_lot::RawMutex` has private storage that owns the entire byte and does not provide any accessor for the unused six bits. https://docs.rs/parking_lot/0.12.5/parking_lot/struct.RawMutex.html https://docs.rs/parking_lot/0.12.5/parking_lot/struct.RawMut... (unless there's somewhere else in the crate that provides an accessor for this but that'd be a weird interface) (or you just use transmute to "know" that it's one byte and which bits within the byte it actually cares about, but really don't do that) (slightly more realistically, you could probably use the `parking_lot_core::park` portion of the implementation and build your own equivalent of `parking_lot::RawMutex` on top of it) (or you send the `parking_lot` folks a PR to extend `parking_lot::RawMutex` with interface you want; it is open source after all)
    - loeg 11mo ago
      The two bit lock was specifically refering to the C++ WTF::ParkingLot (and the comment mentioning it explicitly said that). nextaccountic is confused.
      - scottlamb 11mo ago
        No. nextaccountic's comment and the cuongle.dev article are both talking about Rust. The Rust `parking_lot` implementation only uses two bits within a byte, but it doesn't provide a way for anything else to use the remaining six. pizlonator's comments mention both the (C++) WTF::ParkingLot and the Rust `parking_lot`, and they don't answer nextaccountic's question about the latter. > nextaccountic is confused. nextaccountic asked how this idea could be applied to this Rust implementation. That's a perfectly reasonable question. pizlonator didn't know the anwer. That's perfectly reasonable too. Conscat suggested the article would be helpful; that was wrong.
        loeg 11mo ago
        nextaccountic replied to this original comment: https://news.ycombinator.com/item?id=46035698 https://news.ycombinator.com/item?id=46035698 Yes, nextaccountic's reply is confused about Rust vs C++ implementations. But the original mention was not talking about Rust.
    - pizlonator 11mo ago
      > and neither do the webkit.org articles that describe the parking lot concept but not this Rust implementation The WebKit post explicitly talks about how you just need two bits to describe the lock state. > The correct answer appears to be that it's impossible: `parking_lot::RawMutex` has private storage that owns the entire byte and does not provide any accessor for the unused six bits. Not impossible. One way to do this is to just use parking_lot directly. In WebKit there’s a template mixin that lets you steal two bits for locking however you like. JavaScriptCore uses this to steal two bits from the indexing type byte (if I remember right)
      - 11mo ago
- pizlonator 11mo ago
  Original post: https://webkit.org/blog/6161/locking-in-webkit/ https://webkit.org/blog/6161/locking-in-webkit/ Post that mentions the two bit lock: https://webkit.org/blog/7122/introducing-riptide-webkits-retreating-wavefront-concurrent-garbage-collector/ https://webkit.org/blog/7122/introducing-riptide-webkits-ret... I don’t know the details of the Rust port but I don’t imagine the part that involves the two bits to require unsafe, other than in the ways that any locking algorithm dances with unsafety in Rust (ownership relies on locking algorithms being correct)
  - writebetterc 11mo ago
    This is very similar to how Java's object monitors are implemented. In OpenJDK, the markWord uses two bits to describe the state of an Object's monitor (see markWord.hpp:55). On contention, the monitor is said to become inflated, which basically means revving up a heavier lock and knowing how to find it. I'm a bit disappointed though, I assumed that you had a way of only using 2 bits of an object's memory somehow, but it seems like the lock takes a full byte?
    - zozbot234 11mo ago
      The idea is that six bits in the byte are free to use as you wish. Of course you'll need to implement operations on those six bits as CAS loops (which nonetheless allow for any arbitrary RMW operation) to avoid interfering with the mutex state.
    - pizlonator 11mo ago
      The lock takes two bits. It’s just that if you use the WTF::Lock class the. You get a full byte simply because the smallest possible size of a class instance in C++ is one byte. But there’s a template mixing thing you can use to get it to be two bits (you tell the mixin which byte to steal the two bits from and which two bits). I suspend the same situation holds in the Rust port. I am very familiar with how Java does locks. This is different. Look at the ParkingLot/parking_lot API. It lets you do much more than just locks, and there’s no direct equivalent of what Java VMs call the inflated or fat lock. The closest thing is the on demand created queue keyed by address.
- bobbylarrybobby 11mo ago
  The lock uses two bits but still takes up a whole (atomic) byte
scottlamb 11mo ago
> The main benefit of parking lot is that it makes locks very small, which then encourages the use of fine grained locking. For example, in JavaScriptCore (ParkingLot’s first customer), we stuff a 2-bit lock into every object header - so if there is ever a need to do some locking for internal VM reasons on any object we can do that without increasing the size of the object IMHO that's a very cool feature which is essentially wasted when using it as a `Mutex<InnerBlah>` because the mutex's size will get rounded up to the alignment of `InnerBlah`. And even when not doing that, afaict `parking_lot` doesn't expose a way to use the remaining six bits in `parking_lot::RawMutex`. I think the new std mutexes made the right choice to use a different design. > I’m surprised that this only compared to std on one platform (Linux). Can't speak for the author, but I suspect a lot of people really only care about performance under Linux. I write software that I often develop from a Mac but almost entirely deploy on Linux. (But speaking of Macs: std::mutex doesn't yet use futexes on macOS. Might happen soon. https://github.com/rust-lang/rust/pull/122408 https://github.com/rust-lang/rust/pull/122408)
- pizlonator 11mo ago
  > I suspect a lot of people really only care about performance under Linux Yeah this is true
- Rusky 11mo ago
  Hypothetically Rust could make `Mutex<InnerBlah>` work with just two bits in the same way it makes `Option<&T>` the same size as `&T`. Annotate `InnerBlah` with the information about which bits are available and let `Mutex` use them.
  - timClicks 11mo ago
    References only have a single bit available as a niche (the null byte), which Option makes use of for null pointer optimization (https://doc.rust-lang.org/std/option/index.html#representation https://doc.rust-lang.org/std/option/index.html#representati...). In principle, you Rust could create something like std::num::NonZero and its corresponding sealed trait ZeroablePrimitive to mark that two bits are unused. But that doesn't exist yet as far as I know.
skitter 11mo ago
I do the same in my toy JVM (to implement the reentrant mutex+condition variable that every Java object has), except I've got a rare deadlock somewhere because, as it turns out, writing complicated low level concurrency primitives is kinda hard :p

nextaccountic 11mo ago

How can a parking_lot lock be less than 1 byte? does this uses unsafe? Rust in general doesn't support bit-level objects unless you cast things to [u8] and do some shifts and masking manually (that is, like C), which of course is wildly unsafe for data structures with safety invariants

Conscat 11mo ago
This article elaborates how it works.
- scottlamb 11mo ago
  Unhelpful response. This cuongle.dev article does not answer nextaccountic's question, and neither do the webkit.org articles that describe the parking lot concept but not this Rust implementation. The correct answer appears to be that it's impossible: `parking_lot::RawMutex` has private storage that owns the entire byte and does not provide any accessor for the unused six bits. https://docs.rs/parking_lot/0.12.5/parking_lot/struct.RawMutex.html https://docs.rs/parking_lot/0.12.5/parking_lot/struct.RawMut... (unless there's somewhere else in the crate that provides an accessor for this but that'd be a weird interface) (or you just use transmute to "know" that it's one byte and which bits within the byte it actually cares about, but really don't do that) (slightly more realistically, you could probably use the `parking_lot_core::park` portion of the implementation and build your own equivalent of `parking_lot::RawMutex` on top of it) (or you send the `parking_lot` folks a PR to extend `parking_lot::RawMutex` with interface you want; it is open source after all)
  - loeg 11mo ago
    The two bit lock was specifically refering to the C++ WTF::ParkingLot (and the comment mentioning it explicitly said that). nextaccountic is confused.
    - scottlamb 11mo ago
      No. nextaccountic's comment and the cuongle.dev article are both talking about Rust. The Rust `parking_lot` implementation only uses two bits within a byte, but it doesn't provide a way for anything else to use the remaining six. pizlonator's comments mention both the (C++) WTF::ParkingLot and the Rust `parking_lot`, and they don't answer nextaccountic's question about the latter. > nextaccountic is confused. nextaccountic asked how this idea could be applied to this Rust implementation. That's a perfectly reasonable question. pizlonator didn't know the anwer. That's perfectly reasonable too. Conscat suggested the article would be helpful; that was wrong.
      - loeg 11mo ago
        nextaccountic replied to this original comment: https://news.ycombinator.com/item?id=46035698 https://news.ycombinator.com/item?id=46035698 Yes, nextaccountic's reply is confused about Rust vs C++ implementations. But the original mention was not talking about Rust.
  - pizlonator 11mo ago
    > and neither do the webkit.org articles that describe the parking lot concept but not this Rust implementation The WebKit post explicitly talks about how you just need two bits to describe the lock state. > The correct answer appears to be that it's impossible: `parking_lot::RawMutex` has private storage that owns the entire byte and does not provide any accessor for the unused six bits. Not impossible. One way to do this is to just use parking_lot directly. In WebKit there’s a template mixin that lets you steal two bits for locking however you like. JavaScriptCore uses this to steal two bits from the indexing type byte (if I remember right)
    - 11mo ago
pizlonator 11mo ago
Original post: https://webkit.org/blog/6161/locking-in-webkit/ https://webkit.org/blog/6161/locking-in-webkit/ Post that mentions the two bit lock: https://webkit.org/blog/7122/introducing-riptide-webkits-retreating-wavefront-concurrent-garbage-collector/ https://webkit.org/blog/7122/introducing-riptide-webkits-ret... I don’t know the details of the Rust port but I don’t imagine the part that involves the two bits to require unsafe, other than in the ways that any locking algorithm dances with unsafety in Rust (ownership relies on locking algorithms being correct)
- writebetterc 11mo ago
  This is very similar to how Java's object monitors are implemented. In OpenJDK, the markWord uses two bits to describe the state of an Object's monitor (see markWord.hpp:55). On contention, the monitor is said to become inflated, which basically means revving up a heavier lock and knowing how to find it. I'm a bit disappointed though, I assumed that you had a way of only using 2 bits of an object's memory somehow, but it seems like the lock takes a full byte?
  - zozbot234 11mo ago
    The idea is that six bits in the byte are free to use as you wish. Of course you'll need to implement operations on those six bits as CAS loops (which nonetheless allow for any arbitrary RMW operation) to avoid interfering with the mutex state.
  - pizlonator 11mo ago
    The lock takes two bits. It’s just that if you use the WTF::Lock class the. You get a full byte simply because the smallest possible size of a class instance in C++ is one byte. But there’s a template mixing thing you can use to get it to be two bits (you tell the mixin which byte to steal the two bits from and which two bits). I suspend the same situation holds in the Rust port. I am very familiar with how Java does locks. This is different. Look at the ParkingLot/parking_lot API. It lets you do much more than just locks, and there’s no direct equivalent of what Java VMs call the inflated or fat lock. The closest thing is the on demand created queue keyed by address.
bobbylarrybobby 11mo ago
The lock uses two bits but still takes up a whole (atomic) byte

scottlamb 11mo ago

> The main benefit of parking lot is that it makes locks very small, which then encourages the use of fine grained locking. For example, in JavaScriptCore (ParkingLot’s first customer), we stuff a 2-bit lock into every object header - so if there is ever a need to do some locking for internal VM reasons on any object we can do that without increasing the size of the object IMHO that's a very cool feature which is essentially wasted when using it as a `Mutex<InnerBlah>` because the mutex's size will get rounded up to the alignment of `InnerBlah`. And even when not doing that, afaict `parking_lot` doesn't expose a way to use the remaining six bits in `parking_lot::RawMutex`. I think the new std mutexes made the right choice to use a different design. > I’m surprised that this only compared to std on one platform (Linux). Can't speak for the author, but I suspect a lot of people really only care about performance under Linux. I write software that I often develop from a Mac but almost entirely deploy on Linux. (But speaking of Macs: std::mutex doesn't yet use futexes on macOS. Might happen soon. https://github.com/rust-lang/rust/pull/122408 https://github.com/rust-lang/rust/pull/122408)

pizlonator 11mo ago
> I suspect a lot of people really only care about performance under Linux Yeah this is true
Rusky 11mo ago
Hypothetically Rust could make `Mutex<InnerBlah>` work with just two bits in the same way it makes `Option<&T>` the same size as `&T`. Annotate `InnerBlah` with the information about which bits are available and let `Mutex` use them.
- timClicks 11mo ago
  References only have a single bit available as a niche (the null byte), which Option makes use of for null pointer optimization (https://doc.rust-lang.org/std/option/index.html#representation https://doc.rust-lang.org/std/option/index.html#representati...). In principle, you Rust could create something like std::num::NonZero and its corresponding sealed trait ZeroablePrimitive to mark that two bits are unused. But that doesn't exist yet as far as I know.

skitter 11mo ago

I do the same in my toy JVM (to implement the reentrant mutex+condition variable that every Java object has), except I've got a rare deadlock somewhere because, as it turns out, writing complicated low level concurrency primitives is kinda hard :p