The slowest way to speed up your Go program

There is something great about assembly language programming. It can be very slow and full of errors compared to programming in a language such as Go, but sometimes it is a good idea or at least a very fun activity.

Why spend time programming in assembly language when there are excellent high-level programming languages? Even with today's compilers, there are still a few cases where you want to write assembler code. These are cryptography , performance optimization, or access to things that are usually not available in the language . The most interesting, of course, is performance optimization.

When the performance of some part of your code really matters to the user, and you have already tried the simpler ways to make it faster, writing code in assembler can be a good place to optimize. Although the compiler can be perfectly optimized for creating assembler code, you can know more about a particular case than the compiler can assume.

Writing assembly code in Go

The best way to get started is to write a simple function. For example, a function addadds two int64s.

package main
import "fmt"
func add(x, y int64) int64 {
    return x + y
}
func main() {
    fmt.Println(add(2, 3))
}

Launch: go build -o add-go && ./add-go

To implement this function in assembler, create a separate file add_amd64.sthat will contain assembler code. The examples use assembler for the AMD64 architecture.

add.go:

package main
import "fmt"
func add(x, y int64) int64
func main() {
    fmt.Println(add(2, 3))
}

add_amd64.s:

#include "textflag.h"
TEXT ·add(SB),NOSPLIT,$0
    MOVQ x+0(FP), BX
    MOVQ y+8(FP), BP
    ADDQ BP, BX
    MOVQ BX, ret+16(FP)
    RET

To run the example, put these two files in the same directory and run the command go build -o add && ./add

The assembler syntax is at best ... unclear. There is an official Go manual and a rather ancient manual for Plan 9 assembler , which provides some tips on how the assembler language works in Go. The best sources for the study - an existing assembly code and compiled versions of Go Go functions that can be obtained by running the command: .go tool compile -S

The most important things you need to know are function declarations and stack layouts.

Magic spell to launch function TEXT ·add(SB), NOSPLIT, $0. The Unicode character character ·separates the package name from the function name. In this case, the package name is - main, so the package name is empty, and the function name is add. The directive NOSPLITmeans that you do not need to write the size of the arguments as the next parameter. The constant $0at the end is where you will need to put the size of the arguments, but since we have NOSPLIT, we can just leave it as $0.

Each argument of the function is pushed 0(FP)onto the stack, starting with the address , which means an offset of zero bytes from the pointer FP, and so on for each argument and return value. For func add (x, y int64) int64, it looks like this:

Let's analyze the code of an already familiar function add:

TEXT ·add(SB),NOSPLIT,$0
    MOVQ x+0(FP), BX
    MOVQ y+8(FP), BP
    ADDQ BP, BX
    MOVQ BX, ret+16(FP)
    RET

The assembler version of the function addloads the variable x at the memory address +0(FP)into the register BX. Then it loads from memory yat the address +8(FP)in the register BP, adds BPand BX, saving the result in BX, and finally copies BXto the address +16(FP)and returns from the function. The calling function, which pushes all arguments onto the stack, will read the return value from where we left it.

Function optimization using assembler

It is not necessary to write assembler a function that adds two numbers, but why do you really need to use it?

Suppose you have a bunch of vectors, and you want to multiply them by the transformation matrix. Perhaps vectors are points, and you want to move them in space ( translation on Habré - approx. Per.) . We will use vectors with a 4x4 transform matrix.

type V4 [4]float32
type M4 [16]float32
func M4MultiplyV4(m M4, v V4) V4 {
    return V4{
        v[0]*m[0] + v[1]*m[4] + v[2]*m[8] + v[3]*m[12],
        v[0]*m[1] + v[1]*m[5] + v[2]*m[9] + v[3]*m[13],
        v[0]*m[2] + v[1]*m[6] + v[2]*m[10] + v[3]*m[14],
        v[0]*m[3] + v[1]*m[7] + v[2]*m[11] + v[3]*m[15],
    }
}
func multiply(data []V4, m M4) {
    for i, v := range data {
        data[i] = M4MultiplyV4(m, v)
    }
}

Execution takes 140 ms for 128 MB of data. Which implementation could be faster? The reference will be a copy of the memory, which takes about 14 ms.

The following is a version of the function written in assembler using SIMD instructions to perform multiplications, allowing you to multiply four 32-bit floating-point numbers in parallel:

#include "textflag.h"
// func multiply(data []V4, m M4)
//
// компоновка памяти стека относительно FP
//  +0 слайс data, ptr
//  +8 слайс data, len
// +16 слайс data, cap
// +24 m[0]  | m[1]
// +32 m[2]  | m[3]
// +40 m[4]  | m[5]
// +48 m[6]  | m[7]
// +56 m[8]  | m[9]
// +64 m[10] | m[11]
// +72 m[12] | m[13]
// +80 m[14] | m[15]
TEXT ·multiply(SB),NOSPLIT,$0
  // data ptr
  MOVQ data+0(FP), CX
  // data len
  MOVQ data+8(FP), SI
  // указатель на data
  MOVQ $0, AX
  // ранний возврат, если нулевая длина
  CMPQ AX, SI
  JE END
  // загрузка матрицы в 128-битные xmm-регистры (https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions#Registers)
  // загрузка [m[0], m[1], m[2], m[3]] в xmm0
  MOVUPS m+24(FP), X0
  // загрузка [m[4], m[5], m[6], m[7]] в xmm1
  MOVUPS m+40(FP), X1
  // загрузка [m[8], m[9], m[10], m[11]] в xmm2
  MOVUPS m+56(FP), X2
  // загрузка [m[12], m[13], m[14], m[15]] в xmm3
  MOVUPS m+72(FP), X3
LOOP:
  // загрузка каждого компонента вектора в регистры xmm
  // загрузка data[i][0] (x) в xmm4
  MOVSS    0(CX), X4
  // загрузка data[i][1] (y) в xmm5
  MOVSS    4(CX), X5
  // загрузка data[i][2] (z) в xmm6
  MOVSS    8(CX), X6
  // загрузка data[i][3] (w) в xmm7
  MOVSS    12(CX), X7
  // копирование каждого компонента матрицы в регистры
  // [0, 0, 0, x] => [x, x, x, x]
  SHUFPS $0, X4, X4
  // [0, 0, 0, y] => [y, y, y, y]
  SHUFPS $0, X5, X5
  // [0, 0, 0, z] => [z, z, z, z]
  SHUFPS $0, X6, X6
  // [0, 0, 0, w] => [w, w, w, w]
  SHUFPS $0, X7, X7
  // xmm4 = [m[0], m[1], m[2], m[3]] .* [x, x, x, x]
  MULPS X0, X4
  // xmm5 = [m[4], m[5], m[6], m[7]] .* [y, y, y, y]
  MULPS X1, X5
  // xmm6 = [m[8], m[9], m[10], m[11]] .* [z, z, z, z]
  MULPS X2, X6
  // xmm7 = [m[12], m[13], m[14], m[15]] .* [w, w, w, w]
  MULPS X3, X7
  // xmm4 = xmm4 + xmm5
  ADDPS X5, X4
  // xmm4 = xmm4 + xmm6
  ADDPS X6, X4
  // xmm4 = xmm4 + xmm7
  ADDPS X7, X4
  // data[i] = xmm4
  MOVNTPS X4, 0(CX)
  // data++
  ADDQ $16, CX
  // i++
  INCQ AX
  // if i >= len(data) break
  CMPQ AX, SI
  JLT LOOP
END:
  // так как используем невременные (Non-Temporal) SSE-инструкции (MOVNTPS)
  // убедимся, что все записи видны перед выходом из функции (с помощью SFENCE)
  SFENCE
  RET

This implementation is completed in 18 ms, so it is pretty close to the speed of copying memory. The best optimization may be to run such things on the GPU, not the processor, because the GPU is really good at that.

Operating time for various programs, including the inline version of Go and the assembler implementation without SIMD (with links to the source code):

The cost of optimization will be the complexity of the code, which simplifies the operation of the machine. Writing a program in assembler is a difficult way to optimize, but sometimes it is the best method available.

Implementation Notes

The author developed the assembler parts mainly in C and 64-bit assembler using Xcode, and then ported them to Go format. Xcode has a good debugger that allows you to check the values ​​of the processor registers while the program is running. If you include the assembler .s file in your Xcode project, the IDE will compile it and link it to the desired executable.

The author used the Intel x64 instruction set reference and the Intel Intrinsics guide to figure out which instructions to use. Converting to Go assembly language is not always simple, but many 64-bit assembly instructions are specified in x86 / anames.go , and if not, they can be encoded directly with binary representation.

Translator's Note

In the original article #include "textflag.h", the header is not included in the assembler files , which causes an error when compiling illegal or missing addressing mode for symbol NOSPLIT.
Therefore, I posted the corrected versions on GitHub Gist. To start to unpack the archive, execute the command: chmod +x run.sh && ./run.sh.

You can run the code with assembler only by assembling the binary with go build, otherwise the compiler will swear at the empty body of the function.

Unfortunately, there is really little assembler information on the Internet on Go. I advise you to read an article on Habré about Go assembler architecture .

Another way to use assembler inserts in Go

As you know, Go supports the use of code written in C. Therefore, nothing prevents you from doing this:

sqrt.h:

double sqrt(double x) {
  __asm__ ("fsqrt" : "+t" (x));
  return x;
}

sqrt.go:

package main
/*
#include "sqrt.h"
*/
import "C"
import "fmt"
func main() {
  fmt.Printf("%f\n", C.sqrt(C.double(16)))
}

And run:

$ go run sqrt.go 
4.000000

Assembler is fun!