Crate sparking_lot_core

source ·
Expand description

This library provides a low-level API for parking on addresses.

The parking lot

To keep synchronisation primitives small, most of the parking/unparking can be off-loaded to the parking lot. This allows writing locks that may even use a single bit. The idea comes from Webkit WTF::ParkingLot, which in turn was inspired by Linux futexes. The API provided by this crate is significantly simpler — no park/unpark tokens or timeouts are provided and it also doesn’t readjust based on thread count, which means with large enough thread counts the contention may be worse than when using other crates.

The parking lot provides two operations:

  • Parking — pausing a thread and enqueing it in a queue keyed by an address. This can be done with park.
  • Unparking — unpausing a thread that was queued on an address. This can be done with unpark_one, unpark_some and unpark_all.

For more information read the function docs.

loom

This crate has loom 0.7 integrated, which can be enabled with --cfg loom and optionally the loom-test feature. Using the feature is recommended, but if it’s not present, legacy loom testing will be enabled.

Legacy loom

loom requires consistency in it’s executions, but program addresses are intentionally random on most platforms. As such, when using legacy loom, there are things to keep in mind. When parking on different addresses, there are two possible outcomes: they may map to the same bucket, which may provide extra synchronisation, or different ones, which doesn’t. This additional synchronisation shouldn’t be relied on — the only way to guarantee the same bucket when not running loom is to use the same address with park. To give users control over this, when running legacy loom, there are 2 buckets: one for even addresses, one for odd addresses. In loom tests you should at least include the case with different buckets, since a shared bucket will provide more synchronisation and it shouldn’t really be possible that looser synchronisation will exclude the states possible with stricter ones. One approach is to use a base address, and a second parking address can be made with a cast to u8 and then offsetting by 1. For example, when implementing a SPSC channel, the sender could park on <address of inner state> and the receiver on <address of inner state>.cast::<u8>().offset(1) to park on different buckets. A nice property of this approach is that it also works in non-loom contexts where normally you would park on two non-ZST members.

Limitations

The legacy loom integration technique has some major drawbacks:

  • No more than 2 distinct addresses can be used if you want to properly test the case of non-colliding buckets.
  • Requires some extra work to use loom.
  • Dependents of dependents of sparking-lot-core can’t really use loom tests, because it can easily become impossible to test the case of non-colliding buckets.

Features

  • more-concurrency - increases the number of buckets, which reduces contention, but requires more memory. This flag is unlikely to produce meaningful results if thread count is below 100, but it also isn’t all that expensive — in the worst case it uses 24 extra KiB of RAM (adds ~12 KiB for x86-64).
  • loom-test - enables better loom tests. Has no effect without --cfg loom.
  • thread-parker - changes the parking implementation from a std::sync::Mutex to a std::thread::park based one. It may or may not perform better.

Functions