程序执行太慢？快来学习 SIMD 加速技术，这个案例下的加速效果我也没想到（附带动手实验）

关注
发布于: 2020 年 09 月 25 日
在编译过程中，任何语言都需要转化为对应平台的汇编语言，一个指令完成一个操作。如果告诉你现在有一个指令可以一次完成多个操作，你会怎么使用？
下面教你怎么使用SIMD加速技术。
本文通过Go语言开源社区在ARM64平台对通用字符串比较的优化方案，向读者介绍如何通过SIMD并行化技术提升软件的执行速度。摘自OptimizeLab: https://github.com/OptimizeLab/docs 
﻿
  作者：surechen
﻿
SIMD即单指令多数据流(Single Instruction Multiple Data)指令集，是通过一条指令同时对多个数据进行运算的硬件加速技术，能够有效提高CPU的运算速度，主要适用于计算密集型、数据相关性小的多媒体、数学计算、人工智能等领域。
﻿
Go语言是一种快速、静态类型的开源语言，可以用来轻松构建简单、可靠、高效的软件。目前已经包括丰富的基础库如数学库、加解密库、图像库、编解码等等，其中对于性能要求较高且编译器目前还不能优化的场景，Go语言通过在底层使用汇编技术进行了优化，其中最重要的就是SIMD技术。
﻿
1. 字符串比较的性能问题﻿
先看一个常见的问题，在各行各业的服务系统中，用户登录需要验证用户名或ID，订购货物需要对比货物ID，出行需要验证票号等等，这些都离不开字符串比较操作，字符串实际上就是字节数组，在Go语言中可以表示成[]byte的形式，字符串的比较即两个数组中对应byte的比较。因此可以直观的写出如下的比较函数代码:
﻿
func EqualBytes(a, b []byte) bool {
    if len(a) != len(b) {       //长度不等则返回false
        return false
    }
    for i, _ := range a {
        if a[i] != b[i] {           //按顺序比较数组a和数组b中的每个byte
            return false
        }
    }
    return true
}
﻿
似乎看起来还不错，逻辑没有问题，但是这样的实现就够了吗？是否能满足所有的使用场景呢？本文通过性能测试来给出答案。通过Go benchmark进行测试得出如下数据：
﻿
[注]ns/op:每次函数执行耗费的纳秒时间;MB/s:每秒处理的兆字节数据;B:字节
﻿
如表所示，随着处理数据量的增加，耗时上升明显，当数据量达到4M时，耗时接近3.5毫秒(3496666 ns/op)，作为一个基础操作来讲性能表现较差。
2. Go语言社区字符串比较的SIMD优化方案﻿
那么字符串比较的性能问题是否有优化的办法呢？本文就以Go语言社区对字符串比较的优化案例揭开SIMD技术优化的神秘面纱：
﻿
优化的补丁在Go社区官网可见。
﻿
由于优化前后的代码都是汇编，为便于读者学习代码，首先将上节的Go代码例子与优化前的Equal汇编代码对比，通过如下直观的对比关系图来展示:
﻿
﻿
如图所示，两者实现逻辑是对应的。此处对于一行Go代码a[i]!=b[i]，需要四条汇编指令：
﻿
两条取数指令，分别将切片数组a和b中的byte值取到寄存器中；
通过CMP(比较指令)对比两个寄存器中的值，根据比较结果更新状态寄存器;
BEQ(跳转指令)根据状态寄存器值进行跳转，此处是等于则跳转到loop标签处，即如果相等则继续下一轮比较。
﻿
现在可以正式开始分析Equal的SIMD优化版了，这里的核心思路是通过单指令同时处理多个byte数据的方式，大幅减少数据加载和比较操作的指令条数，发挥SIMD运算部件的算力，提升性能。
﻿
下图是使用SIMD技术优化汇编代码前后的对比图，从图中可以看到优化前代码非常简单，循环取1 byte进行比较，使用SIMD指令优化后，代码被复杂化，这里可以先避免陷入细节，先理解实现原理，具体代码细节可以在章节[优化后代码详解]再进一步学习。此处代码变复杂的主要原因是进行了分情况的分块处理，首先循环处理64 bytes大小的分块，当数组末尾不足64 bytes时，再将余下的按16 bytes分块处理，直到余下长度为1时的情况，下图直观的演示了优化前后的对比关系和优化后分块处理的规则:
﻿
3. 优化前代码详解优化前的代码循环从两个数组中取1 byte进行比较，每byte数据要耗费2个加载操作、1个比较操作、1个数组末尾判断操作，如下所示：
//func Equal(a, b []byte) bool
TEXT bytes·Equal(SB),NOSPLIT,$0-49
//---------数据加载------------
    // 将栈上数据取到寄存器中
    // 对数组长度进行比较，如果不相等直接返回0
    MOVD a_len+8(FP), R1        // 取数组a的长度
    MOVD b_len+32(FP), R3      // 取数组b的长度
    CMP R1, R3                         // 数组长度比较
    BNE notequal                      // 数组长度不同，跳到notequal
    MOVD a+0(FP), R0              // 将数组a的地址加载到通用寄存器R0中
    MOVD b+24(FP), R2            // 将数组b的地址加载到通用寄存器R2中
    ADD R0, R1                         // R1保存数组a末尾的地址
//-----------------------------
//--------数组循环比较操作-------
loop:
    CMP R0, R1                         // 判断是否到了数组a末尾
    BEQ equal                           // 如果已经到了末尾，说明之前都是相等的，跳转到标签equal
    MOVBU.P 1(R0), R4             // 从数组a中取一个byte加载到通用寄存器R4中
    MOVBU.P 1(R2), R5             // 从数组b中取一个byte加载到通用寄存器R5中
    CMP R4, R5                         // 比较寄存器R4、R5中的值
    BEQ loop                             // 相等则继续下一轮循环操作
//-----------------------------
//-------------不相等-----------
notequal:
    MOVB ZR, ret+48(FP)          // 数组不相等，返回0
    RET
//-----------------------------
//-------------相等-------------
equal:
    MOVD $1, R0                       // 数组相等，返回1
    MOVB R0, ret+48(FP)
    RET
//-----------------------------
﻿
4. 优化后代码详解优化后的代码因为做了循环展开，所有看起来比较复杂，但逻辑是很清晰的，即采用分块的思路，将数组划分为64/16/8/4/2/1bytes大小的块，使用多个向量寄存器，利用一条SIMD指令最多同时处理16个bytes的优势，同时也减少了边界检查的次数。汇编代码解读如下(代码中添加了关键指令注释）：
﻿
// 函数的参数，此处是通过寄存器传递参数的
// 调用memeqbody的父函数已经将参数放入了如下寄存器中
// R0: 寄存器R0保存数组a的地址
// R1: 寄存器R1数组a的末尾地址
// R2: 寄存器R2保存数组b的地址
// R8: 寄存器R8存放比较的结果
TEXT runtime·memeqbody<>(SB),NOSPLIT,$0
//---------------数组长度判断-----------------
// 根据数组长度判断按照何种分块开始处理
    CMP    $1, R1
    BEQ    one
    CMP    $16, R1
    BLO    tail
    BIC    $0x3f, R1, R3
    CBZ    R3, chunk16
    ADD    R3, R0, R6
﻿
//------------处理长度为64 bytes的块-----------
// 按64 bytes为块循环处理
chunk64_loop:
// 加载RO,R2指向的数据块到SIMD向量寄存器中，并将RO,R2指针偏移64位
    VLD1.P (R0), [V0.D2, V1.D2, V2.D2, V3.D2]
    VLD1.P (R2), [V4.D2, V5.D2, V6.D2, V7.D2]
// 使用SIMD比较指令，一条指令比较128位，即16个bytes，结果存入V8-v11寄存器
    VCMEQ  V0.D2, V4.D2, V8.D2
    VCMEQ  V1.D2, V5.D2, V9.D2
    VCMEQ  V2.D2, V6.D2, V10.D2
    VCMEQ  V3.D2, V7.D2, V11.D2
// 通过SIMD与运算指令，合并比较结果，最终保存在寄存器V8中
    VAND   V8.B16, V9.B16, V8.B16
    VAND   V8.B16, V10.B16, V8.B16
    VAND   V8.B16, V11.B16, V8.B16
// 下面指令判断是否末尾还有64bytes大小的块可继续64bytes的循环处理
// 判断是否相等，不相等则直接跳到not_equal返回
    CMP    R0, R6                             // 比较指令，比较RO和R6的值，修改寄存器标志位，对应下面的BNE指令
    VMOV   V8.D[0], R4
    VMOV   V8.D[1], R5                   // 转移V8寄存器保存的结果数据到R4,R5寄存器
    CBZ    R4, not_equal
    CBZ    R5, not_equal                   // 跳转指令，若R4,R5寄存器的bit位出现0，表示不相等，跳转not_equal
    BNE    chunk64_loop                  // 标志位不等于0，对应上面RO!=R6则跳转chunk64_loop
    AND    $0x3f, R1, R1                   // 仅保存R1末尾的后6位，这里保存的是末尾不足64bytes块的大小
    CBZ    R1, equal                         // R1为0,跳转equal，否则向下顺序执行
﻿
...............................................
...............................................
﻿
//-----------循环处理长度为16 bytes的块------------
chunk16_loop:
    VLD1.P (R0), [V0.D2]
    VLD1.P (R2), [V1.D2]
    VCMEQ    V0.D2, V1.D2, V2.D2
    CMP R0, R6
    VMOV V2.D[0], R4
    VMOV V2.D[1], R5
    CBZ R4, not_equal
    CBZ R5, not_equal
    BNE chunk16_loop
    AND $0xf, R1, R1
    CBZ R1, equal
//-----处理数组末尾长度小于16、8、4、2 bytes的块-----
tail:
    TBZ $3, R1, lt_8
    MOVD.P 8(R0), R4
    MOVD.P 8(R2), R5
    CMP R4, R5
    BNE not_equal
﻿
lt_8:
    TBZ $2, R1, lt_4
    MOVWU.P 4(R0), R4
    MOVWU.P 4(R2), R5
    CMP R4, R5
    BNE not_equal
﻿
lt_4:
    TBZ $1, R1, lt_2
    MOVHU.P 2(R0), R4
    MOVHU.P 2(R2), R5
    CMP R4, R5
    BNE not_equal
﻿
lt_2:
    TBZ     $0, R1, equal
﻿
one:
    MOVBU (R0), R4
    MOVBU (R2), R5
    CMP R4, R5
    BNE not_equal
//-----------------判断相等返回1----------------
equal:
    MOVD $1, R0
    MOVB R0, (R8)
    RET
//----------------判断不相等返回0----------------
not_equal:
    MOVB ZR, (R8)
    RET
﻿
﻿
上述优化代码中，使用VLD1(数据加载指令)一次加载64bytes数据到SIMD寄存器，再使用VCMEQ(相等比较指令)比较SIMD寄存器保存的数据内容得到结果，相比传统用的单字节比较方式，提高了64byte数据块的比较性能。大于16byte小于64byte块数据，使用一个SIMD寄存器一次处理16byte块的数据，小于16byte数据块使用通用寄存器保存数据，一次比较8\4\2\1byte的数据块。
5. 动手实验感兴趣的读者可以根据下面的命令自己执行一遍，感受SIMD技术的强大。
﻿
环境准备
硬件配置：鲲鹏(ARM64)云Linux服务器-通用计算增强型KC1 kc1.2xlarge.2(8核|16GB)
Go语言发行版 >= 1.12.1，此处开发环境准备请参考文章：Go在ARM64开发环境配置
Go语言github源码仓库下载，此处通过Git安装和使用进行版本控制。
﻿
操作步骤 如下操作包含在鲲鹏服务器上进行编译测试的全过程，本文已经找到了优化前后的两个提交记录，优化前的commit id:0c68b79和优化后的commit id:78ddf27，可以按如下步骤进行操作：
﻿
# 找到一个放置Go源码仓的目录，如/usr/local/src/exp
mkdir /usr/local/src/exp
cd /usr/local/src/exp
# 通过git工具拉取github代码托管平台上Go的代码仓
git clone https://github.com/golang/go
# 进入源码目录
cd /usr/local/src/exp/go/src
# 根据优化前的提交记录0c68b79创建一个新的分支before-simd，这个分支包含优化前的版本
git checkout -b before-simd 0c68b79
# 切换到分支before-simd，此时目录下的代码文件已经变成了优化前的版本
git checkout before-simd
# 编译Go源码，生成Go开发环境
bash make.bash
# 把当前目录设置为GOROOT目录
export GOROOT=/usr/local/src/exp/go
# 使用Go benchmark命令测试性能并记录在文件before-simd-bench.txt中
go test bytes -v -bench ^BenchmarkEqual$ -count=5 -run  ^$ > before-simd-bench.txt
# 根据优化后的提交记录78ddf27创建一个新的分支after-simd，这个分支包含优化后的版本
git checkout -b after-simd 78ddf27
# 切换到分支after-simd，此时目录下的代码文件已经变成了优化后的版本
git checkout after-simd
# 再次编译Go源码，生成Go开发环境
bash make.bash
# 使用Go benchmark命令测试性能并记录在文件after-simd-bench.txt中
go test bytes -v -bench ^BenchmarkEqual$ -count=5 -run  ^$ > after-simd-bench.txt
# benchstat 对比结果
benchstat before-simd-bench.txt after-simd-bench.txt
# 最后，可以根据提交记录78ddf27查看代码变更
git show 78ddf27
﻿
﻿
6. 优化结果如章节[动手实验]所述使用Go benchmark记录优化前后的数据。获得结果后通过使用Go benchstat进行优化前后的性能对比。结果如下表格：
﻿
[注]ns/op:每次函数执行耗费的纳秒时间; ms/op:每次函数执行耗费的毫秒时间; MB/s:每秒处理的兆字节数据; GB/s:每秒处理的G字节数据;
﻿
上表中可以清晰的看到使用SIMD优化后，所有的用例性能都有所提升，其中数据大小为4K时性能提升率最高，耗时减少了93.49%；每秒数据处理量提升14.29倍。
﻿
如果对开源或优化技术感兴趣，欢迎下方留言或者通过https://github.com/OptimizeLab/docs/issues联系我们。
﻿