| |||||||||||||
Ticket spinlocksTicket spinlocksPosted Feb 12, 2008 17:45 UTC (Tue) by bgamsa (guest, #33057)In reply to: Ticket spinlocks by PaulMcKenney Parent article: Ticket spinlocks Has anyone looked at MCS locks recently in the context of Linux and modern hardware. I believe it has more requirements in terms of hardware primitives, but it does provide queueing and local spinning.
(Log in to post comments)
Ticket spinlocks Posted Feb 12, 2008 18:08 UTC (Tue) by PaulMcKenney (subscriber, #9624) [Link] We did take a look a few years ago. Of course, pure MCS locks have an incompatible API, but the K42 folks at IBM Research came up with a variant of MCS locks that matched the Linux-kernel spin_lock() primitives. If I remember correctly, MCS locks outperformed the various NUMA-aware locking primitives, but were outperformed by simple spinlocks. I would expect that ticket locks would out-perform MCS locks at low contention levels (the common case in modern Linux kernels). I am not sure how MCS locks and ticket locks would compare at high levels of contention -- the ticket locks avoid the "thundering herd" problem, so might do quite well. Any benchmark results out there?
Ticket spinlocks Posted Jul 28, 2008 22:35 UTC (Mon) by okeydoke (guest, #46751) [Link] Ticket spinlocks perform terribly for uncontested and highly contested cases. Test cases on LKML do not show any of this (a very trivial test case was done that does not show lock *and* unlock cost). Here are relevant numbers on 16-core (8x2) AMD64 machine: Highly contested, MCS has 30724 a/s (average) and ticket locks have 6315 a/s (average). In the uncontested case, MCS has 836744 a/s (average) and ticket locks have 688817 a/s (average). Both implement FIFO fairness, anyways, so I do not expect relevance WRT "thundering herd" problem. MCS will perform better than the Anderson locks implemented under the name of "Fairlocks" and "J-Locks" for Linux, also (I assume these are the NUMA-aware locking primitives you are talking about?). There are other implementations that perform better than both of these. Ticket lock with proportional back-off helps alleviate performance issues in the highly contested case.
Ticket spinlocks Posted Jul 28, 2008 22:37 UTC (Mon) by okeydoke (guest, #46751) [Link] This is my MCS implementation and an optimized (for pipeline) Linux ticket lock implementation. The results are not for the K42-variant MCS locks originally provided to Linux.
|
|||||||||||||