分类目录归档:Go

Go RISC-V runtime去掉 Duff’s Device 性能提升最大225%

上游Google团队的 Keith Randell 6月时抛出一个有趣的话题,由于近年的CPU预测技术的发展,如果Go runtime去掉Duff device,性能反而会达到一定的提升。
原帖:https://groups.google.com/g/golang-dev/c/bVoLyx0s3tg

我摘出来有趣的部分并翻译了下:

达夫设备(Duff's Device) 通过在运行时部署一个大规模展开的清零/复制循环来优化内存清零和内存复制操作。编译器会合成一个跳转指令,直接跳转到这个展开循环的特定中间位置,以精确执行所需次数的循环操作。
在Go语言中,其实现形式类似于:

s[0] = 0; s = s[1:]
s[0] = 0; s = s[1:]
s[0] = 0; s = s[1:]
...大量重复指令...
s[0] = 0; s = s[1:]
s[0] = 0; s = s[1:]
s[0] = 0; s = s[1:]
return

当编译器需要清零7个字节时,它会计算从末尾倒数第7条指令的地址并直接跳转执行。
这听起来很巧妙,但每次调用都会产生额外开销。况且现代分支预测器已非常高效,消除调用点的循环开销并不再那么重要。

Keith 还提供了几个CL,不过ARM64/AMD64 的实现是不管对齐的问题的,这就意味着 RISC-V 不能这样用(因为 RISC-V 的 unalignement access 是臭名昭著的软件实现/内核 trap/性能损失大)我决定自己实现 type alignment 的版本。

Keith 版 SSA 非常简洁

(Zero [s] ptr mem) && s > 16 && s < 192 => (LoweredZero [s] ptr mem)
(Zero [s] ptr mem) && s >= 192 => (LoweredZeroLoop [s] ptr mem)

然后编写对应的 code gen 就可以了,但……RISCV就麻烦了,因为要传入一个type alignment进去

(Zero [s] {t} ptr mem) =>
        (LoweredZero [t.Alignment()]
                ptr
                (ADD <ptr.Type> ptr (MOVDconst [s-moveSize(t.Alignment(), config)]))
                mem)

如果直接塞多一个参数,变成

(Zero [s] {t} ptr mem) =>
        (LoweredZero [s]
                ptr
                (MOVconst [t.Alignment()])
                mem)

这样在materialize的时候就会多一个MOV const, reg的指令,这样不优雅!

然后想到bit shift,把LoweredZero [s<<32|t.Alignment()],但这样在SSA优化的时候,mem size就非常恐怖了……怎么样优雅的把这个值塞进 AuxInt,就成了头大的问题。

只好看看 SSA compiler 的实现,然后在 AuxInt 的 type list (cmd/compile/internal/ssa/op.go)发现了“auxARM64BitField”

 // architecture specific aux types
 auxARM64BitField     // aux is an arm64 bitfield lsb and width packed into auxInt

给 RISC-V 直接套上,就会造成程序的文不对题。

改成auxRISCVBitFields,还要加几个前置CL来实现。这不优雅!

于是我全部类型都看了遍,终于发现一个合理的:"SymValAndOff",代价就是……Lowered(Zero|Move)需要添加一个 symEffect 说明这个指令有啥副作用(当然都是Write啦),这下就优雅多了

(Zero [s] {t} ptr mem) && s <= 24*moveSize(t.Alignment(), config) =>
    (LoweredZero [makeValAndOff(int32(s),int32(t.Alignment()))] ptr mem)

完美!

然后测试性能发现,咦,Zero竟然没有任何改进?

MemclrKnownSize112-4             5.602Gi ± 0%    5.601Gi ± 0%         ~ (p=0.363 n=10)
MemclrKnownSize128-4             6.933Gi ± 1%    6.545Gi ± 1%    -5.59% (p=0.000 n=10)
MemclrKnownSize192-4             8.055Gi ± 1%    7.804Gi ± 0%    -3.12% (p=0.000 n=10)
MemclrKnownSize248-4             8.489Gi ± 0%    8.718Gi ± 0%    +2.69% (p=0.000 n=10)
MemclrKnownSize256-4             8.762Gi ± 0%    8.763Gi ± 0%         ~ (p=0.494 n=10)
MemclrKnownSize512-4             9.514Gi ± 1%    9.514Gi ± 0%         ~ (p=0.529 n=10)
MemclrKnownSize1024-4            9.940Gi ± 0%    9.939Gi ± 1%         ~ (p=0.989 n=10)

再次祭出SSA debuger,发现,原来runtime的memclr都跑去调用memNoPtrClr了……那自然不会用咱们这个LoweredZeroOp。

然后改用了基于SSA Zero的ClearFat,才有下面的测试结果(删掉了部分不重要的)

ClearFat3-4                   1.300Gi ± 0%    1.301Gi ±  0%         ~ (p=0.447 n=10)
ClearFat4-4                   3.902Gi ± 0%    3.902Gi ±  0%         ~ (p=0.971 n=10)
……
ClearFat16-4                  1.600Gi ± 0%    5.202Gi ±  0%  +225.10% (p=0.000 n=10)
ClearFat18-4                  1.018Gi ± 0%    1.300Gi ±  0%   +27.77% (p=0.000 n=10)
ClearFat20-4                  2.601Gi ± 0%    4.938Gi ± 12%   +89.87% (p=0.000 n=10)
ClearFat24-4                  2.601Gi ± 0%    5.201Gi ±  0%   +99.96% (p=0.000 n=10)
ClearFat32-4                  1.982Gi ± 0%    5.203Gi ±  0%  +162.55% (p=0.000 n=10)
ClearFat56-4                  3.640Gi ± 0%    5.201Gi ±  0%   +42.88% (p=0.000 n=10)
ClearFat64-4                  2.250Gi ± 0%    5.202Gi ±  0%  +131.25% (p=0.000 n=10)
……
geomean                       2.005Gi         3.020Gi         +50.58%

可以看到原来的小byte的实现不变(没改,当然没变),到了16 bytes 就突然涨起来,我看了下原版的是有优化的,理论上应该不变啊

(Zero [16] {t} ptr mem) && t.Alignment()%8 == 0 =>
    (MOVDstore [8] ptr (MOVDconst [0])
        (MOVDstore ptr (MOVDconst [0]) mem))

原来ClearFat的type alignment是 uint32 (也就是4 bytes),所以没有优化,就落到了循环实现(连TM duff也要求 8 bytes alignment)

func BenchmarkClearFat16(b *testing.B) {
        p := new([16 / 4]uint32)        
        Escape(p)                       
        b.ResetTimer()                  
        for i := 0; i < b.N; i++ {      
                *p = [16 / 4]uint32{}   
        }                               
}                                       

既然如此,那我就白捡个性能优化225%吧 :)

RISCV 64 高性能浮点rounding Go实现

引言

RISC-V(下简称RV),作为一种开源的CPU架构,其灵活的指令集和可扩展性为开发者提供了丰富的设计选项。在数值计算中,浮点数的处理尤为重要,而浮点数舍入(rounding)机制则是确保计算精确性和效率的关键一环。本文将聚焦于RV64架构下浮点数的舍入(浮点到浮点)在Go语言中实现,特别是通过FCVTDL/FCVTLD指令的应用来探讨实现的原理。

想看代码的朋友,可以直接看我提交到Go官方的代码参考

golang/go/commit 90391c2

啥是舍入(rounding)

Round(2.5) = 2,就是一种舍入方法(四舍五入嘛)

实际编码中的问题

第一个问题是,既然RV64有浮点转换指令,那直接用不就行了么?

事情并没这么简单,由于RV64并不像其他架构有单独的浮点到浮点的取整指令(例如arm64的FRINTMD),因此只能用FCVT (floating point convert)先转换到整数寄存器中,再从整数寄存器中转回浮点寄存器。

例如浮点值X,在寄存器FA0中,需要以下指令(注:Go的Asm,从左到右):

FCVTLD FA0, A0
FCVTDL A0, FA0

坑就在此出现了!

IEEE 754 中 -Inf (负无穷大)的二进制表达是0x7fffffffffffffff,而根据RV64指令集手册,对于不合格的浮点输入,就“凑到相近的值”并复制到整数寄存器中了。

Floor(-Inf) -> int64(0x7fffffffffffffff)

这下热闹了,整数0x7ff...ff是合法的整数。当你转回浮点时……就变成了float64(9.22e+18)。这意味着

非法数值变成了合法数值

例如这个issue:https://github.com/golang/go/issues/68322

那么通过RV64的FCLASS (浮点类型)指令提前判断呢?可以是可以,但由于多重判断是否数值在取整范围内,经过测试速度不够快(性能下降60%),并不符合我们程序员对于“高效”的追求。如果要达成快捷的判断非法输入的方法,需要我们回顾一下IEEE 754的表达方式。

RV64中浮点数的表示

在RV64浮点数中的表示遵循IEEE 754标准,该标准定义了浮点数的符号位、指数和尾数部分。

IEEE 754标准定义了浮点数在计算机中的存储方式,主要包括三个部分:符号位(S)、指数(E)和尾数(M,也称为有效数字或小数部分)。对于双精度浮点数(即double类型,在大多数现代计算机中占用64位),其格式如下:

  • 符号位(1位):位于最高位,0表示正数,1表示负数。
  • 指数(11位):用于表示浮点数的指数部分,采用偏移量编码方式(对于双精度,偏移量为1023)。
  • 尾数(52位):表示浮点数的有效数字部分,但隐式包含了一个前导的1(除了表示0或次正规数的情况)。

例如要表达IEEE754 DP 0.375,可以拆解为:0.25*1.5

  • 正数,符号位为0
  • 指数需要0.25,2-2,通过补码,即0x3FD
  • 尾数1.5,则是1+2-1,即0x8(1000_0000)b

二进制即0x3FD8_0000_0000_0000

其中IEEE 754 DP非法的输入分别是:

  • ±Inf(正负无穷大)0x7FF0_0000_0000_0000
  • NaN(Not a Number,压根不是个数)

NaN也有很多中表达方式,有

  • qNaN 0x7FF8_0000_0000_0001
  • sNaN 0x7FF0_0000_0000_0001
  • 特殊NaN 0x7FFF_FFFF_FFFF_FFFF

如果仔细留意的话,你会发现,所有的非法输入都是通过指数位表示的,而且都相当大(0x7FF= 2047d - 1023,实际为1024),那么,我们只需要通过右移52位,并加以掩码(mask)去除正负影响,就可以判断一个浮点数是不是非法输入(0x7FF)。重点来了

这个方法可以顺便判断是不是整数取整范围

因为浮点数能取整,就意味着指数小于53,即整个数小于253,如果对大于这个数取整就会出现未定义行为了,所以Go语言限制,必须在这个范围内,超过的合法输入原样输出即可。

var x float64
maskedExp := (math.Float64bits(x) >> 52) & 0x7FF
if maskedExp > 1023 + 52 {
    return x
}
// FCVTLD x, A0
// FCVTDL A0, x

这样是不是就好了?不……还有一个坑……

±0没办法处理

所以最后需要使用RV64的FSGNJD指令,将x中的符号位拷贝复制过来。

最终效果

见前面提到的golang/go/commit 90391c2,提升300%

            │ math.old.bench │           math.new.bench            │
            │     sec/op     │   sec/op     vs base                │
Ceil             54.09n ± 0%   18.72n ± 0%  -65.39% (p=0.000 n=10)
Floor            40.72n ± 0%   18.72n ± 0%  -54.03% (p=0.000 n=10)
Trunc            38.72n ± 0%   18.72n ± 0%  -51.65% (p=0.000 n=10)
geomean          33.56n        20.09n       -40.13%

Go RISCV AES性能提升1100%?使用KCAPI教程

效果

Go-KCAPI地址,https://github.com/mengzhuo/go-kcapi (欢迎各种PR)
AES-CBC benchmark如下:上面是使用KCAPI的,下面是Go标准库

goos: linux
goarch: riscv64
pkg: github.com/mengzhuo/go-kcapi/aes
cpu: Spacemit(R) X60
BenchmarkCBCEncrypto/size=65536             4128            277873 ns/op         235.85 MB/s         752 B/op           3 allocs/op
BenchmarkCBCStdEncrypto/size=65536           391           3064170 ns/op          21.39 MB/s           0 B/op           0 allocs/op

235 MB/s vs 21.39 MB/s

性能提升:1102%

示例代码

go-kcapi我做了一定的封装,跟Go标准库有类似的调用方法
Developer Friendly ™

package main

import (
        "fmt"
        "log"

        "github.com/mengzhuo/go-kcapi/aes"
)

func main() {
        key := []byte("--YOUR-AES-KEY--")
        iv := []byte( "--YOUR-AES--IV--")
        enc, err := aes.NewCBCEncrypter(key, iv)
        if err != nil {
                log.Fatal(err)
        }
        src := []byte("--Hello,世界--")
        dst := make([]byte, 16)
        enc.CryptBlocks(dst, src)
        fmt.Printf("%x", dst) // d57b7738a2d589e0a42ca7424f6d47ed
}

原理

SpacemiT K1 芯片提供了硬件加速功能,并通过Linux Kernel Crypto User Interface暴露了出来。
通过调用相应接口有这么大提升了。

开发念念碎

TLDR;

最近在研究SpacemiT的riscv64 K1芯片,发现这个SoC有个硬件的AES加速模块。
可惜不是用riscv k扩展(crytpo)开发的,而是通过Linux内核暴露出来的自有的引擎(crypto engine)
这能忍不了,Go程序不能榨干芯片性能心痒痒。

于是看看Go咋调用Linux Kernel Crypto Engine。一顿搜索发现竟然没有库……读了读文档,发现还挺简单啊,不就socket编程嘛,就自己写一个!(后来发现我错了,原来相当复杂)

第一难:没有合适的文档
不得不说,Linux的内核文档没有示例代码,基本上啥都要直接翻libkcapi的源码和内核自身的源码。特别是cmsghdr压根没有类型说明,啥都是宏定义……我还是从源码里才翻出来ASSOCLEN是uint32_t,搞得好像这个世界只有C语言用户和C binding了。

第二难:没法debug AF_IF
这个不是shash的问题,内核得开dbg的问题,sendmsg之后。没有合适的地方返回,都是EINVALID,dmesg里也没日志,只能自己strace看调用数据。

第三难:不懂splice,scatter/gather RW,sendfile....
这是我的错,没学习过类似知识,比如网上的例子都是splice的,但Go runtime大牛Andy Pan,提醒我可以直接用sendfile,那不是6字就能代表我的心情的。

第四难:Go crypto接口跟Linux crypto接口不匹配,啊,这就是这个库存在的意义啦,要不开发者自己去用unix包调用也是可以的,反正不就是那几个syscall和buffer构建嘛~

第五难:好像没啥用……man……人艰不拆,还有好几个alg没实现,看看有没有人用再折腾吧……

总之,能调用kcapi提升性能,又学到了不少新知识,那是相当高兴的。
回头再按知识点写个Go开发相关接口的博客吧。

Go riscv64 FMA optimazation notes

FMA, which is short for fused multiply–add, use lots by math in Go compiler and standard library.
I found that Go 1.20 did some riscv64 support for FMA, however, when I'm trying to add test cases for FNMA x * y - z or FNMS -x * y + z.
The binary output always different with my expectation and test cases in math always failed.

At first, I thought that is floating point error since floating point number follows IEEE-754, 2008 edition which allows minor errors within 1e-16 i.e. "veryclose" in math test cases.
However, when I implement the same algorithm for 32 bits FP, there is far more error than it should be.

After my carefully search on SSA code generator, I found that FMA SSA for riscv64 will invert FMA into FNMX if multiplier or adder is negative.

(F(MADD|NMADD|MSUB|NMSUB)D neg:(FNEGD x) y z) && neg.Uses == 1 => (F(NMADD|MADD|NMSUB|MSUB)D x y z)

This SSA will convert FMADDD into FNMADD, unfortunately according to RISCV manual, this is wrong.
In the manual
FMADD means

x * y + z

FNMADD means

 - x * y - z

instead of original CL thought FNMADD should be implemented as

x * y - z

Then I commit a CL that fix this issue for good with some test cases.
https://go-review.googlesource.com/c/go/+/506575