Why is Linux thread locking so slow?

[Jeff Sturm]

On Mon, 18 Oct 1999, Godmar Back wrote:
> > My main point is that it is not adequate to measure simple lock
> > throughput (iters/msec) to judge the quality of a lock algorithm, nor is
> > one algorithm best suited for all situations.  The spinlock code is
> > convenient because it is easy to tune for different machines, especially
> > SMP kernels.  The lock-test porgram is not very realistic since most CPU
> > time is spent competing for a lock, but it serves as a reasonable
> > benchmark for lock contention.
> > 
> 
> Jeff,
> 
> I'm not sure I understand what you're trying to say here.
> Your measurements demonstrate that spinlocks are faster than anything 
> else if there's at least as many processors as there are threads.
> I fully agree and expect this.

Godmar,

I had replied to one of your earlier posts before I read any of the
interesting discussion following... but I was definitely assuming
short-term locks.  For short-term locks I like to use some modified form
of a spinlock.  For long-term locks, I don't use mutexes or Java
synchronized blocks anyway... it is bad form to allow a Java thread to
block within a monitor, since it cannot be interrupted and may lead to
deadlock.

That said, I attempted to experiment a bit to see if a faster monitor is
possible, perhaps based on spinlocks instead of
pthread_mutex_{lock|unlock}.

I agree that if there are idle processors, spinlocks are a win.  The
inverse does not follow.  Even if there are more runnable threads than
processors, if the lock owner happens to be executing as another thread
tries to enter the lock, spinlocks are still a win over system calls.  If
the lock owner happens to get preempted while it owns the lock, the lock
will appear to be stuck to the spinning thread.  But the probability of a
context switch taking place while the lock is held is very low, assuming
short-term lock duration.

My example lock code falls back on sched_yield() if the lock appears to be
stuck.  On a uniprocessor that gives the lock owner a chance to continue.
On a multiprocessor platform, the worst sched_yield() can do is delay the
next test iteration by a few microseconds.

I didn't do anything to handle priority inversion, but that's not an
interesting case, mostly since thread priorites are broken in libgcj
on Linux (unless a real-time privileged scheduler is in use).  But it's
simple to fall back on nanosleep(), as LinuxThreads does.

> But I don't see what I should conclude?  That I should use spinlocks
> implemented via atomic exchange operations in cases like the one we 
> discussed, where you have one heavily contended lock in your application?

No.  The test-lock.c example demonstrates artificially high lock
contention.  I demonstrated a case where four threads compete for one
lock... there was a substantial slowdown, although on average
probably still faster than a system call.  It's sort of a worst-case
scenario.

A more realistic technique to handle high resource contention is a wait
queue.  LinuxThreads seems to use signals to suspend/resume threads.  I
don't think the signal technique is inefficient compared to other system 
calls... at least it seems to obey wake-one semantics.  It could do far
worse.

The XCHG instruction I used is convenient because it handles bus
locking and memory barriers.  There are other similar techniques
available, not always based on a single instruction.

> If that were your conclusion, I would have to disagree, simply because
> we cannot assume that there's at least as many processors as there
> are threads.

True... but that doesn't invalidate the use of spinlocks for short-term
mutual exclusion.

My earlier question stands: why does boehm-gc use spinlocks and not 
pthread mutexes, or condition variables? Was it a deliberate decision, or
ignorance on the part of the Linux porters?  That choice suprised me a
little, since garbage collection can run for long durations and cause
extensive spinning on waiting processors.

> We're not looking for a decision as to whether to use spinlocks or not,
> we're looking for a way to improve the implementation of pthread_mutex_lock
> in the contended case.  We cannot even assume that the lock is only held
> for short-durations, which is another prerequisite to using spinlocks
> to my knowledge.

I don't believe one routine can be optimized for all circumstances... I
prefer to use different techniques for short-term vs. long-term mutual
exclusion.  Though it might help a lot to have more interaction with the
kernel scheduler, as was suggested in another post.  In particular, if the
thread spinning on a lock can know whether the owner thread is running,
it may choose to suspend on a wait queue instead of continuing to spin.  I
don't think it would be desirable to perform a system call in most cases,
but if the user program could read kernel scheduler data through a shared
data area it just might work.  Unfortunately, the Linux kernel doesn't
have such a feature.

For that matter, Linux pthreads is optimized for uniprocessors.  It could
be improved by reading /proc/cpuinfo on startup to determine if it is
running on a SMP kernel.  I hacked libpthread.so once for MP use, and
observed up to a 30% speedup on some of my real-world Java code.

What exactly do you wish to improve in pthread_mutex_lock?  There are so
many variables, such as average latency with or without lock contention,
lock concurrency, resource utilization, predictability (ratio between
average and worst case), etc.  Clearly the technique you favor depends on
whether you are designing for maximum throughput, real-time, or other
needs.

Jeff