Caleb Doxsey

One of my favorite parts about Go is its unwavering focus on utility. Sometimes we place so much emphasis on language design that we forget all the other things programming involves. For example:

• Go's compiler is fast
• Go comes with a robust standard library
• Go works on a multitude of platforms
• Go comes with a complete set of documentation available from the command line / a local web server / the internet
• All Go code is statically compiled so deployment is trivial
• The entirety of the Go source code is available for perusal in an easy format online (like this)
• Go has a well defined (and documented) grammar for parsing. (unlike C++ or Ruby)
• Go comes with a package management tool. go get X (for example go get code.google.com/p/go.net/websocket)
• Like all languages Go has a set of style guidelines, some enforced by the compiler (like Uppercase vs lowercase) and others merely conventional, but it also has a tool to clean up code: gofmt name_of_file.go.
• And there's also go fix which can automatically convert Go code designed for earlier versions to newer versions
• Go comes with a tool to test packages: go test /path/to/package. It can do benchmarks too.
• Go is debuggable and can be profiled.
• Did you know there's a playground to try out Go online?
• Go can interact with C libraries via cgo.

Those are just a few examples, but I want to focus on one that's not generally well known: Go can seamlessly use functions written in Assembly.

How to Use Assembly in Go

Suppose we want to write an assembly version of a sum function. First create a file called sum.go that contains this:

package sum

func Sum(xs []int64) int64 {
  var n int64
  for _, v := range xs {
    n += v
  }
  return n
}

This function just adds a slice of integers and gives you the result. To test it create a file called sum_test.go that contains this:

package sum

import (
  "testing"
)

type (
  testCase struct {
    n int64
    xs []int64
  }
)

var (
  cases = []testCase{
    { 0, []int64{} },
    { 15, []int64{1,2,3,4,5} },
  }
)

func TestSum(t *testing.T) {
  for _, tc := range cases {
    n := Sum(tc.xs)
    if tc.n != n {
      t.Error("Expected", tc.n, "got", n, "for", tc.xs)
    }
  }
}

Writing tests for your code is generally a good idea, but it turns out for library code (anything not package main) it also makes for a good way to experiment. Just type go test from the command line and it will run your tests.

Now lets replace this function with one written in assembly. We can start by examining what the Go compiler produces. Instead of go test or go build run this command: go tool 6g -S sum.go. (for a 64bit binary) You should see something like this:

--- prog list "Sum" ---
0000 (sum.go:3) TEXT    Sum+0(SB),$16-24
0001 (sum.go:4) MOVQ    $0,SI
0002 (sum.go:5) MOVQ    xs+0(FP),BX
0003 (sum.go:5) MOVQ    BX,autotmp_0000+-16(SP)
0004 (sum.go:5) MOVL    xs+8(FP),BX
0005 (sum.go:5) MOVL    BX,autotmp_0000+-8(SP)
0006 (sum.go:5) MOVL    xs+12(FP),BX
0007 (sum.go:5) MOVL    BX,autotmp_0000+-4(SP)
0008 (sum.go:5) MOVL    $0,AX
0009 (sum.go:5) MOVL    autotmp_0000+-8(SP),DI
0010 (sum.go:5) LEAQ    autotmp_0000+-16(SP),BX
0011 (sum.go:5) MOVQ    (BX),CX
0012 (sum.go:5) JMP     ,14
0013 (sum.go:5) INCL    ,AX
0014 (sum.go:5) CMPL    AX,DI
0015 (sum.go:5) JGE     ,20
0016 (sum.go:5) MOVQ    (CX),BP
0017 (sum.go:5) ADDQ    $8,CX
0018 (sum.go:6) ADDQ    BP,SI
0019 (sum.go:5) JMP     ,13
0020 (sum.go:8) MOVQ    SI,.noname+16(FP)
0021 (sum.go:8) RET     ,
sum.go:3: Sum xs does not escape

Assembly can be quite difficult to understand and we will take a look at this in more detail in a bit... but first lets go ahead and use this as a template. Create a new file called sum_amd64.s in the same folder as sum.go which contains this:

// func Sum(xs []int64) int64
TEXT ·Sum(SB),$0
    MOVQ    $0,SI
    MOVQ    xs+0(FP),BX
    MOVQ    BX,autotmp_0000+-16(SP)
    MOVL    xs+8(FP),BX
    MOVL    BX,autotmp_0000+-8(SP)
    MOVL    xs+12(FP),BX
    MOVL    BX,autotmp_0000+-4(SP)
    MOVL    $0,AX
    MOVL    autotmp_0000+-8(SP),DI
    LEAQ    autotmp_0000+-16(SP),BX
    MOVQ    (BX),CX
    JMP     L2
L1: INCL    AX
L2: CMPL    AX,DI
    JGE     L3
    MOVQ    (CX),BP
    ADDQ    $8,CX
    ADDQ    BP,SI
    JMP     L1
L3: MOVQ    SI,.noname+16(FP)
    RET

Basically all I did was replace the hardcoded line numbers for jumps (JMP, JGE) with labels and added a middle dot (·) before the function name. (Make sure to save the file as UTF-8) Next we remove our function definition from our sum.go file:

package sum

func Sum(xs []int64) int64

Now you should be able to run the tests again with go test and our custom assembly version of the function will be used.

How it Works

This type of assembly is described in more detail here. I will briefly explain what it's doing.

MOVQ    $0,SI

First we put 0 in the SI register, which is used to represent our running total. The Q means quadword which is 8 bytes, later we'll see L which is for 4 bytes. The parameters are in (source, destination) order.

MOVQ    xs+0(FP),BX
MOVQ    BX,autotmp_0000+-16(SP)
MOVL    xs+8(FP),BX
MOVL    BX,autotmp_0000+-8(SP)
MOVL    xs+12(FP),BX
MOVL    BX,autotmp_0000+-4(SP)

Next we take the parameter passed in and store its value on the stack. A Go slice is made up of 3 parts: a pointer to its location in memory, a length and a capacity. The pointer is 8 bytes, the length and capacity are 4 bytes each. So this code copies those values through the BX register. (See this for more details about slices)

MOVL    $0,AX
MOVL    autotmp_0000+-8(SP),DI
LEAQ    autotmp_0000+-16(SP),BX
MOVQ    (BX),CX

Next we put 0 in AX which we'll use as an iterator variable. We load the length of the slice into DI, and load xs' elements pointer into CX.

    JMP     L2
L1: INCL    AX
L2: CMPL    AX,DI
    JGE     L3

Now we get to the meat of the code. First we jump down to L2 where we compare AX and DI. If they're equal we've consumed all the items in the slice so we go to L3. (basically i == len(xs)).

MOVQ    (CX),BP
ADDQ    $8,CX
ADDQ    BP,SI
JMP     L1

This does the actual addition. First we get the value of CX and store it in BP. Then we move CX 8 bytes ahead. Finally we add BP to SI and jump to L1. L1 increments AX and starts the loop again.

L3: MOVQ    SI,.noname+16(FP)
  RET

After we've completed our summation we store the result after all the arguments to the function (so 16 bytes ahead because a slice is 16 bytes). Then we return.

Rewritten

Here's my rewrite of the code:

// func Sum(xs []int64) int64
TEXT ·Sum2(SB),7,$0
    MOVQ    $0, SI       // n
    MOVQ    xs+0(FP), BX // BX = &xs[0]
    MOVL    xs+8(FP), CX // len(xs)
    MOVLQSX CX, CX       // len as int64
    INCQ    CX           // CX++

start:
    DECQ    CX           // CX--
    JZ done              // jump if CX = 0
    ADDQ    (BX), SI     // n += *BX
    ADDQ    $8, BX       // BX += 8
    JMP start

done:
    MOVQ    SI, .noname+16(FP) // return n
    RET

Hopefully its a little easier to understand.

Caveats

It's pretty cool that you can do this, but it's not without its caveats:

• Assembly is hard to write, and especially hard to write well. Compilers will often write faster code than you will (and going forward the Go compiler will get better at this).
• Assembly only runs on one platform. In this case the code I wrote will only work on amd64. One solution to this problem is to supply a Go version of the code and call it from x86 and arm. (like this)
• Assembly ties you down in ways standard Go code won't. For example the length of slice is currently a 32 bit int. But it won't be for long. This code will break when that change is made (and it will break in nasty ways the compiler can't detect).
• Currently the Go compiler will not inline functions written in assembly, but it will inline small Go functions. So counterintuitively you can actually make your program slower by using assembly.

Still it's useful for at least two reasons:

1. Sometimes you need the power assembly can give you. (either for performance reasons, or the need for some highly specialized operation available in the CPU) The Go source code includes several good examples of when its appropriate to use (take a look at crypto and math).
2. This is actually a great way to learn assembly, since it's very easy to get started.

This is the first part on a series of posts relating to the recent LA Theology conference I had the privilege of attending. The subsequent entries in this series will deal with the particulars of the talks I attended, but before I talk about those I had a few general thoughts.

I decided to attend this conference mostly on a whim after reading about it on Fred Sander’s blog. I didn’t know anyone there - I’m neither a theologian nor an academic and I only just moved to the west coast. But I’ve had a special love of theology and philosophy since I was in High School, so I thought it might be interesting.

And it was interesting, albeit in ways I didn’t quite expect.

I enjoyed the talks at this conference; they were interesting, well presented and well argued. I was fairly surprised by how much I could follow. I’m not an academic and I’ve never even taken a formal theology class (though I’ve done a lot of study on my own), but there were only a few times where I wasn’t familiar with the material. I got most of the references and the arguments were usually pretty straightforward.

But I realized fairly quickly that my approach to the subject was very different than most of the people there. I’ve had to live most of my Christian life holding two things in tension: On the one hand I have to justify my interest in philosophy as something worth pursuing to the general Evangelical world (where such things aren’t typically held in high regard) and on the other hand I have to defend the common man against a theological precision he has no hope of ever attaining. How do we conceptualize the Christian life such that a Thomas Aquinas and a 3^rd world illiterate working man can share the same faith, while at the same time not presenting theology as a meaningless waste of time? I don’t know how to answer that question.

Pragmatism

Now don’t take this the wrong way; I don’t think I’d call myself practical or pragmatic. The problem with that philosophy is that it assumes the goal is obvious and anything which distracts from an immediate focus on that goal is irrational. But in reality the goal is not obvious.

For example someone might argue that a scholastic, systematic approach to theology is wrongheaded because it has no obvious “application” to our everyday lives. Left unstated is something like this: “the goal of life is [prosperity, comfort, ease, moral living, …] and this kind of theology doesn’t appear to have any obvious impact on that goal.” When you look at it that way its clear why pragmatism is hopelessly misguided. The purpose for our existence has to be something more than just prosperity, comfort, ease or moral living. So if your goal is wrong pragmaticism gets you nowhere.

More than that its mistaken for a second reason: Choosing the most obvious path to our goal is not always the best path. At the very least we can’t simply take this for granted. Sometimes you have to go the long way around to get to where you need to go and the shortcut will never get you there.

Here’s a strange connection: Have you heard of optimization problems? You see them all the time in mathematics and computer science. For example suppose you’re at your house and you want to find the quickest way to get to your local post office. This is an optimization problem. There are a great many ways you could get to your local post office, and you’re trying to find the “best” one (where “best” is something like shortest).

It seems to me that pragmatism is an example of one type of solution to this problem, a Greedy Algorithm:

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. Wikipedia

But the problem with greedy algorithms is that they sometimes get stuck at a “locally optimal” solution and never make it to the “globally optimal” one:

And this kind of proves my point: I don’t think there’s any way I could’ve know ahead of time that a bullet point from a highly specialized, technical discipline would have broad, far-reaching ramifications for my approach to decision making.

Liberalism is an elite person’s psychological investment in enjoying a guilt-free affluence. Victor Davis Hanson