Sunday, July 1, 2012

The master/worker pattern is used to get an amount of work done by a number of workers. Each worker grabs an item from a work queue and does the work on that item. When the worker is done, it will grab the next item from the work queue, and so on until all the work has been done. The cool thing is that all the work can be done in parallel (if the work items have no dependencies on each other). The speedup practically scales linearly with respect to the number of CPU cores used to run the workers. The master/worker pattern can be implemented on a distributed/cluster computer using message passing or on a shared memory computer using threads and mutexes.

Implementing master/worker for a shared memory system in Go is a doddle because of goroutines and channels. Yet I dedicate this post to it because it’s easy to implement it in a suboptimal way. If you care about efficiency, take this to heart:

• Spawn a worker per CPU core beforehand. If you spawn a worker per item, you are spawning too many threads. No matter how cheap spawning a thread may be, spawning fewer threads is cheaper.
• It’s a shared memory model. So pass pointers rather than full objects.
• The workers never signal when they’re done. They don’t have to. Instead, the master signals he is out of work when all work has been done.

Lastly, there is no point in making the master a goroutine by itself. The master does fine running from the main thread.

So, let’s code. The function WorkParallel processes all the work in parallel. Capital Work is a struct that represents a single work item, lowercase work is an array (slice) that holds all the work to be done. The work queue is implemented using a channel.

func WorkParallel(work []Work) {
    queue := make(chan *Work)

    ncpu := runtime.NumCPU()
    if len(work) < ncpu {
        ncpu = len(work)
    }
    runtime.GOMAXPROCS(ncpu)

    // spawn workers
    for i := 0; i < ncpu; i++ {
        go Worker(i, queue)
    }

    // master: give work
    for i, item := range(work) {
        fmt.Printf("master: give work %v\n", item)
        queue <- &work[i]  // be sure not to pass &item !!!
    }

    // all work is done
    // signal workers there is no more work
    for n := 0; n < ncpu; n++ {
        queue <- nil
    }
}

func Worker(id int, queue chan *Work) {
    var wp *Work
    for {
        // get work item (pointer) from the queue
        wp = <-queue
        if wp == nil {
            break
        }
        fmt.Printf("worker #%d: item %v\n", id, *wp)

        handleWorkItem(wp)
    }
}

There is more than one way to do it, and I can imagine you wanting to rewrite this code to not use any pointers in order to increase readability. Personally I like it with pointers though because of the higher performance. Whether you actually need this performance is another question. Often it is largely a matter of opinion, even taste. In fact, Go itself isn’t all that high performing. But if you want to push it to the max, then by definition, the pointer-based code will outperform the code without pointers.