queued spinlock code and results

queued spinlock code and results

[Nick Piggin]

[-- Attachment #1: Type: text/plain, Size: 4979 bytes --]

I made some tests of the queued spinlock code using userspace test code on
64-bit processors. I believe the xadd based code no longer has any theoretical
memory ordering problems.

The tests were done on 3 different architectures of different speeds and
vintages (so not really comparable between columns). I have attached the two
programs I used to make the results. Times are total elapsed time divided by
the number of locks (so effectively you get the time required for lock+unlock).

The threaded results also attempt to have an unfairness count, which is the
max number of times in a row that a lock is acquired,  when all other threads
are also executing in the loop -- the reason xadd for example is not always
0 there is because the other threads may not have reached the lock before
the current thread was able to get it several times (eg. if an interrupt
comes in, this could happen).

The threaded results are actually not too interesting because firstly they
don't really simulate the right mixture and timing of locks and critical
section time vs parallel time, and secondly the times are pretty heavily
skewed toward the unfair locks which tend to be _really_ unfair (eg. on the
last test, some threads were taking a full 2x longer to finish than others)
and so each thread gets to run for a long time without cache misses and thus
the overall throughput goes up. The dual-core core2 for another example did
regularly starve each thread for up to about 7*ms* (13 million cycles) while
the other was taking and releasing the lock.

However the non-threaded numbers (first 4 rows) are reasonably good. I found
on Core2 that if the inner loop was simply a lock+unlock and nothing else,
the inc-lock gained a bit more over the xadd-lock, but I don't think this is
representative of real code and it may just have been some alignment or
scheduling easter egg.

The results show that the xadd lock is definitely slower in single thread,
however the Core2 does really well, and also the cache cold case is pretty
insignificant.

It suggests to me that it *may* be worth trying a wholesale replacement of
spinlock with queued spinlock on x86 (starting as a config option which we
could perhaps default to ON in -mm / early -rcs). I think the main risk is
if there is some code that is really relying on the unfair batching nature
of the locks for good performance. I would argue that would usually be
poor code (eg. taking and dropping the spinlock too often, too much
contention on the lock, or using the wrong type of lock in the first place)  --
I think cacheline batching is great for regular lines, but not quite so nice
for locks. It would be interesting to see how something like the dcache lock
goes in dcache heavy workloads...


                         | Core2           Pentium 4 (Nocona)  Opteron
inc in cache             |  21.4ns           38.7ns              11.8ns
xadd in cache            |  22.5ns           44.4ns              14.5ns
                         |
inc no cache             | 122.2ns          153.5ns             172.7ns
xadd no cache            | 123.9ns          154.7ns             174.0ns
                         |
inc 2 thread (unfair)    | 230.9ns (69211)  376.5ns (3104)      174.0ns (2068) 
xadd 2 thread (unfair)   | 273.2ns (0)      307.1ns (59)        743.8ns (220)
                         |
inc 2 thread, other skt  |                  144.8ns (20444)     145.7ns (39739)
xadd 2 thread, other skt |                  306.8ns (147)       748.0ns (488)
                         |
inc 4 thread             |                 1248.9ns (172)      1158.5ns (139410)
xadd 4 thread            |                 1014.0ns (0)        2843.5ns (0)
                         |
inc 4 thread, diff skts  |                                     1598.0ns (65727)
xadd 4 thread, diff skts |                                     2848.1ns (0)
                         |
inc 16 thread            |                                     19017ns (55698)
xadd 16 thread           |                                     42723ns (0)



#define LOCK_INIT 1
static void lock(short *lock)
{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static void unlock(short *lock)
{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT 0
static void xlock(short *lock)
{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static void xunlock(short *lock)
{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

---


[-- Attachment #2: lock.c --]
[-- Type: text/x-c++src, Size: 3610 bytes --]

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

struct page {
	short lock;
	unsigned int next;
};
#define NR_PAGES (2*1024*1024)
static struct page pages[NR_PAGES];

#define LOCK_INIT 1
static void lock(short *lock)
{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static void unlock(short *lock)
{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT 0
static void xlock(short *lock)
{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static void xunlock(short *lock)
{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static int xlock_is_locked(short *lock)
{
	short tmp = *lock;
	char *x = (char *)&tmp;

	return (*x != *(x+1));
}

#define ITERS (16*1024*1024)
#define IN_ITERS (ITERS*5)

int main(void)
{
	int nr_pages;
	int nr;
	int i;
	struct page *p;
	struct timeval start, end;
	unsigned long long usec;
	unsigned int tmp;

	nr_pages = 10;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = LOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		lock(&p->lock);
		tmp = p->next;
		unlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = XLOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		xlock(&p->lock);
		tmp = p->next;
		xunlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		pages[i].next = 0;

	nr_pages = NR_PAGES;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = LOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		lock(&p->lock);
		tmp = p->next;
		unlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);


	for (i = 0; i < NR_PAGES; i++)
		pages[i].lock = XLOCK_INIT;
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		xlock(&p->lock);
		tmp = p->next;
		xunlock(&p->lock);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);


	return 0;
}

[-- Attachment #3: lock-threads.c --]
[-- Type: text/x-c++src, Size: 3909 bytes --]

#define _GNU_SOURCE
#include <sched.h>
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <unistd.h>

static short glock;

#define LOCK_INIT 1
static void lock(short *lock)
{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static void unlock(short *lock)
{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT 0
static void xlock(short *lock)
{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static void xunlock(short *lock)
{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define NR_THREADS 16
#define ITERS (1024*1024)

static int seq;
static int started, finished;

static void *thread(void *arg)
{
	unsigned long nr = (unsigned long)arg;
	int i;
	int oldseq = -1;
	int max_row = 0;
	int row = 0;
	cpu_set_t cpuset;

	CPU_ZERO(&cpuset);
	CPU_SET(nr, &cpuset);
	if (sched_setaffinity(0, sizeof(cpuset), &cpuset) == -1)
		perror("sched_setaffinity"), exit(1);

	lock(&glock);
	started++;
	unlock(&glock);

	for (i = 0; i < ITERS; i++) {
		int tmp;

		lock(&glock);	
		tmp = seq;
		seq++;		
		unlock(&glock);	

		if (started == NR_THREADS && !finished && tmp == oldseq) {
			row++;
			if (row > max_row)
				max_row = row;
		} else
			row = 0;
		oldseq = tmp+1;
	}

	lock(&glock);
	finished++;
	unlock(&glock);

	printf("inc-lock maximum unfair locks = %d\n", max_row);

	return NULL;
}

static void *xthread(void *arg)
{
	unsigned long nr = (unsigned long)arg;
	int i;
	int oldseq = -1;
	int max_row = 0;
	int row = 0;
	cpu_set_t cpuset;

	CPU_ZERO(&cpuset);
	CPU_SET(nr, &cpuset);
	if (sched_setaffinity(0, sizeof(cpuset), &cpuset) == -1)
		perror("sched_setaffinity"), exit(1);

	xlock(&glock);
	started++;
	xunlock(&glock);

	for (i = 0; i < ITERS; i++) {
		int tmp;

		xlock(&glock);	
		tmp = seq;
		seq++;		
		xunlock(&glock);	

		if (started == NR_THREADS && !finished && tmp == oldseq) {
			row++;
			if (row > max_row)
				max_row = row;
		} else {
			row = 0;
		}
		oldseq = tmp+1;
	}

	xlock(&glock);
	finished++;
	xunlock(&glock);

	printf("xadd-lock maximum unfair locks = %d\n", max_row);

	return NULL;
}


int main(void)
{
	struct timeval start, end;
	unsigned long long usec;
	pthread_t t[NR_THREADS];
	int i;

	seq = started = finished = 0;
	glock = LOCK_INIT;
	lock(&glock);
	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_create(&t[i], NULL, thread, (void *)(unsigned long)i) == -1)
			perror("pthread_create"), exit(1);
	}
	usleep(1000000);
	gettimeofday(&start, NULL);
	unlock(&glock);

	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_join(t[i], NULL) == -1)
			perror("pthread_join"), exit(1);
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock contended takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	seq = started = finished = 0;
	glock = XLOCK_INIT;
	xlock(&glock);
	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_create(&t[i], NULL, xthread, (void *)(unsigned long)i) == -1)
			perror("pthread_create"), exit(1);
	}
	usleep(1000000);
	gettimeofday(&start, NULL);
	xunlock(&glock);

	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_join(t[i], NULL) == -1)
			perror("pthread_join"), exit(1);
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock contended takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	return 0;
}

Re: queued spinlock code and results

[Nick Piggin]

On Sun, Jul 08, 2007 at 01:18:10PM +0200, Andi Kleen wrote:
> Nick Piggin <npiggin@suse.de> writes:
> 
> > I made some tests of the queued spinlock code using userspace test code on
> > 64-bit processors. I believe the xadd based code no longer has any theoretical
> > memory ordering problems.
> 
> Linus, the background of this is that on 8 socket Opteron systems
> the current spinlocks can become very unfair to the point of severe 
> starvation. These boxes are becomming more common.
> 
> > The threaded results also attempt to have an unfairness count, which is the
> > max number of times in a row that a lock is acquired,  when all other threads
> > are also executing in the loop -- the reason xadd for example is not always
> > 0 there is because the other threads may not have reached the lock before
> > the current thread was able to get it several times (eg. if an interrupt
> > comes in, this could happen).
> 
> Interesting. I was also thinking about switching the lock types
> at boot time. Since all the lock calls are out of line this would
> be reasonably easy.
> 
> I would say the main drawback of switchable and queued locks 
> would be also that they require a larger spinlock_t thus increasing
> cache usage

Technically the queued locks require twice the size (but I think
the implementation can handle 256 CPUs with 16 bits, while dec based
can only handle 128 with 8 bits -- not a big deal I know, but we'll
probably get there soon).

However currently spinlocks are much bigger than they could be anyway
(4 bytes, could be 1). Although often the alignment of data structures
will make the gain not so big.

But that said, I don't like to justify slightly suboptimal code by
saying that existing code is even less optimal :)

One other upshot of the queued spinlocks is that they don't need
the break_lock field, or any of the associated logic with that
(because it is trivial to test whether a lock is held and also how
many others are spinning on it). So that gives us for free an
avenue into more advanced congestion or spin backoff algorithms.

Re: queued spinlock code and results

[Andi Kleen]

Nick Piggin <npiggin@suse.de> writes:

> I made some tests of the queued spinlock code using userspace test code on
> 64-bit processors. I believe the xadd based code no longer has any theoretical
> memory ordering problems.

Linus, the background of this is that on 8 socket Opteron systems
the current spinlocks can become very unfair to the point of severe 
starvation. These boxes are becomming more common.

> The threaded results also attempt to have an unfairness count, which is the
> max number of times in a row that a lock is acquired,  when all other threads
> are also executing in the loop -- the reason xadd for example is not always
> 0 there is because the other threads may not have reached the lock before
> the current thread was able to get it several times (eg. if an interrupt
> comes in, this could happen).

Interesting. I was also thinking about switching the lock types
at boot time. Since all the lock calls are out of line this would
be reasonably easy.

I would say the main drawback of switchable and queued locks 
would be also that they require a larger spinlock_t thus increasing
cache usage

e.g. it would probably hurt for the large spinlock tables used 
by TCP, but then those should be fixed anyways to be smaller.

-Andi

Re: queued spinlock code and results

[Linus Torvalds]

On Sun, 8 Jul 2007, Andi Kleen wrote:
>
> Nick Piggin <npiggin@suse.de> writes:
> 
> > I made some tests of the queued spinlock code using userspace test code on
> > 64-bit processors. I believe the xadd based code no longer has any theoretical
> > memory ordering problems.
> 
> Linus, the background of this is that on 8 socket Opteron systems
> the current spinlocks can become very unfair to the point of severe 
> starvation. These boxes are becomming more common.

Yeah, considering the numbers, I don't have any real objections here.

I would ask that the code be given to both Intel and AMD engineers to look 
over, just to verify that the lfence is sufficient (or whether it's even 
needed), but I think the use of "xaddw" to both increment _and_ load the 
old value for the non-contention case is an obviously good (and clever) 
way to handle that one, and even if we'd have to add something heavier 
than the lfence to the contended case, it looks fine to me.

So the only remaining issue is that unfairness is probably really good for 
some loads (not just for the spinlock itself - it will likely cause much 
better cache behaviour for stuff _inside_ the lock to stay on the same 
core), but I don't think we want to optimize for the contended case 
anyway, so that's more of a "it will be interesting to see" kind of 
comment.

In short: if we can have AMD/Intel engineers look this over for any subtle 
issues, and they are happy, then I'm happy. 

		Linus

Re: queued spinlock code and results

[Davide Libenzi]

On Sun, 8 Jul 2007, Nick Piggin wrote:

> I made some tests of the queued spinlock code using userspace test code on
> 64-bit processors. I believe the xadd based code no longer has any theoretical
> memory ordering problems.
> 
> The tests were done on 3 different architectures of different speeds and
> vintages (so not really comparable between columns). I have attached the two
> programs I used to make the results. Times are total elapsed time divided by
> the number of locks (so effectively you get the time required for lock+unlock).
> 
> The threaded results also attempt to have an unfairness count, which is the
> max number of times in a row that a lock is acquired,  when all other threads
> are also executing in the loop -- the reason xadd for example is not always
> 0 there is because the other threads may not have reached the lock before
> the current thread was able to get it several times (eg. if an interrupt
> comes in, this could happen).

I was trying to look how costly is having a double-short counter, instead 
of a single byte.
The V-lock uses two short counters w/out the double-xadd optimization, 
while the Z-lock uses it.
This is a dual Opteron 252, but the test is done in single thread only 
(multi-thread really has no meaning for this test):

inc-lock in cache takes 7.28ns
xadd-lock in cache takes 8.93ns
vadd-lock in cache takes 10.35ns
zadd-lock in cache takes 8.43ns
inc-lock out of cache takes 87.85ns
xadd-lock out of cache takes 88.15ns
vadd-lock out of cache takes 89.38ns
zadd-lock out of cache takes 88.10ns

In this box, the always-lfence V-lock code pays for it. If I remove the 
lfence from the V-lock (but that's not possible), I get:

inc-lock in cache takes 7.28ns
xadd-lock in cache takes 8.93ns
vadd-lock in cache takes 7.67ns
zadd-lock in cache takes 8.44ns
inc-lock out of cache takes 87.87ns
xadd-lock out of cache takes 88.15ns
vadd-lock out of cache takes 88.24ns
zadd-lock out of cache takes 88.12ns

So in this box, and in this test, the double-short Z-lock seems faster 
than a double-byte. I've no idea why, since it uses two ops more and an 
extra register.




- Davide



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

struct page {
	short lock[2];
	unsigned int next;
};
#define NR_PAGES (2*1024*1024)
static struct page pages[NR_PAGES];

#define LOCK_INIT(l) (l)[0] = 1
static inline void lock(short *lock)
{
	__asm__ __volatile__ ("1:\n\t"
			      "lock ; decb %0\n\t"
			      "jns 2f\n\t"
			      "3:\n\t"
			      "rep ; nop\n\t"
			      "cmpb $0,%0\n\t"
			      "jle 3b\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

static inline void unlock(short *lock)
{
	__asm__ __volatile__ ("movb $1,%0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define XLOCK_INIT(l) (l)[0] = 0
static inline void xlock(short *lock)
{
	short i = 0x0100;
	__asm__ __volatile__ ("lock ; xaddw %%ax, %1\n\t"
			      "1:\n\t"
			      "cmpb %%ah, %%al\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movb %1, %%al\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+a" (i), "+m" (*lock)
			    : : "memory");
}

static inline void xunlock(short *lock)
{
	__asm__ __volatile__ ("incb %0\n\t"
			    : "+m" (*lock)
			    : : "memory");
}

#define VLOCK_INIT(l) (l)[0] = 0, (l)[1] = 0
static inline void vlock(short *lock)
{
	__asm__ __volatile__ ("lock ; xaddw %%ax, %0\n\t"
			      "1:\n\t"
			      "cmpw %%ax, %1\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			      "lfence\n\t"
			    : "+m" (lock[1])
			    : "m" (lock[0]), "a" (1) : "memory");
}

static inline void vunlock(short *lock)
{
	__asm__ __volatile__ ("incw %0\n\t"
			    : "+m" (lock[0])
			    : : "memory");
}

#define ZLOCK_INIT(l) (l)[0] = 0, (l)[1] = 0
static inline void zlock(short *lock)
{
	__asm__ __volatile__ ("lock ; xaddl %%eax, %0\n\t"
			      "mov %%eax, %%ebx\n\t"
			      "shr $16, %%ebx\n\t"
			      "1:\n\t"
			      "cmpw %%ax, %%bx\n\t"
			      "je 2f\n\t"
			      "rep ; nop\n\t"
			      "movw %1, %%bx\n\t"
			      "lfence\n\t"
			      "jmp 1b\n\t"
			      "2:\n\t"
			    : "+m" (*(int *) lock)
			    : "m" (lock[0]), "a" (0x10000) : "ebx", "memory");
}

static inline void zunlock(short *lock)
{
	__asm__ __volatile__ ("incw %0\n\t"
			    : "+m" (lock[0])
			    : : "memory");
}

static int xlock_is_locked(short *lock)
{
	short tmp = *lock;
	char *x = (char *)&tmp;

	return (*x != *(x+1));
}

#define ITERS (16*1024*1024)
#define IN_ITERS (ITERS*5)

int main(void)
{
	int nr_pages;
	int nr;
	int i;
	struct page *p;
	struct timeval start, end;
	unsigned long long usec;
	unsigned int tmp;

	nr_pages = 10;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		LOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		lock(&p->lock[0]);
		tmp = p->next;
		unlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		XLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		xlock(&p->lock[0]);
		tmp = p->next;
		xunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		VLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		vlock(&p->lock[0]);
		tmp = p->next;
		vunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("vadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);

	for (i = 0; i < NR_PAGES; i++)
		ZLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < IN_ITERS; i++) {
		zlock(&p->lock[0]);
		tmp = p->next;
		zunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("zadd-lock in cache takes %0.2lfns\n", (double)usec * 1000 / IN_ITERS);
	
	for (i = 0; i < NR_PAGES; i++)
		pages[i].next = 0;

	nr_pages = NR_PAGES;
	srandom(10);
	p = &pages[0];
	i = 0;
	nr = 0;
	while (nr < nr_pages-1) {
		unsigned int n;

		n = random() % NR_PAGES;
		while (p == &pages[n] || pages[n].next)
			n = (n+1) % NR_PAGES;
		p->next = n;
		p = &pages[n];
		nr++;
	}
	p->next = 0;

	for (i = 0; i < NR_PAGES; i++)
		LOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		lock(&p->lock[0]);
		tmp = p->next;
		unlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("inc-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);


	for (i = 0; i < NR_PAGES; i++)
		XLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		xlock(&p->lock[0]);
		tmp = p->next;
		xunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("xadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	for (i = 0; i < NR_PAGES; i++)
		VLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		vlock(&p->lock[0]);
		tmp = p->next;
		vunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("vadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	for (i = 0; i < NR_PAGES; i++)
		ZLOCK_INIT(pages[i].lock);
	gettimeofday(&start, NULL);
	p = &pages[0];
	for (i = 0; i < ITERS; i++) {
		zlock(&p->lock[0]);
		tmp = p->next;
		zunlock(&p->lock[0]);
		p = &pages[tmp];
	}
	gettimeofday(&end, NULL);
	usec = end.tv_usec + 1000000*(end.tv_sec - start.tv_sec) - start.tv_usec;
	printf("zadd-lock out of cache takes %0.2lfns\n", (double)usec * 1000 / ITERS);

	return 0;
}

Re: queued spinlock code and results

[Davide Libenzi]

On Mon, 9 Jul 2007, Davide Libenzi wrote:

> #define ZLOCK_INIT(l) (l)[0] = 0, (l)[1] = 0
> static inline void zlock(short *lock)
> {
> 	__asm__ __volatile__ ("lock ; xaddl %%eax, %0\n\t"
> 			      "mov %%eax, %%ebx\n\t"
> 			      "shr $16, %%ebx\n\t"
> 			      "1:\n\t"
> 			      "cmpw %%ax, %%bx\n\t"
> 			      "je 2f\n\t"
> 			      "rep ; nop\n\t"
- 			      "movw %1, %%bx\n\t"
+ 			      "movw %1, %%ax\n\t"
> 			      "lfence\n\t"
> 			      "jmp 1b\n\t"
> 			      "2:\n\t"
> 			    : "+m" (*(int *) lock)
> 			    : "m" (lock[0]), "a" (0x10000) : "ebx", "memory");
> }

Erm, modulo that bugger ;) that'd never should up in the non-contended 
case (and that does not change numbers):

inc-lock in cache takes 7.28ns
xadd-lock in cache takes 8.93ns
vadd-lock in cache takes 10.34ns
zadd-lock in cache takes 8.43ns
inc-lock out of cache takes 87.98ns
xadd-lock out of cache takes 88.89ns
vadd-lock out of cache takes 89.59ns
zadd-lock out of cache takes 89.86ns



- Davide

Re: queued spinlock code and results

[Linus Torvalds]

On Mon, 9 Jul 2007, Davide Libenzi wrote:
> 
> So in this box, and in this test, the double-short Z-lock seems faster 
> than a double-byte. I've no idea why, since it uses two ops more and an 
> extra register.

At this kind of level, the exact instruction scheduling can make a big 
difference.

The extra register usage won't matter if there is no register pressure, 
and any extra instructions can actually happen to *help*, if they end up 
just aligning something just the right way.

There can also be various random effects of prefixes: decoding x86 
instructions is basically a very uarch-specific issue, and for all we know 
it might be that the AMD setup may well end up behaving differently from 
most Intel chips (and within the Intel family, the netburst situation is 
likely different from the other P6-derived cores).

For example, does a single prefix decode faster? It could be that the 
combination of "lock" _and_ "opsize" prefixes is problematic (as in a 
16-bit locked "lock xaddw"), and causes a decode hickup, but that "lock" 
and "opsize" on their own don't cause any decoder issues (ie doing the 
"lock" on the 32-bit xadd, and just the "opsize" prefix on the 16-bit decw 
both are fast).

But on another uarch it might work out the other way: if "lock" is always 
a complex op, then having a opsize prefix on that one might be "free", and 
then you're better combining them for the locked 16-bit xadd, and having 
the releasing "decb" not have any prefix at all.

And regardless of that, just a random "it happened to get aligned that 
way" (where "alignment" might be about hitting the cache-line just right, 
but might also be about just having the right instruction mix to get the 
intel decoders to run at their full 4-1-1-1 capacity), causing the timing 
differences.

So before taking these numbers as any kind of "real" values, I'd suggest:

 - trying it out on at least a few different uarchs (Opteron, P4 and Core 
   2 all have quite different restrictions on decoding)

 - possibly trying it out with things in different order and different 
   compiler options (-O2 vs -Os), trying to cause different kinds of 
   alignment issues.

Also, just a small nit: in the kernel, the locking would _not_ be inlined 
(but the unlocking would), so marking the lock functions "inline" is 
probably a bad idea. Without the inline, it's likely more realistic, and 
the effects of register pressure will be hidden. Because of the uninlining 
nature of locks, I think you can generally ignore the "one or two 
registers" issue - you'll have three caller-clobbered registers to play 
with regardless.

			Linus

Re: queued spinlock code and results

[Davide Libenzi]

On Mon, 9 Jul 2007, Linus Torvalds wrote:

> On Mon, 9 Jul 2007, Davide Libenzi wrote:
> > 
> > So in this box, and in this test, the double-short Z-lock seems faster 
> > than a double-byte. I've no idea why, since it uses two ops more and an 
> > extra register.
> 
> At this kind of level, the exact instruction scheduling can make a big 
> difference.
> 
> The extra register usage won't matter if there is no register pressure, 
> and any extra instructions can actually happen to *help*, if they end up 
> just aligning something just the right way.
> 
> There can also be various random effects of prefixes: decoding x86 
> instructions is basically a very uarch-specific issue, and for all we know 
> it might be that the AMD setup may well end up behaving differently from 
> most Intel chips (and within the Intel family, the netburst situation is 
> likely different from the other P6-derived cores).
> 
> For example, does a single prefix decode faster? It could be that the 
> combination of "lock" _and_ "opsize" prefixes is problematic (as in a 
> 16-bit locked "lock xaddw"), and causes a decode hickup, but that "lock" 
> and "opsize" on their own don't cause any decoder issues (ie doing the 
> "lock" on the 32-bit xadd, and just the "opsize" prefix on the 16-bit decw 
> both are fast).
> 
> But on another uarch it might work out the other way: if "lock" is always 
> a complex op, then having a opsize prefix on that one might be "free", and 
> then you're better combining them for the locked 16-bit xadd, and having 
> the releasing "decb" not have any prefix at all.
> 
> And regardless of that, just a random "it happened to get aligned that 
> way" (where "alignment" might be about hitting the cache-line just right, 
> but might also be about just having the right instruction mix to get the 
> intel decoders to run at their full 4-1-1-1 capacity), causing the timing 
> differences.
> 
> So before taking these numbers as any kind of "real" values, I'd suggest:
> 
>  - trying it out on at least a few different uarchs (Opteron, P4 and Core 
>    2 all have quite different restrictions on decoding)
> 
>  - possibly trying it out with things in different order and different 
>    compiler options (-O2 vs -Os), trying to cause different kinds of 
>    alignment issues.
> 
> Also, just a small nit: in the kernel, the locking would _not_ be inlined 
> (but the unlocking would), so marking the lock functions "inline" is 
> probably a bad idea. Without the inline, it's likely more realistic, and 
> the effects of register pressure will be hidden. Because of the uninlining 
> nature of locks, I think you can generally ignore the "one or two 
> registers" issue - you'll have three caller-clobbered registers to play 
> with regardless.

Indeed, with no inline, on a P4 (with -O2), numbers betweeen xadd-lock 
and zadd-lock gets closer:

inc-lock in cache takes 35.15ns
xadd-lock in cache takes 43.84ns
vadd-lock in cache takes 53.51ns
zadd-lock in cache takes 43.28ns
inc-lock out of cache takes 122.92ns
xadd-lock out of cache takes 126.98ns
vadd-lock out of cache takes 172.36ns
zadd-lock out of cache takes 126.01ns

The always-lfence instruction in vadd-lock really is painfull though.
If numbers are close, and given that spinlock size considering structure 
alignments should not matter much, wouldn't it be better to use a double 
short and remove the 256 CPUs cap?



- Davide

Re: queued spinlock code and results

[Linus Torvalds]

On Mon, 9 Jul 2007, Davide Libenzi wrote:
> 
> The always-lfence instruction in vadd-lock really is painfull though.
> If numbers are close, and given that spinlock size considering structure 
> alignments should not matter much, wouldn't it be better to use a double 
> short and remove the 256 CPUs cap?

On x86? No.

There are no issues with the 255-CPU cap on 32-bit x86. It's just not 
relevant to anybody. So the _only_ thing that matters is speed and to a 
secondary degree size.

On x86-64, things are slightly different, and we would want to have at 
least the _capability_ to do 16 bits. So there might be a (somewhat weak) 
argument in favor of trying to share code.

But even then, size and performance are really the only things that 
matter, and if the 8/16-bit version is no slower, then I'd pick that by 
default, and suggest the 16/32-bit one to be enabled by CONFIG_MAX_CPU's 
being >=256 (at which point you can share the code with x86 anyway, since 
that just becomes the <256 cpu case).

		Linus

Re: queued spinlock code and results

[Linus Torvalds]

On Mon, 9 Jul 2007, Linus Torvalds wrote:
> 
> There are no issues with the 255-CPU cap on 32-bit x86. It's just not 
> relevant to anybody. So the _only_ thing that matters is speed and to a 
> secondary degree size.

..of course, from a pure speed standpoint, the "lock dec" one seems to 
be the fastest, with the difference bwteen the 16-bit/32-bit "lock xadd" 
being comparatively totally in the noise.

Which is what I'd expect.

The difference between a 16-bit and 32-bit xadd should basically not be 
likely to be really measurable (ie we're likely talking about a single CPU 
cycle - if that - for the decode of the operand size override, and since 
both variants need it for _one_ of the operations, it likely ends up being 
about instruction scheduling noise), while the difference between a "dec" 
and "xadd" could be the difference between a native uop and microcoded.

[ Not that "xadd" couldn't be as fast as a "dec" in theory, but it's much 
  less likely to be that. It obviously has to actually write to two 
  targets: the register -and- memory, and that tends to require at least 
  an extra uop.

  And together with being a r-op-w memory instruction to begin with (which 
  is generally the "most complex" normal instruction), and not a very 
  often used instruction, the end result is that it would often tend to be 
  handled specially somehow - either in a special decode unit, or as 
  actual microcode. ]

So from a pure performance standpoint, xadd will likely continue to lose 
against dec. So the reason to choose xadd in the first place isn't "best 
performance", but "best performance given fairness".

And any performance difference between xadd and dec is going to be much 
bigger than any difference between 16/32-bit versions of xadd.

So I wouldn't get too hung up on a potential single cycle, and it's 
arguably more important to make the (inlined) "unlock" thing be as simple 
and small as possible.

			Linus

Re: queued spinlock code and results

[Christoph Lameter]

On Sun, 8 Jul 2007, Andi Kleen wrote:

> I would say the main drawback of switchable and queued locks 
> would be also that they require a larger spinlock_t thus increasing
> cache usage

Right. Zoran Radovic has shown that queued locks are inferior 
to other approaches. The best approach that he found in his research were 
the HBO locks that are somewhat more intelligent form of spinlocks.

http://user.it.uu.se/~zoranr/
http://www.it.uu.se/research/group/uart/projects/nucasynch/

Paper on the issue with measurements:
http://www.it.uu.se/research/publications/lic/2003-008/2003-008.pdf

Re: queued spinlock code and results

[Nick Piggin]

On Tue, Jul 10, 2007 at 01:52:47PM -0700, Christoph Lameter wrote:
> On Sun, 8 Jul 2007, Andi Kleen wrote:
> 
> > I would say the main drawback of switchable and queued locks 
> > would be also that they require a larger spinlock_t thus increasing
> > cache usage
> 
> Right. Zoran Radovic has shown that queued locks are inferior 
> to other approaches. The best approach that he found in his research were 
> the HBO locks that are somewhat more intelligent form of spinlocks.
> 
> http://user.it.uu.se/~zoranr/
> http://www.it.uu.se/research/group/uart/projects/nucasynch/
> 
> Paper on the issue with measurements:
> http://www.it.uu.se/research/publications/lic/2003-008/2003-008.pdf


OK, maybe I do have my terminology wrong -- we'll call them FIFO locks
or ticket locks. The point is not to improve performance of the contended
case (although they may have slightly better contended case characteristicds),
but to improve worst case latency and improve fairness.

BTW. some advanced congestion algorithms like HBO may find these ticket
locks useful because you can see immediately how many CPUs are contending
the lock, and spinners know how many CPUs are in front of them. That info
could be fed into the spin backoff scheme.

Re: queued spinlock code and results

[Christoph Lameter]

On Wed, 11 Jul 2007, Nick Piggin wrote:

> BTW. some advanced congestion algorithms like HBO may find these ticket
> locks useful because you can see immediately how many CPUs are contending
> the lock, and spinners know how many CPUs are in front of them. That info
> could be fed into the spin backoff scheme.

That would mean having to keep a lot of status information for a spinlock. 
Gets pretty complicated.

The RT tree already converts spinlocks to sleeping locks? If we want to be 
that complicated then maybe going with one sophisticated lock type for all 
would be the solution.

Re: queued spinlock code and results

[Nick Piggin]

On Tue, Jul 10, 2007 at 07:26:10PM -0700, Christoph Lameter wrote:
> On Wed, 11 Jul 2007, Nick Piggin wrote:
> 
> > BTW. some advanced congestion algorithms like HBO may find these ticket
> > locks useful because you can see immediately how many CPUs are contending
> > the lock, and spinners know how many CPUs are in front of them. That info
> > could be fed into the spin backoff scheme.
> 
> That would mean having to keep a lot of status information for a spinlock. 
> Gets pretty complicated.
 
Did you look at the implementation? It takes 2 bytes on x86 and is almost
the same code size and speed as the existing locks.


> The RT tree already converts spinlocks to sleeping locks? If we want to be 
> that complicated then maybe going with one sophisticated lock type for all 
> would be the solution.

I don't want to convert spinlocks to sleeping locks though.