Why is Linux thread locking so slow?

[Jeff Sturm]

Godmar Back wrote:
> I admit it's a long time since I used SysV semaphores.  Obviously,
> one of the reasons why they don't see widespread application is their
> lack of proper reclamation when a process exits (-> ipcs, ipcrm etc.),
> and the lack of a mechanism to create unique keys etc., etc.....

Semaphores were designed for inter-process communication in the first
place... not inter-thread, as in pthread mutexes.  That's why they
operate in a system-wide namespace.

> FWIW, I coded Matt's example using semaphores and I'm now seeing a
> degradation of about 60 iters/ms vs. 600 iters/ms for the contended case.
> Code is at http://www.cs.utah.edu/~gback/sem-test.c if anybody is interested.
> Note that I've simply replaced the pthread_mutex_(un)lock() with a call
> to semop(); this means that we're having a system call even in the
> uncontended case.   This is not what a sem-converted linux-thread would
> look like.  The 600->60 comparison only makes sense if one assumes that
> every single attempt to lock is contended.  Nevertheless, my gut feeling
> is that even a linux-threads that would use Linux's SysV semaphores
> would perform as poorly as the current signal-based implementation.
> 
> So, I believe that kernel support is indeed needed.

Don't do in the kernel what can adequately be performed in user space. 
Let me add my own data here... I modified Matt's program to get better
timings, and compared mutexes to a spinlock implementation for ix86:

Uniprocessor (Pentium Pro 200MHz, Linux 2.2.12):

Threads          mutex       spinlock (SPIN_MAX=0)
         iters/msec switches  iters/msec switches
-------------------------------------------------
   1         1115        1        3624        1
   2         1116       13        3302        3
   4         1108     1249        2522        7

Multiprocessor (Pentium Pro 200MHz x 4, Linux 2.2.12):

Threads          mutex        spinlock (SPIN_MAX=0) spinlock
(SPIN_MAX=100)
         iters/msec switches   iters/msec switches   iters/msec switches
------------------------------------------------------------------------
   1         1568        1        3440         1        3443         1
   2         1148     7399        3365        80         414    563928
   4          588    65102        3018      2721         199    867046


All tests were run with 1000000 iterations per thread.  The 'switches'
column reports the number of times the lock owner has changed, and gives
an idea of the concurrency of the lock algorithm.  In general, on a MP a
short spin interval yields greater concurrency but diminished overall
throughput, due to cache synchronization and bus contention.  The 4
CPU's are swapping ownership of a single cache line, which is expensive
(but probably less so than a system call).

For such short lock durations system calls are not effective.  During
the time one thread spends in sched_yield(), perhaps several
microseconds, another thread may grab the spinlock hundreds of times
succesfully.  The effect is to inflate overall throughput but severely
increase latency and diminish concurrency.

On the other hand, for a uniprocessor spinlocks are not effective.

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.

The test_and_set code is borrowed from boehm-gc (anybody know why the GC
code uses spinlocks and not pthread_mutex_lock?).

Here is my modified lock-test.c:

/* lock-test.c
 * Compile with: gcc -O2 -o lock-test lock-test.c -lpthread
 * Run with: ./lock-test
 */

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>

pthread_key_t key;
pthread_mutex_t themutex = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;

static volatile unsigned int thelock = 0;

#if defined(__i386__)
inline static int test_and_set(volatile unsigned int *addr) {
    int oldval;
    /* Note: the "xchg" instruction does not need a "lock" prefix */
    __asm__ __volatile__("xchgl %0, %1"
        : "=r"(oldval), "=m"(*(addr))
        : "0"(1), "m"(*(addr)));
    return oldval;
}
inline static void clear(volatile unsigned int *addr) {
    int oldval;
    /* Note: the "xchg" instruction does not need a "lock" prefix */
    __asm__ __volatile__("xchgl %0, %1"
        : "=r"(oldval), "=m"(*(addr))
        : "0"(0), "m"(*(addr)));
}
#elif
#   error need implementation of test_and_set
#endif

static volatile int giterations = 0;
static volatile int glastthread = 0;
static volatile int gswitches = 0;

struct my_starter {
    void *(*method) (void *);
    int tnum;
    char *name;
};

#define SPIN_MAX 500

int my_mutex_lock() {
#if 0
    return pthread_mutex_lock(&themutex);
#else
    int i = 0;

    while (test_and_set(&thelock)) {
        while (thelock) {
            if (i++ > SPIN_MAX) {
                sched_yield();
                i = 0;
            }
        }
    }
    return 0;
#endif
}

int my_mutex_unlock() {
#if 0
    return pthread_mutex_unlock(&themutex);
#else
    clear(&thelock);
    return 0;
#endif
}

void *my_start(void *x) {
    struct my_starter *info = (struct my_starter *)x;

    pthread_setspecific(key, info);
    info->method(info);
    return NULL;
}

void print_time(char *name, struct timeval *before, struct timeval
*after, int num) {
    float msec = ((after->tv_sec) - (before->tv_sec)) * 1.0e3;
    msec += ((after->tv_usec) - (before->tv_usec)) / 1.0e3;
    fprintf(stderr,"%s: %d iters in %f msec, or %f iters/msec\n",
        name, num, msec, num/msec);
}

void *my_threadrun(void *x) {
    struct my_starter *info = (struct my_starter *)x;
    int i = 0;

    fprintf(stderr, "%s starting\n", info->name);
    for (i = 1; i <= 1000000; i++) {
        my_mutex_lock();
        if (glastthread != info->tnum) {

            glastthread = info->tnum;
            gswitches++;
        }
        giterations++;
        my_mutex_unlock();
    }
    fprintf(stderr, "%s complete\n", info->name);
}

int main(int argc, char **argv) {
    pthread_t threads[MAX_THREADS + 1];
    struct timeval before, after;
    int i;

    pthread_key_create (&key, NULL);

    gettimeofday(&before, NULL);

    for (i = 1; i <= MAX_THREADS; i++) {
      struct my_starter *info;

      info = (struct my_starter *) malloc (sizeof (struct my_starter));
      info->tnum = i;
      info->method = my_threadrun;
      info->name = (char *)malloc(80);
      sprintf(info->name,"thread-%d", i);

      pthread_create (&threads[i], NULL, my_start, (void *) info);
    }

    for (i = 1; i <= MAX_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
    gettimeofday(&after, NULL);
    print_time("total", &before, &after, giterations);
    printf("switches = %d\n", gswitches);

    return 0;
}


-- 
Jeff Sturm
jsturm@sigma6.com