前言
矢量化是性能优化的重要技术，也是寄托硬件层面的优化技术。本篇来看下。
概括
一：矢量化支持的问题：
矢量化的System.Runtime.Intrinsics.X86.Sse2.MoveMask
函数和矢量化的Vector128.Create().ExtractMostSignificantBits()
函数返回的结果是一样的。但是前者只能在支持SSE2的128位矢量化平台上工作，而后者可以在任何支持128位矢量化平台上工作，包括Risc-V,Arm64，WASM等平台。这里以一段代码看下：
private static void Main()
{
Vector128<byte> v = Vector128.Create((byte)123);
while (true)
{
WithIntrinsics(v);
WithVector(v);
break;
}
}
[MethodImpl(MethodImplOptions.NoInlining)]
private static int WithIntrinsics(Vector128<byte> v) => Sse2.MoveMask(v);
[MethodImpl(MethodImplOptions.NoInlining)]
private static uint WithVector(Vector128<byte> v) => v.ExtractMostSignificantBits();
看下它的ASM代码：
WithIntrinsics：
G_M000_IG01: ;; offset=0000H
55 push rbp
C5F877 vzeroupper
488BEC mov rbp, rsp
48894D10 mov bword ptr [rbp+10H], rcx
G_M000_IG02: ;; offset=000BH
488B4510 mov rax, bword ptr [rbp+10H]
C5F91000 vmovupd xmm0, xmmword ptr [rax]
C5F9D7C0 vpmovmskb eax, xmm0
G_M000_IG03: ;; offset=0017H
5D pop rbp
C3 ret
WithVector
G_M000_IG01: ;; offset=0000H
55 push rbp
C5F877 vzeroupper
488BEC mov rbp, rsp
48894D10 mov bword ptr [rbp+10H], rcx
G_M000_IG02: ;; offset=000BH
488B4510 mov rax, bword ptr [rbp+10H]
C5F91000 vmovupd xmm0, xmmword ptr [rax]
C5F9D7C0 vpmovmskb eax, xmm0
G_M000_IG03: ;; offset=0017H
5D pop rbp
C3 ret
可以看到这两个函数生成的ASM几乎一模一样。
2.矢量化的一个例子
由于以上代码体现的SSE2的局限性，所以需要把一些代码矢量化，以便在任何平台上运行，这里看一个例子。
static bool Contains(ReadOnlySpan<byte> haystack, byte needle)
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
return false;
}
查找元素，找到了然后返回。怎么对这例子进行矢量化呢？首先需要判断你代码运行的硬件是否支持矢量化，可以通过Vector.IsHardwareAccelerated的返回值来判断。其次，传入的变量长度(haystack.length）必须的大于一个向量的长度(Vector
static bool Contains(ReadOnlySpan<byte> haystack, byte needle)
{
if (Vector.IsHardwareAccelerated && haystack.Length >= Vector<byte>.Count)
{
// ...
}
else
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
}
return false;
}
如果以上if的两个判断均为true的话，那么我们进入矢量化阶段。代码如下：
static unsafe bool Contains(ReadOnlySpan<byte> haystack, byte needle)
{
if (Vector.IsHardwareAccelerated && haystack.Length >= Vector<byte>.Count)//判断当前运行的硬件是否符合矢量化以及变量的长度不能小于矢量化里面一个向量的长度。
{
fixed (byte* haystackPtr = &MemoryMarshal.GetReference(haystack))//获取变量的头指针
{
Vector<byte> target = new Vector<byte>(needle);//向量化需要查找的变量needle
byte* current = haystackPtr;//变量haystack的头指针，以便于后面循环
byte* endMinusOneVector = haystackPtr + haystack.Length - Vector<byte>.Count;//头指针+变量的长度减去一个向量的长度。同头指针current开始到endMinusOneVector在这个里面遍历循环，查找需要查找的变量target也就是向量化的needle，这里为什么要进去Vector<byte>.Count因为向量是从0开始查找的。
do
{
if (Vector.EqualsAny(target, *(Vector<byte>*)current))//判断当前的指针是否与需要查找的变量相等
{
return true;//相等就返回true
}
current += Vector<byte>.Count;//不相等指针就位移到下一个向量，继续遍历循环。
}
while (current < endMinusOneVector);//这里判断是否达到循环终点。
}
}
else
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
}
return false;
}
以上代码几乎完成了90%,但是依然有点点问题。那就是最后一个向量endMinusOneVector没有被查找。所以还需要加上它的查找。最后的点如下，第一个Contains是不矢量化的，第二个Contains_Vector是矢量化之后的。
static bool Contains(ReadOnlySpan<byte> haystack, byte needle)
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
return false;
}
static unsafe bool Contains_Vector(ReadOnlySpan<byte> haystack, byte needle)
{
if (Vector.IsHardwareAccelerated && haystack.Length >= Vector<byte>.Count)
{
fixed (byte* haystackPtr = &MemoryMarshal.GetReference(haystack))
{
Vector<byte> target = new Vector<byte>(needle);
byte* current = haystackPtr;
byte* endMinusOneVector = haystackPtr + haystack.Length - Vector<byte>.Count;
do
{
if (Vector.EqualsAny(target, *(Vector<byte>*)current))
{
return true;
}
current += Vector<byte>.Count;
}
while (current < endMinusOneVector);
if (Vector.EqualsAny(target, *(Vector<byte>*)endMinusOneVector))
{
return true;
}
}
}
else
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
}
return false;
}
上面的代码几乎是完美的，测试下基准
private byte[] _data = Enumerable.Repeat((byte)123, 999).Append((byte)42).ToArray();//Enumerable.Repeat表示999个123的byte,放在数组，最后又加了一个42数值到数组
[Benchmark(Baseline = true)]
[Arguments((byte)42)]
public bool Find(byte value) => Contains(_data, value); // just the fallback path in its own method
[Benchmark]
[Arguments((byte)42)]
public bool FindVectorized(byte value) => Contains_Vectorized(_data, value); // the implementation we just wrote
| Method | value | Mean | Error | StdDev | Ratio | Code Size |
|--------------- |------ |----------:|---------:|---------:|------:|----------:|
| Find | 42 | 508.42 ns | 2.336 ns | 2.185 ns | 1.00 | 110 B |
| FindVectorized | 42 | 21.57 ns | 0.342 ns | 0.303 ns | 0.04 | 253 B |
可以看到矢量化之后的性能，进行了夸张的25倍的增长。这段代码几乎完美，但是并不完美。这里是用的1000个元素测试，如果是小于30个元素呢？有两个方法，第一个是退回到没有矢量化的代码也就是Contains函数，第二个是把Vector切换到128位来操作。代码如下，几乎没变更：
static unsafe bool Contains128(ReadOnlySpan<byte> haystack, byte needle)
{
if (Vector128.IsHardwareAccelerated && haystack.Length >= Vector128<byte>.Count)
{
ref byte current = ref MemoryMarshal.GetReference(haystack);
Vector128<byte> target = Vector128.Create(needle);
ref byte endMinusOneVector = ref Unsafe.Add(ref current, haystack.Length - Vector128<byte>.Count);
do
{
if (Vector128.EqualsAny(target, Vector128.LoadUnsafe(ref current)))
{
return true;
}
current = ref Unsafe.Add(ref current, Vector128<byte>.Count);
}
while (Unsafe.IsAddressLessThan(ref current, ref endMinusOneVector));
if (Vector128.EqualsAny(target, Vector128.LoadUnsafe(ref endMinusOneVector)))
{
return true;
}
}
else
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
}
return false;
}
来进行一个基准测试：
private byte[] _data = Enumerable.Repeat((byte)123, 29).Append((byte)42).ToArray();
[Benchmark(Baseline = true)]
[Arguments((byte)42)]
public bool Find(byte value) => Contains(_data, value);
[Benchmark]
[Arguments((byte)42)]
public bool FindVectorized(byte value) => Contains_Vectorized(_data, value);
| Method | value | Mean | Error | StdDev | Ratio | Code Size |
|--------------- |------ |----------:|----------:|----------:|------:|----------:|
| Find | 42 | 16.363 ns | 0.1833 ns | 0.1530 ns | 1.00 | 110 B |
| FindVectorized | 42 | 1.799 ns | 0.0320 ns | 0.0299 ns | 0.11 | 191 B |
同样的性能进行了16倍的提速。
结尾
作者：江湖评谈
欢迎关注公众号:jianghupt。文章首发。
