sync: bad placement of multiple contested locks can cause drastic slowdown

[ianlancetaylor]

This program runs in a couple of seconds in the normal case. When invoked with the argument -offset=251, it takes over four minutes. The problem is the hash table in runtime/sema.go. When two contested mutexes happen to wind up using the same hash table entry, the linear search in semrelease is a significant performance drag. While this is not a likely occurrence, 1 in 251 is not so terribly unlikely either, and the performance effect is extreme. This actually occurred in an internal Google program.

CC @dvyukov

package main

import (
    "flag"
    "sync"
)

var offset = flag.Int("offset", 1, "Offset for the second lock")

func main() {
    flag.Parse()
    locks := make([]sync.RWMutex, *offset+1)
    ch := make(chan struct{})

    var wg sync.WaitGroup

    for i := 0; i < 10000; i++ {
	    wg.Add(1)
	    go func() {
		    <-ch
		    for i := 0; i < 10; i++ {
			    locks[0].Lock()
			    locks[*offset].Lock()
			    locks[*offset].Unlock()
			    locks[0].Unlock()
		    }
		    wg.Done()
	    }()
    }

    for i := 0; i < 100; i++ {
	    go func() {
		    for {
			    locks[*offset].Lock()
			    locks[*offset].Unlock()
		    }
	    }()
    }

    close(ch)
    wg.Wait()
}

[dvyukov]

This is not specific to RWMutex, right? Mutex should be affected the same way. If RWMutex is used only for write locks it behaves exactly as Mutex.

It's solvable if we increase size of the Mutex by at least 1 word to store *semaRoot directly. Maybe we could even pack all state into 2 words without indirection.
Solving it without Mutex size increase will require playing dirty games like packing pointers into integers (which should work provided that pointee is non-movable and is preserved alive by other pointers, which is true for e.g. G).

[ianlancetaylor]

As far as I can see it would be OK to grow Mutex by a word. It seems unlikely that any program's memory usage is dominated by the number of Mutex values it creates.

[rsc]

I'd really prefer not to store internal runtime state (pointers) in a user-corruptible data structure. We've seen malloc implementations have to move their metadata into separate pages to make sure that user corruption doesn't cause what look like internal errors in malloc, and I think that lesson applies here.

I have a different, simpler idea. Instead of making the 251-entry hash table have a list of all goroutines blocked on addresses hashing to that bucket, make it have a list of only goroutines blocked on unique addresses hashing to that bucket. Instead of inserting an address into the list a second time, a secondary list can hang off of each of these unique representatives. Because the wakeups are FIFO, the length of those secondary lists don't matter - the ops on them are O(1) - and moving the large numbers of goroutines blocked on the same lock off the main list eliminates that as a cause for slowdown if there's another lock hitting the same hash bucket.

I've implemented this, and it eliminates the problem in @ianlancetaylor's test program. Ian, if you can send me more details about the Google problem off-list then I'll see if it would fix that too.

[gopherbot]

CL https://golang.org/cl/36792 mentions this issue.

[gopherbot]

CL https://golang.org/cl/37103 mentions this issue.