code review 4711045: runtime: improve Linux mutex

runtime: improve Linux mutex
The implementation is hybrid active/passive spin/blocking mutex.
The design minimizes amount of context switches and futex calls.
The idea is that all critical sections in runtime are intentially
small, so pure blocking mutex behaves badly causing
a lot of context switches, thread parking/unparking and kernel calls.
Note that some synthetic benchmarks become somewhat slower,
that's due to increased contention on other data structures,
it should not affect programs that do any real work.

On 2 x Intel E5620, 8 HT cores, 2.4GHz
benchmark                     old ns/op    new ns/op    delta
BenchmarkSelectContended         521.00       503.00   -3.45%
BenchmarkSelectContended-2       661.00       320.00  -51.59%
BenchmarkSelectContended-4      1139.00       629.00  -44.78%
BenchmarkSelectContended-8      2870.00       878.00  -69.41%
BenchmarkSelectContended-16     5276.00       818.00  -84.50%
BenchmarkChanContended           112.00       103.00   -8.04%
BenchmarkChanContended-2         631.00       174.00  -72.42%
BenchmarkChanContended-4         682.00       272.00  -60.12%
BenchmarkChanContended-8        1601.00       520.00  -67.52%
BenchmarkChanContended-16       3100.00       372.00  -88.00%
BenchmarkChanSync                253.00       239.00   -5.53%
BenchmarkChanSync-2             5030.00      4648.00   -7.59%
BenchmarkChanSync-4             4826.00      4694.00   -2.74%
BenchmarkChanSync-8             4778.00      4713.00   -1.36%
BenchmarkChanSync-16            5289.00      4710.00  -10.95%
BenchmarkChanProdCons0           273.00       254.00   -6.96%
BenchmarkChanProdCons0-2         599.00       400.00  -33.22%
BenchmarkChanProdCons0-4        1168.00       659.00  -43.58%
BenchmarkChanProdCons0-8        2831.00      1057.00  -62.66%
BenchmarkChanProdCons0-16       4197.00      1037.00  -75.29%
BenchmarkChanProdCons10          150.00       140.00   -6.67%
BenchmarkChanProdCons10-2        607.00       268.00  -55.85%
BenchmarkChanProdCons10-4       1137.00       404.00  -64.47%
BenchmarkChanProdCons10-8       2115.00       828.00  -60.85%
BenchmarkChanProdCons10-16      4283.00       855.00  -80.04%
BenchmarkChanProdCons100         117.00       110.00   -5.98%
BenchmarkChanProdCons100-2       558.00       218.00  -60.93%
BenchmarkChanProdCons100-4       722.00       287.00  -60.25%
BenchmarkChanProdCons100-8      1840.00       431.00  -76.58%
BenchmarkChanProdCons100-16     3394.00       448.00  -86.80%
BenchmarkChanProdConsWork0      2014.00      1996.00   -0.89%
BenchmarkChanProdConsWork0-2    1207.00      1127.00   -6.63%
BenchmarkChanProdConsWork0-4    1913.00       611.00  -68.06%
BenchmarkChanProdConsWork0-8    3016.00       949.00  -68.53%
BenchmarkChanProdConsWork0-16   4320.00      1154.00  -73.29%
BenchmarkChanProdConsWork10     1906.00      1897.00   -0.47%
BenchmarkChanProdConsWork10-2   1123.00      1033.00   -8.01%
BenchmarkChanProdConsWork10-4   1076.00       571.00  -46.93%
BenchmarkChanProdConsWork10-8   2748.00      1096.00  -60.12%
BenchmarkChanProdConsWork10-16  4600.00      1105.00  -75.98%
BenchmarkChanProdConsWork100    1884.00      1852.00   -1.70%
BenchmarkChanProdConsWork100-2  1235.00      1146.00   -7.21%
BenchmarkChanProdConsWork100-4  1217.00       619.00  -49.14%
BenchmarkChanProdConsWork100-8  1534.00       509.00  -66.82%
BenchmarkChanProdConsWork100-16 4126.00       918.00  -77.75%
BenchmarkSyscall                  34.40        33.30   -3.20%
BenchmarkSyscall-2               160.00       121.00  -24.38%
BenchmarkSyscall-4               131.00       136.00   +3.82%
BenchmarkSyscall-8               139.00       131.00   -5.76%
BenchmarkSyscall-16              161.00       168.00   +4.35%
BenchmarkSyscallWork             950.00       950.00   +0.00%
BenchmarkSyscallWork-2           481.00       480.00   -0.21%
BenchmarkSyscallWork-4           268.00       270.00   +0.75%
BenchmarkSyscallWork-8           156.00       169.00   +8.33%
BenchmarkSyscallWork-16          188.00       184.00   -2.13%
BenchmarkSemaSyntNonblock         36.40        35.60   -2.20%
BenchmarkSemaSyntNonblock-2       81.40        45.10  -44.59%
BenchmarkSemaSyntNonblock-4      126.00       108.00  -14.29%
BenchmarkSemaSyntNonblock-8      112.00       112.00   +0.00%
BenchmarkSemaSyntNonblock-16     110.00       112.00   +1.82%
BenchmarkSemaSyntBlock            35.30        35.30   +0.00%
BenchmarkSemaSyntBlock-2         118.00       124.00   +5.08%
BenchmarkSemaSyntBlock-4         105.00       108.00   +2.86%
BenchmarkSemaSyntBlock-8         101.00       111.00   +9.90%
BenchmarkSemaSyntBlock-16        112.00       118.00   +5.36%
BenchmarkSemaWorkNonblock        810.00       811.00   +0.12%
BenchmarkSemaWorkNonblock-2      476.00       414.00  -13.03%
BenchmarkSemaWorkNonblock-4      238.00       228.00   -4.20%
BenchmarkSemaWorkNonblock-8      140.00       126.00  -10.00%
BenchmarkSemaWorkNonblock-16     117.00       116.00   -0.85%
BenchmarkSemaWorkBlock           810.00       811.00   +0.12%
BenchmarkSemaWorkBlock-2         454.00       466.00   +2.64%
BenchmarkSemaWorkBlock-4         243.00       241.00   -0.82%
BenchmarkSemaWorkBlock-8         145.00       137.00   -5.52%
BenchmarkSemaWorkBlock-16        132.00       123.00   -6.82%
BenchmarkContendedSemaphore      123.00       102.00  -17.07%
BenchmarkContendedSemaphore-2     34.80        34.90   +0.29%
BenchmarkContendedSemaphore-4     34.70        34.80   +0.29%
BenchmarkContendedSemaphore-8     34.70        34.70   +0.00%
BenchmarkContendedSemaphore-16    34.80        34.70   -0.29%
BenchmarkMutex                    26.80        26.00   -2.99%
BenchmarkMutex-2                 108.00        45.20  -58.15%
BenchmarkMutex-4                 103.00       127.00  +23.30%
BenchmarkMutex-8                 109.00       147.00  +34.86%
BenchmarkMutex-16                102.00       152.00  +49.02%
BenchmarkMutexSlack               27.00        26.90   -0.37%
BenchmarkMutexSlack-2            149.00       165.00  +10.74%
BenchmarkMutexSlack-4            121.00       209.00  +72.73%
BenchmarkMutexSlack-8            101.00       158.00  +56.44%
BenchmarkMutexSlack-16            97.00       129.00  +32.99%
BenchmarkMutexWork               792.00       794.00   +0.25%
BenchmarkMutexWork-2             407.00       409.00   +0.49%
BenchmarkMutexWork-4             220.00       209.00   -5.00%
BenchmarkMutexWork-8             267.00       160.00  -40.07%
BenchmarkMutexWork-16            315.00       300.00   -4.76%
BenchmarkMutexWorkSlack          792.00       793.00   +0.13%
BenchmarkMutexWorkSlack-2        406.00       404.00   -0.49%
BenchmarkMutexWorkSlack-4        225.00       212.00   -5.78%
BenchmarkMutexWorkSlack-8        268.00       136.00  -49.25%
BenchmarkMutexWorkSlack-16       300.00       300.00   +0.00%
BenchmarkRWMutexWrite100          27.10        27.00   -0.37%
BenchmarkRWMutexWrite100-2        33.10        40.80  +23.26%
BenchmarkRWMutexWrite100-4       113.00        88.10  -22.04%
BenchmarkRWMutexWrite100-8       119.00        95.30  -19.92%
BenchmarkRWMutexWrite100-16      148.00       109.00  -26.35%
BenchmarkRWMutexWrite10           29.60        29.40   -0.68%
BenchmarkRWMutexWrite10-2        111.00        61.40  -44.68%
BenchmarkRWMutexWrite10-4        270.00       208.00  -22.96%
BenchmarkRWMutexWrite10-8        204.00       185.00   -9.31%
BenchmarkRWMutexWrite10-16       261.00       190.00  -27.20%
BenchmarkRWMutexWorkWrite100    1040.00      1036.00   -0.38%
BenchmarkRWMutexWorkWrite100-2   593.00       580.00   -2.19%
BenchmarkRWMutexWorkWrite100-4   470.00       365.00  -22.34%
BenchmarkRWMutexWorkWrite100-8   468.00       289.00  -38.25%
BenchmarkRWMutexWorkWrite100-16  604.00       374.00  -38.08%
BenchmarkRWMutexWorkWrite10      951.00       951.00   +0.00%
BenchmarkRWMutexWorkWrite10-2   1001.00       928.00   -7.29%
BenchmarkRWMutexWorkWrite10-4   1555.00      1006.00  -35.31%
BenchmarkRWMutexWorkWrite10-8   2085.00      1171.00  -43.84%
BenchmarkRWMutexWorkWrite10-16  2082.00      1614.00  -22.48%

[dvyukov, 2011-07-21 18:05:45]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[rsc, 2011-07-21 18:09:46]

I am afraid of sacrificing the GOMAXPROCS=1 case
for performance in the other cases.  Does it make
sense to check runtime.gomaxprocs before spinning?

Russ

[dvyukov, 2011-07-21 19:38:00]

On 2011/07/21 18:09:46, rsc wrote:
> I am afraid of sacrificing the GOMAXPROCS=1 case
> for performance in the other cases.  Does it make
> sense to check runtime.gomaxprocs before spinning?

When GOMAXPROCS=1 there is generally only 1 thread running, so slow path is
never taken. If there are more threads due to sys/cgo calls and/or thread to
gorotuine locking, then it's nothing different than case of GOMAXPROCS>1.
Active spinning makes no sense when there is only 1 hardware thread or a user
limits it to 1 (think of running a Go program under taskset). However, passive
spinning still makes perfect sense in this case.
I am thinking about adding public API for querying various system parameters
(think of sysconf()) like number of hardware threads, cores, NUMA nodes, etc.
Then it will be easy to turn off active spinning in case of only 1 hardware
thread (I think it mostly makes sense for ARM as of now). Moreover other
parameters most likely will require further static and dynamic tuning - I've
done very rough tuning only on 2 machines.
I would prefer to commit it as is for now if I am not missing any other issues
of course.

[iant, 2011-07-22 05:38:06]

FYI

http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/386/sys.s
File src/pkg/runtime/linux/386/sys.s (right):

http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/386/sy...
src/pkg/runtime/linux/386/sys.s:320: MOVL	$24, AX
For 32-bit GNU/Linux sched_yield is syscall 158.  It's only syscall 24 on 64-bit
GNU/Linux.

http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/thread.c
File src/pkg/runtime/linux/thread.c (right):

http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/thread...
src/pkg/runtime/linux/thread.c:70: // If any procs are sleeping on addr, wake up
at most one.
I think the comment is wrong: looks like it now wakes at most cnt processes.

http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/thread...
src/pkg/runtime/linux/thread.c:120: prv = MUTEX_CONTENDED;
I don't understand this.  If v == MUTEX_CONTENDED && i < TOTAL_SPIN, then we
just set l->key to MUTEX_LOCKED.  In that case it seems to me that we now hold
the lock, and should not sleep.

[dvyukov, 2011-07-22 13:53:44]

On 2011/07/22 05:38:06, iant wrote:
> FYI
> 
>
http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/386/sys.s
> File src/pkg/runtime/linux/386/sys.s (right):
> 
>
http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/386/sy...
> src/pkg/runtime/linux/386/sys.s:320: MOVL	$24, AX
> For 32-bit GNU/Linux sched_yield is syscall 158.  It's only syscall 24 on
64-bit
> GNU/Linux.

OMG! It was getuid()


>
http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/thread.c
> File src/pkg/runtime/linux/thread.c (right):
> 
>
http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/thread...
> src/pkg/runtime/linux/thread.c:70: // If any procs are sleeping on addr, wake
up
> at most one.
> I think the comment is wrong: looks like it now wakes at most cnt processes.

Done.


>
http://codereview.appspot.com/4711045/diff/22001/src/pkg/runtime/linux/thread...
> src/pkg/runtime/linux/thread.c:120: prv = MUTEX_CONTENDED;
> I don't understand this.  If v == MUTEX_CONTENDED && i < TOTAL_SPIN, then we
> just set l->key to MUTEX_LOCKED.  In that case it seems to me that we now hold
> the lock, and should not sleep.

MUTEX_CONTENDED means contended *and* locked (I've added appropriate comment).
So when a thread changes MUTEX_CONTENDED to MUTEX_LOCKED, it does not get
ownership. The idea is that while some threads are spinning trying to obtain the
lock, owner does not need to wake a waiter in unlock, because a spinning thread
will obtain the lock and then he will wake waiters.
So unlock wakes waiters iff there are no spinning threads.
Note that when a thread changes MUTEX_CONTENDED to MUTEX_LOCKED, it remembers
that there are waiters in prv=MUTEX_CONTENDED. So when it will finally lock the
mutex, it will set the state to MUTEX_CONTENDED. Then in unlock() it will see
that state=MUTEX_CONTENDED and wake a waiter.

[dvyukov, 2011-07-22 13:54:08]

Hello golang-dev@googlegroups.com, rsc@golang.org, iant@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[iant, 2011-07-22 15:00:43]

FYI

Thanks for the explanation.  The code looks OK to me as far as I can tell.

Like Russ I'm concerned about the effect on a single core machine.  This is easy
enough to determine on GNU/Linux: call uname; if the u.uts.version field has SMP
in it, the kernel was configured to have SMP support.

[msolo, 2011-07-22 18:27:37]

FYI

I patched this into a pre-production test of a server app I've been working on,
to get a sense of real-worth benefits.

With GOMAXPROCS=32, I find the server throughput unmodified, but aggregate cpu
time is down slightly:

user cpu -2.71%
sys cpu -12.7%


On 2011/07/22 15:00:43, iant wrote:
> FYI
> 
> Thanks for the explanation.  The code looks OK to me as far as I can tell.
> 
> Like Russ I'm concerned about the effect on a single core machine.  This is
easy
> enough to determine on GNU/Linux: call uname; if the u.uts.version field has
SMP
> in it, the kernel was configured to have SMP support.

[dvyukov, 2011-07-22 18:42:05]

On 2011/07/22 18:27:37, msolo wrote:
> FYI
> 
> I patched this into a pre-production test of a server app I've been working
on,
> to get a sense of real-worth benefits.
> 
> With GOMAXPROCS=32, I find the server throughput unmodified, but aggregate cpu
> time is down slightly:
> 
> user cpu -2.71%
> sys cpu -12.7%

Thanks for evaluating it!
May it be so that throughput is limited by other things
(disk/network/memory/client throughput)?
I think reduction of cpu time may be considered as positive thing anyway.

[dvyukov, 2011-07-22 19:24:15]

Hello golang-dev@googlegroups.com, rsc@golang.org, iant@golang.org,
msolo@gmail.com (cc: golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2011-07-22 19:26:45]

Note that I've added XORQ DX,DX to runtime.write(). Can't it be so that high 32
bits of RDX contain garbage?

[fw, 2011-07-22 20:02:06]

> Note that I've added XORQ DX,DX to runtime.write(). Can't it be so that
> high 32 bits of RDX contain garbage?

A 32 bit load into a 64 bit register automatically clears the upper
part of the register on amd64, so this instruction appears to be
unnecessary.

[dvyukov, 2011-07-22 20:48:45]

On 2011/07/22 20:02:06, fw_deneb.enyo.de wrote:
> > Note that I've added XORQ DX,DX to runtime.write(). Can't it be so that
> > high 32 bits of RDX contain garbage?
> 
> A 32 bit load into a 64 bit register automatically clears the upper
> part of the register on amd64, so this instruction appears to be
> unnecessary.

Hummm... isn't "MOVL 24(SP), DX" 32-bit load to 32-bit register (EDX) that
leaves high 32 bits intact?

[iant, 2011-07-22 21:27:02]

On amd64 a 32-bit load to a 64-bit register zero extends.

[fw, 2011-07-23 07:01:06]

> On 2011/07/22 20:02:06, fw_deneb.enyo.de wrote:
>> > Note that I've added XORQ DX,DX to runtime.write(). Can't it be so
> that
>> > high 32 bits of RDX contain garbage?
>
>> A 32 bit load into a 64 bit register automatically clears the upper
>> part of the register on amd64, so this instruction appears to be
>> unnecessary.
>
> Hummm... isn't "MOVL 24(SP), DX" 32-bit load to 32-bit register (EDX)
> that leaves high 32 bits intact?

If this is equivalent to "movl %esp(24), %edx", then it's a load into
%rdx, clearing the upper 32 bits.

[rsc, 2011-07-24 20:14:53]

http://codereview.appspot.com/4711045/diff/9004/src/cmd/6l/optab.c
File src/cmd/6l/optab.c (right):

http://codereview.appspot.com/4711045/diff/9004/src/cmd/6l/optab.c#newcode536
src/cmd/6l/optab.c:536: uchar	ypause[] =
Delete; use ynone instead.

http://codereview.appspot.com/4711045/diff/9004/src/cmd/8l/optab.c
File src/cmd/8l/optab.c (right):

http://codereview.appspot.com/4711045/diff/9004/src/cmd/8l/optab.c#newcode351
src/cmd/8l/optab.c:351: uchar	ypause[] =
Delete; use ynone.

http://codereview.appspot.com/4711045/diff/9004/src/libmach/8db.c
File src/libmach/8db.c (right):

http://codereview.appspot.com/4711045/diff/9004/src/libmach/8db.c#newcode1434
src/libmach/8db.c:1434: [0x102] =	{ 0,0,		"PAUSE" },
Adding this line doesn't do anything.
This is a table indexed by the first byte of the instruction.
0x100 and 0x101 are fake entries used explicitly below.

It's fine if you want to just not edit this file.
As written PAUSE will disassemble to REP; NOP,
which is close enough.

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/linux/thread.c
File src/pkg/runtime/linux/thread.c (right):

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/linux/thread....
src/pkg/runtime/linux/thread.c:30: MUTEX_CONTENDED = 3, // contended and locked
Why is this 3 and not 2?
Unless there's a reason, make it 2.

Also, the salient point about this state seems to be
that a thread is sleeping and needs to be woken up,
so maybe call it 

MUTEX_SLEEPING = 2,  // some thread is sleeping on this mutex

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/linux/thread....
src/pkg/runtime/linux/thread.c:101: fd = runtime·open((byte*)"/proc/version",
O_RDONLY, 0);
include O_CLOEXEC flag to be thread safe

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/linux/thread....
src/pkg/runtime/linux/thread.c:119: 
Please insert a comment here explaining what the
possible lock states are, like the old implementation had
(but with the new details of course).

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/linux/thread....
src/pkg/runtime/linux/thread.c:121: futexlock(Lock *l)
I find this function very difficult to read.  Is this a standard algorithm?
I suggest the following alternate phrasing of it.


futexlock(Lock *l)
{
	uint32 i, v, new, wait, spin;

	// Speculative grab for lock.
	v = runtime.xchg(&l->key, MUTEX_LOCKED);
	if(v == MUTEX_UNLOCKED)
		return;

	if(proccount == 0)
		initproccount();

	// wait is either MUTEX_LOCKED or MUTEX_SLEEPING
	// depending on whether there is a thread sleeping
	// on this mutex.  If we ever change l->key from
	// MUTEX_SLEEPING to some other value, we must be
	// careful to change it back to MUTEX_SLEEPING before
	// returning, to ensure that the sleeping thread gets
	// its wakeup call.
	wait = v;

	// On uniprocessor's, no point spinning.
	// On multiprocessors, spin for ACTIVE_SPIN attempts.
	if(proccount <= 1)
		spin = 0;
	else
		spin = ACTIVE_SPIN;

	for(;;) {
		// Try for lock, spinning.
		for(i = 0; i < spin; i++) {
			while(l->key == MUTEX_UNLOCKED)
				if(runtime.cas(&l->key, MUTEX_UNLOCKED, wait))
						return;
			runtime.procyield(ACTIVE_SPIN_CNT);
		}

		// Try for lock, rescheduling.
		for(; i < TOTAL_SPIN; i++) {
			while(l->key == MUTEX_UNLOCKED)
				if(runtime.cas(&l->key, MUTEX_UNLOCKED, wait))
					return;
			runtime.osyield();
		}

		// Sleep.
		wait = MUTEX_SLEEPING;
		v = runtime.xchg(&l->key, MUTEX_SLEEPING);
		if(v == MUTEX_UNLOCKED)
			return;
		futexsleep(&l->key, MUTEX_SLEEPING, &shorttime);
	}
}

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/runtime.h#new...
src/pkg/runtime/runtime.h:604: void	runtime·schedyield();
(void).

Also, please call this osyield.
schedyield makes it sound like it has to do with
the runtime scheduler, which it doesn't.

[dvyukov, 2011-07-25 16:34:55]

Hello rsc@golang.org, iant@golang.org, msolo@gmail.com, fw@deneb.enyo.de (cc:
golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2011-07-25 16:37:24]

On 2011/07/22 21:27:02, iant wrote:
> On amd64 a 32-bit load to a 64-bit register zero extends.

I can't find the statement in the Instruction Set Reference. But I see that it
works this way.
Fixed.

[dvyukov, 2011-07-25 16:44:18]

>
http://codereview.appspot.com/4711045/diff/9004/src/pkg/runtime/linux/thread....
> src/pkg/runtime/linux/thread.c:121: futexlock(Lock *l)
> I find this function very difficult to read.  Is this a standard algorithm?
> I suggest the following alternate phrasing of it.


It's not a standard algorithm. I've combined it from a known pieces. In my
algorithm threads change SLEEPING to LOCKED during spinning, so that unlocking
thread does not need to do kernel futex call. Your version does not seem to do
it. However, the main performance gain comes from spinning (both active and
passive), I've benchmarked both versions on some benchmarks and I can't conclude
which one is faster - there is high fluctuation, sometimes one version is
faster, sometimes - another.
I think we can commit your version for now, and tune it later if we see
necessity and decide on which version is better.


Everything else is Done.

[rsc, 2011-07-25 17:06:08]

> It's not a standard algorithm. I've combined it from a known pieces. In
> my algorithm threads change SLEEPING to LOCKED during spinning

But it does: that happens as part of the
opportunistic grab.

[rsc, 2011-07-25 17:12:04]

http://codereview.appspot.com/4711045/diff/32003/src/pkg/runtime/linux/thread.c
File src/pkg/runtime/linux/thread.c (right):

http://codereview.appspot.com/4711045/diff/32003/src/pkg/runtime/linux/thread...
src/pkg/runtime/linux/thread.c:110: if(runtime·strstr(buf, (byte*)"SMP"))
This checks whether an SMP kernel is being used.
That doesn't imply that it's running on a multiprocessor.
Isn't there some other file we can look at instead?
I'd suggest looking at /proc/cpuinfo but it's so big.

http://codereview.appspot.com/4711045/diff/32003/src/pkg/runtime/linux/thread...
src/pkg/runtime/linux/thread.c:122: // the latter - by a short sleeping time.
I don't believe this is true.  If there is a sleeping thread when
the state is not MUTEX_SLEEPING, it is because some other thread
is trying to acquire the lock *and* has wait == MUTEX_SLEEPING,
so it will eventually change l->key back to MUTEX_SLEEPING.
The short time should not matter at all.
Can you try with a long time?

[dvyukov, 2011-07-25 17:13:45]

On 2011/07/25 17:06:08, rsc wrote:
> > It's not a standard algorithm. I've combined it from a known pieces. In
> > my algorithm threads change SLEEPING to LOCKED during spinning
> 
> But it does: that happens as part of the
> opportunistic grab.

My algo does it all other the time - during spinning and after sleep.

[rsc, 2011-07-25 17:25:40]

do you agree that the comment does not
describe the current code?  if so, please
update the comment.

[dvyukov, 2011-07-25 17:26:08]

On 2011/07/25 17:12:04, rsc wrote:
>
http://codereview.appspot.com/4711045/diff/32003/src/pkg/runtime/linux/thread.c
> File src/pkg/runtime/linux/thread.c (right):
> 
>
http://codereview.appspot.com/4711045/diff/32003/src/pkg/runtime/linux/thread...
> src/pkg/runtime/linux/thread.c:110: if(runtime·strstr(buf, (byte*)"SMP"))
> This checks whether an SMP kernel is being used.
> That doesn't imply that it's running on a multiprocessor.
> Isn't there some other file we can look at instead?
> I'd suggest looking at /proc/cpuinfo but it's so big.


We can call sysconf(_SC_NPROCESSORS_ONLN), but I need to force my way through
libc to do it.


>
http://codereview.appspot.com/4711045/diff/32003/src/pkg/runtime/linux/thread...
> src/pkg/runtime/linux/thread.c:122: // the latter - by a short sleeping time.
> I don't believe this is true.  If there is a sleeping thread when
> the state is not MUTEX_SLEEPING, it is because some other thread
> is trying to acquire the lock *and* has wait == MUTEX_SLEEPING,
> so it will eventually change l->key back to MUTEX_SLEEPING.
> The short time should not matter at all.
> Can you try with a long time?


Mmmm... it's not quite that way. Consider:
1. Mutex is LOCKED by thread 0.
2. Thread 1 tries to acquire it, and eventually sets state to SLEEPING.
3. Thread 2 does initial xchg(&key, LOCKED), resets SLEEPING state and remembers
it in wait.
4. Thread 3 tries to acquire it, and eventually sets state to SLEEPING.
5. Thread 2 does xchg(&key, SLEEPING) before sleep, at this point thread 2 need
to remember "2 sleeps" in wait, however it can remember at most 1 there.
6. Thread 0 unlocks the mutex and wakes thread 2.
7. Thread 2 locks the mutex, and sets state to SLEEPING.
8. Thread 2 unlocks the mutex and wakes thread 1.
9. Thread 1 locks the mutex, but sets state to LOCKED.
10. Thread 1 unlocks the mutex, but does NOT wake thread 3.

[rsc, 2011-07-25 17:29:44]

> 1. Mutex is LOCKED by thread 0.
> 2. Thread 1 tries to acquire it, and eventually sets state to SLEEPING.
> 3. Thread 2 does initial xchg(&key, LOCKED), resets SLEEPING state and
> remembers it in wait.
> 4. Thread 3 tries to acquire it, and eventually sets state to SLEEPING.
> 5. Thread 2 does xchg(&key, SLEEPING) before sleep, at this point thread
> 2 need to remember "2 sleeps" in wait, however it can remember at most 1
> there.
> 6. Thread 0 unlocks the mutex and wakes thread 2.
> 7. Thread 2 locks the mutex, and sets state to SLEEPING.
> 8. Thread 2 unlocks the mutex and wakes thread 1.
> 9. Thread 1 locks the mutex, but sets state to LOCKED.

Thread 1 was sleeping.  It will not set the state to LOCKED.

Russ

[rsc, 2011-07-25 17:30:36]

> Thread 1 was sleeping.  It will not set the state to LOCKED.

oh, i see.  you didn't use the code i sent.

               // Sleep.
               wait = MUTEX_SLEEPING;
               v = runtime.xchg(&l->key, MUTEX_SLEEPING);
               if(v == MUTEX_UNLOCKED)
                       return;
               futexsleep(&l->key, MUTEX_SLEEPING, &shorttime);

[rsc, 2011-07-25 17:38:45]

On Mon, Jul 25, 2011 at 13:26,  <dvyukov@google.com> wrote:
> We can call sysconf(_SC_NPROCESSORS_ONLN), but I need to force my way
> through libc to do it.

Go doesn't link against libc.
If you meant figure out what libc does,
don't use the source.  Use strace.
It looks like it reads the first few lines of /proc/stat
and counts the number that begin with cpu.

Russ

[iant2, 2011-07-25 18:21:20]

dvyukov@google.com writes:

> On 2011/07/22 21:27:02, iant wrote:
>> On amd64 a 32-bit load to a 64-bit register zero extends.
>
> I can't find the statement in the Instruction Set Reference. But I see
> that it works this way.

In my copy of the Intel docs, it's section 3.4.1.1 of book 1,
"General-Purpose registers in 64-Bit Mode."

    When in 64-bit mode, operand size determines the number of valid
    bits in the destination general-purpose register:

    · 64-bit operands generate a 64-bit result in the destination
      general-purpose register.

    · 32-bit operands generate a 32-bit result, zero-extended to a
      64-bit result in the destination general-purpose register.

    · 8-bit and 16-bit operands generate an 8-bit or 16-bit result. The
      upper 56 bits or 48 bits (respectively) of the destination
      general-purpose register are not be modified by the operation. If
      the result of an 8-bit or 16-bit operation is intended for 64-bit
      address calculation, explicitly sign-extend the register to the
      full 64-bits.

Ian

[dvyukov, 2011-07-25 18:30:11]

Hello rsc@golang.org, iant@golang.org, msolo@gmail.com, fw@deneb.enyo.de,
iant@google.com (cc: golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2011-07-25 18:30:55]

On 2011/07/25 18:21:20, iant2 wrote:
> mailto:dvyukov@google.com writes:
> 
> > On 2011/07/22 21:27:02, iant wrote:
> >> On amd64 a 32-bit load to a 64-bit register zero extends.
> >
> > I can't find the statement in the Instruction Set Reference. But I see
> > that it works this way.
> 
> In my copy of the Intel docs, it's section 3.4.1.1 of book 1,
> "General-Purpose registers in 64-Bit Mode."
> 
>     When in 64-bit mode, operand size determines the number of valid
>     bits in the destination general-purpose register:
> 
>     · 64-bit operands generate a 64-bit result in the destination
>       general-purpose register.
> 
>     · 32-bit operands generate a 32-bit result, zero-extended to a
>       64-bit result in the destination general-purpose register.
> 
>     · 8-bit and 16-bit operands generate an 8-bit or 16-bit result. The
>       upper 56 bits or 48 bits (respectively) of the destination
>       general-purpose register are not be modified by the operation. If
>       the result of an 8-bit or 16-bit operation is intended for 64-bit
>       address calculation, explicitly sign-extend the register to the
>       full 64-bits.


Aha! Thank you.
I was looking in the instruction set reference.

[dvyukov, 2011-07-25 18:32:29]

I've fixed what we discussed with Russ wrt missed wakeups. Now threads do long
sleep (1<<30 seconds) again.

I've also fixed detection of SMP machine - I read /proc/stat and look for "cpu1"
string.

[iant2, 2011-07-25 19:03:05]

rsc@golang.org writes:

> This checks whether an SMP kernel is being used.
> That doesn't imply that it's running on a multiprocessor.
> Isn't there some other file we can look at instead?
> I'd suggest looking at /proc/cpuinfo but it's so big.

In practice I think checking for an SMP kernel is fine.  Most GNU/Linux
distros will use an SMP kernel on a multiprocessor and a non-SMP kernel
on a uniprocessor.

Glibc uses this same check to decide whether to use the SMP version of
its mutexes.

Ian

[rsc, 2011-07-25 19:39:59]

> I've also fixed detection of SMP machine - I read /proc/stat and look
> for "cpu1" string.

could you count the number of initial lines
that begin with cpu instead?  i want the
number for the garbage collector too and
it's silly to do it twice.

thanks.

[dvyukov, 2011-07-25 19:47:17]

On 2011/07/25 19:39:59, rsc wrote:
> > I've also fixed detection of SMP machine - I read /proc/stat and look
> > for "cpu1" string.
> 
> could you count the number of initial lines
> that begin with cpu instead?  i want the
> number for the garbage collector too and
> it's silly to do it twice.

I need to add runtime.proccount(), right? It will use /proc/stat on Linux, and
on other platforms it will return GOMAXPROCS for now.
Ultimately it will use GetSystemInfo()/GetLogicalProcessorInfo() on Windows,
"sysctl -a hw"/"system_profiler SPHardwareDataType" on Mac and ??? on Plan9.

[rsc, 2011-07-25 19:48:07]

> I need to add runtime.proccount(), right?

no just leave everything as you have it
but make it return the actual count instead
of 1 or 2.

[dvyukov, 2011-07-26 12:01:23]

Hello rsc@golang.org, iant@golang.org, msolo@gmail.com, fw@deneb.enyo.de,
iant@google.com (cc: golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2011-07-26 12:24:55]

Btw, Russ, in your syscall CL you mentioned some "less artificial server
benchmark". If you have all infrastructure inplace, may you benchmark this CL on
it as well?

[rsc, 2011-07-26 14:54:33]

On Tue, Jul 26, 2011 at 08:24,  <dvyukov@google.com> wrote:
> Btw, Russ, in your syscall CL you mentioned some "less artificial server
> benchmark". If you have all infrastructure inplace, may you benchmark
> this CL on it as well?

msolo already did, and replied earlier in this thread.

[dvyukov, 2011-07-28 10:27:48]

On 2011/07/26 14:54:33, rsc wrote:
> On Tue, Jul 26, 2011 at 08:24,  <mailto:dvyukov@google.com> wrote:
> > Btw, Russ, in your syscall CL you mentioned some "less artificial server
> > benchmark". If you have all infrastructure inplace, may you benchmark
> > this CL on it as well?
> 
> msolo already did, and replied earlier in this thread.

I just thought that was another server.
Anyway PTAL, I've made reusable getproccount().

[rsc, 2011-07-29 16:35:09]

LGTM

[rsc, 2011-07-29 16:44:16]

*** Submitted as http://code.google.com/p/go/source/detail?r=3d02ca6a988b ***

runtime: improve Linux mutex
The implementation is hybrid active/passive spin/blocking mutex.
The design minimizes amount of context switches and futex calls.
The idea is that all critical sections in runtime are intentially
small, so pure blocking mutex behaves badly causing
a lot of context switches, thread parking/unparking and kernel calls.
Note that some synthetic benchmarks become somewhat slower,
that's due to increased contention on other data structures,
it should not affect programs that do any real work.

On 2 x Intel E5620, 8 HT cores, 2.4GHz
benchmark                     old ns/op    new ns/op    delta
BenchmarkSelectContended         521.00       503.00   -3.45%
BenchmarkSelectContended-2       661.00       320.00  -51.59%
BenchmarkSelectContended-4      1139.00       629.00  -44.78%
BenchmarkSelectContended-8      2870.00       878.00  -69.41%
BenchmarkSelectContended-16     5276.00       818.00  -84.50%
BenchmarkChanContended           112.00       103.00   -8.04%
BenchmarkChanContended-2         631.00       174.00  -72.42%
BenchmarkChanContended-4         682.00       272.00  -60.12%
BenchmarkChanContended-8        1601.00       520.00  -67.52%
BenchmarkChanContended-16       3100.00       372.00  -88.00%
BenchmarkChanSync                253.00       239.00   -5.53%
BenchmarkChanSync-2             5030.00      4648.00   -7.59%
BenchmarkChanSync-4             4826.00      4694.00   -2.74%
BenchmarkChanSync-8             4778.00      4713.00   -1.36%
BenchmarkChanSync-16            5289.00      4710.00  -10.95%
BenchmarkChanProdCons0           273.00       254.00   -6.96%
BenchmarkChanProdCons0-2         599.00       400.00  -33.22%
BenchmarkChanProdCons0-4        1168.00       659.00  -43.58%
BenchmarkChanProdCons0-8        2831.00      1057.00  -62.66%
BenchmarkChanProdCons0-16       4197.00      1037.00  -75.29%
BenchmarkChanProdCons10          150.00       140.00   -6.67%
BenchmarkChanProdCons10-2        607.00       268.00  -55.85%
BenchmarkChanProdCons10-4       1137.00       404.00  -64.47%
BenchmarkChanProdCons10-8       2115.00       828.00  -60.85%
BenchmarkChanProdCons10-16      4283.00       855.00  -80.04%
BenchmarkChanProdCons100         117.00       110.00   -5.98%
BenchmarkChanProdCons100-2       558.00       218.00  -60.93%
BenchmarkChanProdCons100-4       722.00       287.00  -60.25%
BenchmarkChanProdCons100-8      1840.00       431.00  -76.58%
BenchmarkChanProdCons100-16     3394.00       448.00  -86.80%
BenchmarkChanProdConsWork0      2014.00      1996.00   -0.89%
BenchmarkChanProdConsWork0-2    1207.00      1127.00   -6.63%
BenchmarkChanProdConsWork0-4    1913.00       611.00  -68.06%
BenchmarkChanProdConsWork0-8    3016.00       949.00  -68.53%
BenchmarkChanProdConsWork0-16   4320.00      1154.00  -73.29%
BenchmarkChanProdConsWork10     1906.00      1897.00   -0.47%
BenchmarkChanProdConsWork10-2   1123.00      1033.00   -8.01%
BenchmarkChanProdConsWork10-4   1076.00       571.00  -46.93%
BenchmarkChanProdConsWork10-8   2748.00      1096.00  -60.12%
BenchmarkChanProdConsWork10-16  4600.00      1105.00  -75.98%
BenchmarkChanProdConsWork100    1884.00      1852.00   -1.70%
BenchmarkChanProdConsWork100-2  1235.00      1146.00   -7.21%
BenchmarkChanProdConsWork100-4  1217.00       619.00  -49.14%
BenchmarkChanProdConsWork100-8  1534.00       509.00  -66.82%
BenchmarkChanProdConsWork100-16 4126.00       918.00  -77.75%
BenchmarkSyscall                  34.40        33.30   -3.20%
BenchmarkSyscall-2               160.00       121.00  -24.38%
BenchmarkSyscall-4               131.00       136.00   +3.82%
BenchmarkSyscall-8               139.00       131.00   -5.76%
BenchmarkSyscall-16              161.00       168.00   +4.35%
BenchmarkSyscallWork             950.00       950.00   +0.00%
BenchmarkSyscallWork-2           481.00       480.00   -0.21%
BenchmarkSyscallWork-4           268.00       270.00   +0.75%
BenchmarkSyscallWork-8           156.00       169.00   +8.33%
BenchmarkSyscallWork-16          188.00       184.00   -2.13%
BenchmarkSemaSyntNonblock         36.40        35.60   -2.20%
BenchmarkSemaSyntNonblock-2       81.40        45.10  -44.59%
BenchmarkSemaSyntNonblock-4      126.00       108.00  -14.29%
BenchmarkSemaSyntNonblock-8      112.00       112.00   +0.00%
BenchmarkSemaSyntNonblock-16     110.00       112.00   +1.82%
BenchmarkSemaSyntBlock            35.30        35.30   +0.00%
BenchmarkSemaSyntBlock-2         118.00       124.00   +5.08%
BenchmarkSemaSyntBlock-4         105.00       108.00   +2.86%
BenchmarkSemaSyntBlock-8         101.00       111.00   +9.90%
BenchmarkSemaSyntBlock-16        112.00       118.00   +5.36%
BenchmarkSemaWorkNonblock        810.00       811.00   +0.12%
BenchmarkSemaWorkNonblock-2      476.00       414.00  -13.03%
BenchmarkSemaWorkNonblock-4      238.00       228.00   -4.20%
BenchmarkSemaWorkNonblock-8      140.00       126.00  -10.00%
BenchmarkSemaWorkNonblock-16     117.00       116.00   -0.85%
BenchmarkSemaWorkBlock           810.00       811.00   +0.12%
BenchmarkSemaWorkBlock-2         454.00       466.00   +2.64%
BenchmarkSemaWorkBlock-4         243.00       241.00   -0.82%
BenchmarkSemaWorkBlock-8         145.00       137.00   -5.52%
BenchmarkSemaWorkBlock-16        132.00       123.00   -6.82%
BenchmarkContendedSemaphore      123.00       102.00  -17.07%
BenchmarkContendedSemaphore-2     34.80        34.90   +0.29%
BenchmarkContendedSemaphore-4     34.70        34.80   +0.29%
BenchmarkContendedSemaphore-8     34.70        34.70   +0.00%
BenchmarkContendedSemaphore-16    34.80        34.70   -0.29%
BenchmarkMutex                    26.80        26.00   -2.99%
BenchmarkMutex-2                 108.00        45.20  -58.15%
BenchmarkMutex-4                 103.00       127.00  +23.30%
BenchmarkMutex-8                 109.00       147.00  +34.86%
BenchmarkMutex-16                102.00       152.00  +49.02%
BenchmarkMutexSlack               27.00        26.90   -0.37%
BenchmarkMutexSlack-2            149.00       165.00  +10.74%
BenchmarkMutexSlack-4            121.00       209.00  +72.73%
BenchmarkMutexSlack-8            101.00       158.00  +56.44%
BenchmarkMutexSlack-16            97.00       129.00  +32.99%
BenchmarkMutexWork               792.00       794.00   +0.25%
BenchmarkMutexWork-2             407.00       409.00   +0.49%
BenchmarkMutexWork-4             220.00       209.00   -5.00%
BenchmarkMutexWork-8             267.00       160.00  -40.07%
BenchmarkMutexWork-16            315.00       300.00   -4.76%
BenchmarkMutexWorkSlack          792.00       793.00   +0.13%
BenchmarkMutexWorkSlack-2        406.00       404.00   -0.49%
BenchmarkMutexWorkSlack-4        225.00       212.00   -5.78%
BenchmarkMutexWorkSlack-8        268.00       136.00  -49.25%
BenchmarkMutexWorkSlack-16       300.00       300.00   +0.00%
BenchmarkRWMutexWrite100          27.10        27.00   -0.37%
BenchmarkRWMutexWrite100-2        33.10        40.80  +23.26%
BenchmarkRWMutexWrite100-4       113.00        88.10  -22.04%
BenchmarkRWMutexWrite100-8       119.00        95.30  -19.92%
BenchmarkRWMutexWrite100-16      148.00       109.00  -26.35%
BenchmarkRWMutexWrite10           29.60        29.40   -0.68%
BenchmarkRWMutexWrite10-2        111.00        61.40  -44.68%
BenchmarkRWMutexWrite10-4        270.00       208.00  -22.96%
BenchmarkRWMutexWrite10-8        204.00       185.00   -9.31%
BenchmarkRWMutexWrite10-16       261.00       190.00  -27.20%
BenchmarkRWMutexWorkWrite100    1040.00      1036.00   -0.38%
BenchmarkRWMutexWorkWrite100-2   593.00       580.00   -2.19%
BenchmarkRWMutexWorkWrite100-4   470.00       365.00  -22.34%
BenchmarkRWMutexWorkWrite100-8   468.00       289.00  -38.25%
BenchmarkRWMutexWorkWrite100-16  604.00       374.00  -38.08%
BenchmarkRWMutexWorkWrite10      951.00       951.00   +0.00%
BenchmarkRWMutexWorkWrite10-2   1001.00       928.00   -7.29%
BenchmarkRWMutexWorkWrite10-4   1555.00      1006.00  -35.31%
BenchmarkRWMutexWorkWrite10-8   2085.00      1171.00  -43.84%
BenchmarkRWMutexWorkWrite10-16  2082.00      1614.00  -22.48%

R=rsc, iant, msolo, fw, iant
CC=golang-dev
http://codereview.appspot.com/4711045

Committer: Russ Cox <rsc@golang.org>