kubo39's blog

ただの雑記です。

SpinlockのExponential Backoff実装について

Lock Rust

SpinLockのExponential Backoffアルゴルズムの実装を少し調べた.

ParkingLot (WebKit,C++)

https://webkit.org/blog/6161/locking-in-webkit/ という素晴らしいブログ記事で spinning という節で触れている. どうやら JikesRVM というJVM実装に由来するようだ.

また本文中で Intelのpause命令に触れている箇所 があるが, どうも思うような性能が出なかったようだ. ParkingLotのSpinLockではマイクロベンチで性能のよかったsched_yieldを使った実装になっている.

Finally, it’s clear that the x86 pause instruction is not useful for our spinlocks. Intel shows that it is a speed-up, but we cannot confirm their claim.

parking_lot (Rust)

spinwait というところで実装されている.

  • カウンタ <= 10: Intelのpause命令 (nightlyかつx86の場合)
  • カウンタ <= 20: sched_yield (Unixの場合)
  • それ以上: falseを返す

Rustの実装ではIntelのpause命令を用いている.

corssbeam-channel (Rust)

crossbeam-channelでは parking_lot のspinwaitは使わず独自で実装している. といっても spin_loop_wait はx86のpause命令を使っているし yield_now は sched_yield なのでカウンタの値による分岐が違っているくらい.

どうやら parking_lot でされている話が元で実装されているようだ. https://github.com/Amanieu/parking_lot/issues/43 本家の方は追随しないのだろうか.