译文 Go 编译器优化器

xiemengjun · 2020年02月11日 · 60 次阅读

Go compiler intrinsics

如有需要,Go 允许使用者通过汇编来写函数。这被称作 stubforward 声明.

package asm

// Add returns the sum of a and b.
func Add(a int64, b int64) int64

这里,我们声明了 Add 函数,其接受 2 个 int64 类型入参,并返回二者之和。Add 函数相较于 Go 常见形式的函数声明,缺少了函数体部分。

如果我们尝试编译这个包时,编译器自然是会给出警告信息的:

% go build
examples/asm
./decl.go:4:6: missing function body

为了满足编译器要求,我们通过汇编的方式为 Add 提供函数体,这里可以在同一个包下新增 .s 文件。

TEXT ·Add(SB),$0-24
        MOVQ a+0(FP), AX
        ADDQ b+8(FP), AX
        MOVQ AX, ret+16(FP)
        RET

现在我们可以进行 buildtest 操作,像普通的 Go 代码一样使用 Add 函数。但是,有一个问题,汇编函数无法被内联。

这一直是被 Go 开发者所抱怨的,他们希望通过汇编来提高性能或访问未被语言暴露的操作。比如说,矢量指令,原子指令等等。如果没有内联汇编函数的能力,在 Go 中编写这些函数会产生相对较大的负担。

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

译者注:Go 原生的方式,性能优于汇编方式,这也是本文所关注的 Go 内建函数的优化。

多年来,已经有多种提案来支持内联汇编的语法,比如类似与 gcc 的 asm(...) 指令。但没有任何一个提案被 Go 团队接受。相反,Go 添加了一种内建函数 intrinsic functions

注 1:内建函数 可能不是他们的正式名称,但是这个词在编译器及其测试中是很常用的。

译者注:参见维基百科Intrinsic function

内建函数intrinsic function是使用常规 Go 编写的 Go 代码。这些函数在 Go 编译器中是已知的,它包含可在编译期间进行替换的待替换元素。从 Go 1.13 开始,编译器支持的包有:

  • math/bits
  • sync/atomic

这些包中的函数具有巴洛克式签名(译者注:形容繁琐且富于变化的签名形式),但在你的系统架构支持更有效的执行方式时,编译器可以使用相近的原生指令来进行透明的替换函数调用。

对于本文的其余部分,我们将研究 Go 编译器使用内建函数 intrinsic function 生成更高效代码的两种不同方式。

Ones count 位为 1 的计数

一个词中位为 1 的数量,这类计数是一种重要的加密和压缩原语。因为这是一项基础且重要的操作,所以大多数现代 CPU 都提供了原生硬件实现。

math/bits 包通过 OnesCount 系列函数提供了对该操作的支持。 各种 OnesCount 函数被编译器识别,并且取决于 CPU 架构和 Go 的版本,将被本机硬件指令替换。

要了解这有多么有效,我们可以比较三种不同的计数实现。 第一个是 Kernighan 在《The C Programming Language 2nd Ed, 1998》书中提到的算法。

注 2:Kernighan 《The C Programming Language 2nd Ed, 1998》,C 语言 Bible

func kernighan(x uint64) int {
        var count int
        for ; x > 0; x &= (x - 1) {
                count++
        }
        return count
}

该算法最大循环次数由数字本身的位数决定; 数字具有的位数越多,则它的循环次数越多。

第二个算法会令黑客们会心一笑,来自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)
 }

如果输入是一个常量(如果编译器可以在编译时间找出答案的话,整个事情会优化掉),这个版本算法中很多比特位都会在恒定时间内运行并且非常好地优化。

让我们根据 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
}

为了保持公平,我们在为每个被测函数提供相同的输入:从零到 b.N 的整数序列。这对于 Kernighan 的方法更为公平,因为它的运行时间随着入参的位数而逐渐增加。

注 3:作为加分小作业,可以尝试将 0xdeadbeefdeadbeef 传递给每个被测试的函数,看看运行结果如何。

来看下测试结果:go test -bench=. -run=none

BenchmarkKernighan-8        100000000       11.2 ns/op
BenchmarkPopcnt-8           618312062       2.02 ns/op
BenchmarkMathBitsOnesCount64-8  1000000000  0.565 ns/op

math/bits.OnesCount64 以近 4 倍的速度优势胜出,但是这真的是因为使用硬件指令,还是因为编译器在代码优化方面做得更好呢?让我们来检查下汇编的过程。

% 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 

这里输出了很多内容,但关键的内容是第 48 行(取自 _test.go 文件的源代码),程序确实使用了我们期望的 x86 POPCNT 指令。事实证明这比操作位运算更快。

有趣的是比较 POPCNT 之前的两条指令:

CMPB $0x0, runtime.x86HasPOPCNT(SB)

并非所有的英特尔 CPU 都支持 POPCNT ,如果 CPU 支持此指令,那么 Go 运行时在启动时,就会将此结果存储在 runtime.x86HasPOPCNT 中。这样每次进行基准测试循环时,程序通过检查 CPU 是否支持 POPCNT ,然后再发出 POPCNT 请求。

runtime.x86HasPOPCNT 的值在程序执行期间不会变化,因此检查结果是高度可预测的,这使得这种检查的成本相对低廉。

Atomic counter 原子计数器

除了生成更高效的代码之外,内建函数intrinsic functions只是常规的 Go 代码,内联规则(包括中间堆栈内联)同样适用于它们。

这是一个原子计数器类型的例子。它有类型的方法,深层的方法调用,多个包等情况。

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()
}

译者注:原文代码有误无法编译,代码进行了部分修改,(uint64)(c) 修改为 (*uint64)(&c)

你或许会认为上述这种操作会产生很多开销,这是可以理解的。但由于内联和编译器内建函数之间的交互,这些代码在大多数平台上会转换为很高效的原生代码。

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 

下面我们逐一解释下。第一个操作,counter.go:13c.inc 一个 LOCKXADDQ 指令,这在 x86 上是一个原子性的增量。第二个,counter.go:10c.get ,由于 x86 强大的内存一致性模型,它是内存级的常规操作。最后一个操作,counter.go:16c.resetCX 中地址与 AX 的原子交换,而 AX 在前一行被归零 (XORL AX, AX,按位异或,相当于清零)。这将 AX 中的值(零)放入存储在 CX 中的地址中,而先前存储在 (CX) 的值被丢弃。

Conclusion 总结

内建函数是一种简洁的解决方案,它使 Go 程序员可以进行低层架构的操作,而无需扩展语言规范。如果某个体系结构没有特定的 sync/atomic 原语(比如某些 ARM 的变体)或者 math/bits 操作,那么编译器会隐式地降级为用纯 Go 编写的操作。

  1. Notes on exploring the compiler flags in the Go compiler suite
  2. Padding is hard
  3. Should methods be declared on T or *T
  4. Wednesday pop quiz: spot the race
更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册