在 Golang 中针对 int64 类型优化 abs()
原文:Optimized abs() for int64 in Go,译文:在 Golang 中针对 int64 类型优化 abs(),欢迎转载。 前言Go 语言没有内置 我最近为了解决 Advent of Code 2017 上边的 Day 20 难题,自己实现了一个 Go 实际上已经在 帖子 Pure Go math.Abs outperforms assembly version 讨论了针对浮点数如何优化 文章中的源码和测试用例在 cavaliercoder/go-abs 类型转换 VS 分支控制的方法对我来说取绝对值最简单的函数实现是:输入参数 n 大于等于 0 直接返回 n,小于零则返回 -n(负数取反为正),这个取绝对值的函数依赖分支控制结构来计算绝对值,就命名为: package abs func WithBranch(n int64) int64 { if n < 0 { return -n } return n } 成功返回 n 的绝对值,这就是 Go v1.9.x package abs func WithStdLib(n int64) int64 { return int64(math.Abs(float64(n))) } 上边的代码中,将 n 先从 $ go test -bench=. goos: darwin goarch: amd64 pkg: github.com/cavaliercoder/abs BenchmarkWithBranch-8 2000000000 0.30 ns/op BenchmarkWithStdLib-8 2000000000 0.79 ns/op PASS ok github.com/cavaliercoder/abs 2.320s 测试结果:0.3 ns/op, 举个例子: 不依赖分支控制的方法取绝对值的方法对有符号整数显然更快更准,不过还有更好的办法吗? 我们都知道不依赖分支控制的方法的代码破坏了程序的运行顺序,即 pipelining processors 无法预知程序的下一步动作。 与不依赖分支控制的方法不同的方案Hacker’s Delight 第二章介绍了一种无分支控制的方法,通过 Two’s Complement 计算有符号整数的绝对值。 为计算 x 的绝对值:
func WithASM(n int64) int64 // abs_amd64.s TEXT ·WithASM(SB),$0 MOVQ n+0(FP),AX // copy input to AX MOVQ AX,CX // y ← x SARQ $63,CX // y ← y >> 63 XORQ CX,AX // x ← x ? y SUBQ CX,AX // x ← x - y MOVQ AX,ret+8(FP) // copy result to return value RET 我们先命名这个函数为
$ go test -bench=. goos: darwin goarch: amd64 pkg: github.com/cavaliercoder/abs BenchmarkWithBranch-8 2000000000 0.29 ns/op BenchmarkWithStdLib-8 2000000000 0.78 ns/op BenchmarkWithASM-8 2000000000 1.78 ns/op PASS ok github.com/cavaliercoder/abs 6.059s 这就比较尴尬了,这个简单的基准测试显示无分支控制结构高度简洁的代码跑起来居然很慢:1.78 ns/op,怎么会这样呢? 编译选项我们需要知道 Go 的编译器是怎么优化执行 运行效果: $ go tool compile -m abs.go # github.com/cavaliercoder/abs ./abs.go:11:6: can inline WithBranch ./abs.go:21:6: can inline WithStdLib ./abs.go:22:23: inlining call to math.Abs 对于我们这个简单的函数,Go 的编译器支持 function inlining,函数内联是指在调用我们函数的地方直接使用这个函数的函数体来代替。举个例子: package main import ( "fmt" "github.com/cavaliercoder/abs" ) func main() { n := abs.WithBranch(-1) fmt.Println(n) } 实际上会被编译成: package main import "fmt" func main() { n := -1 if n < 0 { n = -n } fmt.Println(n) } 根据编译器的输出,可以看出 因为 如果我们在其他函数中不使用内联会怎么样?可以写个简单的示例程序: package abs //go:noinline func WithBranch(n int64) int64 { if n < 0 { return -n } return n } 重新编译,我们会看到编译器优化内容变少了: $ go tool compile -m abs.go abs.go:22:23: inlining call to math.Abs 基准测试的结果: $ go test -bench=. goos: darwin goarch: amd64 pkg: github.com/cavaliercoder/abs BenchmarkWithBranch-8 1000000000 1.87 ns/op BenchmarkWithStdLib-8 1000000000 1.94 ns/op BenchmarkWithASM-8 2000000000 1.84 ns/op PASS ok github.com/cavaliercoder/abs 8.122s 可以看出,现在三个函数的平均执行时间几乎都在 1.9 ns/op 左右。 你可能会觉得每个函数的调用开销在 1.5ns 左右,这个开销的出现否定了我们 我从上边学到的东西是, 只使用一个内联函数Go 编译器无法内联由汇编实现的函数,但是内联我们重写后的普通函数是很容易的: package abs func WithTwosComplement(n int64) int64 { y := n >> 63 // y ← x >> 63 return (n ^ y) - y // (x ? y) - y } 编译结果说明我们的方法被内联了: $ go tool compile -m abs.go ... abs.go:26:6: can inline WithTwosComplement 但是性能怎么样呢?结果表明:当我们启用函数内联时,性能与 $ go test -bench=. goos: darwin goarch: amd64 pkg: github.com/cavaliercoder/abs BenchmarkWithBranch-8 2000000000 0.29 ns/op BenchmarkWithStdLib-8 2000000000 0.79 ns/op BenchmarkWithTwosComplement-8 2000000000 0.29 ns/op BenchmarkWithASM-8 2000000000 1.83 ns/op PASS ok github.com/cavaliercoder/abs 6.777s 现在函数调用的开销消失了, 使用 $ go tool compile -S abs.go ... "".WithTwosComplement STEXT nosplit size=24 args=0x10 locals=0x0 0x0000 00000 (abs.go:26) TEXT "".WithTwosComplement(SB),NOSPLIT,$0-16 0x0000 00000 (abs.go:26) FUNCDATA $0,gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB) 0x0000 00000 (abs.go:26) FUNCDATA $1,gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) 0x0000 00000 (abs.go:26) MOVQ "".n+8(SP),AX 0x0005 00005 (abs.go:26) MOVQ AX,CX 0x0008 00008 (abs.go:27) SARQ $63,AX 0x000c 00012 (abs.go:28) XORQ AX,CX 0x000f 00015 (abs.go:28) SUBQ AX,CX 0x0012 00018 (abs.go:28) MOVQ CX,"".~r1+16(SP) 0x0017 00023 (abs.go:28) RET ... 编译器在编译 最后关于内存分配,上边所有函数的实现都是比较理想的情况,我运行 总结
最后,我对 int64 的 abs 实现如下: func abs(n int64) int64 { y := n >> 63 return (n ^ y) - y } via:Optimized abs() for int64 in Go 作者:Ryan Armstrong (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |