Home Benchmarks Software Miscellaneous

Spinlocks

These implementations are old and have gone through major over-hauls. I've also done new studies. Expect an update soon (estimated date around the end of October). Different spinlock algorithms implement different synchronization protocols consisting of a lock phase and unlock phase (or acquisition and release phase). Different waiting mechanisms are used to block the process (or processor) attempting to acquire the spinlock until the lock is once again available for acquisition. A latency mismatch can occur in the lock phase, the unlock phase or both phases from process to process due to several architectural constraints. If there is a mismatch in lock/unlock phase latency between different processes then unfairness becomes much more evident. Spinlock implementations which generate a lot of cache traffic exasperate unfairness. This can lead to resource starvation when a process cannot acquire resources quickly enough in order to complete its task at a reasonable rate.

Current Implementations

Program	Algorithm	Fairness
cas	Compare and swap	None
cas_gb	cas with geometric back-off	None
cas_rd	cas with non-serializing busy loop	None
inc	Increment/Decrement	None
inc_gb	Increment/Decrement with geometric backoff	None
mcs	Mellor-Crummey and Scott queue lock	FIFO
ticket	Ticket lock	FIFO

Notes

The ticket lock is inspired by the Linux ticket lock implementation by Nick Piggin.
The increment lock algorithm is the same as the one used by the Linux inc/dec lock implementation.

Benchmark Description

Opteron is a Sun x4600 (AMD Opteron 2354, 4 cores, 2 sockets)
Q8200 is a desktop system (Intel Q8200, 4 cores, 2 L2 cache)
Atom is an embedded system (Intel Atom 330, 2 cores)

Measurements are captured from ~10 seconds of micro-benchmark execution. As benchmarks were run in user-space, context switching overhead must be taken into account. A snapshot of the development version of the benchmark suite is available for download. The benchmark suite and spinlock implementations are a work in progress. Please note that throughput is scaled to 1/60.

Performance Measurements

Uncontested Workload

	Acquisitions/Second (1/60)
Algorithm	Opteron	Q8200	Atom
cas	559,968	755,868	642,289
inc	650,545	824,224	940,796
mcs	636,243	444,963	496,407
ticket	656,392	497,380	826,200

Highly-Contested Workloads

Algorithm	Acquisitions	Average	Deviation
cas	23,772,853	11,886,426	97.77%
cas_gb	71,466,818	35,733,409	4.01%
cas_rd	48,567,421	24,283,710	99.81%
inc	48,348,586	24,174,293	99.37%
inc_gb	55,921,880	27,960,940	89.31%
mcs	24,281,425	12,140,712	0%
ticket	40,931,434	20,465,717	0.01%

Algorithm	Acquisitions	Average	Deviation
cas	5,981,864	747,733	91.09%
cas_gb	64,092,979	8,011,622	37.19%
cas_rd	12,719,533	1,589,941	136.89%
inc	12,589,696	1,573,712	112.83%
inc_gb	66,564,916	8,320,614	99.20%
mcs	19,165,466	2,395,670	0.00%
ticket	11,437,131	1,429,641	0.01%