3 ms·

Spinning in locks are always tricky business. The sharpest thorn, to me, is: what happens when you are running inside the critical section and your thread gets

Spinning in locks are always tricky business. The sharpest thorn, to me, is: what happens when you are running inside the critical section and your thread gets preempted? Well, now the next thread which tries to acquire the lock is stuck waiting. But waiting for what? Waiting for the original thread to get scheduled. Now, the OS has no idea that the original thread should get scheduled again and is free to continue scheduling more and more work items. Fortunately for the lock in this article, and most other locks which spin, it is adaptive and will not spin for too long. But how long is long enough? If the spin is timed for a few loads and stores, then all is probably well as spins will not be attempted for very long. I wonder how these locks figure out how long they should spin? In the nasty case I previously mentioned, you'd want to spin for a very short while to avoid large amounts of waste. But spins which are too short lead to higher lock/unlock latency if the lock was held for any appreciable amount of time. This leads me to the following conclusion: spinning inevitable leads to _some_ number of wasted CPU cycles and therefore increased latency. I'm curious as to how the amount of spinning was chosen.

pron 10y ago
See the Doug Lea talk I linked to in another comment. Turns out that even the process of spinning is itself not so simple on some new processors.
pizlonator 10y ago
The post details why we spin for the amount of time that we do. It turns out that there is a wealth of measurements that support our 40-spins-while-yielding rule. It worked for a strangely diverse set of workloads: - IBM Research found it to be optimal on the portBOB benchmark on a 12-way AIX POWER box in 1999. - I found it to be optimal for DaCapo multi-threaded benchmarks on both AMD and Intel SMPs in ~2007. - I again found it to be optimal for WebKit these days. The point of spinning for a short time and then parking is that parking is hella slow. That's why you can get away with spinning. Spinning is net profitable so long as the amount you spin for is much smaller than the amount of time the OS will waste while parking.
kazinator 10y ago
I attempted to address these concerns using an adaptive algorithm in glibc some 15 years ago: http://stackoverflow.com/questions/19863734/what-is-pthread-mutex-adaptive-np/#25168942 http://stackoverflow.com/questions/19863734/what-is-pthread-... The idea is to avoid spinning using hard-coded constants, but put a modicum of on-the-fly empirical science into it: measure the duration of the critical regions with a smoothed estimator, which is maintained in the mutex. If the actual wait exceeds this smoothed average by too much (say double) then conclude that the owner must be pre-empted and break the spin with rescheduling. The smoothing is done very easily using a few bit operations that implement an IIR filter, similarly to the TCP RTO estimator.

pron 10y ago

See the Doug Lea talk I linked to in another comment. Turns out that even the process of spinning is itself not so simple on some new processors.

pizlonator 10y ago

The post details why we spin for the amount of time that we do. It turns out that there is a wealth of measurements that support our 40-spins-while-yielding rule. It worked for a strangely diverse set of workloads: - IBM Research found it to be optimal on the portBOB benchmark on a 12-way AIX POWER box in 1999. - I found it to be optimal for DaCapo multi-threaded benchmarks on both AMD and Intel SMPs in ~2007. - I again found it to be optimal for WebKit these days. The point of spinning for a short time and then parking is that parking is hella slow. That's why you can get away with spinning. Spinning is net profitable so long as the amount you spin for is much smaller than the amount of time the OS will waste while parking.

kazinator 10y ago

I attempted to address these concerns using an adaptive algorithm in glibc some 15 years ago: http://stackoverflow.com/questions/19863734/what-is-pthread-mutex-adaptive-np/#25168942 http://stackoverflow.com/questions/19863734/what-is-pthread-... The idea is to avoid spinning using hard-coded constants, but put a modicum of on-the-fly empirical science into it: measure the duration of the critical regions with a smoothed estimator, which is maintained in the mutex. If the actual wait exceeds this smoothed average by too much (say double) then conclude that the owner must be pre-empted and break the spin with rescheduling. The smoothing is done very easily using a few bit operations that implement an IIR filter, similarly to the TCP RTO estimator.