加速CQ码解析背后原理

2021-03-22 约 2406 字预计阅读 5 分钟次阅读

前言

在开源项目 go-cqhttp 中，我提交了两个 pr(#659,#660) 使得CQ码 (一种用字符串表示IM消息的方式)效率变为了原来的400%。这篇文章简单介绍了加速解析的原理，里面的某些优化方法对 Go 语言是通用的，希望能对读者优化 Go 程序有一定启发。

CQ码解析的原方案

CQ码的语法规则

CQ码的表示可以为[1]

 1CQCode
 2    : "[CQ:" Type (',' ParameterList)? ']'
 3    ;
 4
 5Type
 6    : string
 7    ;
 8
 9ParameterList
10    : Parmeter (',' Parmeter)*
11    ;
12
13Parameter
14    : string '=' string
15    ;

其中Type是消息类型，ParameterList是参数列表

正则表达式解析

在最初解析方案是采用正则表达式，使用标准库中的regex包进行解析

1var matchReg = regexp.MustCompile(`\[CQ:\w+?.*?]`)
2var typeReg = regexp.MustCompile(`\[CQ:(\w+)`)
3var paramReg = regexp.MustCompile(`,([\w\-.]+?)=([^,\]]+)`)

自动机解析

使用正则表达式可以获得比较高的通用性，可读性，可维护性，但是为了压榨性能，手写自动机就是优化解析的重要途经。 Mrs4s大佬给出了一份自动机解析的实现[2]

优化加速

在上一版自动机中，效率比正则表达式提高了 30% ，但这对于性能压榨还不够彻底，于是我便开始了优化之路。

优化后的初稿如下

 1func ParseCQCode(s string) Message {
 2    var d = map[string]string{} // parameters
 3    var key, Type = "", ""
 4    l := len(s)
 5    i, j := 0, 0
 6S1: // Plain Text
 7    for ; i < l; i++ {
 8        if s[i] == '[' && s[i:i+4] == "[CQ:" {
 9            if i > j {
10                saveText(s[j:i])
11            }
12            i += 4
13            j = i
14            goto S2
15        }
16    }
17    goto End
18S2: // CQCode Type
19    d = map[string]string{}
20    for ; i < l; i++ {
21        switch s[i] {
22        case ',': // CQ Code with params
23            Type = s[j:i]
24            i++
25            j = i
26            goto S3
27        case ']': // CQ Code without params
28            Type = s[j:i]
29            i++
30            j = i
31            saveCQCode()
32            goto S1
33        }
34    }
35    goto End
36S3: // CQCode param key
37    for ; i < l; i++ {
38        if s[i] == '=' {
39            key = s[j:i]
40            i++
41            j = i
42            goto S4
43        }
44    }
45    goto End
46S4: // CQCode param value
47    for ; i < l; i++ {
48        switch s[i] {
49        case ',': // more param
50            d[key] = CQCodeUnescapeValue(s[j:i])
51            i++
52            j = i
53            goto S3
54        case ']':
55            d[key] = CQCodeUnescapeValue(s[j:i])
56            i++
57            j = i
58            saveCQCode()
59            goto S1
60        }
61    }
62    goto End
63End:
64    if i > j {
65        saveText(s[j:i])
66    }
67}

去除不必要的转换

在上一版自动机中，将整个字符串转换成了 []rune ，观察到 CQ 码的结构中只含有 ASCII 字符，根据 UTF-8 的性质，所有的非 ASCII 字符的个个字节都大于128，所以对于解析CQ码，我们并不需要将字符串转换成 []rune 。

设计一个更全面的状态机

在上一版状态机中,状态数目较少，只能解析出整个CQ码的字符串，将Type和参数取出来，需要使用Split分割，于是我设计了一个更加全面的状态机。

相比之前的状态机，可以更加精细的解析CQ码的内容，避免了重复操作，通过一次遍历就完成了所有 CQ码的解析。

避免拷贝，使用切片进行内存复用

对于CQ码，我们只需要从字符串中提取一部分，而且后续的操作中，我们不会对字符串进行修改，所以我是用了切片操作来截取字符串，尽可能的减少内存分配

消除边界检查

Go语言是一门内存安全的语言，程序运行过程中会进行边界检查，这对程序的稳定避免发生更严重的错误很重要，但是有些情况下，我们可以保证一定不会发生数组(切片)越界，这时边界检查就变得多余了。

在 Go 编译器中，实现了对某些情况的边界检查消除，例如标准库encoding/binary中

1func (littleEndian) PutUint32(b []byte, v uint32) {
2    _ = b[3] // early bounds check to guarantee safety of writes below
3    b[0] = byte(v)
4    b[1] = byte(v >> 8)
5    b[2] = byte(v >> 16)
6    b[3] = byte(v >> 24)
7}

在第二行中，提前检查了边界，Go编译器就会对后续的4行操作不进行边界检查。 Go对边界检查消除优化还不够全面，往往需要我们手动提示编译器进行边界检查消除。

例如下面代码中，对is的范围进行暗示

1func foo(is []int, bs []byte) {
2    if len(is) >= 256 {
3        is = is[:256] // 给编译器一个暗示
4        for _, n := range bs {
5            _ = is[n] // 边界检查消除了！
6        }
7    }
8}

虽然我重写了一遍状态机，为了探究性能并无很大提升的原因，我使用了

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

查找了代码中所有的边界检查，结果发现代码中几乎所有切片操作都进行了边界检查，同时，在我的自动机实现代码中，保证了索引一定不会越界 (i < l)，于是我尝试给编译器一定提示，尝试消除边界检查。

不幸的是，我尝试了已知的所有 Hint 手段，编译器始终不能进行边界检查消除，这时候我选择另一条道路—— unsafe。

通过 unsafe 操作，实现边界消除。

unsafe

unsafe (×)

I say it is safe (√)

使用了unsafe操作后的代码如下

 1// add 指针运算
 2add := func(ptr unsafe.Pointer, offset uintptr) unsafe.Pointer {
 3    return unsafe.Pointer(uintptr(ptr) + offset)
 4}
 5
 6S1: // Plain Text
 7    for ; i < l; i++ {
 8        if *(*byte)(add(ptr, uintptr(i))) == '[' && i+4 < l &&
 9            *(*uint32)(add(ptr, uintptr(i))) == magicCQ { // Magic :uint32([]byte("[CQ:"))
10            if i > j {
11                saveText(s[j:i])
12            }
13            i += 4
14            j = i
15            goto S2
16        }
17    }
18    goto End
19S2: // CQCode Type
20    d = map[string]string{}
21    for ; i < l; i++ {
22        switch *(*byte)(add(ptr, uintptr(i))) {
23        case ',': // CQ Code with params
24            Type = s[j:i]
25            i++
26            j = i
27            goto S3
28        case ']': // CQ Code without params
29            Type = s[j:i]
30            i++
31            j = i
32            saveCQCode()
33            goto S1
34        }
35    }
36    goto End
37S3: // CQCode param key
38    for ; i < l; i++ {
39        if *(*byte)(add(ptr, uintptr(i))) == '=' {
40            key = s[j:i]
41            i++
42            j = i
43            goto S4
44        }
45    }
46    goto End
47S4: // CQCode param value
48    for ; i < l; i++ {
49        switch *(*byte)(add(ptr, uintptr(i))) {
50        case ',': // more param
51            d[key] = CQCodeUnescapeValue(s[j:i])
52            i++
53            j = i
54            goto S3
55        case ']':
56            d[key] = CQCodeUnescapeValue(s[j:i])
57            i++
58            j = i
59            saveCQCode()
60            goto S1
61        }
62    }
63    goto End
64End:
65    if i > j {
66        saveText(s[j:i])
67    }
68    return

同时，我将判断是否是CQ码头 "[CQ:" 改成了用 uint32 进行比较(与大小端有关),进一步优化了性能. 最终的结果是十分的 Amazing 啊，比重写前的状态机快了几倍。

减少map的创建

目前的实现已经十分快了，正当我觉得没有任何可以优化的地方时，我突然发现了用于保存CQ码参数的map可以进行内存复用。

Go 编译器对map的清空进行了优化，下面这样的代码，Go 编译器会将它优化成一个runtime内部函数，对整个map一次清空。

1var a map[type1]type2
2
3for k := range a {
4    delete(a, k)
5}

虽然并不能释放已使用的内存，但是我们可以复用内存，减少map的扩容，减少alloc，大大提高运行速度。

内存复用

在并发的场景下，可以使用 sync 包中的 sync.Pool 实现线程安全的内存复用。

于是我做了一个小改动

1S2: // CQCode Type
2    // d = map[string]string{} // old 
3    for k := range a {
4        delete(a, k)
5    }
6    for ; i < l; i++ {
7        // ignore
8    }
9    goto End

经过这次改动后，CQ码的解析速度又提高了33%。

总结

最后总结下来，优化Go程序的性能可以从下面几个角度入手

善于内存复用，使用切片或 sync.Pool 减少内存分配。
尽量避免不必要的类型转换带来的开销，例如 []byte 与 string 之间转换， []rune 与 string 之间的转换。
合理暗示编译器，避免不必要的越界检查。

目录

加速CQ码解析背后原理

前言

CQ码解析的原方案

CQ码的语法规则

正则表达式解析

自动机解析

优化加速

去除不必要的转换

设计一个更全面的状态机

避免拷贝，使用切片进行内存复用

消除边界检查

减少map的创建

总结