golang中写个字符串遍历谁不会？且看我如何提升 50 倍

作者:张富春(ahfuzhang)，转载时请注明作者和引用链接，谢谢！

• cnblogs博客
  
• zhihu
  
• Github
  
• 公众号:一本正经的瞎扯
  
  
  
  

引子

VictoriaMetrics (Github: https://github.com/VictoriaMetrics/VictoriaMetrics)是一个远远好于 Prometheus 的监控组件，一开始我因为工作需要详细阅读了它的源码，并做了很多分享。今年开始，VictoriaMetrics 团队发布了用于日志处理的高性能组件 VictoriaLogs 的 1.0 版本，我阅读了这个组件的源码，依然非常优秀。
偶然发现，VictoriaLogs 中存在一个明显的性能热点：func tokenizeHashes(dst []uint64, a []string) []uint64。为了便于在查询日志时提升性能，在写入日志时需要对日志进行简单的分词，然后使用 Bloom Filter 作为分词索引。这样，根据某个关键词搜索时，就可以通过 Bloom Filter 快速判断关键词是否在数据块中存在。例如：存在日志 "it is a nice day", 函数会以空格分割各个单词，分别为 5 个单词计算 hash 值，然后根据 hash 值把 Bloom Filter 的对应 bit 置 1。查询时，把关键词计算成hash值，然后检测对应的 bit 位，这样就可以快速跳过不含有某个词的数据块，从而加快查询速度。
这个分词函数中依赖的一个简单函数引起了我的注意：

1. func isASCII(s string) bool {
2.         for i := range s {
3.                 if s[i] >= utf8.RuneSelf {
4.                         return false
5.                 }
6.         }
7.         return true
8. }

复制代码

纯英文的分词，与 unicode 字符集的分词是不一样的。所以日志的每个字符，都需要经过这个函数来检查一次。我们团队中很多大服务每天打印的日志量有数十 TB，做这个字符串是否为纯 ASCII 的计算任务其实并不轻松。
于是，我决定从这个简单的 isASCII 函数入手，尝试在这个场景中提高性能。
我先对原始版本做了 Benchmark 测试：

1. func getRandomString(strLen int) string {
2.         buf := make([]byte, strLen)
3.         for i := 0; i < strLen; i++ {
4.                 buf[i] = byte(rand.Intn(128)) // 0-127
5.         }
6.         return unsafe.String(&buf[0], strLen)
7. }
9. func Benchmark_is_ascii_one_by_one(b *testing.B) {
10.         strLen := 1024 * 1024
11.         s := getRandomString(strLen)
12.         s = s[3:]
13.         b.SetBytes(int64(len(s)))
14.         b.ResetTimer()
15.         for i := 0; i < b.N; i++ {
16.                 ret := IsASCII(s)
17.                 if !ret {
18.                         b.Fatalf("ret=%v", ret)
19.                 }
20.         }
21. }

复制代码

运行结果为：1161.58 MB/s

1. goos: linux
2. goarch: amd64
3. pkg: is_ascii
4. cpu: Intel(R) Xeon(R) Platinum 8457C   // CPU 频率 3.1GHz
5. Benchmark_is_ascii_one_by_one
6. Benchmark_is_ascii_one_by_one-192           1363            902709 ns/op        1161.58 MB/s           0 B/op          0 allocs/op

复制代码

第一轮优化：一次检查 8 个字符

很容易想到，可以将逐字符处理改为更大宽度的处理：

1. const maskOfAscii uint64 = uint64(0x8080808080808080)
3. func IsASCII_v1(s string) bool {
4.         l := len(s)
5.         align8 := l & (-8)
6.         buf := unsafe.Slice(unsafe.StringData(s), align8)
7.         for i := 0; i < align8; i += 8 {
8.                 var v uint64 = *((*uint64)(unsafe.Pointer(&buf[i])))
9.                 if (v & maskOfAscii) != 0 {
10.                         return false
11.                 }
12.         }
13.         s = s[align8:]
14.         for i := range s {
15.                 if s[i] >= utf8.RuneSelf {
16.                         return false
17.                 }
18.         }
19.         return true
20. }

复制代码

先把 8 字节对齐的部分，使用 unsafe 指针转换为 uint64。utf8.RuneSelf 这个值是 127， 正好就等于 uint8 类型的最高位等于 1：

1. s[i] >= utf8.RuneSelf 等价于 s[i] & 0x80 !=0

复制代码

运行 Benchmark 得到：13231.79 MB/s,  比原始版本提升 11.4 倍，效果明显！
第二轮优化：去掉数组越界检查

为什么 golang 中数组越界的时候会发生 panic, 且 panic 还可以捕获？
答案是编译器在数组访问阶段，加上了是否越界的代码，相当于:

1. func visit(arr []int, index int){
2.   // 编译器会生成代码
3.   if index<0 || index>=len(arr){
4.     panic("out of range")
5.   }
6.   // end
7.   fmt.Printf("%d", arr[index])
8. }

复制代码

明显：在上层已经确定数组范围的情况下，数组的越界检查是不必要的。
我用下面的方法来找出越界检查：

1. go build -gcflags="-d=ssa/check_bce/debug=1" ./

复制代码

输出：

1. go build -gcflags="-d=ssa/check_bce/debug=1" ./
2. # is_ascii/experiment
3. ./is_ascii.go:10:7: Found IsInBounds
4. ./is_ascii.go:24:49: Found IsInBounds
5. ./is_ascii.go:31:7: Found IsInBounds

复制代码

对应到代码：

1. func IsASCII_v2(s string) bool {
2.         l := len(s)
3.         align8 := l & (-8)
4.         buf := unsafe.Slice(unsafe.StringData(s), align8)
5.         for i := 0; i < align8; i += 8 {
6.                 var v uint64 = *((*uint64)(unsafe.Pointer(&buf[i])))  // 这里有越界检查
7.                 if (v & maskOfAscii) != 0 {
8.                         return false
9.                 }
10.         }
11.         s = s[align8:]
12.         for i := range s {
13.                 if s[i] >= utf8.RuneSelf {    // 这里有越界检查
14.                         return false
15.                 }
16.         }
17.         return true
18. }

复制代码

我使用了 unsafe 代码来去掉数组越界检查：

1. func IsASCII_v3(s string) bool {
2.         l := len(s)
3.         align8 := l & (-8)
4.         ptr := unsafe.Pointer(unsafe.StringData(s))
5.         for i := 0; i < align8; i += 8 {
6.                 var v uint64 = *((*uint64)(unsafe.Add(ptr, i)))  // 使用指针偏移，代替数组下标
7.                 if (v & maskOfAscii) != 0 {
8.                         return false
9.                 }
10.         }
11.         ptr = unsafe.Add(ptr, align8)
12.         for i := 0; i < l&7; i++ {
13.                 var c byte = *((*byte)(unsafe.Add(ptr, i)))
14.                 if c >= utf8.RuneSelf {
15.                         return false
16.                 }
17.         }
18.         return true
19. }

复制代码

Benchmark 结果为：24633.25 MB/s, 从 11.4 倍提升到 21.2 倍。
第三轮优化：循环展开

现代编译器一个典型的性能提升手段就是循环展开：

• 相当于用于判断循环是否结束的哪条指令的执行次数，变成了 N 次展开的 N 分之一
  
• 有利于 CPU 充分利用多级流水线来提升性能
  

循环展开的代码如下：

1. func IsASCII_v3(s string) bool {
2.         l := len(s)
3.         align64 := l & (-64)  // 从一轮处理 8 个字符，变成了一轮处理 64 个字符
4.         ptr := unsafe.Pointer(unsafe.StringData(s))
5.         for i := 0; i < align64; i += 64 {
6.                 values := ((*[8]uint64)(unsafe.Add(ptr, i)))
7.                 if (values[0]&maskOfAscii) != 0 ||
8.                         (values[1]&maskOfAscii) != 0 ||
9.                         (values[2]&maskOfAscii) != 0 ||
10.                         (values[3]&maskOfAscii) != 0 ||
11.                         (values[4]&maskOfAscii) != 0 ||
12.                         (values[5]&maskOfAscii) != 0 ||
13.                         (values[6]&maskOfAscii) != 0 ||
14.                         (values[7]&maskOfAscii) != 0 {
15.                         return false
16.                 }
17.         }
18.         ptr = unsafe.Add(ptr, align64)
19.         for i := 0; i < l&63; i++ {
20.                 var c byte = *((*byte)(unsafe.Add(ptr, i)))
21.                 if c >= utf8.RuneSelf {
22.                         return false
23.                 }
24.         }
25.         return true
26. }

复制代码

Benchmark 结果为：42500.99 MB/s，与上一次相比，从 21.2 倍 提升到 36.6 倍。
第四轮优化：cache line 对齐

这个好像也是显而易见的优化方法：当内存地址以 64 字节对齐时，在数据加载到 cache line 的时候，会明显的提速。
优化后的代码如下：

1. func IsASCII_v4(s string) bool {
2.         addr := uint64(uintptr(unsafe.Pointer(unsafe.StringData(s))))
3.         alignAddr := (addr + uint64(63)) & (^uint64(63))
4.         headLen := alignAddr - addr
5.         ptr := unsafe.Pointer(unsafe.StringData(s))
6.         for i := 0; i < int(headLen); i++ {  // 先处理未按照 64 字节对齐的部分
7.                 var c byte = *((*byte)(unsafe.Add(ptr, i)))
8.                 if c >= utf8.RuneSelf {
9.                         return false
10.                 }
11.         }
12.         l := len(s) - int(headLen)
13.         align64 := l & (-64)
14.         ptr = unsafe.Add(ptr, headLen)
15.         for i := 0; i < align64; i += 64 {
16.                 values := ((*[8]uint64)(unsafe.Add(ptr, i)))
17.                 if (values[0]&maskOfAscii) != 0 ||
18.                         (values[1]&maskOfAscii) != 0 ||
19.                         (values[2]&maskOfAscii) != 0 ||
20.                         (values[3]&maskOfAscii) != 0 ||
21.                         (values[4]&maskOfAscii) != 0 ||
22.                         (values[5]&maskOfAscii) != 0 ||
23.                         (values[6]&maskOfAscii) != 0 ||
24.                         (values[7]&maskOfAscii) != 0 {
25.                         return false
26.                 }
27.         }
28.         ptr = unsafe.Add(ptr, align64)
29.         for i := 0; i < l&63; i++ {
30.                 var c byte = *((*byte)(unsafe.Add(ptr, i)))
31.                 if c >= utf8.RuneSelf {
32.                         return false
33.                 }
34.         }
35.         return true
36. }

复制代码

Benchmark 结果为：41727.41 MB/s，与上一次相比，从 36.6 倍降低到 35.9 倍。
怎么还慢了？不急，加上下一步就能看见增长了。
第五轮优化：位运算代替比较运算

在循环展开的代码中：

1.                 if (values[0]&maskOfAscii) != 0 ||
2.                         (values[1]&maskOfAscii) != 0 ||
3.                         (values[2]&maskOfAscii) != 0 ||
4.                         (values[3]&maskOfAscii) != 0 ||
5.                         (values[4]&maskOfAscii) != 0 ||
6.                         (values[5]&maskOfAscii) != 0 ||
7.                         (values[6]&maskOfAscii) != 0 ||
8.                         (values[7]&maskOfAscii) != 0 {
9.                         return false
10.                 }

复制代码

if 中的每一行，编译器其实生成了两条指令，一条 CMP，一条按照条件来 Jump.
从反汇编的结果中可以发现这一点：

1. command-line-arguments_IsASCII_v4_pc20:
2.         CMPQ    DX, BX
3.         JGE     command-line-arguments_IsASCII_v4_pc124
4.         MOVQ    (AX)(DX*1), SI
5.         MOVQ    $-9187201950435737472, DI
6.         TESTQ   DI, SI  // 0-8 的比较.  每 8 个字节，都有比较指令和跳转指令。
7.         JNE     command-line-arguments_IsASCII_v4_pc121  // 跳转
8.         MOVQ    8(AX)(DX*1), SI
9.         TESTQ   SI, DI  // 8-16 的比较
10.         JNE     command-line-arguments_IsASCII_v4_pc121  // 跳转
11.         MOVQ    16(AX)(DX*1), SI
12.         NOP
13.         TESTQ   SI, DI    // 16-24 的比较
14.         JNE     command-line-arguments_IsASCII_v4_pc121  // 跳转
15.         MOVQ    24(AX)(DX*1), SI
16.         TESTQ   SI, DI   // 24-32 的比较
17.         JNE     command-line-arguments_IsASCII_v4_pc121
18.         MOVQ    32(AX)(DX*1), SI
19.         TESTQ   SI, DI   // 32-40 的比较
20.         JNE     command-line-arguments_IsASCII_v4_pc121
21.         MOVQ    40(AX)(DX*1), SI
22.         NOP
23.         TESTQ   SI, DI   // 40-48 的比较
24.         JNE     command-line-arguments_IsASCII_v4_pc121
25.         MOVQ    48(AX)(DX*1), SI
26.         TESTQ   SI, DI   // 48-56 的比较
27.         JNE     command-line-arguments_IsASCII_v4_pc121
28.         MOVQ    56(AX)(DX*1), SI
29.         TESTQ   SI, DI  // 56-64 的比较
30.         JEQ     command-line-arguments_IsASCII_v4_pc16

复制代码

如果能去掉那 16 条比较 + 跳转的指令肯定更好，等到 64 字节全部计算完成后，再比较一次就够了。
优化后的代码如下：

1. func IsASCII_v5(s string) bool {
2.         addr := uint64(uintptr(unsafe.Pointer(unsafe.StringData(s))))
3.         alignAddr := (addr + uint64(63)) & (^uint64(63))
4.         headLen := alignAddr - addr
5.         ptr := unsafe.Pointer(unsafe.StringData(s))
6.         for i := 0; i < int(headLen); i++ {
7.                 var c byte = *((*byte)(unsafe.Add(ptr, i)))
8.                 if c >= utf8.RuneSelf {
9.                         return false
10.                 }
11.         }
12.         l := len(s) - int(headLen)
13.         align64 := l & (-64)
14.         ptr = unsafe.Add(ptr, headLen)
15.         for i := 0; i < align64; i += 64 {
16.                 values := ((*[8]uint64)(unsafe.Add(ptr, i)))
17.                 a := values[0]
18.                 b := values[1]
19.                 c := values[2]
20.                 d := values[3]
21.                 e := values[4]
22.                 f := values[5]
23.                 g := values[6]
24.                 h := values[7]
25.                 bits := (a | b | c | d | e | f | g | h) & maskOfAscii // 一定要加括号，否则优先级有问题
26.                 if bits != 0 {
27.                         return false
28.                 }
29.         }
30.         ptr = unsafe.Add(ptr, align64)
31.         for i := 0; i < l&63; i++ {
32.                 var c byte = *((*byte)(unsafe.Add(ptr, i)))
33.                 if c >= utf8.RuneSelf {
34.                         return false
35.                 }
36.         }
37.         return true
38. }

复制代码

Benchmark 结果为：43419.36 MB/s，与上上次相比，从 36.6 倍 提升到 37.38 倍。
再回到 cache line 优化这里：如果上面的代码去掉 cache line 对齐，性能如何？ Benchmark 结果为 39891.79 MB/s，由此可见 cache line 对齐对于连续的数据加载提升明显。
第六轮优化：用跳转表优化短字符串处理

先看这样一个简单的例子：

1. func switchTest(a int) int {
2.         switch a {
3.         case 1:
4.                 return 100
5.         case 2:
6.                 return 103
7.         case 3:
8.                 return 205
9.         case 4:
10.                 return 309
11.         case 5:
12.                 return 413
13.         case 6:
14.                 return 517
15.         case 7:
16.                 return 621
17.         case 8:
18.                 return 725
19.         case 9:
20.                 return 829
21.         default:
22.                 return 933
23.         }
24. }

复制代码

假设我有连续的多个值，并且每个分支有不一样的返回。在编译器的层面，是编译为连续的多条比较指令吗？其实编译器用了跳转表来提升性能。让我们看看对应的汇编代码：

1.         TEXT    command-line-arguments.switchTest(SB), NOSPLIT|NOFRAME|ABIInternal, $0-8
2.         FUNCDATA        $0, gclocals·FzY36IO2mY0y4dZ1+Izd/w==(SB)
3.         FUNCDATA        $1, gclocals·FzY36IO2mY0y4dZ1+Izd/w==(SB)
4.         FUNCDATA        $5, command-line-arguments.switchTest.arginfo1(SB)
5.         FUNCDATA        $6, command-line-arguments.switchTest.argliveinfo(SB)
6.         PCDATA  $3, $1
7.         LEAQ    -1(AX), CX
8.         CMPQ    CX, $8
9.         JHI     command-line-arguments_switchTest_pc75
10.         LEAQ    command-line-arguments.switchTest.jump3(SB), AX
11.         JMP     (AX)(CX*8)
12.         MOVL    $100, AX
13.         RET
14.         MOVL    $103, AX
15.         NOP
16.         RET
17.         MOVL    $205, AX
18.         RET
19.         MOVL    $309, AX
20.         RET
21.         MOVL    $413, AX
22.         RET
23.         MOVL    $517, AX
24.         RET
25.         MOVL    $621, AX
26.         RET
27.         MOVL    $725, AX
28.         RET
29.         MOVL    $829, AX
30.         RET
31. command-line-arguments_switchTest_pc75:
32.         MOVL    $933, AX
33.         RET
34.         
35.         
36. .switchTest.jump3 SRODATA static size=72
37.         rel 0+8 t=R_ADDR <unlinkable>.SwitchTest+20
38.         rel 8+8 t=R_ADDR <unlinkable>.SwitchTest+26
39.         rel 16+8 t=R_ADDR <unlinkable>.SwitchTest+33
40.         rel 24+8 t=R_ADDR <unlinkable>.SwitchTest+39
41.         rel 32+8 t=R_ADDR <unlinkable>.SwitchTest+45
42.         rel 40+8 t=R_ADDR <unlinkable>.SwitchTest+51
43.         rel 48+8 t=R_ADDR <unlinkable>.SwitchTest+57
44.         rel 56+8 t=R_ADDR <unlinkable>.SwitchTest+63
45.         rel 64+8 t=R_ADDR <unlinkable>.SwitchTest+69   

复制代码

编译器构造了长度为 9 的数组，数组中的值可以理解为代码段的偏移量。运行时，根据输入的值，在跳转表中查询到指令的偏移量，然后跳转到对应的指令去执行。使用这个方法即可避免大量的比较指令。
因此，可以用跳转表的方法优化短字符串的判断。小于 8 字节的短字符串，可以用下面的代码来加速：

1. func isAsciiForLenLess8(ptr unsafe.Pointer, l int) uint64 {
2.         switch l {
3.         case 1:
4.                 v := *(*uint8)(ptr)
5.                 return uint64(v)
6.         case 2:
7.                 v := *(*uint16)(ptr)
8.                 return uint64(v)
9.         case 3:
10.                 v1 := *(*uint16)(ptr)
11.                 v2 := *(*uint8)(unsafe.Add(ptr, 2))
12.                 return uint64(v1 | uint16(v2))
13.         case 4:
14.                 v := *(*uint32)(ptr)
15.                 return uint64(v)
16.         case 5:
17.                 v1 := *(*uint32)(ptr)
18.                 v2 := *(*uint8)(unsafe.Add(ptr, 4))
19.                 return uint64(v1 | uint32(v2))
20.         case 6:
21.                 v1 := *(*uint32)(ptr)
22.                 v2 := *(*uint16)(unsafe.Add(ptr, 4))
23.                 return uint64(v1 | uint32(v2))
24.         case 7:
25.                 v1 := *(*uint32)(ptr)
26.                 v2 := *(*uint16)(unsafe.Add(ptr, 4))
27.                 v3 := *(*uint8)(unsafe.Add(ptr, 6))
28.                 return uint64(v1 | uint32(v2) | uint32(v3))
29.         case 8:
30.                 return *(*uint64)(ptr)
31.         default:
32.                 return 0
33.         }
34. }
35. /*
36.         TEXT    command-line-arguments.isAsciiForLenLess8_v4(SB), NOSPLIT|NOFRAME|ABIInternal, $0-16
37.         FUNCDATA        $0, gclocals·2NSbawKySWs0upw55xaGlw==(SB)
38.         FUNCDATA        $1, gclocals·ISb46fRPFoZ9pIfykFK/kQ==(SB)
39.         FUNCDATA        $5, command-line-arguments.isAsciiForLenLess8_v4.arginfo1(SB)
40.         FUNCDATA        $6, command-line-arguments.isAsciiForLenLess8_v4.argliveinfo(SB)
41.         PCDATA  $3, $1
42.         LEAQ    -1(BX), CX
43.         CMPQ    CX, $7
44.         JHI     command-line-arguments_isAsciiForLenLess8_v4_pc81
45.         // 从汇编代码可以看出，编译器使用了跳转表的技术
46.         LEAQ    command-line-arguments.isAsciiForLenLess8_v4.jump3(SB), DX
47.         JMP     (DX)(CX*8)
48.         MOVBLZX (AX), AX
49.         RET
50.         MOVWLZX (AX), AX
51.         RET
52.         MOVWLZX (AX), CX
53.         MOVBLZX 2(AX), DX
54.         ORL     DX, CX
55.         MOVWLZX CX, AX
56.         RET
57.         MOVL    (AX), AX
58.         RET
59.         MOVBLZX 4(AX), CX
60.         ORL     (AX), CX
61.         MOVL    CX, AX
62.         RET
63.         MOVWLZX 4(AX), CX
64.         ORL     (AX), CX
65.         MOVL    CX, AX
66.         RET
67.         MOVWLZX 4(AX), CX
68.         MOVBLZX 6(AX), DX
69.         ORL     (AX), CX
70.         ORL     DX, CX
71.         MOVL    CX, AX
72.         RET
73.         MOVQ    (AX), AX
74.         RET
75. command-line-arguments_isAsciiForLenLess8_v4_pc81:
76.         XORL    AX, AX
77.         RET
78. */

复制代码

仔细阅读代码会发现： case 8 这一段是肯定用不到的，因为函数的目的就只是优化小于 8 的字符判断。为什么要加上这一行？
答案在 golang 源码的：github.com/golang/go/src/cmd/compile/internal/walk/switch.go

1. // Try to implement the clauses with a jump table. Returns true if successful.
2. func (s *exprSwitch) tryJumpTable(cc []exprClause, out *ir.Nodes) bool {
3.         const minCases = 8   // have at least minCases cases in the switch
4.         const minDensity = 4 // use at least 1 out of every minDensity entries
6.         if base.Flag.N != 0 || !ssagen.Arch.LinkArch.CanJumpTable || base.Ctxt.Retpoline {
7.                 return false
8.         }
9.   // ...
10. }  

复制代码

编译器要至少 8 个 case 才编译成跳转表，因此 case 8 是用于欺骗编译器的。
最终，使用了跳转表优化技术的版本如下：

1. const maskOfAscii uint64 = uint64(0x8080808080808080)
3. func IsASCII_v6(s string) bool {
4.         if len(s) == 0 {
5.                 return true
6.         }
7.         ptr := unsafe.Pointer(unsafe.StringData(s))
8.         addr := uint64(uintptr(ptr))
9.         alignAddr := (addr + uint64(63)) & (^uint64(63))
10.         headLen := alignAddr - addr
11.         isEnd := false
12.         var processLen int
13.         var tempLen int
14.         var result uint64
15.         var align64Len int
16.         var leftLen int
17.         var uint64Cnt int
18.         var values *[8]uint64
19.         //
20.         if len(s) < 64 {
21.                 isEnd = true
22.                 processLen = len(s)
23.                 goto len_less_64
24.         }
25.         tempLen = (len(s) - int(headLen))
26.         align64Len = tempLen & (-64)
27.         leftLen = tempLen & 63
28.         if headLen == 0 {
29.                 goto align64
30.         }
31.         processLen = int(headLen)
32. len_less_64:
33.         result = 0
34.         uint64Cnt = processLen >> 3 // processLen / 8
35.         tempLen = processLen & 7
36.         switch uint64Cnt {
37.         case 1:
38.                 result |= *(*uint64)(ptr)
39.         case 2:
40.                 values = (*[8]uint64)(ptr)
41.                 result |= (values[0] | values[1])
42.         case 3:
43.                 values = (*[8]uint64)(ptr)
44.                 result |= (values[0] | values[1] | values[2])
45.         case 4:
46.                 values = (*[8]uint64)(ptr)
47.                 result |= (values[0] | values[1] | values[2] | values[3])
48.         case 5:
49.                 values = (*[8]uint64)(ptr)
50.                 result |= (values[0] | values[1] | values[2] | values[3] | values[4])
51.         case 6:
52.                 values = (*[8]uint64)(ptr)
53.                 result |= (values[0] | values[1] | values[2] | values[3] | values[4] | values[5])
54.         case 7:
55.                 values = (*[8]uint64)(ptr)
56.                 result |= (values[0] | values[1] | values[2] | values[3] | values[4] | values[5] | values[6])
57.         case 8:
58.                 values = (*[8]uint64)(ptr)
59.                 result |= (values[0] | values[1] | values[2] | values[3] | values[4] | values[5] | values[6] | values[7])
60.         }
61.         ptr = unsafe.Add(ptr, processLen&(-8))
62.         switch tempLen {
63.         case 1:
64.                 v := *(*uint8)(ptr)
65.                 result |= uint64(v)
66.         case 2:
67.                 v := *(*uint16)(ptr)
68.                 result |= uint64(v)
69.         case 3:
70.                 v1 := *(*uint16)(ptr)
71.                 v2 := *(*uint8)(unsafe.Add(ptr, 2))
72.                 result |= uint64(v1 | uint16(v2))
73.         case 4:
74.                 v := *(*uint32)(ptr)
75.                 result |= uint64(v)
76.         case 5:
77.                 v1 := *(*uint32)(ptr)
78.                 v2 := *(*uint8)(unsafe.Add(ptr, 4))
79.                 result |= uint64(v1 | uint32(v2))
80.         case 6:
81.                 v1 := *(*uint32)(ptr)
82.                 v2 := *(*uint16)(unsafe.Add(ptr, 4))
83.                 result |= uint64(v1 | uint32(v2))
84.         case 7:
85.                 v1 := *(*uint32)(ptr)
86.                 v2 := *(*uint16)(unsafe.Add(ptr, 4))
87.                 v3 := *(*uint8)(unsafe.Add(ptr, 6))
88.                 result |= uint64(v1 | uint32(v2) | uint32(v3))
89.         case 8:
90.                 result |= *(*uint64)(ptr)
91.         }
92.         ptr = unsafe.Add(ptr, tempLen)
93.         if (result & maskOfAscii) != 0 {
94.                 return false
95.         }
96.         if isEnd {
97.                 return true
98.         }
99. align64:
100.         for i := 0; i < align64Len; i += 64 {
101.                 values := ((*[8]uint64)(unsafe.Add(ptr, i)))
102.                 a := values[0]
103.                 b := values[1]
104.                 c := values[2]
105.                 d := values[3]
106.                 e := values[4]
107.                 f := values[5]
108.                 g := values[6]
109.                 h := values[7]
110.                 bits := (a | b | c | d | e | f | g | h) & maskOfAscii
111.                 if bits != 0 { // 一定要加括号，否则优先级有问题
112.                         return false
113.                 }
114.         }
115.         isEnd = true
116.         ptr = unsafe.Add(ptr, align64Len)
117.         processLen = leftLen
118.         goto len_less_64
119. }

复制代码

使用 goto 是为了避免内联函数而导致代码膨胀。
Benchmark 结果为：43472.71 MB/s，与上次相比，从 37.38 倍 提升到 37.43 倍。
看起来是微小的提升，但如果仅对小于 64 字节的短字符做 Benchmark，性能对比如下：

• 原始版本：1135.18 MB/s
  
• IsASCII_v6:  11607.68 MB/s， 提升 10.2 倍。
  

第七轮优化： plan9 汇编 + AVX2 指令

这个优化已经超过了 golang 的范畴。
但是 AVX2 指令优化的思路还是可以学习的，可能很快就能在 golang 中用上 SIMD 指令集了。请看这篇文章的介绍：《告别手写汇编：Go官方提出原生SIMD支持，高性能计算将迎来巨变》(https://zhuanlan.zhihu.com/p/1915320517000427200)
汇编优化的内容，我也向 VictoriaLogs 团队提了 PR: add simd version of IsASCII()
汇编的代码如下：

1. #include "textflag.h"
3. TEXT ·IsASCII(SB), NOSPLIT | NOFRAME, $0-17
4.     // frame length:  0
5.     // args size: 16 bytes
6.     // return value size: 1 byte
7.     MOVQ inPtr+0(FP), R8  // start
8.     MOVQ inLen+8(FP), R9  // string length
9.     // variables
10.     LEAQ (R8)(R9*1), R10  // end = in + len
11.     XORQ R11, R11  // offset = 0
12.     MOVQ R9, R12  // left_len = len
13. align_32:
14.     CMPQ R12, $31  // if left_len < 32 then goto align_32_end
15.     JLE align_32_end
16.     VMOVDQU (R8)(R11*1), Y0  // _mm256_loadu_si256, load 32 bytes to Y0
17.     VPMOVMSKB Y0, R13  // _mm256_movemask_epi8, move mask
18.     ADDQ $32, R11  // offset += 32
19.     ADDQ $-32, R12  // left_len -= 32
20.     TESTQ R13, R13  // if mask== 0 then goto align_32
21.     JE align_32
22.     MOVB $0, ret+16(FP)  // return 0
23.     VZEROUPPER  // clear registers
24.     RET
25. align_32_end:
26.     LEAQ (R8)(R11*1), R12  // current
27. next_char:
28.     CMPQ R12, R10  // if current==end then goto end
29.     JEQ end
30.     MOVQ $0, R13 //
31.     MOVB (R12), R13  // r13 = str[i]
32.     CMPQ R13,$127 // if r13 >= 127 then goto not_ascii_end
33.     JA not_ascii_end
34.     ADDQ $1, R12  // current += 1
35.     JMP next_char
36. end:
37.     MOVB $1, ret+16(FP)  // return 1
38.     VZEROUPPER
39.     RET
40. not_ascii_end:
41.     MOVB $0, ret+16(FP)  // return 0
42.     VZEROUPPER
43.     RET

复制代码

原理上非常简单：

• 一次性加载 32 字节到 256 bit 的寄存器
  
• 使用 move mask 指令，取每个 uint8 的最高位
  
• 把 32 个最高位变成 uint32 的掩码，掩码不为 0 ，说明存在非 ASCII 字符
  

以上的汇编函数还缺乏很多优化手段：

• cache line 对齐
  
• 使用 jump table 优化短字符串处理
  
• 循环展开
  

Benchmark 结果为：64138.16 MB/s，与上次相比，从 37.43 倍 提升到 55.2 倍。
并且，汇编版本仍然有优化的空间。
最后的总结

• 底层的热点算法可以考虑直接用 plan9 汇编 + SIMD 指令集来实现。golang 的编译器非常“老实”，可以发现生成的汇编与编写的golang代码几乎一致，优化并不多。SIMD 指令集的提升非常明显，比死扣golang的写法爽太多了。
  
• 日常的 golang 代码开发中，也可以参考第一轮到第六轮的优化思路，可以发现，改改写法也能尽可能地接近汇编版本。
  
• 网站 https://godbolt.org/ 是个非常好的工具，可以把 golang 代码立即转成 plan9 汇编供对比。
  

然后再提供一些链接：

• Inside VictoriaMetrics: https://github.com/ahfuzhang/InsideVictoriaMetrics， 我正在写一本关于 VictoriaMetrics 和 VictoriaLogs 的书，可以学到时序数据库是如何做出来的。
  
• learning_go_plan9_assembly: https://github.com/ahfuzhang/learning_go_plan9_assembly， 我做的 golang plan9 汇编的教程和相关的开源书籍。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！