Saturday, November 15, 2014

Go Solves Busy-Waiting

Are you wasting CPU time?

It's something that I see all too often, busy waiting in applications and libraries alike. You've probably seen it too, it looks a little like this:
 for{  
   poll() // returns right away if nothing happened!
 }  
The main problem with this is that the CPU spins constantly in that for loop when it doesn't need to be. So of course, the generally accepted solution is to make the poll function above, instead, become blocking:
 for{  
   block() // waits for something to happen!  
 }  

The Problem

/sarcasm/ And that's great! /sarcasm/. Until you want to do multiple things:
 for{  
   type() // Blocking: wait for someone to type something.  
   cursor() // Blocking: wait for someone to move their cursor.  
 }  
I know what you're thinking:

  • That's just unreasonable!
  • You should just go back to polling!
  • Two things can't be done at once! You'd have to use a very complex threading scheme!

A Real World Problem

Recently while developing the gfx.v2/window package for Azul3Dwhich lets you open, manipulate, and render graphics to windows on your computer: I ran into this very problem.

For the new version of this package, we wanted to give users two new features (among others):
  1. Full control of the main loop, if you want it. (i.e. to run Cocoa API's yourself).
  2. Multiple windows instead of just one window, on platforms that support it. (i.e. not mobile devices).
Now, not so deep in the depths of this package it makes use of libraries like GLFW -- which on OS X makes use of the Cocoa API. And if you don't already know: Cocoa is a finicky beast because it has to be ran on the main thread. That's right, not just the same thread but literally the main thread.

This puts us into a very tricky situation: each window needs to run functions on the main thread itself, but we want to give control of the main OS thread to the user without busy-waiting.

Existing Approaches Don't Work Well

The Blocking Approach

  • The user can't run anything else in the main loop.
  • (Is there a point in exposing the main loop with this approach at all?)

The Polling Approach

  • The user can run what they want in the main loop.
  • The CPU spins constantly waiting for work to do, a complete waste!

A Communicative Main Loop!

The solution that we came up with is not extremely novel, but it does show the true power of Go in complex situations such as this. Here we present a pattern for a communicative main loop:
  1. If you want to constantly run things on the main loop, start a separate goroutine.
    • Each window in our case, is a separate goroutine.
  2. When a goroutine wants to run something on the main OS thread, send it over a channel to the main loop.
    • Each window in our case, sends tasks to, for example, create the window, render to the window, etc over a channel to the main loop for execution.
  3. The main loop (which runs on the main thread) simply waits for tasks to execute on the main loop.

Implementation

So our main loop (see 3) could be implemented as easily as this:
 var MainLoopChan = make(chan func())  
 func MainLoop() {  
   for{  
     fn := <-MainLoopChan  
     fn()  
   }  
 }  
Notice that the channel is a channel of closure functions: You can literally send a closure over a channel to another goroutine for execution by that goroutine!

Each separate goroutine (see 1 and 2) could send their task to be ran on the main loop with just:
 MainLoopChan <- func() {  
   fmt.Println("I am running in the main loop!")  
 }  
When that function is executed by the MainLoop, it will be executed on the main OS thread.

If we had a function that needs to execute things on the main OS thread -- but might error out, we can handle this situation by introducing one more channel:
 func OpenWindow() error {  
   err := make(chan error, 1)  
   MainLoopChan <- func() {  
     if e := cocoa.OpenWindow(); e != nil {  
       // Can't open the window.  
       err <- e  
       return  
     }  
     err <- nil // No error occurred.  
   }  
   return <-err  
 }  

Thread-Safety

A fun side effect of the above implementation of OpenWindow, is that it has indirectly made the OpenWindow function callable safely from any goroutine/thread! No matter which thread calls the function, it will always ask the main thread to execute the actual, thread-specific, task of opening a Cocoa window.

Conclusion

You could probably implement the same thing in other standard languages (C++, Java, etc) but I would be shocked if you could have the code appear so clean and easy to understand.

Go's features such as first-class functions, goroutines, and channels give us the ability to solve difficult and complex problems like this one to make thread-specific API's like Cocoa accessible from multiple goroutines. And best of all, the code is easy to read and understand.