{"id":823,"date":"2009-11-13T09:19:35","date_gmt":"2009-11-13T09:19:35","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/11\/13\/the-go-i-forgot-concurrency-and-go-routines\/"},"modified":"2009-11-13T09:19:35","modified_gmt":"2009-11-13T09:19:35","slug":"the-go-i-forgot-concurrency-and-go-routines","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/11\/13\/the-go-i-forgot-concurrency-and-go-routines\/","title":{"rendered":"The Go I Forgot: Concurrency and Go-Routines"},"content":{"rendered":"

A couple of people pointed out that in my wednesday post about Go<\/a>, I completely left out the concurrency stuff! That’s what I get for rushing the post – I managed to leave out one of the most interesting subjects! Go provides very strong support for communicating processes. <\/p>\n

I haven’t done a lot of hacking with the concurrency stuff yet – so my impressions of it are still very preliminary. But my early impressions are very<\/em> good. <\/p>\n

<\/p>\n

A lot of people have been talking about Go as a language for distributed computation. I don’t think that’s correct: Go programs run in a single, shared address space. You can have multiple concurrent threads; if you have multiple CPUs, those threads can be run in parallel. But it’s only concurrency within a single OS process and a single address space. To me at least, distributed means that a program runs on multiple machines. Go is pretty good for writing distributed programs, but that’s not what the concurrency support in Go is; What it is<\/em> is really solid support for coroutine-style threading, with explicit communication between the threads.<\/p>\n

(Addendum 2011: Go now supports a library called netchan, and with that, it’s really a great language for distributed programs. In fact, in my opinion, it’s the<\/em> best imperative language for distributed programs.)<\/p>\n

The flavor of the communication system is very π-calculus-like. You can, at any time, start a new thread by invoking a function: just prefix the invocation with the word “go”. So “f(x)<\/code>” is a function call; “go f(x)<\/code>” is an invocation of a goroutine<\/em> which is, which runs concurrently with the code that called it.<\/p>\n

Once you’ve created a go-routine, you can only talk to it through channels<\/em>> – you don’t have any handle or identifier for the executing goroutine, unless you create one by using a channel. A channel is very much like the π-calculus concept of a channel name: it’s a first-class value which can be passed around. Channels support two operations: output, and input. Any channel operation blocks until a matching operation is executed by a different goroutine. So writing to a channel blocks until someone reads it; reading from a channel blocks until someone writes something for you to read. The channels are strongly typed – you can only pass a single type of value over a channel.<\/p>\n

So, for example, to write a program where you launch a thread to do a computation, and then read the result when it’s done, you could do:<\/p>\n

\nfunc ComputeAValue(c chan float64) {\n  \/\/ Do the computation.\n  x := 2.3423 \/ 534.23423\n  c <- x\n}\n\nfunc UseAGoroutine() {\n  channel := make(chan float64)\n  go ComputeAValue(channel)\n  \/\/ do something else for a while\n  value := <- channel\n  fmt.Printf(\"Result was: %v\", value)\n}\n<\/pre>\n
 It’s very simple, and very convenient. And since Go has anonymous functions, you could also write it as:<\/p>\n
\nfunc UseAGoroutine() {\n  channel := make(chan float64)\n  go func(c chan float64) {\n    \/\/ Do the computation.\n    x := 2.3423 \/ 534.23423\n    c <- x\n  }(channel)\n  \/\/ do something else for a while\n  value := <- channel;\n  fmt.Printf(\"Result was: %v\", value);\n}\n<\/pre>\n
 Even better, Go has lexical scope – so you don’t actually need to pass the channel:<\/p>\n
\nfunc UseAGoroutine() {\n  channel := make(chan float64)\n  go func() {\n    \/\/ Do the computation.\n    x := 2.3423 \/ 534.23423\n    c <- x\n  }()\n  \/\/ do something else for a while\n  value := <- channel\n  fmt.Printf(\"Result was: %v\", value)\n}\n<\/pre>\n
 Goroutines all run in the same thread, so you can also do implicit communication via shared variables. The standard libraries include things like mutexes so that you can implement other forms of communication and sharing between goroutines, but communication via channels is intended to be the main way that gorountines interact.<\/p>\n
 In the implementation, the goroutines are very cheap and lightweight, and they’re multiplexed onto OS threads. So you don’t need to worry (much) about creating lots of goroutines – they’ll get mapped onto a manageable set of OS threads. This allows you to do some really neat things where you create tons of goroutines. An example that I really like is in the Go tutorial: it’s a go-routine based version of the sieve algorithm for computing primes.<\/p>\n
 In the sieve, you start with the set of all integers greater than or equal to 2. 2 is the first prime – so you go through the rest of the list, and get rid of all multiples of 2. Now, the first number remaining in the list is the next prime: 3. So you go through and strike out all multiples of 3. Then the first element of the list is the next prime, 5. And so on.<\/p>\n
 This translates pretty naturally into a collection of concurrent filters. Each filter removes multiples of one prime. You just pump numbers through the filter in sequence. Anything that passes the filter for 2 gets sent to the filter for three. Anything that passes the filter for three gets sent to the filter for 5. Anything that gets past the last filter is the next prime – so you add another filter to the chain, and return the new prime.<\/p>\n
 To write that in Go, you start with a go-routine that generates the sequence of integers:<\/p>\n
\nfunc generate_integers() chan int {\n  ch := make(chan int)\n  go func(){\n    for i := 2; ; i++ {\n      ch <- i\n    }\n  }()\n  return ch;\n}\n<\/pre>\n
 That’s very simple: just create a channel, and then start a goroutine that loops through the integers greater than or equal to to, writing them to the channel. It returns the channel that you can read the numbers from. <\/p>\n
 Next, we need to write a filter that removes all multiples of some number: <\/p>\n
\nfunc filter_multiples(in chan int, prime int) chan int {\n  out := make(chan int)\n  go func() {\n    for {\n      if i := <- in; i % prime != 0 {\n        out <- i\n      }\n    }\n  }();\n  return out;\n}\n<\/pre>\n
 That creates a channel, which will be used to emit the values that pass the filter. Then it starts a goroutine which actually runs the filter: itreads values from the input channel, and then tests them to see if they’re a multiple of the filter prime. If they’re not, it writes them to the output channel. (You can see another bit of minimalism there; all loops in Go are written using for<\/code>.)<\/p>\n
 Now for the clever part: stringing the go-routines together.<\/p>\n
\nfunc sieve() chan int {\n  out := make(chan int)\n  go func() {\n    ch := generate_integers()\n    for {\n      prime := <- ch\n      out <- prime\n      ch = filter_multiples(ch, prime)\n    }\n  }()\n  return out\n}\n<\/pre>\n
 So – we create an initial output channel – that’s the channel from which we’ll be able to read the primes. Then we start running the sieve in a goroutine. The goroutine starts the integer sequence generator. Then it runs a loop. It grabs the next number in sequence, which is the next prime. It writes that to the output channel. Then it creates a new filter, which filters that one. It takes the output from the previous filter, and chains it to be the input to the next one. Soyou wind up building a chain of filters. Each time you get a new prime, it creates a new filter with its own goroutine, and adds it to the chain.<\/p>\n
 Then you can easily print out the primes:<\/p>\n
\nfunc main() {\n  primes := sieve()\n  for {\n    fmt.Println(<-primes);\n  }\n}\n<\/pre>\n
 That’s obviously a toy example – but it’s a very cool<\/em> toy example.<\/p>\n
 More real examples of where this could be useful? Well, in my not-very-abundant free time, I’ve been working on a text editor. I’m building it in a very decoupled way – there’s a backend which has an interface that’s almost like a little programming language based on regular expressions, and a front-end that basically translates keystrokes and UI actions into commands. In Go, it’s a pair of goroutines. The UI sends commands to the backend; the backend sends UI updates to the front-end. It’s all done with a single pair of channels. I came up with that basic design before I knew about Go; I started the original implementation in Java using threads, queues, and locks to build the communication between the components. In Go, it’s much simpler, and much cleaner. And I can add other things into the process just by chaining together channels.<\/p>\n
 There is, of course, a lot more to goroutines and channels than what I’ve written here. The type system for channels is pretty nice: you can distinguish between generic channels (with which you can do whatever you want), read-only channels, and write-only channels. You can use a switch-like select<\/code> block to allow you to do things like wait for an input from any of a group of channels. You can set buffer sizes.<\/p>\n
 Why a whole post about this? Because, these days, we’re all using multi-core computers. For the most part, the way that we’re making things faster isn’t really by making them faster<\/em>: we’ve been running into some physical barriers that make it hard to keep pushing raw CPU speed. Instead, we’ve been adding CPUs: my laptop has 2 processors, and my server has 8 processors. We’re getting things done faster by dividing the work up into pieces, and doing those pieces simultaneously. But most of our programming languages really<\/em> suck at describing concurrency.<\/p>\n
 Goroutines and channels provide the best support I’ve seen outside of Erlang for making use of concurrency. And frankly, I think Go is a lot less ugly than Erlang. (Sorry Erlang fans, but I really don’t like Erlong.) Compared to Java, which I think is the main competitor to Go in this area, Go’s goroutines and channels are just so much easier to work with than Java threads and locks, there’s just absolutely no<\/em> comparison at all. Go pretty much destroys the competition in this area.<\/p>\n
 Of course, some of my general complaints about Go carry over. Channels are basically parametric types. But I can’t write my own parametric channels. In other words, I can’t write a piece of code that does something like create generic software-transactional memory, and then let people create a cell of STM that specifically stores integers. I can create an STM cell which stores values – but I can’t do much to say what those values are. <\/p>\n
 On the other hand, channels do make it easy to do good exception handling of concurrent code. You add a parameter to the goroutine function which is a channel that will be used to signal errors. If anything goes wrong in the goroutine, you have it send an error report to that channel. That’s actually about as good as any thread-based exception handling system I’ve ever seen.<\/p>\n","protected":false},"excerpt":{"rendered":"
A couple of people pointed out that in my wednesday post about Go, I completely left out the concurrency stuff! That’s what I get for rushing the post – I managed to leave out one of the most interesting subjects! Go provides very strong support for communicating processes. I haven’t done a lot of hacking […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[50,54],"tags":[],"class_list":["post-823","post","type-post","status-publish","format-standard","hentry","category-pi-calculus","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-dh","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/823","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=823"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/823\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=823"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=823"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=823"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}