runtime: bad performance of core GO features (GC, go routines, channels, map)

[StephanVerbeeck]

We measured the impact of GC related to the amount of persistent memory objects.
Existing interactive accounting program used 44K to 90K of persistent heap objects.
Next multiplatform distributed VR/AR program will be using at least 1000K persistent heap objects.
Tested by adding extra functions BurnCPU() on the background that allocates small data structures and keeps less than 1% of the created structures persistent.

Environment

• OS = windows 10
• go version = 1.12.5 windows/amd64

Expected

• "BurnCPU" routine running in te background would slow-down the entire system (both the program that contains it and other programs running on windows) by the excerted stress on memory and CPU.
• Added function does not share memory or other resources with program to which it was addes and due should have little affect on it (other than slowing the entire system down).
• "BurnCPU" will not block normal usage of the interactive application that contains it.
• BurnCPU will not be significantly slower than native C equivalent.

Observed (After adding "go BurnCPU()" as first line of the main() function)

• Creation of interactive GUI window is delayed 30sec to 200sec
• Normal usage of GUI is only possible after BurnCPU has run to completion
• Multi threading version was slower then single threaded (core i7 at 4Ghz with 16Gb RAM)
• usage of channels degraded performance instead of raising it
• both bufferd and unbuffered channels were unusable due to introduced slowdown
• map became extreme slow when having many items (using simple integer index with simple pointer as data)
• locking between go routines was extreme even after tweaking co-operative multi-tasking ( using runtime.Gosched() )

Benchmark code:

• was added to proprietary code (that can not be listed here) that was based on the lxn/walk GUI library for windows
• effect can be reproduced by using public available example and adding "go BurnCPU()" as first line of its main() function in https://github.com/lxn/walk/blob/master/examples/filebrowser/filebrowser.go

code:

func main() {
	go BurnCPU()		
	// <- code of existing GUI application remains here
}

func BurnCPU() {
	type aha struct{ a, b int }
	oho := map[int]*aha{}
	com := make(chan *aha, 100)
	wg := sync.WaitGroup{}
	go func() {
		for {
			c := <-com
			oho[c.a+c.b] = c
		}
		return
	}()
	for a := 1; a < 1e5; a++ {
		wg.Add(1)
		go func(a int) {
			for b := 1; b < 1e5; b++ {
				b += 1234
				c := new(aha) // allocate some memory to cause GC
				c.a = 10 * (a)
				c.b = 10 * (b - 1234)
				b -= 1234
				if b%1000 == 0 {
					com <- c
					runtime.Gosched()
				}
			}
			wg.Done()
			return
		}(a)
		runtime.Gosched()
	}
	wg.Wait()
	memStats := runtime.MemStats{}
	runtime.ReadMemStats(&memStats)
	return // <- set debug break here and examine memStats
}

Conclusions:

• co-operative multi-tasking tweaked by "runtime.Gosched()" is something I did not have to bother about since windows 3.1, now it is back!
• reading and writing from channels (according to the documentation) invokes a co-operative multi-tasking so adding "runtime.Gosched()" at that point should have no effect but clearly it does have affect so the documentation is WRONG. Doing IO is not sufficient for not having to add "runtime.Gosched()" in loops.
• launching go routines had to be preceded by "runtime.Gosched()" to make it run "kind of" smooth.
• adding channels to simulate lock free concurrent processing by object degraded performance to a point of "entire project canceled".
• observed values of memstat percentage CPU spend on GC and cumulative duration of GC stops does not match (indicated 73% cpu usage during 200sec while cumulative time showed 0.47sec)

Variants:

• we tested with various combinations of inner and outer loop iteration count (example shows 1e51e5, changing that to 1e31e7, 1e41e6, 1e71e3 produced even stranger effects like immediate program abend without error message).
• compared to native C code (only the BurnCPU function, without adding it to existing interactive program) showed remarkable figures. best case GO was 373x slower, worst case was 2847x slower. (Native C lternative can not be listed here because uses proprietary templates for simulating channel based on circular buffer with read and write index advanced via interlocked increments).

Assumptions based on these observations:

• GO in its current state of development is only suited for interactive applications or applications that have idle time. Heavy load and large persistent heap of objects do not function properly in Golang at this moment.
• usage of channels is documented as native GO method to avoid deadlocks, while it seems to introduce extreme slow-down due to locking (tested both buffered and unbuffered variants with 0, 10 and 1000 items buffer)
• usage of map relative to fixed array with modulus index (simulating map) caused serious performance degradation in excess of 18x (unexpected due to map having no locking)
• GO was selected (candidate) for shared code on multi-platform development (windows,mac,iOS,android) with native GUI front-end (GO,swift,Kotlin) per platform. However the shared code needs to contain 1M..100M memory data structures describing 3D animated shapes. It seems GO is not up to the task while Rust (second candidate) is also not yet mature enougn for commercial use, so we are back to native C++ for this purpose.
• Documented advances on reducing the delay time of GC "stop the world" are "misleading". The advance is due to the way the stops are measured (making it such that GC calls intersect with idle time of the application). However functions that do not actively WORK with this logic (by calling "runtime.Gosched()" all the time) seem to block the start of GC cleanup WHILE BLOCKING ALL OTHER GO ROUTINES. So this documented method of measuring GC performance is misleading (put politely).

[mvdan]

Just want to point out that "abominable" is not a good way to start a discussion about performance. Constructive issues get attention and often positive outcomes, but this doesn't seem constructive to me.

Also, it would be much better to raise issues about specific performance problems you've encountered, and reliable ways to reproduce them. This issue is quite massive, so it would be hard to stay on topic and tackle any specific problems separately.

[StephanVerbeeck]

I have done some deeper digging and (although yet speculative) might have found a reason for the bad performance that can not be found in software. It might be a pure hardware problem. GO "claims" to have no problems with numbers of go routines that far exceeds the number of available CPU cores.

To a degree that is accurate and since go routines are "distributed" over a fixed number of worker threads (about as many as there are CPU cores). HOWEVER . . . there is still an excessive amount of context switching in such a worker thread and each time such a switch occurs the data which is in the L1/L2/L3 cache of the CPU core that runs the worker thread becomes "useless". So the excessive amount of context switching makes that the CPU cache can not do its normal function.

With normal OS round-robin scheduling the switches between processes is determined by the OS and is far less (in the order of e.g. 50x per second) so that the cache is only useless every 20msec or so. GO has broken this rule and can have (depending on the application) 1000x more context switches per worker thread per second.

I have tried to test this hypothesis by adding...

	for runtime.NumGoroutine() > runtime.NumCPU() {
		time.Sleep(1e6)
	}

... to the loop that launches the go routines. So the BurnCPU() now looks like this:

	type aha struct{ a, b int }
	oho := map[int]*aha{}
	com := make(chan *aha, 100)
	wg := sync.WaitGroup{}
	go func() {
		for {
			c := <-com
			oho[c.a+c.b] = c
		}
		return
	}()
	outer := int(1e3)
	inner := int(1e7)
	wg.Add(outer)
	for a := 1; a <= outer; a++ {
		go func(a int) {
			for b := 1; b <= inner; b++ {
				b += 1234
				c := new(aha) // allocate some memory to cause GC
				c.a = 10 * (a)
				c.b = 10 * (b - 1234)
				b -= 1234
				if b%1000 == 0 {
					com <- c
				}
			}
			wg.Done()
		}(a)
		for runtime.NumGoroutine() > runtime.NumCPU() {
			time.Sleep(1e6)
		}
	}
	wg.Wait()
}

The results now look better and the blocking of the interactive part of the program is gone.
So this is good BUT there is no method of knowing how many of the runtime.NumGoroutine() are blocked (e.g. waiting for channel input) so this code is a potential DEADLOCK. So to make this solution work properly "runtime.NumGoroutine()" would have to be "runtime.NumUnblockedGoroutine()" (returning the number of go routines that are active plus the number of go routines that are pending to become active, so not counting go routines that wait for an IO/timer event).

Ideal solution would be that this kind of logic would be part of the "go" command itself.
To avoid backward compatibility issues maybe add a boolean flag that enables this via a call to e.g. "runtime.SetIdleGO(state bool) bool".

So the basic idea is that any "go" would block the routine that tries to do it until the number of already active routines becomes less than the number of available worker threads. How this influences existing code and benchmarks has to be investigated first of course.

Another alternative could be to add a function "WaitGroup.Go(func)" that does this checking only based on the number of routines in the WorkGroup. Then the WorkGroup.Add(1) is done by WaitGroup.Go(func) and you would only have to call WorkGroup.Done() at the end of the started go routine.

[ALTree]

The implementation of your BurnCPU function doesn't make sense to me. Why are you spawning 10000 goroutines? In an hypothetical C implementation of BurnCPU, would you spawn 10000 OS threads? No, obviously... that would just completely trash the OS scheduler without helping you actually burning CPU in any way. But in your Go code, you're doing exactly that.

GO "claims" to have no problems with numbers of go routines that far exceeds the number of available CPU cores.

This is only true when the goroutines are spawned to execute light-weigth tasks, or tasks that block. In every other case, it makes no sense to spawn more goroutines than cores you have on your machine. Experienced Go developers are well aware of this.

The number of goroutines that are tasked to execute heavy workloads (like "burning" CPU in your test) needs to be limited to the amount of cores on your machine; if anything just for the reason that anyway you cannot do more CPU-heavy concurrent work than the number of cores on your machine.

Your BurnCPU function needs to be changed so that it only spawns an amount of goroutines that is exactly equal to the amount of threads that can be executed concurrently on your machine (e.g.: 4 or 8). Otherwise you're just trashing the goroutines scheduler for no reason. Then the goroutines that are in charge of the GUI get trapped in the 10000 goroutines scheduler-hell you created, and the UI won't be responsive.

In general, from the code and the message you posted, it appears that you have a very superficial understanding on how Go works and, more importantly, how Go primitives like goroutines should be used.

I encourage you to gain more experience in writing idiomatic, high-performance Go code before you trust yourself with an opinion about whether the language is up to a specific task you have to accomplish. I'm not saying Go is definitely the right choice for your application: maybe it's not.

[networkimprov]

Preemptive goroutine scheduling is in progress, probably landing in 1.14, see #24543.

Also, channels are not the fastest possible way to synchronize goroutines. The sync and sync/atomic packages are more efficient, if harder to get right. "Sharing memory by communicating" only takes you so far :-)

And if I may, I'd encourage everyone to be more gentle in tone.

[StephanVerbeeck]

Why are you spawning 10000 goroutines? In an hypothetical C implementation of BurnCPU, would you spawn 10000 OS threads? No, obviously... that would just completely trash the OS scheduler without helping you actually burning CPU in any way. But in your Go code, you're doing exactly that.

The constructed benchmark is in scale and load equivalent to the target application which maintains a distributed AR scene with persistent shape count in the range 1 to 100 million objects, each having their own local methods that can use go routines.

The abilities of C++ both on CPU and GPU are in that performance range.
The purpose of a benchmark is also to see how the system scales up so why would we do a small scale test?

[ALTree]

1 to 100 million objects, each having their own local methods that can use go routines.

It's hard to make sensible comments about the kind of high-level architecture an application of this level of complexity should have, but as as a general observation, if those millions of objects could potentially fire-up CPU-intensive tasks, each on in their own goroutines, concurrently, I don't think this kind of architecture can and will work, at all, for the reasons I have stated above.

So basically it appears that the main issue you have here is that your Go CPUBurner prototype is modelling an architecture that is fundamentally not suitable for the kind of application you'd like to build. My impression is that the fact that Go provides certain features (like goroutines and channels) at a language-level has misled you into producing a design that is not suitable for your needs, and more importantly:

The abilities of C++ both on CPU and GPU are in that performance range.

the design of your Go prototype is fundamentally different from the one you would produce if you had to code this in C/C++, since I'm sure that if you were to build this in C++ you wouldn't spawn a thread of computation each time one of the millions of live objects needs to do something, and you wouldn't expect the application to work while thousands of these threads are all executing in a given moment.

While it's true that spawning goroutines to perform atomic tasks and communicating using channels is often the good and idiomatic way to write Go code, this is not always true. Sometimes, the kind of application you need to build forces you to design an architecture that comes closer to the one you'd design when you're writing C/C++ code.

[randall77]

I'm not surprised that your GUI response is terrible. You have 10000 goroutines, and only one of them is the GUI goroutine. The runtime has no way to know which of those 10000 is your latency critical one. The scheduler tries to be at least somewhat fair to all the goroutines, which means your GUI one is only getting 1/10000 of the machine. A fix for this kind of application would require goroutine priorities. We don't have that at the moment, but you can simulate it with runtime.LockOSThread and then using the OS priority mechanisms.

reading and writing from channels (according to the documentation) invokes a co-operative multi-tasking so adding "runtime.Gosched()" at that point should have no effect but clearly it does have affect so the documentation is WRONG. Doing IO is not sufficient for not having to add "runtime.Gosched()" in loops.

You're not reading and writing channels in your loop. The only operation in the loop is a waitgroup add and a goroutine spawn. The operations inside the goroutine don't count.

Nevertheless, your use of runtime.GoSched isn't really necessary. It is required only for tight loops that do not have any other calls in them. But your usage does have the side effect of lowering the priority of the spawning loop in BurnCPU, which helps limit the pool of runnable goroutines (by running the ones you spawned and getting them to a blocking channel op before spawning more) and hence gives the GUI goroutine a larger fraction of the CPU.

adding "runtime.Gosched()" at that point should have no effect

I'm not sure where you are getting that from. Gosched is not required, but I'm not sure where you're getting the assertion that it should have no effect at all. It certainly can, and currently acts as a signal that other goroutines should execute in preference to the calling one (as described in the godoc for Gosched).

observed values of memstat percentage CPU spend on GC and cumulative duration of GC stops does not match (indicated 73% cpu usage during 200sec while cumulative time showed 0.47sec)

The GC is concurrent with program execution. The GC stops are very short and most of the GC work is done while the application is also running. That may explain the numbers you're seeing.

usage of map relative to fixed array with modulus index (simulating map) caused serious performance degradation in excess of 18x (unexpected due to map having no locking)

Maps are definitely slower than arrays. 18x does not sound unreasonable. Does that mean maps are really slow, or arrays are really fast? Array access can be as little as one instruction. Map access is at least a function call, and is hundreds of instructions even on the fast path.

Documented advances on reducing the delay time of GC "stop the world" are "misleading". The advance is due to the way the stops are measured (making it such that GC calls intersect with idle time of the application). However functions that do not actively WORK with this logic (by calling "runtime.Gosched()" all the time) seem to block the start of GC cleanup WHILE BLOCKING ALL OTHER GO ROUTINES. So this documented method of measuring GC performance is misleading (put politely).

I'm not sure how this relates to the benchmark provided. How are you determining that GC cleanup is blocking all other goroutines? It shouldn't, unless there's a bug somewhere. If there's a bug, we'd need to understand how you're reaching that conclusion. Ideally, with a self-contained example that we can run.

The results now look better and the blocking of the interactive part of the program is gone.
So this is good BUT there is no method of knowing how many of the runtime.NumGoroutine() are blocked (e.g. waiting for channel input) so this code is a potential DEADLOCK. So to make this solution work properly "runtime.NumGoroutine()" would have to be "runtime.NumUnblockedGoroutine()" (returning the number of go routines that are active plus the number of go routines that are pending to become active, so not counting go routines that wait for an IO/timer event).

Something like this would be really nice. We'd love to be able to stop the "spawning goroutine" when we have enough ready goroutines to saturate the cpus, and only resume the spawning goroutine when some of the spawned goroutines block or finish. Unfortunately, there's no easy way to look into the future behavior of goroutines; maybe the goroutine that was the spawning goroutine is actually done spawning and will next do something latency sensitive. There might be heuristics we can do, but it's tricky.

[StephanVerbeeck]

So this is good BUT there is no method of knowing how many of the runtime.NumGoroutine() are blocked (e.g. waiting for channel input) so this code is a potential DEADLOCK. So to make this solution work properly "runtime.NumGoroutine()" would have to be "runtime.NumUnblockedGoroutine()" (returning the number of go routines that are active plus the number of go routines that are pending to become active, so not counting go routines that wait for an IO/timer event).

Something like this would be really nice. We'd love to be able to stop the "spawning goroutine" when we have enough ready goroutines to saturate the cpus, and only resume the spawning goroutine when some of the spawned goroutines block or finish. Unfortunately, there's no easy way to look into the future behavior of goroutines; maybe the goroutine that was the spawning goroutine is actually done spawning and will next do something latency sensitive. There might be heuristics we can do, but it's tricky.

Agreed, but applies also to "runtime.NumGoroutine()" as the number of go routines can increase or decrease between the moment we test it and the moment we launch our own go routine.
From what I have measured today having slightly more active go routines than worker threads has little impact. As long as the number of active go routines fluctuates close to the number of worker threads the performance peaks.

Without the throttling logic e.g. ...

func ThrottleGO() {
	maxGoroutine := runtime.NumCPU() * 2
	nanoSec := time.Duration(0)
	for runtime.NumGoroutine() > maxGoroutine {
		time.Sleep(nanoSec)
		if nanoSec < 1e8 { // 100msec
			nanoSec += 1e5 // 0.1msec
		}
	}
}

... the amount of used memory for the same logic fluctuates wildly. With ...

outer := int(1e3)
inner := int(1e7)

...the amount of used (private allocated virtual pages) memory is 12Gb while with...

outer := int(1e7)
inner := int(1e3)

...the amount of used (private allocated virtual pages) memory is 260Mb. That is while in theory the amount of used CPU or memory should not change.

[StephanVerbeeck]

Finished optimisation by making my own version of the go routine logic.
Sharing the code here, average speedup (tested various combinations of load) is >300x

func burnCPU() {
	type aha struct{ a, b int }
	com := make(chan *aha, 100)
	throttle := Throttle{}
	for i := 1; i <= 10; i++ {
		go func() {
			oho := map[int]*aha{}
			for {
				c := <-com
				if c == nil {
					break
				}
				oho[c.a+c.b] = c
			}
		}()
	}
	outer := int(1e5)
	inner := int(1e5)
	throttle.Expect(outer)
	for a := 1; a <= outer; a++ {
		throttle.Go(func() {
			a := a
			for b := 1; b <= inner; b++ {
				b += 1234
				c := new(aha) // allocate some memory to cause GC
				c.a = 10 * (a)
				c.b = 10 * (b - 1234)
				b -= 1234
				if b%100 == 0 {
					com <- c
				}
			}
		})
	}
	routines := runtime.NumGoroutine()
	_ = routines
	throttle.Wait()
	close(com)
	routines = runtime.NumGoroutine()
	memStats := runtime.MemStats{}
	runtime.ReadMemStats(&memStats)
	return // <- set debug break here and examine memStats
}

Throttle.go

package main

// Alternative for sync.WaitGroup that uses automatic memory and CPU throttling

import (
	"runtime"
	"sync/atomic"
)

var (
	throttleNextGo Barrier
)

// Throttle CPU and memory usage by limiting amount of concurrent go routines
type Throttle struct {
	expected, started, done, max uint32
}

// Expect number of routines to launch (only required when calling Wait() before all routines are started)
func (tg *Throttle) Expect(expected int) {
	tg.expected = uint32(expected)
}

// Go routine (call to start go routine)
func (tg *Throttle) Go(action func()) {
	if tg.max == 0 {
		tg.max = uint32(runtime.NumCPU())
	}

	for tg.started-tg.done >= tg.max {
		throttleNextGo.Wait(100)
	}

	doit := func() {
		defer func() {
			atomic.AddUint32(&tg.done, 1)
			throttleNextGo.Open()
		}()
		action()
	}
	atomic.AddUint32(&tg.started, 1)
	go doit()
}

// Wait till last go routine is done (must have started at least 1 go routine)
func (tg *Throttle) Wait() {
	for tg.started > tg.done || tg.max == 0 || (tg.expected != 0 && tg.done < tg.expected) { // all routines done after starting at least one
		throttleNextGo.Wait(100)
	}
	*tg = Throttle{} // reset to make next Wait() work in case same throttle is used again
}

Barrier.go

package main

import (
	"golang.org/x/sys/windows"
)

/*
Barrier implements the ability to synchronize with another thread by waiting for the barrier until the other threads opens the barrier for us.
Each time the barrier is opened only a single thread can pass through before it closes again!
NOTE: The barrier does not remain open when nobody is waiting for it.  Only who is waiting when the barrier goes open can go through!
*/
type Barrier struct {
	handle   windows.Handle
	oneByOne bool
}

// Open barrier to wakeup threads that are waiting for the barrier
func (b *Barrier) Open() {
	if b.handle == windows.Handle(0) {
		b.handle, _ = windows.CreateEvent(nil, 0, 0, nil)
	}
	if b.oneByOne {
		windows.SetEvent(b.handle) // Release a single waiting thread
	} else {
		windows.PulseEvent(b.handle) // Release all waiting threads
	}
}

// Wait will suspend current thread until the barrier is opened by another thread, returns false on timeout
func (b *Barrier) Wait(msec int) bool {
	stat, _ := windows.WaitForSingleObject(b.handle, uint32(msec))
	return stat == windows.WAIT_OBJECT_0
}

// Cleanup will release used system resources
func (b *Barrier) Cleanup() {
	if b.handle != windows.Handle(0) {
		windows.CloseHandle(b.handle)
		b.handle = windows.Handle(0)
	}
}

[networkimprov]

What is the key to the latter code's success? Using the Windows API for scheduling?

Have you used the stdlib testing.B benchmark feature? Could it apply here? I'd find it easier to evaluate the slow and fast samples if they were compared one after the other. Also it would help to benchmark just the scheduling mechanism, as any workload to be scheduled takes the same time in either case.

Why do you need func doit (vs go func(){...}()), and why does it have a deferred call after a single stmt?