向量化 | Notes

void foo(byte[] dst, byte[] src) {
    for(int i = 0; i < dst.length - 4; i += 4) {
        dst[i] = src[i];
        dst[i+1] = src[i+1];
        dst[i+2] = src[i+2];
        dst[i+3] = src[i+3];
    }
    ...//post-loop
}

由于X86_64平台不支持内存间的直接移动，上述代码中的dst[i]=src[i]通常会被编译为两条内存访问指令：第一条指令把src[i]的值读取至寄存器中，而第二条指令则把寄存器中的值写入至dst[i]中。因此上述代码中的一个循环迭代将会执行四条内存读取指令，以及四条内存写入指令。

由于数组元素在内存中是连续的，当从src[i]的内存地址读取32位的内容时，将一并读取src[i]至src[i+3]的值。同样，当向dst[i]的内存地址处写入32位的内容时，将一并写入dst[i]至dst[i+3]的值。
通过综合这两个批量操作，可以使用一条内存读取指令以及一条内存写入指令，完成上述代码中循环体内的全部工作。如果用x[i:i+3]来指代x[i]至x[i+3]合并后的值，上述优化可以表述为如下伪代码：

void foo(byte[] dst, byte[] src) {
    for(int i = 0; i < dst.length - 4; i += 4) {
        dst[i:i+3] = src[i:i+3];
    }
    ...//post-loop
}

SIMD指令

示例中使用的是byte数组，四个数组元素并起来4个字节。如果换成int数组，或者long数组，那么四个数组元素并起来将会是16字节或32字节。

X86_64体系架构上通用寄存器的大小为64位(8个字节)，无法暂存这些超长的数据。因此，即时编译器将借助长度足够的XMM寄存器，来完成int数组与long数组的向量化读取和写入操作。(为了实现方便，byte数组的向量化读取、写入操作同样适用了XMM寄存器。)

XMM寄存器，是由SSE(Streaming SIMD Extensions)指令集所引入的。最初为128位。自从X86平台上的CPU开始支持AVX(Advanced Vector Extensions)指令集后(2011)，XMM寄存器升级为256位，并更名为YMM寄存器。原本使用XMM寄存器的指令，现将使用YMM寄存器的低128位。后续推出的AVX512指令集，将YMM寄存器升级至512位，并更名为ZMM寄存器。

SSE指令集以及之后的AVX指令集都涉及了一个重要的概念，单指令流多数据流(Single Instruction Multipe Data, SIMD)，即通过单条指令操控多组数据的计算操作。这些指令称之为SIMD指令。
SIMD指令将XMM寄存器(或YMM寄存器、ZMM寄存器)中的值看成多个整数或者浮点数组成的向量，并且批量进行计算。

128位XMM寄存器里的值可以看成16个byte值组成的向量，或者8个short值组成的向量，4个int值组成的向量，2个long值组成的向量；而SIMD指令PADDB、PADDW、PADDD以及PADDQ，将分别实现byte值、short值、int值或者long值的向量加法。

void foo(int[] a, int[] b, int[] c) {
    for(int i = 0; i < c.length; i++) {
        c[i] = a[i] + b[i]
    }
}

上述代码经过向量化优化之后，将使用PADDD指令来实现c[i:i+3] = a[i:i+3] + b[i:i+3]。原本需要c.length次加法操作的代码，现在最少只需要c.length/4次向量加法即可完成。因此SIMD指令也被看成CPU指令级别的并行。(现实中，C2将考虑缓存行对齐等因素，导致能够应用向量化加法的仅有数组中间的部分元素。)

使用SIMD指令的HotSpot Intrinsic

SIMD指令虽然高效，但是使用起来很玛法。主要是因为不同的CPU所支持的SIMD指令可能不同。一般来说，越新的SIMD指令，它所支持的寄存器长度越大，功能越强。

为了能够尽量利用新的SIMD指令，需要提前知道程序会被运行在支持哪些指令集的CPU上，并在编译过程中选择所支持的SIMD指令中最新的哪些。或者可以在编译结果中纳入同一段代码的不同版本，每个版本使用不同的SIMD指令。在运行过程中，程序将根据CPU所支持的指令集，来选择执行哪一个版本。

JVM所执行的Java字节码是平台无关的。它首先会被解释执行，而后反复执行的部分才会被JVM即时编译为机器码。在进行即时编译的时候，JVM已经运行在目标CPU之上，可以轻易的得知其所支持的指令集。

Java字节码的平台无关性，使得Java程序无法像C++程序那样，直接使用由Intel提供的，将被替换为具体SIMD指令的intrinsic方法。

HotSpot虚拟机提供的替代方案是Java层面的intrinsic方法，这些intrinsic方法的语义要比单个SIMD指令复杂得多。在运行过程中，HotSpot虚拟机将根据当前体系架构来决定是否将对该intrinsic方法的调用替换为另一高效的实现。如果不，则使用原本的Java实现。

使用SIMD指令的HotSpot intrinsic是虚拟机开发人员根据其语义定制的，性能优越，但是开发及维护成本较高，屈指可数，这些intrinsic方法只能做到点覆盖。不少情况下，应用程序并不会用到这些intrinsic的语义，却又存在向量化优化的机会。这时需要借助即时编译器中的自动向量化(auto vectorization)。

自动向量化

即时编译器的自动向量化将针对能够展开的计数循环，进行向量化优化。

void foo(int[] a, int[] b, int[] c) {
    for(int i = 0; i < c.length; i++) {
        c[i] = a[i] + b[i];
    }
}

即时编译器能够自动将其展开优化成使用PADDD指令的向量加法。

关于计数循环的判定，参考《循环优化》。
自动向量优化的条件：

循环变量的增量应为1，即能够遍历整个数组。
循环变量不能为long类型，否则C2无法将循环识别为计数循环。
循环迭代之间最好不要有数据依赖，例如类似于a[i] = a[i-1]的语句。当循环展开之后，循环体内存在数据依赖，那么C2无法进行自动向量化。
循环体内不要有分支跳转。
不要手工进行循环展开。如果C2无法自动展开，那么它也将无法进行自动向量化。

自动向量化的条件较为苛刻。而且C2支持的整数向量化操作并不多，只有向量加法、向量减法、按位与、或、异或、批量移位、批量乘法。C2还支持向量点积的自动向量化，即两两相乘再求和，这需要多条SIMD指令才能完成，并不是十分高效。

总结

向量化优化借助的是CPU的SIMD指令，即通过单条指令控制多组数据的运算。它被称为CPU指令级别的并行。

HotSpot虚拟机运用向量化优化的方式有两种。
第一种是使用HotSpot intrinsic，在调用特定方法的时候替换为使用了SIMD指令的高效实现。Intrinsic属于点覆盖，只有当应用程序明确需要这些intrinsic的语义，才能够获得由它带来的性能提升。
第二种是依赖即时编译器进行自动向量化，在循环展开优化之后将不同迭代的运算合并为向量运算。自动向量化的触发条件较为苛刻，因此也无法覆盖大多数用例。