The kernel scheduler is invoked when 1. an interrupt handler exits (hardware irqs or timer ticks) 2. a syscall exits. 3. the scheduler is explicitly called. Which means the worst-case resolution of scheduling is equal to the resolution of the timer ticks when the system is idle (no irq and no traffic of syscalls). So it's doubtful that the 100us-ish timeout would work as expected when the granularity of the kernel scheduling is much coarse. And if you check out the manpage of futex, it has a sentence about the timeout saying that "This interval will be rounded up to the system clock granularity". That probably explains why the spinlock gets waken up faster.

@typeless futex explicitly calls scheduler, so that's number 3

I don't think this affects cgo calls, notesleep should not be on fast path there.
It should affect cgo callbacks, though.

@dvyukov

futex explicitly calls scheduler, so that's number 3

But for the user process being able to call the scheduler, doesn't the process have to be invoked by the scheduler first?

If it's not running, it won't be able to set n.key either.

@dvyukov

Apologies for my ambiguous wording. By processes I actually mean the OS threads.

If it's not running, it won't be able to set n.key either.

Isn't it possible that a running thread being interrupted and yield the CPU to others temporarily (unless it can disable the IRQs)? The timing that the thread gets rescheduled again can only be the next scheduling points, which is beyond the control of the thread.

P.S. FWIW a possible way to occupy the CPU exclusively other than disabling the IRQs is to use sched_setscheduler for the SCHD_FIFO policy.

I don't think this affects cgo calls, notesleep should not be on fast path there.
It should affect cgo callbacks, though.

@dvyukov original benchmark uses only CGo calls without CGo callbacks. lockOSThread is used on cgocall fast path for every CGo call:

https://github.com/golang/go/blob/ab401077/src/runtime/cgocall.go#L107

and somehow, as benchmark shows, it gets intermixed with the scheduler:

CGo-4        581ns ± 1%   556ns ± 0%   -4.27%  (p=0.000 n=10+10)
CGo10-4     2.20µs ± 6%  1.23µs ± 0%  -44.32%  (p=0.000 n=10+9)

@typeless sorry, I don't see how this is related the topic.

@navytux

and somehow, as benchmark shows, it gets intermixed with the scheduler:

What is the result if you comment out lockOSThread/unlockOSThread in cgocall (it's not really needed there)?

@dvyukov thanks for the question, I too thought about it just after commenting. So on today's unmodified tip (go version devel +c2f8ed267b Wed Sep 13 07:19:21 2017 +0000 linux/amd64) it gives:

$ benchstat dv0.txt
name     time/op
CGo-4     576ns ± 1%
CGo10-4  2.22µs ± 2%

with adding

diff --git a/src/runtime/cgocall.go b/src/runtime/cgocall.go
index ce4d707e06..decc310088 100644
--- a/src/runtime/cgocall.go
+++ b/src/runtime/cgocall.go
@@ -106,7 +106,7 @@ func cgocall(fn, arg unsafe.Pointer) int32 {
 
        // Lock g to m to ensure we stay on the same stack if we do a
        // cgo callback. In case of panic, unwindm calls endcgo.
-       lockOSThread()
+//     lockOSThread()
        mp := getg().m
        mp.ncgocall++
        mp.ncgo++
@@ -159,7 +159,7 @@ func endcgo(mp *m) {
                raceacquire(unsafe.Pointer(&racecgosync))
        }
 
-       unlockOSThread() // invalidates mp
+//     unlockOSThread() // invalidates mp
 }
 
 // Call from C back to Go.

it becomes:

$ benchstat dv0.txt dv1.txt 
name     old time/op  new time/op  delta
CGo-4     576ns ± 1%   558ns ± 1%  -3.18%  (p=0.000 n=10+10)
CGo10-4  2.22µs ± 2%  2.03µs ± 4%  -8.63%  (p=0.000 n=9+8)

with adding notesleep spin patch on top (so both cgocall and notesleep are patched) it becomes:

$ benchstat dv1.txt dv2.txt 
name     old time/op  new time/op  delta
CGo-4     558ns ± 1%   552ns ± 2%   -1.00%  (p=0.021 n=10+10)
CGo10-4  2.03µs ± 4%  1.17µs ± 1%  -42.45%  (p=0.000 n=8+8)

which shows the speedup is not only related to lockOSThread and somehow generally (?) applies to scheduler or some other details of CGo calls.

which shows the speedup is not only related to lockOSThread and somehow generally (?) applies to scheduler or some other details of CGo calls.

This makes sense now.

I guess it is general tradeoff between latency and burning CPU.
If we do more aggressive scheduler spinning, it can make sense to do it directly in findrunnable/stoplockedm.
But generally it's unclear to me if this translates to real world improvements. Synthetic synchronization tests are usually misleading. If a locked goroutine blocks for more than 10us, then we just burn 10us on CPU time in vain.

If in cgocall I also disable entersyscall/exitsyscall even without notesleep spin patch, so whole patch is below:

diff --git a/src/runtime/cgocall.go b/src/runtime/cgocall.go
index ce4d707e06..70fbe7e7b1 100644
--- a/src/runtime/cgocall.go
+++ b/src/runtime/cgocall.go
@@ -106,7 +106,7 @@ func cgocall(fn, arg unsafe.Pointer) int32 {
 
        // Lock g to m to ensure we stay on the same stack if we do a
        // cgo callback. In case of panic, unwindm calls endcgo.
-       lockOSThread()
+//     lockOSThread()
        mp := getg().m
        mp.ncgocall++
        mp.ncgo++
@@ -129,9 +129,9 @@ func cgocall(fn, arg unsafe.Pointer) int32 {
        // "system call", run the Go code (which may grow the stack),
        // and then re-enter the "system call" reusing the PC and SP
        // saved by entersyscall here.
-       entersyscall(0)
+//     entersyscall(0)
        errno := asmcgocall(fn, arg)
-       exitsyscall(0)
+//     exitsyscall(0)
 
        // From the garbage collector's perspective, time can move
        // backwards in the sequence above. If there's a callback into
@@ -159,7 +159,7 @@ func endcgo(mp *m) {
                raceacquire(unsafe.Pointer(&racecgosync))
        }
 
-       unlockOSThread() // invalidates mp
+//     unlockOSThread() // invalidates mp
 }
 
 // Call from C back to Go.

compared to only lockOSThread commented it becomes:

$ benchstat dv1.txt dv1nosys.txt 
name     old time/op  new time/op  delta
CGo-4     558ns ± 1%   509ns ± 1%   -8.86%  (p=0.000 n=10+9)
CGo10-4  2.03µs ± 4%  0.77µs ± 3%  -61.97%  (p=0.000 n=8+10)

And if I comment only syscallenter/syscallexit, so whole patch is:

diff --git a/src/runtime/cgocall.go b/src/runtime/cgocall.go
index ce4d707e06..243688f0af 100644
--- a/src/runtime/cgocall.go
+++ b/src/runtime/cgocall.go
@@ -129,9 +129,9 @@ func cgocall(fn, arg unsafe.Pointer) int32 {
        // "system call", run the Go code (which may grow the stack),
        // and then re-enter the "system call" reusing the PC and SP
        // saved by entersyscall here.
-       entersyscall(0)
+//     entersyscall(0)
        errno := asmcgocall(fn, arg)
-       exitsyscall(0)
+//     exitsyscall(0)
 
        // From the garbage collector's perspective, time can move
        // backwards in the sequence above. If there's a callback into

compared to unmodified tip it becomes:

$ benchstat dv0.txt dv1nosysonly.txt 
name     old time/op  new time/op  delta
CGo-4     576ns ± 1%   515ns ± 1%  -10.62%  (p=0.000 n=10+10)
CGo10-4  2.22µs ± 2%  0.84µs ± 2%  -62.07%  (p=0.000 n=9+10)

so in case of CGo calls the notesleep spin patch brings speedup not becuase of lockOSThread but due to entersyscall/exitsyscall being there.

Yes, entersyscall/exitsyscall is what interacts with Go scheduler in case of cgo calls.

I guess it is general tradeoff between latency and burning CPU.
If we do more aggressive scheduler spinning, it can make sense to do it directly in findrunnable/stoplockedm.
But generally it's unclear to me if this translates to real world improvements. Synthetic synchronization tests are usually misleading. If a locked goroutine blocks for more than 10us, then we just burn 10us on CPU time in vain.

I generally agree but some kind of adaptive spinning could be brought to notesleep/notewakeup too -
similar to what you did to runtime.lock/unlock in 4e5086b (runtime: improve Linux mutex):

4e5086b9#diff-608e335144c55dc824f257f5a66ac4d3R125
https://github.com/golang/go/blob/c2f8ed26/src/runtime/lock_futex.go#L54

becuase currently notesleep always unconditionally goes directly to sys_futex to kernel.

And by the way - many fast syscalls is not synthetic benchmark - they appear in real programs either reading fast from cached files or sending/receiving on network (yes network is epolled but still every send/recv goes through full - not raw - syscall). In my experience every such event has potential to shake the scheduler.

notesleep is not meant for sleeping for brief periods. There are callers for which spinning will be plain harmful. mutex is meant for brief blocking.
Non-blocking network calls should not invoke scheduler, they don't give up P for 20us, while non-blocking read/write takes on a par of 5us.

Thanks for feedback. I understand there is difference between notesleep and mutex and notesleep by definition is more heavier sleep. With this in mind and adjusted patch:

diff --git a/src/runtime/lock_futex.go b/src/runtime/lock_futex.go
index 9d55bd129c..5648ef66f3 100644
--- a/src/runtime/lock_futex.go
+++ b/src/runtime/lock_futex.go
@@ -146,7 +146,14 @@ func notesleep(n *note) {
                // Sleep for an arbitrary-but-moderate interval to poll libc interceptors.
                ns = 10e6
        }
-       for atomic.Load(key32(&n.key)) == 0 {
+       for spin := 0; atomic.Load(key32(&n.key)) == 0; spin++ {
+               // spin a bit hoping we'll get wakup soon hopefully without context switch
+               if spin < 10 {
+                       osyield()
+                       continue
+               }
+
+               // no luck -> go to sleep heavily to kernel; this might result in context switch
                gp.m.blocked = true
                futexsleep(key32(&n.key), 0, ns)
                if *cgo_yield != nil {

it still works for both LockOSThread and CGo cases:

$ benchstat dv00.txt dv0+osyield.txt 
name        old time/op  new time/op  delta
Unlocked-4   482ns ± 1%   478ns ± 0%   -0.90%  (p=0.011 n=10+9)
Locked-4    5.08µs ± 1%  1.51µs ± 4%  -70.29%  (p=0.000 n=9+10)
CGo-4        577ns ± 0%   558ns ± 1%   -3.38%  (p=0.000 n=9+10)
CGo10-4     2.22µs ± 3%  1.30µs ± 1%  -41.47%  (p=0.000 n=10+10)

but the spinning now does not wastefully burn CPU and gives up to OS scheduler via osyield(). This works similarly to "passive spinning" phase of mutex lock. For mutex the N(passive-spin) = 1 and since notesleep is more heavier having N(passive-spin) for it an order of magnitude more seems logical. The osyield will release the CPU to other threads if there is other work to do and thus hopefully should not have negative impact (this has to be verified).

Non-blocking network calls should not invoke scheduler, they don't give up P for 20us, while non-blocking read/write takes on a par of 5us.

Maybe you are right here. I will try to reverify this once getting to a related topic and will hopefully come back with feedback.

@dvyukov, could you please clear up that

Non-blocking network calls should not invoke scheduler, they don't give up P for 20us, while non-blocking read/write takes on a par of 5us.

bit for me?

Do I parse it correctly, that network syscalls are treated specially and P is not removed from under a G which spends more than 20 us in such a syscall, like this is done for all other syscalls?

Or does this merely happen "all by itself" — as a byproduct of such syscalls commonly lasting only about 5 us (thanks to the sockets being non-blocking)?

It happens for all syscalls/cgocalls if they return faster than 20us.

but the spinning now does not wastefully burn CPU and gives up to OS scheduler via osyield().

This is still wasteful for some callers. What exactly caller of notesleep is affected by this change? Can we improve the caller instead?

For LockOSThread case it seems to be stoplockedm/startlockedm:

(svg)

However for CGo case it is less clear, at least from CPU profile point of view:

(svg)

Btw, do you have particular example where osyielding in notesleep will be wasteful? (go scheduler is new to me)

I would try spinning in findrunnable more, before dropping P, that can yield better result without impacting other cases.

Re stoplockedm, I am still not sure. We could also spin there before dropping P, but then this is an optimization for the case when a locked G in unblocked very quickly. It's unclear how often this happens in real life, and even if it does happen it still won't be fast because of the required thread jumps. But this will hurt other goroutines because we are holding the P.
We could spin just in notesleep when called from stoplockedm, but then at least we need to avoid futexwake as well. And it's still not clear if it is the right thing to do.

If you care about performance of locked goroutines, there seems to be a bunch of other missed optimizations. E.g. when a locked G is woken, we wake another M, but that M cannot execute the G, so it wakes the right M and passes G/P to it. I guess we need to wake the right M right away.

@dvyukov thanks for your feedback with knowledge sharing - it is appreciated.

My situation is this: I have a case where my server is misperforming because of, I think, go scheduler (tracing shows many spawned goroutines are queued to same P and are not stealed while I need all them to execute in parallel to significantly reduce latency; other Ps are idle) . There I do not use LockOSThread and CGo at all at the moment. I cannot even describe the problem properly yet because it has not been fully analyzed yet. I spent some time learning how go scheduler works to better understand what happens when a goroutine is started, channel sent/received etc. Along the way I did a quick tool to profile how often goroutines are migrated in between Ms:

https://lab.nexedi.com/kirr/neo/blob/851864a9/go/gmigrate.go

because unfortunately it seems to be a frequent event and changing M probably means changing CPU and thus loosing CPU caches.

After studying I quickly looked around for scheduler bugs here on issue tracker and found LockOSThread case. I tried to test whether I understood at least something via trying to fix it, and so we are here.

So if someone else does not fix the LockOSThread and CGo cases before me, I will hopefully try to give it a fresh look while working on my scheduler-related issues. However scheduler bits are currently lower priority for me compared to proper memory and other tuning - so it will be some time before I could dig in more details on this topic.

Thanks again for feedback and appologize for throttling,
Kirill

tracing shows many spawned goroutines are queued to same P and are not stealed while I need all them to execute in parallel to significantly reduce latency; other Ps are idle

Sounds pretty bad. But does not look like an issue with notesleep.
Repro would be useful (and/or trace file).

It is running on my notebook which has 4 CPU (2 physical * 2 HT). There are 2 programs: server + client. The client tries to issue 512 simultaneous networking requests over same TCP connection to server and then waits for completion, but from what I recall even initiating them go mostly serially. GOMAXPROCS is unadjusted and default to ncpu=4. No other program significantly uses the processor.

I admit networking over loopback is not the same as networking on LAN (on LAN RTT ~= 500μs while for TCP/loopback and separate processes it is aroung 5-8μs). We do care about loopback case too though.

I promise I get back to this once dealing with other urgent tunings. Probably in a week or two.

Thanks for reopening.

I've moved CGo stuff to #19574 (comment).

I looked at this a bit. I find that if I add time.Sleep(time.Microsecond) to the loop in the function _server, then the locked variant performs much better:

BenchmarkUnlocked-8   	   20000	     58347 ns/op
BenchmarkLocked-8     	  100000	     17142 ns/op

So I think this may be a misleading benchmark. In the unmodified benchmark, the server races ahead of the clients, and frequently goes to sleep reading from the channel. Then, I suspect, writes to the channel wake up the serving goroutine, but on the wrong M. So it has to then wake up the right M, as @dvyukov describes at #21827 (comment) . So if there is something to fix, it should probably focus on that, not on the behavior of notesleep.

@ianlancetaylor, the sleep for 1μs in server causes some scheduler badness for unlocked case:

$ gotip test -count=3 -bench Unlocked tmp3_test.go 
goos: linux
goarch: amd64
BenchmarkUnlocked-4        20000             66237 ns/op
BenchmarkUnlocked-4        20000             66948 ns/op
BenchmarkUnlocked-4        20000             66971 ns/op

$ gotip test -count=3 -trace x.trace -bench Unlocked tmp3_test.go 
goos: linux
goarch: amd64
BenchmarkUnlocked-4       100000             14993 ns/op
BenchmarkUnlocked-4       100000             14758 ns/op
BenchmarkUnlocked-4       200000             15068 ns/op

i.e. it runs ~ 4.5x slower when run without tracing enabled.

For the reference the time for locked case only somewhat increases if tracing is enabled.

$ gotip test -count=3 -bench Locked tmp3_test.go 
goos: linux
goarch: amd64
BenchmarkLocked-4         100000             13924 ns/op
BenchmarkLocked-4         100000             13800 ns/op
BenchmarkLocked-4         100000             14025 ns/op

$ gotip test -count=3 -trace y.trace -bench Locked tmp3_test.go 
goos: linux
goarch: amd64
BenchmarkLocked-4         100000             18203 ns/op
BenchmarkLocked-4         100000             18162 ns/op
BenchmarkLocked-4         100000             18230 ns/op

go version devel +b56e24782f Mon Jul 9 02:18:16 2018 +0000 linux/amd64

I generally agree that what @dvyukov suggests should be the way to go, not my silly spinning patch.

Guys any update on this issue?
We want to use C library that assumes we're not jumping between threads while invoking it (it's assync library) and currently don't know if it solved or not.
I'll be glad for any update ;)

@omriperi Many programs and libraries use runtime.LockOSThread without issue. The benchmark here is synthetic and unlikely to correspond to most real use cases. Don't worry about this unless you see unexpected performance problems.

I can only restate that the benchmark is not synthetic: #21827 (comment).

My apologies. It would help a great deal if you could share the real code, so that we can understand the real problem.

I apologize as well as I don't actively work on this topic now (the issue is from 2017), and cannot provide "the real code". However I clearly remember that scheduler performance issues start to show in practically all scenarious where either many system calls or Cgo calls are made. My understanding is that LockOSThread only brings those performance issues more to the surface.

Here are some evidence, from what I could remember, to justify my words:

#19574
#19574 (comment)
#19563 (comment)

Many projects switch off from using Go for this reason:

#19574 (comment)

In the end, only the code that does not push this pain points stay with Go, and due to that there might be impression that there are no real scheduler/Cgo/LockOSThread performance problems...

My apologies. It would help a great deal if you could share the real code, so that we can understand the real problem.

I've recently discovered that this problem affects Delve, for example.

Debugger-related calls (ptrace on linux, WaitForDebugEvent/ContinueDebugEvent on windows) need to be done on the same thread as the thread that spawned the target process, for this we use a goroutine that calls runtime.LockOSThread and executes thunks sent to it through a channel.

The code for this is in https://github.com/go-delve/delve/blob/f863be0a172a9c62d679143ec53587ef6255737e/pkg/proc/native/proc.go#L348 which is pretty much identical to the set up in this issue.

Back in january I looked into optimizing the performance of conditional breakpoint evaluation. There were several performance problems on our side (note: not all have landed upstream yet), when those were taken care the flame graph looked like this:

which shows that a lot of our time was spent inside runtime.findrunnnable. By simply moving all the code inside the LockOSThread goroutine I can get this flame graph:

the LockOSThread thing is responsible for 2/3 of the time it takes to evaluate a conditional breakpoint (specifically 0.4ms out of 0.6ms).

@navytux There is a big difference between cgo overhead, which has gotten somewhat better, and LockOSThread overhead, which remains unclear. As we've discussed before, a cgo call does not call LockOSThread. Only a call from Go to C to Go calls LockOSThread.

@ianlancetaylor, I wrote #21827 (comment) with full understanding that LockOSThread is no longer there on Go->C call after 332719f. I still stand on my points based on experience: LockOSThread only highlights Go scheduler performance problems related to crossing Go->non-Go world boundary (Go->C, Go->kernel) that are present there even when goroutines are not locked to OS threads.

Anyway, whatever it is, e.g. Delve case (#21827 (comment); thanks @aarzilli) demonstrates this issue on a real-world program.

I recently hit this problem working with GLFW/OpenGL based frameworks. I found a relatively simple program was consuming huge amount of CPU, >50% via park_m and futex.

Go packages commonly use a channel to pass functions that must be executed on the main thread (GLFW/GL requirement). Eg, github.com/faiface/mainthread uses this technique. Channel operations cause a huge number of futex sleep/wake cycles as they swap between the Ms. This adds significant latency to calls (>8-9us).

This cut down example demonstrates the technique, and the kind of CPU profiles it generates:

package main

import (
    "fmt"
    "os"
    "runtime"
    "runtime/pprof"
    "time"
)

const iterations = 1e6

func main() {
    runtime.LockOSThread()

    f, _ := os.Create("cpu.prof")
    defer f.Close()
    _ = pprof.StartCPUProfile(f)
    defer pprof.StopCPUProfile()

    // Increasing chan size significantly improves performance when
    // not waiting for completion (keeps the main thread busy).
    calls := make(chan func(), 1)

    go func() {
        for i := 0; i < iterations; i++ {
            done := make(chan struct{})
            calls <- func() {
                close(done)
            }
            <-done // Comment to reduce parking main thread.
        }
        close(calls)
    }()

    // Process calls on the "main" thread.
    t0 := time.Now()
    for fn := range calls {
        fn()
    }
    fmt.Println("Mean:", time.Since(t0)/iterations)
}

@mpx @ianlancetaylor Why is this a problem at all? The doc clearly states that LockOSThread causes a single goroutine to be run exclusively on a single thread. This naturally implies that communication via channels (or whatever) will cross thread boundaries, therefore requires locking/context switch & causes overhead. This seems totally reasonable.

@mpx It is true, that graphics stacks require you to use LockOSThread due to thread-local storage often used in old & rotten C libraries. However, passing callbacks from other goroutines usually work differently. You use a locked slice of callbacks and simply queue them. In the render loop you simply check every frame if there are callbacks and run them. If not, wait until the next frame. In this case, there is less chance of lock contention and park & wake-up. Also, your problem is totally not related to Go. As soon as you start using multiple threads, even in C/C++, you need a way of syncing the main render loop.

@navytux Maybe it would be helpful to summarize the initial problem more clearly?

@chrisprobst This issue is about speeding up a specific case, for which a reduced test case appears in the initial comment. I agree that using LockOSThread is inevitably slower than not using it. But for this test case the slowdown appears to be unreasonably high.

Change https://go.dev/cl/562915 mentions this issue: runtime: don't call lockOSThread for every syscall call on Windows