LEFT | RIGHT |
(no file at all) | |
| 1 The Research Problems of Implementing Go |
| 2 |
| 3 Russ Cox |
| 4 Google |
| 5 |
| 6 http://golang.org/ |
| 7 |
| 8 * About the Talk |
| 9 |
| 10 I gave this talk at Google's Cambridge, Massachusetts office at an event for are
a Ph.D. students. The purpose of the event and the talk was to give a sense of s
ome of the research that goes on at Google. The talk presents some research ques
tions motivated by Go. We have answered some well, but others remain open. |
| 11 |
| 12 * About Go |
| 13 |
| 14 Go is an open source programming language that makes it easy to build simple, re
liable, and efficient software. |
| 15 |
| 16 Design began in late 2007. |
| 17 |
| 18 - Robert Griesemer, Rob Pike, Ken Thompson |
| 19 - Russ Cox, Ian Lance Taylor |
| 20 |
| 21 Became open source in November 2009. |
| 22 |
| 23 Developed entirely in the open; very active community. |
| 24 Language stable as of Go 1, early 2012. |
| 25 Work continues. |
| 26 |
| 27 * Motivation for Go |
| 28 |
| 29 .image ../2012/splash/datacenter.jpg |
| 30 |
| 31 * Motivation for Go |
| 32 |
| 33 Started as an answer to software problems at Google: |
| 34 |
| 35 - multicore processors |
| 36 - networked systems |
| 37 - massive computation clusters |
| 38 - scale: 10⁷ lines of code |
| 39 - scale: 10³ programmers |
| 40 - scale: 10⁶⁺ machines (design point) |
| 41 |
| 42 Deployed: parts of YouTube, dl.google.com, Blogger, Google Code, Google Fiber, .
.. |
| 43 |
| 44 * Go |
| 45 |
| 46 A simple but powerful and fun language. |
| 47 |
| 48 - start with C, remove complex parts |
| 49 - add interfaces, concurrency |
| 50 - also: garbage collection, closures, reflection, strings, ... |
| 51 |
| 52 For more background on design: |
| 53 |
| 54 - [[http://commandcenter.blogspot.com/2012/06/less-is-exponentially-more.html][L
ess is exponentially more]] |
| 55 - [[http://talks.golang.org/2012/splash.article][Go at Google: Language Design i
n the Service of Software Engineering]] |
| 56 |
| 57 * Research and Go |
| 58 |
| 59 Go is designed for building production systems at Google. |
| 60 |
| 61 - Goal: make that job easier, faster, better. |
| 62 - Non-goal: break new ground in programming language research |
| 63 |
| 64 Plenty of research questions about how to implement Go well. |
| 65 |
| 66 - Concurrency |
| 67 - Polymorphism |
| 68 - Garbage collection |
| 69 - Program translation |
| 70 |
| 71 * Concurrency |
| 72 |
| 73 * Concurrency |
| 74 |
| 75 Go provides two important concepts: |
| 76 |
| 77 A goroutine is a thread of control within the program, with its own local variab
les and stack. Cheap, easy to create. |
| 78 |
| 79 A channel carries typed messages between goroutines. |
| 80 |
| 81 * Concurrency |
| 82 |
| 83 .play ../2013/distsys/hello.go |
| 84 |
| 85 * Concurrency: CSP |
| 86 |
| 87 Channels adopted from Hoare's Communicating Sequential Processes. |
| 88 |
| 89 - Orthogonal to rest of language |
| 90 - Can keep familiar model for computation |
| 91 - Focus on _composition_ of regular code |
| 92 |
| 93 Go _enables_ simple, safe concurrent programming. |
| 94 It doesn't _forbid_ bad programming. |
| 95 |
| 96 Caveat: not purely memory safe; sharing is legal. |
| 97 Passing a pointer over a channel is idiomatic. |
| 98 |
| 99 Experience shows this is practical. |
| 100 |
| 101 * Concurrency |
| 102 |
| 103 Sequential network address resolution, given a work list: |
| 104 |
| 105 .play ../2013/distsys/addr1.go /lookup/+1,/^}/-1 |
| 106 |
| 107 * Concurrency |
| 108 |
| 109 Parallel network address resolution, given a work list: |
| 110 |
| 111 .play ../2013/distsys/addr2.go /lookup/+1,/^}/-1 |
| 112 |
| 113 * Implementing Concurrency |
| 114 |
| 115 Challenge: Make channel communication scale |
| 116 |
| 117 - start with one global channel lock |
| 118 - per-channel locks, locked in address order for multi-channel operations |
| 119 |
| 120 Research question: lock-free channels? |
| 121 |
| 122 * Polymorphism |
| 123 |
| 124 * Interfaces |
| 125 |
| 126 An interface defines a set of methods. |
| 127 |
| 128 package io |
| 129 ········ |
| 130 type Writer interface { |
| 131 Write(data []byte) (n int, err error) |
| 132 } |
| 133 |
| 134 * Interfaces |
| 135 |
| 136 A type implements the interface by implementing the methods. |
| 137 |
| 138 package bytes |
| 139 ········ |
| 140 type Buffer struct { |
| 141 ... |
| 142 } |
| 143 ········ |
| 144 func (b *Buffer) Write(data []byte) (n int, err error) { |
| 145 ... |
| 146 } |
| 147 |
| 148 * Interfaces |
| 149 |
| 150 An implementation of an interface can be assigned to a variable of that interfac
e type. |
| 151 |
| 152 package fmt |
| 153 ········ |
| 154 func Fprintf(w io.Writer, format string, args ...interface{}) |
| 155 |
| 156 * Interfaces |
| 157 |
| 158 .play ../2013/distsys/writebuffer.go /^func.main/+1,/^}/-1 |
| 159 |
| 160 * Interface Advantages |
| 161 |
| 162 - no dependence between interface and implementation |
| 163 - easy testing |
| 164 - avoids overdesign, rigid hierarchy of inheritance-based OO |
| 165 |
| 166 The source of all generality in the Go language. |
| 167 |
| 168 * Implementing Interfaces |
| 169 |
| 170 How do you make method dispatch efficient? |
| 171 |
| 172 b := new(bytes.Buffer) |
| 173 var w io.Writer |
| 174 w = b |
| 175 fmt.Fprintf(w, "hello, %s\n", "world") |
| 176 ... w.Write(text) // what happens here? |
| 177 |
| 178 At w.Write call, how does the runtime find the method to call? |
| 179 |
| 180 * Implementing Interfaces |
| 181 |
| 182 How do you make method dispatch efficient? |
| 183 |
| 184 b := new(bytes.Buffer) |
| 185 var w io.Writer |
| 186 w = b // do the work here! |
| 187 fmt.Fprintf(w, "hello, %s\n", "world") |
| 188 ... w.Write(text) // plain indirect function call |
| 189 |
| 190 Interface holds two words: "itable" and actual value (or pointer to value). |
| 191 |
| 192 Itable contains type information plus list of function pointers for methods in i
nterface. |
| 193 |
| 194 w.itable.fn[1](w.data, text) |
| 195 |
| 196 Conversion sites usually trivial to cache. |
| 197 |
| 198 * Interfaces for Algorithms |
| 199 |
| 200 package sort |
| 201 ········ |
| 202 type Interface interface { |
| 203 Len() int // return number of elements, len(x) |
| 204 Less(i, j int) bool // report whether x[i] < x[j] |
| 205 Swap(i, j int) // x[i], x[j] = x[j], x[i] |
| 206 } |
| 207 ········ |
| 208 func Sort(data Interface) |
| 209 |
| 210 Requires some boilerplate for each use: |
| 211 |
| 212 type bySubject []Thread |
| 213 ········ |
| 214 func (x bySubject) Less(i, j int) bool { return x[i].Subject < x[j].Subj
ect } |
| 215 func (x bySubject) Swap(i, j int) { x[i], x[j] = x[j], x[i] } |
| 216 func (x bySubject) Len() int { return len(x) } |
| 217 |
| 218 sort.Sort(bySubject(threads)) |
| 219 |
| 220 * Polymorphism: Can we do better? |
| 221 |
| 222 func Sort(data []T, less func(x, y *T) bool) |
| 223 |
| 224 sort.Sort(threads, func(x, y *Thread) bool { |
| 225 return x.Subject < y.Subject |
| 226 }) |
| 227 ········ |
| 228 Research question: what's a reasonable semantics? |
| 229 Research question: what's a reasonable implementation? |
| 230 |
| 231 - C says don't bother. |
| 232 - C++ makes many copies of the same function. |
| 233 - Java boxes everything implicitly: one function, but expensive data model. |
| 234 - Java discards run-time type information. |
| 235 |
| 236 Do you want slow programmers, slow compilers and bloated binaries, or slow execu
tion? |
| 237 |
| 238 * Garbage Collection |
| 239 |
| 240 * Garbage Collection |
| 241 |
| 242 Garbage collection simplifies APIs. |
| 243 |
| 244 - In C and C++, too much API design (and too much programming effort!) is about
memory management. |
| 245 |
| 246 Fundamental to concurrency: too hard to track ownership otherwise. |
| 247 |
| 248 Fundamental to interfaces: memory management details do not bifurcate otherwise-
similar APIs. |
| 249 |
| 250 Of course, adds cost, latency, complexity in run time system. |
| 251 |
| 252 * Avoiding Garbage Collection |
| 253 |
| 254 Observation: garbage collection is a service, and like any service it can be ove
rloaded, oversubscribed. |
| 255 |
| 256 Go lets you limit allocation by controlling memory layout. |
| 257 |
| 258 type Point struct { |
| 259 X, Y int |
| 260 } |
| 261 ········ |
| 262 type Rectangle struct { |
| 263 Min, Max Point |
| 264 } |
| 265 |
| 266 * Implementing Garbage Collection |
| 267 |
| 268 Language decision: interior pointers are allowed, as are foreign pointers |
| 269 |
| 270 - Cannot reuse Java GC algorithms directly. |
| 271 - But gives _programmer_ more control over allocation. |
| 272 |
| 273 Allocator: objects are allocated in pages with other objects of the same size. |
| 274 |
| 275 Current GC: stop the world, parallel mark, start the world, background sweep. |
| 276 |
| 277 Research question: how to make collector lower latency, possibly incremental? |
| 278 |
| 279 * Program Translation |
| 280 |
| 281 * Program Translation |
| 282 |
| 283 Go programs can be parsed without context (unlike C and C++). |
| 284 Go ships with a standard program formatter. |
| 285 |
| 286 Makes automated edits indistinguishable from manual edits. |
| 287 |
| 288 $ cat x.go |
| 289 package main |
| 290 ········ |
| 291 var b bytes.Buffer |
| 292 ········ |
| 293 $ gofmt -r 'bytes.Buffer -> bytes.Writer' x.go |
| 294 package main |
| 295 ········ |
| 296 var b bytes.Writer |
| 297 ········ |
| 298 $· |
| 299 |
| 300 More advanced rewrites: "go fix" for API adjustments. |
| 301 |
| 302 * Program Translation |
| 303 |
| 304 Research Question: What about translating other programs to Go? |
| 305 |
| 306 Exploring the conversion of C programs to Go today. |
| 307 |
| 308 - Decide return type (for example, int vs bool). |
| 309 - Decide which variables are pointers vs arrays. |
| 310 - Decide which functions are really methods. |
| 311 - Decide natural package boundaries. |
| 312 |
| 313 What about other languages? |
| 314 |
| 315 * Research and Go |
| 316 |
| 317 Plenty of research questions about how to implement Go well. |
| 318 |
| 319 - Concurrency |
| 320 - Polymorphism |
| 321 - Garbage collection |
| 322 - Program translation |
| 323 |
LEFT | RIGHT |