Skip to contentSkip to conversation

i386: spinlock optimization

PATCH Chuck Ebbert 2 participants 2 messages Oct 15, 2005

lore
Share & tools
lore
#0 lore raw

In-Reply-To: <[email protected]>

Quoted 3 lines · Andi Kleen

I doubt your change adds any noticeable delay on a aggressive OOO CPU, which are pretty much all modern x86s. It's probably a nop.

Well it certainly improves the spinlock fairness when owner releases
the lock and tries to re-acquire it. And on the test machine with a slow bus my program runs faster even though the spinlock ping-pongs more often with the new code than with the old. ("Total runs" == number of times spinlock changes hands during test run; "run length" == how many cycles in a row the current owner held the spinlock.) Timer interrupts skew these results a bit by stealing the CPU, so don't take them too literally.

--------------------------------------------
Dual Pentium II Xeon 350 running 2.6.14-rc4:
--------------------------------------------

$ gcc -O2 -Wall -o spintest.o -DSETAFFINITY=2 -DFAST_SPINLOCK=0 -mcpu=pentium2 spintest.c
$ ./spintest.o
Parent CPU 1, child CPU 0, using old code for lock
CPU clocks: 2066947815
Parent did: 5033294 of 10000001 iterations
Run length histogram:
   1: 4
   2: 105
   3: 1161
   4: 502
   5: 113
   6: 130
   7: 56
   8: 54
   9: 81
  10: 60
  11: 72
  12: 57
  13: 72
  14: 43
  15: 85
Quoted 1 line

=16: 94661

Total runs 97256, longest was 2713 iterations, average was 102

$ gcc -O2 -Wall -o spintest.o -DSETAFFINITY=2 -DFAST_SPINLOCK=1 -mcpu=pentium2 spintest.c
$ ./spintest.o
Parent CPU 1, child CPU 0, using new code for lock
CPU clocks: 2818166922
Parent did: 4148727 of 10000001 iterations
Run length histogram:
   1: 52346
   2: 383050
   3: 137185
   4: 42970
   5: 36475
   6: 8407
   7: 11177
   8: 2666
   9: 1033
  10: 791
  11: 763
  12: 870
  13: 726
  14: 1075
  15: 1041
Quoted 1 line

=16: 68272

Total runs 748847, longest was 3488 iterations, average was 13

-----------------------------------------------------------------
Dual Pentium II OverDrive 333 with Socket 8 bus running 2.6.13.4:
-----------------------------------------------------------------

$ gcc -O2 -Wall -DSETAFFINITY=3 -DFAST_SPINLOCK=0 -o spintest.o -mcpu=pentium2 spintest.c
$ ./spintest.o
Parent CPU 1, child CPU 0, using old code for lock
CPU clocks: 5635093038
Parent did: 4825431 of 10000001 iterations
Run length histogram:
   1: 2264420
   2: 1137639
   3: 565597
   4: 7039
   5: 560015
   6: 5832
   7: 240
   8: 128
   9: 82
  10: 37
  11: 24
  12: 11
  13: 16
  14: 20
  15: 21
Quoted 1 line

=16: 3312

Total runs 4544433, longest was 31193 iterations, average was 2

$ gcc -O2 -Wall -DSETAFFINITY=3 -DFAST_SPINLOCK=1 -o spintest.o -mcpu=pentium2 spintest.c
$ ./spintest.o
Parent CPU 1, child CPU 0, using new code for lock
CPU clocks: 5250078921
Parent did: 4831071 of 10000001 iterations
Run length histogram:
   1: 2792457
   2: 2596109
   3: 201958
   4: 28941
   5: 82932
   6: 8071
   7: 518
   8: 207
   9: 75
  10: 58
  11: 38
  12: 11
  13: 6
  14: 6
  15: 8
Quoted 1 line

=16: 3254

Total runs 5714649, longest was 29512 iterations, average was 1

-------------
Test program:
-------------

/* spinlock test
*
* Tests Linux spinlock fairness on SMP i386 machine.
* 32-bit spinlocks instead of Linux's 8-bit locks. */

/* number of tests */
#ifndef ITERS
#define ITERS 10000000
#endif

/* cpu to run parent process; child will use !PARENT_CPU */ #ifndef PARENT_CPU
#define PARENT_CPU 1
#endif

/* use faster spinlock code */
#ifndef FAST_SPINLOCK
#define FAST_SPINLOCK 0
#endif

/* change this to match your version of glibc -- "3" means use 3 args */ #ifndef SETAFFINITY
#define SETAFFINITY 3
#endif

#if SETAFFINITY == 3
#define setaffinity(pid, mask) sched_setaffinity((pid), sizeof(mask), &(mask)) #else /* 2 args */
#define setaffinity(pid, mask) sched_setaffinity((pid), &(mask)) #endif

#define _GNU_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <fcntl.h>
#include <sched.h>
#include <sys/ptrace.h>
#include <sys/wait.h>
#include <sys/mman.h>
#include <asm/user.h>

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

#define RDTSCLL(r) asm volatile("rdtsc" : "=A" (r))

unsigned long long tsc1, tsc2;
cpu_set_t cpuset0, cpuset1;
int test = 1; /* for testing -- starts unlocked */ int strt = 0; /* sync startup -- starts locked */ unsigned int i, runs;
int stk[2048];
int shrd_iters __attribute__ ((aligned(64))); struct stats

{
	unsigned int iters;
	unsigned int prev;
	unsigned int run, max_run;
	unsigned int hist[16];
};

struct stats p __attribute__ ((aligned(64)));
struct stats c __attribute__ ((aligned(64)));

static inline void __raw_spin_lock(int *l)

{
	asm volatile(
		"\n1:\t"
		"lock ; decl %0\n\t"
		"jns 3f\n"
		"2:\t"
		"rep;nop\n\t"
		"cmpl $0,%0\n\t"
#if FAST_SPINLOCK == 1
		"jg 1b\n\t"
		"jmp 2b\n"
#else
		"jle 2b\n\t"
		"jmp 1b\n"
#endif
		"3:\n\t"
		:"=m" (*l) : : "memory");
}

static inline void __raw_spin_unlock(int *l)

{
	asm volatile("movl $1,%0"
		     : "=m" (*l) : : "memory");
}

int do_child(void *vp)

{
	CPU_SET(!PARENT_CPU, &cpuset1);
	if (unlikely(setaffinity(0, cpuset1)))
		perror("child setaffinity");

	__raw_spin_unlock(&strt); /* release parent  */
again:
	__raw_spin_lock(&test);
	c.iters++;
	if (shrd_iters == c.prev)
		c.run++;
	else {
		if (c.run > c.max_run)
			c.max_run = c.run;
		c.hist[c.run <= 15 ? c.run : 15]++;
		c.run = 0;
	}
	if (likely(++shrd_iters < ITERS)) {
		c.prev = shrd_iters;
		__raw_spin_unlock(&test);
		goto again;
	}
	__raw_spin_unlock(&test);

	return 0;
}

int main(int argc, char * const argv[])

{
	CPU_SET(PARENT_CPU, &cpuset0);
	if (unlikely(setaffinity(0, cpuset0)))
		perror("parent setaffinity");

	clone(do_child, &stk[2047], CLONE_VM, 0);
	__raw_spin_lock(&strt); /* wait for child to init  */

	RDTSCLL(tsc1);
again:
	__raw_spin_lock(&test);
	p.iters++;
	if (shrd_iters == p.prev)
		p.run++;
	else {
		if (p.run > p.max_run)
			p.max_run = p.run;
		p.hist[p.run <= 15 ? p.run : 15]++;
		p.run = 0;
	}
	if (likely(++shrd_iters < ITERS)) {
		p.prev = shrd_iters;
		__raw_spin_unlock(&test);
		goto again;
	}
	__raw_spin_unlock(&test);
	RDTSCLL(tsc2);

	printf("Parent CPU %d, child CPU %d, ", PARENT_CPU, !PARENT_CPU);
	printf("using %s code for lock\n", FAST_SPINLOCK == 1 ? "new" : "old");
	printf("CPU clocks: %llu\n", tsc2 - tsc1);
	printf("Parent did: %u of %u iterations\n", p.iters, shrd_iters);
	printf("Run length histogram:\n");
	for (i = 0; i < 16; i++) {
		printf ("%s%2u: %u\n", i == 15 ? ">=" : "  ",
			i + 1, p.hist[i] + c.hist[i]);
		runs += p.hist[i] + c.hist[i];
	}
	printf("Total runs %u, longest was %u iterations, average was %u\n",
		runs, p.max_run > c.max_run ? p.max_run : c.max_run,
		shrd_iters / runs);

	return 0;
}

__
Chuck

#1 lore raw
Quoted 9 lines · Chuck Ebbert

Parent CPU 1, child CPU 0, using old code for lock CPU clocks: 2066947815
Parent CPU 1, child CPU 0, using new code for lock CPU clocks: 2818166922

Parent CPU 1, child CPU 0, using old code for lock CPU clocks: 5635093038
Parent CPU 1, child CPU 0, using new code for lock CPU clocks: 5250078921

your numbers show that for the first box, there's a 36% net slowdown resulting from the new code. On the other (older) box, there's a 7% speedup from the new code.

i ran the code on two newer boxes, 2.4 and 3.4 GHz Xeons, on two sibling CPUs sharing the same physical CPU and on two different CPUs as well:

HT non-siblings [Xeon 2.40GHz], 1% slowdown:

Parent CPU 2, child CPU 0, using old code for lock CPU clocks: 6712771070
Parent CPU 2, child CPU 0, using new code for lock CPU clocks: 6787556068

HT siblings [Xeon 2.40GHz], 14% speedup:

Parent CPU 1, child CPU 0, using old code for lock CPU clocks: 3587124593
Parent CPU 1, child CPU 0, using new code for lock CPU clocks: 3079647206

HT non-siblings [Xeon 3.40GHz], 3% speedup:

Parent CPU 2, child CPU 0, using old code for lock CPU clocks: 8486900988
Parent CPU 2, child CPU 0, using new code for lock CPU clocks: 8255818784

HT siblings [Xeon 3.40GHz], 1% slowdown:

Parent CPU 3, child CPU 0, using old code for lock CPU clocks: 3684195488
Parent CPU 3, child CPU 0, using new code for lock CPU clocks: 3739797320

but given that the code is a drastic slowdown on older boxes (and results in higher memory bus traffic, which may slow down other CPUs too, which effect isnt measured here), i dont think we should apply the patch, just yet - up until the point it becomes a clear winner on new CPUs.

(in fact the ping-pong effect should be worse if more than 2 CPUs contend for the spinlock.)

could someone run the tests on a dual-core box too?

Ingo