More Research Problems of Implementing Go

Dmitry Vyukov
Google

http://golang.org/

* About Go

Go is an open source programming language that makes it easy to build simple, reliable, and efficient software.

Design began in late 2007.

- Robert Griesemer, Rob Pike, Ken Thompson
- Russ Cox, Ian Lance Taylor

Became open source in November 2009.

Developed entirely in the open; very active community.
Language stable as of Go 1, early 2012.
Work continues.

* Motivation for Go

.image research2/datacenter.jpg

* Motivation for Go

Started as an answer to software problems at Google:

- multicore processors
- networked systems
- massive computation clusters
- scale: 10⁷⁺ lines of code
- scale: 10³⁺ programmers
- scale: 10⁶⁺ machines (design point)

Deployed: parts of YouTube, dl.google.com, Blogger, Google Code, Google Fiber, ...

* Go

A simple but powerful and fun language.

- start with C, remove complex parts
- add interfaces, concurrency
- also: garbage collection, closures, reflection, strings, ...

For more background on design:

- [[http://commandcenter.blogspot.com/2012/06/less-is-exponentially-more.html][Less is exponentially more]]
- [[http://talks.golang.org/2012/splash.article][Go at Google: Language Design in the Service of Software Engineering]]

* Research and Go

Go is designed for building production systems at Google.

- Goal: make that job easier, faster, better.
- Non-goal: break new ground in programming language research

Plenty of research questions about how to implement Go well.

- Concurrency
- Scheduling
- Garbage collection
- Race and deadlock detection
- Testing of the implementation


* Concurrency

.image research2/busy.jpg

* Concurrency

Go provides two important concepts:

A goroutine is a thread of control within the program, with its own local variables and stack. Cheap, easy to create.

A channel carries typed messages between goroutines.

* Concurrency

.play research2/hello.go

* Concurrency: CSP

Channels adopted from Hoare's Communicating Sequential Processes.

- Orthogonal to rest of language
- Can keep familiar model for computation
- Focus on _composition_ of regular code

Go _enables_ simple, safe concurrent programming.
It doesn't _forbid_ bad programming.

Caveat: not purely memory safe; sharing is legal.
Passing a pointer over a channel is idiomatic.

Experience shows this is practical.

* Concurrency

Sequential network address resolution, given a work list:

.play research2/addr1.go /lookup/+1,/^}/-1

* Concurrency

Concurrent network address resolution, given a work list:

.play research2/addr2.go /lookup/+1,/^}/-1

* Concurrency

Select statements: switch for communication.

.play research2/select.go /select/,/^}/-1

That's select that makes efficient implementation difficult.

* Implementing Concurrency

Challenge: Make channel communication scale

- start with one global channel lock
- per-channel locks, locked in address order for multi-channel operations

Research question: lock-free channels?


* Scheduling

.image research2/gophercomplex6.jpg

* Scheduling

On the one hand we have arbitrary user programs:

- fine-grained goroutines, coarse-grained goroutines or a mix of both
- computational goroutines, IO-bound goroutines or a mix of both
- arbitrary dynamic communication patterns
- busy, idle, bursty programs

No user hints!

* Scheduling

On the other hand we have complex hardware topology:

- per-core caches
- caches shared between cores
- cores shared between hyper threads (HT)
- multiple processors with non-uniform memory access (NUMA)

* Scheduling

Challenge: make it all magically work efficiently

- start with one global lock for all scheduler state
- distributed work-stealing scheduler with per-"processor" state
- integrated network poller into scheduler
- lock-free work queues

* Scheduling

Current scheduler:

 ┌─┐         ┌─┐         ┌─┐         ┌─┐                  ┌─┐
 │ │         │ │         │ │         │ │                  │ │
 ├─┤         ├─┤         ├─┤         ├─┤                  ├─┤ Global
 │ │         │G│         │ │         │ │                  │ │ state
 ├─┤         ├─┤         ├─┤         ├─┤                  ├─┤
 │G│         │G│         │G│         │ │                  │G│
 ├─┤         ├─┤         ├─┤         ├─┤                  ├─┤
 │G│         │G│         │G│         │G│                  │G│
 └┬┘         └┬┘         └┬┘         └┬┘                  └─┘
  │           │           │           │
  ↓           ↓           ↓           ↓
 ┌─┬──────┐  ┌─┬──────┐  ┌─┬──────┐  ┌─┬──────┐     ┌────┐┌──────┐┌───────┐
 │P│mcache│  │P│mcache│  │P│mcache│  │P│mcache│     │heap││timers││netpoll│
 └┬┴──────┘  └┬┴──────┘  └┬┴──────┘  └┬┴──────┘     └────┘└──────┘└───────┘
  │           │           │           │
  ↓           ↓           ↓           ↓
 ┌─┐         ┌─┐         ┌─┐         ┌─┐               ┌─┐ ┌─┐ ┌─┐
 │M│         │M│         │M│         │M│               │M│ │M│ │M│
 └─┘         └─┘         └─┘         └─┘               └─┘ └─┘ └─┘

G - goroutine; P - logical processor; M - OS thread (machine)

* Scheduling

Want:

- temporal locality to exploit caches
- spatial locality to exploit NUMA
- schedule mostly LIFO but ensure weak fairness
- allocate local memory and stacks
- scan local memory in GC
- collocate communicating goroutines
- distribute non-communicating goroutines
- distribute timers and network poller
- poll network on the same core where last read was issued


* Garbage Collection

* Garbage Collection

Garbage collection simplifies APIs.

- In C and C++, too much API design (and too much programming effort!) is about memory management.

Fundamental to concurrency: too hard to track ownership otherwise.

Fundamental to interfaces: memory management details do not bifurcate otherwise-similar APIs.

Of course, adds cost, latency, complexity in run time system.

* Garbage Collection

Plenty of research about garbage collection, mostly in Java context.

- Parallel stop-the-world
- CMS: concurrent mark-and-sweep, stop-the-world compaction
- G1: region-based incremental copying collector

Java collectors usually:

- are generational/incremental because allocation rate is high
- compact memory to support generations
- have pauses because concurrent compaction is tricky and slow

* Garbage Collection

But Go is very different!

- User can avoid lots of allocations by embedding objects:

	type Point struct {
		X, Y int
	}
	type Rectangle struct {
		Min, Max Point
	}

- Less pointers.
- Lots of stack allocations.
- Interior pointers are allowed:

	p := &rect.Max

- Hundreds of thousands of stacks (goroutines)
- No object headers so far

* Implementing Garbage Collection

Current GC: stop the world, parallel mark, start the world, concurrent sweep.
Concurrent mark is almost ready.

Cannot reuse Java GC algorithms directly.

Research question: what GC algorithm is the best fit for Go?
Do we need generations? Do we need compaction? What are efficient data structures that support interior pointers?


* Race and deadlock detection

.image research2/race.png 160 600

* Race detection

Based on ThreadSanitizer runtime, originally mainly targeted C/C++.
Traditional happens-before race detector based on vector clocks (devil in details!).
Works fine for Go, except:

 $ go run -race lots_of_goroutines.go
 race: limit on 8192 simultaneously alive goroutines is exceeded, dying

Research question: race dectector that efficiently supports hundreds of thousands of goroutines?

* Deadlock detection

Deadlock on mutexes due to lock order inversion:

 // thread 1                       // thread 2
 pthread_mutex_lock(&m1);          pthread_mutex_lock(&m2);
 pthread_mutex_lock(&m2);          pthread_mutex_lock(&m1);
 ...                               ...
 pthread_mutex_unlock(&m2);        pthread_mutex_unlock(&m1);
 pthread_mutex_unlock(&m1);        pthread_mutex_unlock(&m2);

Lock order inversions are easy to detect:

- build "M1 is locked under M2" relation.
- if it becomes cyclic, there is a potential deadlock.
- whenever a new edge is added to the graph, do DFS to find cycles.

* Deadlock detection

Go has channels and mutexes. Channels are semaphores. A mutex can be unlocked in
a different goroutine, so it is essentially a binary semaphore too.

Deadlock example:

	// Parallel file tree walk.
	func worker(pendingItems chan os.FileInfo)
		for f := range pendingItems {
			if f.IsDir() {
				filepath.Walk(f.Name(), func(path string, info os.FileInfo, err error) error {
					pendingItems <- info
				})
			} else {
				visit(f)
			}
		}
	}

pendingItems channel has limited capacity. All workers can block on send to pendingItems.

* Deadlock detection

Another deadlock example:

 var (
 	c = make(chan T, 100)
 	mtx sync.RWMutex
  )
 
 // goroutine 1      // goroutine 2         // goroutine 3
 // does send        // does receive        // "resizes" the channel
 mtx.RLock()         mtx.RLock()            mtx.Lock()
 c <- v              v := <-c               tmp := make(chan T, 200)
 mtx.RUnlock()       mtx.RUnlock()          copyAll(c, tmp)
                                            c = tmp
                                            mtx.Unlock()

RWMutex is fair for both readers and writers: when a writer arrives, new readers are not let to enter the critical section.
Goroutine 1 blocks on chan send; then goroutine 3 blocks on mtx.Lock; then goroutine 2 blocks on mtx.RLock.

* Deadlock detection

Research question: how to detect deadlocks on semaphores?

No known theory to date.


* Testing of the implementation

.image research2/gopherswrench.jpg 240 405

* Testing of the implementation

So now we have a new language with several complex implementations:

- lexer
- parser
- transformation and optimization passes
- code generation
- linker
- channel and map operations
- garbage collector
- ...

*How*do*you*test*it?*

* Testing of the implementation

Csmith is a tool that generates random C programs that statically and dynamically conform to the C99 standard.

.image research2/csmith.png

* Testing of the implementation

Gosmith is a tool that generates random Go programs that statically and dynamically conform to the Go standard.

Turned out to be much simpler than C: no undefined behavior all around!

- no unitialized variables
- no concurrent mutations between sequence points (x[i++] = --i)
- no UB during signed overflow
- total 191 kinds of undefined behavior and 52 kinds of unspecified behavior in C

* Testing of the implementation

But generates uninteresting programs from execution point of view: most of them deadlock or crash on nil deref.

Trophies:

- 31 bugs in gc compiler
- 18 bugs in gccgo compiler
- 5 bugs in llgo compiler
- 1 bug in gofmt
- 3 bugs in the spec

.image research2/emoji.png

* Testing of the implementation

Research question: how to generate random *interesting*concurrent* Go programs?

Must:

- create and wait for goroutines
- communicate over channels
- protect data with mutexes (reader-writer)
- pass data ownership between goroutines (explicitly and implicitly)

Must not:

- deadlock
- cause data races
- have non-deterministic results


* Research and Go

Plenty of research questions about how to implement Go well.

- Concurrency
- Scheduling
- Garbage collection
- Race and deadlock detection
- Testing of the implementation
- [Polymorphism]
- [Program translation]