Why is Linux thread locking so slow?

[Xavier Leroy]

> > I have a simple Java program where 2 threads spin in a tight loop each 
> > grabbing the same lock and releasing it. This is on Linux x86 and has been
> > tested using GCJ 2.95.1, Blackdown JDK 1.1.7v3 (native threads), and 
> > IBM JDK 1.1.8 (native threads). Note that I am on an SMP system (IBM
> > Netfinity Dual PIII Xeon). 
> > 
> > When the lock is uncontended, performance is fine: about 2,000 loop 
> > iterations per millisecond. But with more than one thread trying to 
> > grab the lock, performance decreases considerably: down to 25 or 30 
> > iters/millisecond! 

I'm not surprised.  Given the 1-to-1 implementation model for
LinuxThread, each time a thread needs to suspend (e.g. because it's
waiting on a locked mutex), it needs to go through the kernel and
trigger a context switch.  Context switch in the Linux kernel is
pretty efficient compared with other Unix kernels, but still on the
order of 20 to 40 microseconds.

User-level threads or two-level threads fare better in these
circumstances, but are less efficient for doing I/O.  Also, Linux
lacks the kernel support required for proper two-level scheduling.

> I believe that this problem may be caused by the lack of proper support 
> for user-level threading in the linux kernel.
> One thing I'm wondering about is Linux's support for SYSV-style IPC
> (semop etc.).  Those appear to be kernel-supported semaphores.  Maybe
> the problem is not in the lack of kernel support, but could be fixed
> by using SysV semaphores instead?  It would definitely be worth a try.

Using SysV semaphores as a suspend/resume mechanism for threads would
be no more efficient than the current signal-based implementation:
you'd still incur a kernel context switch for each suspend and resume
implementation.

Using SysV semaphores as an alternative to mutexes is even worse:
you'd pay the cost of a system call on each mutex operation, not just
on those that contend for the mutex.

Finally, SysV IPC are nearly unusable due to the fact that resources
are not automatically reclaimed when no longer needed.

The last thing I want to say is that regardless of the thread library,
high contention on mutexes will result in bad performance for your
application, especially on multiprocessors (because contention means
you're not taking advantage of all available parallelism).  Thus,
properly written multi-threaded applications have very low mutex
contention, and consequently all thread libraries emphasize fast mutex
operations when there is no contention and don't worry too much about
performance in the other cases.  You need to benchmark real
applications, not just silly micro-benchmarks, before coming to
conclusions.

Regards,

- Xavier Leroy