1BRC 挑战 - SIMD & Vector API
1BRC 挑战 - SIMD & Vector API
简单介绍一下 SIMD 和 vector API。
Vector API
本文提到的 Vector 不是那个存在已久的线程安全的数组类
Vector，更不是它的 API。
概念
标量 Scalar、向量 Vector
向量、矢量在编程方面的文章/书籍中基本是一个意思，只不过在某些要求比较严格的中文翻译里面，物理等一些领域内译为矢量，数学上译为向量。
这里我们对硬件相关内容进行极度抽象，不然光硬件方面的内容都不知道要写多久。
假设一个处理器(比如 cpu )有多个处理单元，而每个处理单元一次操作只能处理一个值，这个值就是标量，这里的操作可以是一元运算（对单个值进行计算）比如
i++，或者二元运算（对两个值进行计算）1+1。 三元运算（(i > 0) ? true : false;）不在本文讨论范围内。处理单元执行不同的操作需要一定的时间，为了方便衡量时间，这里用周期来作为计量单位。
SIMD
Single instruction, multiple data 的缩写。
SIMD 需要硬件支持，不过硬件细节我们这里不去说明，你姑且认为现代硬件基本上都支持但细节不同就可以了。
标量计算你可以简单的认为是处理单元从内存中加载标量数据，而 SIMD 则是在操作之前就提前把一堆数据从内存加载到寄存器中，这里的一堆数据就是向量数据，多个处理单元在相同的周期内同时对向量数据进行相同操作。
因为它有提前加载向量数据的要求，并且是从内存中取，所以后面你会看到，向量数据经常跟数组脱不开关系。
因此 SIMD 这种运算方式天然具有并行性，注意与并发进行区分，某种程度上讲这种并行性其实是不利于并发的，因为周期内这些处理单元都在忙相同的事情。
Vector API 的基础概念
Java 中定义向量的顶级类是 abstract class Vector<E>，它是所有向量子类的父类，并且是封闭在它所在的包中，这个类的类注释写的特别详细，也特别长，如果你想详细了解可以直接去看注释，会比本篇所介绍的内容详细的多。
它的 E 代表的是 byte、short、int、long、float、double 对应的装箱类型。
向量类的集成关系也很简单，以 512 位的 byte 向量为例：
Byte512Vector -> ByteVector -> AbstractVector<Byte> -> Vector<Byte>
最常用的就是对应六种类型的向量类（如 ByteVector ），他们的子类就是不同位数的实现，他们的父类（AbstractVector<Byte> 和 Vector<Byte>）则是封装在包内不允许用户访问。
Vector API 中为了定义向量，引入了三个概念，简单的说就是 Shape、Specie、Lane，我就随便翻译一下，Shape 形状，Species 种类，Lane 车道。
这三个概念的简化理解如下：
Shape 可以简单的认为就是向量的位数，这个位数通常跟平台相关。
Species = Shape + E。
Lane 就是用来装载 E 的，结合 SIMD 的概念我们就可以知道，Lane 的宽度就是 E 的 bit-size，Lane 的数量就是 Shape / Lane的宽度。
以 Byte64Vector 为例，E 是 Byte，Shape 是 64，Species 是 Shape+E，也就是 Byte64，一个 Lane 里装载一个 Byte，Java 中 Byte 占 8 位，所以 Lane 的数量为 64/8 = 8。
一个向量的车道数量就是它的 VLENGTH 属性，换句话说就是向量的长度就是它拥有多少个车道。
使用 Vector API 进行向量计算
有了上述概念，接下来我们通过一系列简单的 demo/test 来熟悉一下如何使用 ``Vector API`` 进行向量计算。
SIMDBenchmark
这个测试非常简单，就是两个数组相加。
标量计算：
@Benchmark public int[] add_Scalar(){ for (int i = 0; i < SIZE; i++){ result[i] = a[i] + b[i]; } return result; }向量计算：
@Benchmark public int[] add_Vector(){ return aVector.add(bVector).toArray(); }测试结果如下：
Benchmark Mode Cnt Score Error Units SIMDBenchmark.add_Scalar avgt 20 7.575 ± 0.149 ns/op SIMDBenchmark.add_Vector avgt 20 6.397 ± 0.087 ns/op测试中使用的数组大小均为 8，运行很快，所以单位换成了纳秒，可以看到哪怕是如此小的循环向量计算依然占优。
创建向量
来看一下创建向量这部分代码：
IntVector aVector; // ... aVector = IntVector.fromArray(Int_Vector_Species, a, 0);fromArray方法就是根据给出的数组生成向量，它接收三个参数，向量的 Species，a 就是用来生成向量的数组，0 就是从数组 a 的哪个位置开始读数据。后面俩参数没啥可说的，主要就是如何确定向量的 Species。Species = Shape + E，E 在这里就是 Integer，Shape 的值则与平台相关。
假设我们不知道如何计算/获取 Shape 的值，这时只要用 Vector API 提供的
SPECIES_PREFERRED即可。我在这个测试里使用的就是这种方式：VectorSpecies<Integer> Int_Vector_Species = IntVector.SPECIES_PREFERRED;，在我机器上这个值实际上就是 SPECIES_256。明白这三个参数后我们再来看
IntVector.fromArray(Int_Vector_Species, a, 0)这行代码，它其实就是从int[] a的a[0]开始读取数据并装入向量，而该向量的 Species 是 SPECIES_256，也就是 256(bits) / 32 （int 的 bit-size），所以这个向量最多只能装载 8 个 int 数据，其实就是把a[0]到a[7]按装入车道，一共八个车道(VLENGTH为 8)。aVector.add(bVector)就是两个向量的八个 Lane 同时相加，它的返回值依然是一个 SPECIES_256 的IntVector，这也是为什么 SIMDBenchmark 中我设置数组 size = 8 的原因，如果数组 SIZE 超过8，那多出来的数据即放不进向量中也不会参与计算。问题自然就来了，SIZE 超过 8 怎么办，或者 SIZE 不是
Vector.VLENGTH的整数倍怎么办？ 来看下面的例子。VectorMaskDemo
这个问题肯定很简单，如果是
Vector.VLENGTH的整数倍用循环就好了，如果不是，那么将整数倍的部分循环，多出来的余数部分单独进行尾处理即可，不想单独进行尾处理则可以使用VectorMask。这个测试并非 Benchmark，就是一个简单的演示 Demo，不想切回另外一个项目了所以依然放在了
./1brc-Benchmark中。 这个 demo 依然是两个数组相加，提供了以下四个方法add_multiple(); add_use_mask(); add_no_mask(); add_mask_and_tail();add_multiple就是倍数版，循环边界既可以使用IntSpecies.loopBound(a_multi_vlength.length)也可以使用a_multi_vlength.length，步长则是IntSpecies.length()，也就是 Vector 的VLENGTH。add_use_mask则是非倍数版，循环边界直接使用a.length，步长同上，有 mask 的辅助因此不需要单独进行尾部处理。add_no_mask也是非倍数版，但不使用 mask，循环边界使用IntSpecies.loopBound(a.length)，步长同上，尾部数据需要单独处理。add_mask_and_tail()是最常见的通用方案，mask + loopBound 作为边界 + 尾部处理版本。Demo 中数组的元素都是随机的生成的，结果肯定每次不一样，输出结果大致如下：
--- VLength 倍数版 --- array size : 16 222 251 217 232 146 218 200 203 210 162 128 205 182 172 229 222 --- use mask --- array size : 17 295 129 132 250 139 239 240 215 200 127 142 208 246 199 235 214 187 --- no mask --- array size : 17 295 129 132 250 139 239 240 215 200 127 142 208 246 199 235 214 187 --- mask and tail --- array size : 17 295 129 132 250 139 239 240 215 200 127 142 208 246 199 235 214 187只考虑计算结果的正确性的话，中间两种方式任选其一即可，那为什么还有一个通用版，原因看后面。
至此，向量运算入门教程就算完成了。当然向量运算肯定不仅仅是加法，其他的运算方式，或者说应用场景自行探索就好了。
Java 中那些你可能天天在用但并没有意识到的向量计算
可能对于很多人来说 SIMD 和 vector API 可能非常陌生（如果你是处理视频、音频、以及目前最火的 AI 这些当我没说），但其实你可能很早就使用或者体验过向量计算带来的性能提升，比如阅读 Arrays#equals 的源代码你会发现其中用到的 ArraysSupport#vectorizedMismatch 就是利用向量计算来比较两个数组的内容。
Arrays#equals 是否使用向量计算取决于数组长度，以 byte[] 数组为例，8 bytes 以下采用标量计算，大于等于 8 bytes 则会使用向量计算。与此同时，Arrays#equals 拥有 @IntrinsicCandidate 注解，这就意味着当这段代码运行在 HotSpot 虚拟机上时就有可能会替换为内部手写的汇编代码（or hand-written compiler IR），这意味着在 JVM 内部它甚至可能会直接调用对应的矢量指令。
还有一种比较隐蔽的方式那就是 Auto-vectorization，这个功能是由 HotSpot 虚拟机中 C2 JIT-compiler 实现的，作用方式与大部分 Java 开发人员更加熟悉的 inline 类似，简单的说它也是运行多次后才会决定是否对代码进行 Auto-vectorization 处理，也就是把标量计算的代码自动转换为向量计算，这玩意也是有开关的并且默认开启，XX:+UseSuperWord。
Auto-vectorization 基于 SuperWord 算法，该算法的论文见 Reference 2。 HotSpot 就是实现了这个算法，不过它只作用于循环内部，或者说 loop body，并且不会立刻转换，而是先运行几次循环展开(loop unrolling，见 JMH 入门，还没来得及发 -,-)，之后才决定是否转换。 关于它的具体细节和机制就不展开了，太长，感兴趣的话可以去阅读 Reference 中的博客文章：《SuperWord-Introduction》。
SuperWordDemo
VM Options:
-XX:CompileCommand=print,*SuperWordDemo.doubleIt -XX:CompileCommand=compileonly,*SuperWordDemo.doubleIt。需要提前设置 hsdis 插件（hsdis 的介绍也还没发 -，-），简单的说 hsdis 是 jdk 自带的一个插件/工具，由于法律问题他们不能提供分发，所以这个东西理论上讲你需要自己去编译（中文搜一下还是有不少下载链接的），你可以去 github 上找到 jdk 的仓库，hsdis 就在
src/utils/hsdis路径，你可以先 checkout 到你想要的 jdk 的版本，然后去该目录下编译一个对应操作系统+架构的版本，编译成功后放到指定路径下。以我的机器 macOS + intel 架构为例，我编译出的文件就是 hsdis-amd64.dylib，不同操作系统编译出的文件名和文件后缀都不一样，下载的话注意区分，然后存放路径为：
{JAVAHOME}/lib/server/，你放在{JAVAHOME}/lib/中也是可以的，它查询顺序是先去查前者，然后查后者。这里我提供了一个简单的 Demo（与 SuperWord-Introduction 中给出的 Test.java 基本一样）来观察普通的标量代码是否被 Auto-vectorization 自动向量化。与 《SuperWord-Introduction》 中不同，我们这里直接用正常 JVM 观察不了那么细，它用的参数正常 JVM 并不支持。我们这里是通过观察指定方法是否被编译为 SIMD 指令来进行判断。
如果你能看到如下类似指令，说明自动向量化被应用了：
// ... 0x000000011bbf8cb2: vmovdqu 0x10(%rbx,%rbp,4),%ymm0 0x000000011bbf8cb8: movslq %ebp,%r10 0x000000011bbf8cbb: vpslld $0x1,%ymm0,%ymm0 0x000000011bbf8cc0: vmovdqu %ymm0,0x10(%rbx,%rbp,4) 0x000000011bbf8cc6: vmovdqu 0x30(%rbx,%r10,4),%ymm0 0x000000011bbf8ccd: vpslld $0x1,%ymm0,%ymm0 0x000000011bbf8cd2: vmovdqu %ymm0,0x30(%rbx,%r10,4) // ... 0x000000011bbf8d5c: vzeroupper // ...不同机器上的指令是有可能不同的，不过你可以看有没有 v 开头的指令，这些基本都是 SIMD 指令，比如 vmovdqu 就是 x86 SIMD 指令，它用于在向量寄存器之间/寄存器-内存之间移动数据，可以看作是 SIMD 版的 mov。
vpslld 也是 x86 SIMD 指令之一，含义是对向量寄存器中的整数元素进行左移动，
vpslld $0x1,%ymm0,%ymm0知道含义之后哪怕你看不懂这个代码，也可以猜到这一步的意思就是向量寄存器中的数据左移一位，然后将结果保存回该寄存器中，也就是intArray[i] = intArray[i] * 2;。vzeroupper 同样是一个 x86 SIMD 指令，用来清除向量寄存器中的数据，可以避免数据泄露、保证数据隔离等等。
还可以通过
-XX:-UseSuperWord关闭自动向量化进行对比。
Benchmark：SIMDV2Benchmark
虽然 Vector API 大大简化了向量计算的编写难度，但是依然很容易出现不符合预期的结果。
以SIMDV2Benchmark 为例，依然是使用 jmh，通过 jvmArgs 禁用掉 SuperWord，然后为相同的业务逻辑分别提供标量计算方法和向量计算方法，使用循环来放大结果，并配合 sink 方法来保证循环安全。
当 SIZE = (2 << 14) | LoopBound = 10_000 时，本机测试结果如下：
Benchmark Mode Cnt Score Error Units
SIMDV2Benchmark.double_it_Scalar avgt 5 123.909 ± 1.168 ms/op
SIMDV2Benchmark.double_it_Vector avgt 5 49.284 ± 0.889 ms/op
结果看起来符合预期，但是此时我们不修改代码，只调整 SIZE 就可能得到相反的测试结果。
这里我们把 SIZE 调大 1，SIZE = (2 << 14) + 1，本机测试会出现向量比标量慢的情况：
Benchmark Mode Cnt Score Error Units
SIMDV2Benchmark.double_it_Scalar avgt 5 119.896 ± 37.094 ms/op
SIMDV2Benchmark.double_it_Vector avgt 5 133.562 ± 12.594 ms/op
观察一下原因也很简单，后者的数据非对其，虽然 mask 可以省掉尾部处理的代码，但从测试结果看性能损失可有点大。
加入两种带尾部处理的版本后的测试结果如下：
Benchmark Mode Cnt Score Error Units
SIMDV2Benchmark.double_it_Scalar avgt 5 127.614 ± 2.093 ms/op
SIMDV2Benchmark.double_it_Vector avgt 5 133.873 ± 18.476 ms/op
SIMDV2Benchmark.double_it_Vector_Tail avgt 5 47.149 ± 1.386 ms/op
SIMDV2Benchmark.double_it_Vector_no_mask_tail avgt 5 43.347 ± 4.271 ms/op
其中 SIMDV2Benchmark.double_it_Vector_Tail 就是通用版本，它后面那个是不使用 mask 的尾处理版本。
相信读者从这个简单的例子中也能感受到，即便是 Vector API 简化了向量运算代码的编写难度，还是很容易写错的。