Go allows authors to write functions in assembly if required. This is called a stub or forward declaration.
package asm // Add returns the sum of a and b. func Add(a int64, b int64) int64
Here we’re declaring Add, a function which takes two int64‘s and returns their sum.Add is a normal Go function declaration, except it is missing the function body.
If we were to try to compile this package the compiler, justifiably, complains;
% go build examples/asm ./decl.go:4:6: missing function body
To satisfy the compiler we must supply a body for Add via assembly, which we do by adding a .s file in the same package.
TEXT ·Add(SB),$0-24
MOVQ a+0(FP), AX
ADDQ b+8(FP), AX
MOVQ AX, ret+16(FP)
RET
Now we can build, test, and use our Add function just like normal Go code. But, there’s a problem, assembly functions cannot be inlined.
This has long been a complaint by Go developers who want to use assembly either for performance or to access operations which are not exposed in the language. Some examples would be vector instructions, atomic instructions, and so on. Without the ability to inline assembly functions writing these functions in Go can have a relatively large overhead.
var Result int64
func BenchmarkAddNative(b *testing.B) {
var r int64
for i := 0; i < b.N; i++ {
r = int64(i) + int64(i)
}
Result = r
}
func BenchmarkAddAsm(b *testing.B) {
var r int64
for i := 0; i < b.N; i++ {
r = Add(int64(i), int64(i))
}
Result = r
}
BenchmarkAddNative-8 1000000000 0.300 ns/op BenchmarkAddAsm-8 606165915 1.93 ns/op
Over the years there have been various proposals for an inline assembly syntax similar to gcc’s asm(...) directive. None have been accepted by the Go team. Instead, Go has added intrinsic functions1.
An intrinsic function is Go code written in regular Go. These functions are known the the Go compiler which contains replacements which it can substitute during compilation. As of Go 1.13 the packages which the compiler knows about are:
math/bitssync/atomic
The functions in these packages have baroque signatures but this lets the compiler, if your architecture supports a more efficient way of performing the operation, transparently replace the function call with comparable native instructions.
For the remainder of this post we’ll study two different ways the Go compiler produces more efficient code using intrinsics.
Ones count
Population count, the number of 1 bits in a word, is an important cryptographic and compression primitive. Because this is an important operation most modern CPUs provide a native hardware implementation.
The math/bits package exposes support for this operation via the OnesCount series of functions. The various OnesCount functions are recognised by the compiler and, depending on the CPU architecture and the version of Go, will be replaced with the native hardware instruction.
To see how effective this can be lets compare three different ones count implementations. The first is Kernighan’s Algorithm2.
func kernighan(x uint64) int {
var count int
for ; x > 0; x &= (x - 1) {
count++
}
return count
}
This algorithm has a maximum loop count of the number of bits set; the more bits set, the more loops it will take.
The second algorithm is taken from Hacker’s Delight via issue 14813.
func hackersdelight(x uint64) int {
const m1 = 0x5555555555555555
const m2 = 0x3333333333333333
const m4 = 0x0f0f0f0f0f0f0f0f
const h01 = 0x0101010101010101
x -= (x >> 1) & m1
x = (x & m2) + ((x >> 2) & m2)
x = (x + (x >> 4)) & m4
return int((x * h01) >> 56)
}
Lots of clever bit twiddling allows this version to run in constant time and optimises very well if the input is a constant (the whole thing optimises away if the compiler can figure out the answer at compiler time).
Let’s benchmark these implementations against math/bits.OnesCount64.
var Result int
func BenchmarkKernighan(b *testing.B) {
var r int
for i := 0; i < b.N; i++ {
r = kernighan(uint64(i))
}
Result = r
}
func BenchmarkPopcnt(b *testing.B) {
var r int
for i := 0; i < b.N; i++ {
r = hackersdelight(uint64(i))
}
Result = r
}
func BenchmarkMathBitsOnesCount64(b *testing.B) {
var r int
for i := 0; i < b.N; i++ {
r = bits.OnesCount64(uint64(i))
}
Result = r
}
To keep it fair, we’re feeding each function under test the same input; a sequence of integers from zero to b.N. This is fairer to Kernighan’s method as its runtime increases with the number of one bits in the input argument.3
BenchmarkKernighan-8 100000000 11.2 ns/op BenchmarkPopcnt-8 618312062 2.02 ns/op BenchmarkMathBitsOnesCount64-8 1000000000 0.565 ns/op
The winner by nearly 4x is math/bits.OnesCount64, but is this really using a hardware instruction, or is the compiler just doing a better job at optimising this code? Let’s check the assembly
% go test -c % go tool objdump -s MathBitsOnesCount popcnt-intrinsic.test TEXT examples/popcnt-intrinsic.BenchmarkMathBitsOnesCount64(SB) /examples/popcnt-intrinsic/popcnt_test.go popcnt_test.go:45 0x10f8610 65488b0c2530000000 MOVQ GS:0x30, CX popcnt_test.go:45 0x10f8619 483b6110 CMPQ 0x10(CX), SP popcnt_test.go:45 0x10f861d 7668 JBE 0x10f8687 popcnt_test.go:45 0x10f861f 4883ec20 SUBQ $0x20, SP popcnt_test.go:45 0x10f8623 48896c2418 MOVQ BP, 0x18(SP) popcnt_test.go:45 0x10f8628 488d6c2418 LEAQ 0x18(SP), BP popcnt_test.go:47 0x10f862d 488b442428 MOVQ 0x28(SP), AX popcnt_test.go:47 0x10f8632 31c9 XORL CX, CX popcnt_test.go:47 0x10f8634 31d2 XORL DX, DX popcnt_test.go:47 0x10f8636 eb03 JMP 0x10f863b popcnt_test.go:47 0x10f8638 48ffc1 INCQ CX popcnt_test.go:47 0x10f863b 48398808010000 CMPQ CX, 0x108(AX) popcnt_test.go:47 0x10f8642 7e32 JLE 0x10f8676 popcnt_test.go:48 0x10f8644 803d29d5150000 CMPB $0x0, runtime.x86HasPOPCNT(SB) popcnt_test.go:48 0x10f864b 740a JE 0x10f8657 popcnt_test.go:48 0x10f864d 4831d2 XORQ DX, DX popcnt_test.go:48 0x10f8650 f3480fb8d1 POPCNT CX, DX // math/bits.OnesCount64 popcnt_test.go:48 0x10f8655 ebe1 JMP 0x10f8638 popcnt_test.go:47 0x10f8657 48894c2410 MOVQ CX, 0x10(SP) popcnt_test.go:48 0x10f865c 48890c24 MOVQ CX, 0(SP) popcnt_test.go:48 0x10f8660 e87b28f8ff CALL math/bits.OnesCount64(SB) popcnt_test.go:48 0x10f8665 488b542408 MOVQ 0x8(SP), DX popcnt_test.go:47 0x10f866a 488b442428 MOVQ 0x28(SP), AX popcnt_test.go:47 0x10f866f 488b4c2410 MOVQ 0x10(SP), CX popcnt_test.go:48 0x10f8674 ebc2 JMP 0x10f8638 popcnt_test.go:50 0x10f8676 48891563d51500 MOVQ DX, examples/popcnt-intrinsic.Result(SB) popcnt_test.go:51 0x10f867d 488b6c2418 MOVQ 0x18(SP), BP popcnt_test.go:51 0x10f8682 4883c420 ADDQ $0x20, SP popcnt_test.go:51 0x10f8686 c3 RET popcnt_test.go:45 0x10f8687 e884eef5ff CALL runtime.morestack_noctxt(SB) popcnt_test.go:45 0x10f868c eb82 JMP examples/popcnt-intrinsic.BenchmarkMathBitsOnesCount64(SB) :-1 0x10f868e cc INT $0x3 :-1 0x10f868f cc INT $0x3
There’s quite a bit going on here, but the key take away is on line 48 (taken from the source code of the _test.go file) the program is using the x86 POPCNT instruction as we hoped. This turns out to be faster than bit twiddling.
Of interest is the comparison two instructions prior to the POPCNT,
CMPB $0x0, runtime.x86HasPOPCNT(SB)
As not all intel CPUs support POPCNT the Go runtime records at startup if the CPU has the necessary support and stores the result in runtime.x86HasPOPCNT. Each time through the benchmark loop the program is checking does the CPU have POPCNT support before it issues the POPCNT request.
The value of runtime.x86HasPOPCNT isn’t expected to change during the life of the program’s execution so the result of the check should be highly predictable making the check relatively cheap.
Atomic counter
As well as generating more efficient code, intrinsic functions are just regular Go code, the rules of inlining (including mid stack inlining) apply equally to them.
Here’s an example of an atomic counter type. It’s got methods on types, method calls several layers deep, multiple packages, etc.
import (
"sync/atomic"
)
type counter uint64
func (c counter) get() uint64 {
return atomic.LoadUint64((uint64)(c))
}
func (c counter) inc() uint64 {
return atomic.AddUint64((uint64)(c), 1)
}
func (c counter) reset() uint64 {
return atomic.SwapUint64((uint64)(c), 0)
}
var c counter
func f() uint64 {
c.inc()
c.get()
return c.reset()
}
You’d be forgiven for thinking this would have a lot of overhead. However, because of the interaction between inlining and compiler intrinsics, this code collapses down to efficient native code on most platforms.
TEXT main.f(SB) examples/counter/counter.go counter.go:23 0x10512e0 90 NOPL counter.go:29 0x10512e1 b801000000 MOVL $0x1, AX counter.go:13 0x10512e6 488d0d0bca0800 LEAQ main.c(SB), CX counter.go:13 0x10512ed f0480fc101 LOCK XADDQ AX, 0(CX) // c.inc counter.go:24 0x10512f2 90 NOPL counter.go:10 0x10512f3 488b05fec90800 MOVQ main.c(SB), AX // c.get counter.go:25 0x10512fa 90 NOPL counter.go:16 0x10512fb 31c0 XORL AX, AX counter.go:16 0x10512fd 488701 XCHGQ AX, 0(CX) // c.reset counter.go:16 0x1051300 c3 RET
By way of explanation. The first operation, counter.go:13 is c.inc a LOCKed XADDQ, which on x86 is an atomic increment. The second, counter.go:10 is c.get which on x86, due to its strong memory consistency model, is a regular load from memory. The final operation, counter.go:16, c.reset is an atomic exchange of the address in CX with AX which was zeroed on the previous line. This puts the value in AX, zero, into the address stored in CX. The value previously stored at (CX) is discarded.
Conclusion
Intrinsics are a neat solution that give Go programmers access to low level architectural operations without having to extend the specification of the language. If an architecture doesn’t have a specific sync/atomic primitive (like some ARM variants), or a math/bits operation, then the compiler transparently falls back to the operation written in pure Go.