翻译 | 郑子铭
矢量化 (Vectorization)
SIMD，即单指令多数据 (Single Instruction Multiple Data)，是一种处理方式，其中一条指令同时适用于多条数据。你有一个数字列表，你想找到一个特定值的索引？你可以在列表中一次比较一个元素，这在功能上是没有问题的。但是，如果在读取和比较一个元素的相同时间内，你可以读取和比较两个元素，或四个元素，或32个元素呢？这就是SIMD，利用SIMD指令的艺术被亲切地称为 "矢量化"，其中操作同时应用于一个 "矢量 "中的所有元素。
.NET长期以来一直以Vector的形式支持矢量化，它是一种易于使用的类型，具有一流的JIT支持，使开发者能够编写矢量化的实现。Vector最大的优点之一也是它最大的缺点之一。该类型被设计为适应你的硬件中可用的任何宽度的向量指令。如果机器支持256位宽度的向量，很好，这就是Vector的目标。如果不支持，如果机器支持128位宽度的向量，很好，这就是Vector的目标。但是这种灵活性有各种缺点，至少在今天是这样；例如，你可以在Vector上执行的操作最终需要与所用向量的宽度无关，因为宽度是根据代码实际运行的硬件而变化的。这意味着可以在Vector上进行的操作是有限的，这反过来又限制了可以用它来矢量化的操作种类。另外，由于它在一个给定的进程中只有单一的大小，一些介于128位和256位之间的数据集大小可能不会像你希望的那样被处理好。你写了基于Vector的算法，并在一台支持256位向量的机器上运行，这意味着它一次可以处理32个字节，但是你给它的输入是31个字节。如果Vector映射到128位向量，它就可以用来改善对该输入的处理，但是由于它的向量大小大于输入数据的大小，实现最终会退回到没有加速的状态。还有与R2R和Native AOT有关的问题，因为超前编译需要事先知道哪些指令应该用于Vector操作。你在前面讨论DOTNET_JitDisasmSummary的输出时已经看到了这一点；我们看到NarrowUtf16ToAscii方法是 "hello, world "控制台应用程序中仅有的几个被JIT编译的方法之一，这是因为它由于使用Vector而缺乏R2R代码。
从.NET Core 3.0开始，.NET获得了数以千计的新的 "硬件本征 "方法，其中大部分是映射到这些SIMD指令之一的.NET API。这些内在因素使专家能够编写一个针对特定指令集的实现，如果做得好，可以获得最好的性能，但这也要求开发者了解每个指令集，并为每个可能相关的指令集实现他们的算法，例如，如果支持AVX2实现，或支持SSE2实现，或支持ArmBase实现，等等。
.NET 7引入了一个中间地带。以前的版本引入了Vector128和Vector256类型，但纯粹是作为数据进出硬件本征的载体，因为它们都与特定宽度的向量有关。现在在.NET 7中，通过dotnet/runtime#53450、dotnet/runtime#63414、dotnet/runtime#60094和dotnet/runtime#68559，在这些类型上也定义了大量的跨平台操作，例如Vector128.ExtractMostSignificantBits、Vector256.ConditionalSelect，等等。想要或需要超越高层Vector提供的内容的开发者可以选择针对这两种类型中的一种或多种。通常情况下，开发者会在Vector128的基础上编写一条代码路径，因为这条路径的覆盖面最广，可以从矢量化中获得大量的收益，然后如果有动力的话，可以为Vector256添加第二条路径，以便在拥有256位宽度矢量的平台上进一步增加吞吐量。把这些类型和方法看作是一个平台抽象层：你向这些方法编码，然后JIT将它们翻译成最适合底层平台的指令。考虑一下这个简单的代码作为一个例子。
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
internal class Program
{
private static void Main()
{
Vector128<byte> v = Vector128.Create((byte)123);
while (true)
{
WithIntrinsics(v);
WithVector(v);
}
}
[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();
}
我有两个函数：一个直接使用Sse2.MoveMask硬件本征，一个使用新的Vector128.ExtractMostSignificantBits方法。使用DOTNET_JitDisasm=Program.*，以下是在我的x64 Windows机器上这些优化后的一级代码的样子。
; Assembly listing for method Program:WithIntrinsics(Vector128`1):int
G_M000_IG01: ;; offset=0000H
C5F877 vzeroupper
G_M000_IG02: ;; offset=0003H
C5F91001 vmovupd xmm0, xmmword ptr [rcx]
C5F9D7C0 vpmovmskb eax, xmm0
G_M000_IG03: ;; offset=000BH
C3 ret
; Total bytes of code 12
; Assembly listing for method Program:WithVector(Vector128`1):int
G_M000_IG01: ;; offset=0000H
C5F877 vzeroupper
G_M000_IG02: ;; offset=0003H
C5F91001 vmovupd xmm0, xmmword ptr [rcx]
C5F9D7C0 vpmovmskb eax, xmm0
G_M000_IG03: ;; offset=000BH
C3 ret
; Total bytes of code 12
注意到什么了吗？这两种方法的代码是相同的，都会产生一条vpmovmskb（移动字节掩码 (Move Byte Mask)）指令。然而，前者的代码只能在支持SSE2的平台上工作，而后者的代码可以在任何支持128位向量的平台上工作，包括Arm64和WASM（以及未来任何支持SIMD的平台）；只是在这些平台上发出的指令不同。
为了进一步探讨这个问题，让我们举一个简单的例子，并将其矢量化。我们将实现一个包含方法，我们想在一个字节的范围内搜索一个特定的值，并返回是否找到它。
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对其进行矢量化？首先，我们需要检查它是否被支持，如果不被支持，则退回到我们现有的实现（Vector.IsHardwareAccelerated）。如果输入的长度小于一个向量的大小，我们也需要回退（Vector.Count）。
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;
}
现在我们知道我们有足够的数据，我们可以开始为我们的矢量循环编码了。在这个循环中，我们将搜索针，这意味着我们需要一个每个元素都包含该值的向量；Vector的构造函数提供了这一点（new Vector(need)）。而且我们需要能够一次切下一个向量宽度的数据；为了更有效率，我将使用指针。我们需要一个当前的迭代指针，我们需要迭代到我们无法形成另一个向量的地方，因为我们离终点太近了，一个直接的方法是得到一个离终点正好是一个向量宽度的指针；这样，我们就可以直接迭代到我们当前的指针等于或大于这个阈值。最后，在我们的循环体中，我们需要比较我们的当前向量和目标向量，看是否有任何元素是相同的（Vector.EqualsAny），如果有则返回真，如果没有则将我们的当前指针撞向下一个位置。在这一点上，我们有。
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);
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);
// ...
}
}
else
{
for (int i = 0; i < haystack.Length; i++)
{
if (haystack[i] == needle)
{
return true;
}
}
}
return false;
}
而我们几乎已经完成了。最后要处理的问题是，我们可能在最后还有一些元素没有搜索到。我们有几种方法可以处理这个问题。一种是继续执行我们的后退方案，并逐个处理剩余的元素。另一种方法是采用向量异步操作时常见的技巧。我们的操作没有改变任何东西，这意味着如果我们多次比较同一个元素也没有关系，这意味着我们可以只对搜索空间中的最后一个向量做最后的向量比较；这可能与我们已经看过的元素重叠，也可能不重叠，但即使重叠也不会有什么影响。就这样，我们的实现就完成了。
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);
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;
}
恭喜你，我们对这个操作进行了矢量处理，而且处理得相当好。我们可以把它扔到benchmarkdotnet中，看到非常好的速度。
private byte[] _data = Enumerable.Repeat((byte)123, 999).Append((byte)42).ToArray();
[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
方法 | 平均值 | 比率 |
Find | 484.05 ns | 1.00 |
FindVectorized | 20.21 ns | 0.04 |
24倍的提速! 呜呼，胜利，你所有的表现都属于我们！
你在你的服务中部署了这个，你看到蕲春在你的热路径上被调用，但你没有看到你所期望的改进。你再深入研究一下，你发现虽然你是用一个有1000个元素的输入数组来测试的，但典型的输入有30个元素。如果我们改变我们的基准，只有30个元素，会发生什么？这还不足以形成一个向量，所以我们又回到了一次一个的路径，而且我们根本没有得到任何速度的提升。
我们现在可以做的一件事是从使用Vector切换到Vector128。这将把阈值从32字节降低到16字节，这样，在这个范围内的输入仍然会有一定量的矢量化应用。由于这些Vector128和Vector256类型是最近设计的，它们也利用了所有很酷的新玩具，因此我们可以使用Refs而不是指针。除此之外，我们可以保持我们的实现的形状几乎相同，在我们使用Vector的地方替换Vector128，并在我们固定的跨度上使用Unsafe上的一些方法来操作我们的Refs而不是指针算术。
static unsafe bool Contains(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;
}
有了这一点，我们现在可以在我们较小的30个元素的数据集上试试。
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);
方法 | 平均值 | 比率 |
Find | 15.388 ns | 1.00 |
FindVectorized | 1.747 ns | 0.11 |
呜呼，胜利，你所有的表现都属于我们......再次！
再大的数据集上呢？之前用Vector我们有24倍的速度，但现在。
方法 | 平均值 | 比率 |
Find | 484.25 ns | 1.00 |
FindVectorized | 32.92 ns | 0.07 |
...更接近于15倍。这没什么好奇怪的，但它不是我们以前看到的24倍。如果我们想把蛋糕也吃了呢？让我们也添加一个Vector256路径。要做到这一点，我们从字面上复制/粘贴我们的Vector128代码，在复制的代码中用Vector256搜索/替换所有对Vector128的引用，然后把它放到一个额外的条件中，如果支持Vector256路径并且有足够的元素来利用它，就使用它。
static unsafe bool Contains(ReadOnlySpan<byte> haystack, byte needle)
{
if (Vector128.IsHardwareAccelerated && haystack.Length >= Vector128<byte>.Count)
{
ref byte current = ref MemoryMarshal.GetReference(haystack);
if (Vector256.IsHardwareAccelerated && haystack.Length >= Vector256<byte>.Count)
{
Vector256<byte> target = Vector256.Create(needle);
ref byte endMinusOneVector = ref Unsafe.Add(ref current, haystack.Length - Vector256<byte>.Count);
do
{
if (Vector256.EqualsAny(target, Vector256.LoadUnsafe(ref current)))
{
return true;
}
current = ref Unsafe.Add(ref current, Vector256<byte>.Count);
}
while (Unsafe.IsAddressLessThan(ref current, ref endMinusOneVector));
if (Vector256.EqualsAny(target, Vector256.LoadUnsafe(ref endMinusOneVector)))
{
return true;
}
}
else
{
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;
}
然后，轰隆一声，我们回来了。
方法 | 平均值 | 比率 |
Find | 484.53 ns | 1.00 |
FindVectorized | 20.08 ns | 0.04 |
我们现在有一个在任何具有128位或256位矢量指令的平台上矢量化的实现（x86、x64、Arm64、WASM等），它可以根据输入长度使用其中之一，如果有兴趣的话，它可以被包含在R2R图像中。
有很多因素会影响你走哪条路，我希望我们会有指导意见，以帮助驾驭所有的因素和方法。但是能力都在那里，无论你选择使用Vector、Vector128和/或Vector256，还是直接使用硬件本征，都有一些惊人的性能机会可以利用。
我已经提到了几个暴露了新的跨平台矢量支持的PR，但这只是触及了为实际启用这些操作并使其产生高质量代码所做工作的表面。作为这类工作的一个例子，有一组修改是为了帮助确保零矢量常量得到良好的处理，比如dotnet/runtime#63821将Vector128/256.Create(default) "变形"（改变）为Vector128/256.Zero，这使得后续优化只关注Zero；dotnet/runtime#65028使Vector128/256的持续传播。 Zero；dotnet/runtime#68874和dotnet/runtime#70171在JIT的中间表示中添加了矢量常量的一流知识；dotnet/runtime#62933、dotnet/runtime#65632、dotnet/runtime#55875、dotnet/runtime#67502和dotnet/runtime#64783都提高了为零矢量比较生成指令的代码质量。
内联 (Inlining)
内联是JIT可以做的最重要的优化之一。这个概念很简单：与其调用某个方法，不如从该方法中获取代码并将其烘烤到调用位置。这有一个明显的优势，就是避免了方法调用的开销，但是除了在非常热的路径上的非常小的方法，这往往是内联带来的较小的优势。更大的胜利是由于被调用者的代码被暴露给调用者的代码，反之亦然。例如，如果调用者将一个常数作为参数传递给被调用者，如果该方法没有被内联，被调用者的编译就不知道这个常数，但是如果被调用者被内联，被调用者的所有代码就知道它的参数是一个常数，并且可以对这样一个常数进行所有可能的优化，比如消除死代码、消除分支、常数折叠和传播，等等。当然，如果这一切都是彩虹和独角兽，所有可能被内联的东西都会被内联，但这显然不会发生。内联带来的代价是可能增加二进制的大小。如果被内联的代码在调用者中会产生与调用被调用者相同或更少的汇编代码（如果JIT能够快速确定这一点），那么内联就是一个没有问题的事情。但是，如果被内联的代码会不经意地增加被调用者的大小，现在JIT需要权衡代码大小的增加和可能带来的吞吐量优势。由于增加了要执行的不同指令的数量，从而给指令缓存带来了更大的压力，代码大小的增加本身就可能导致吞吐量的下降。就像任何缓存一样，你需要从内存中读取的次数越多，缓存的效果就越差。如果你有一个被内联到100个不同的调用点的函数，这些调用点的每一个被调用者的指令副本都是独一无二的，调用这100个函数中的每一个最终都会使指令缓存受到影响；相反，如果这100个函数都通过简单地调用被调用者的单一实例来 "共享 "相同的指令，那么指令缓存可能会更有效，并导致更少的内存访问。
所有这些都说明，内联真的很重要，重要的是 "正确 "的东西被内联，而且不能过度内联，因此，在最近的记忆中，每一个.NET版本都围绕内联进行了很好的改进。.NET 7也不例外。
围绕内联的一个真正有趣的改进是dotnet/runtime#64521，它可能是令人惊讶的。考虑一下Boolean.ToString方法；这里是它的完整实现。
public override string ToString()
{
if (!m_value) return "False";
return "True";
}
很简单，对吗？你会期望这么简单的东西能被内联。唉，在.NET 6上，这个基准。
private bool _value = true;
[Benchmark]
public int BoolStringLength() => _value.ToString().Length;
产生这个汇编代码。
; Program.BoolStringLength()
sub rsp,28
cmp [rcx],ecx
add rcx,8
call System.Boolean.ToString()
mov eax,[rax+8]
add rsp,28
ret
; Total bytes of code 23
请注意对System.Boolean.ToString()的调用。其原因是，从历史上看，JIT不能跨汇编边界内联方法，如果这些方法包含字符串字面（如Boolean.ToString实现中的 "False "和 "True"）。这一限制与字符串互译有关，而且这种内联可能会导致可见的行为差异。这些顾虑已不再有效，因此本PR删除了这一限制。因此，在.NET 7上的同一基准测试现在产生了以下结果。
; Program.BoolStringLength()
cmp byte ptr [rcx+8],0
je short M00_L01
mov rax,1DB54800D20
mov rax,[rax]
M00_L00:
mov eax,[rax+8]
ret
M00_L01:
mov rax,1DB54800D18
mov rax,[rax]
jmp short M00_L00
; Total bytes of code 38
不再调用System.Boolean.ToString()。
dotnet/runtime#61408做了两个与内联有关的修改。首先，它教会了内联程序如何更好地看到内联候选程序中正在调用的方法，特别是当分层编译被禁用或一个方法将绕过第0层时（例如在OSR存在之前或OSR被禁用时带有循环的方法）；通过了解正在调用的方法，它可以更好地理解方法的成本，例如，如果这些方法调用实际上是成本很低的硬件内含物。第二，它在更多有SIMD向量的情况下启用CSE。
dotnet/runtime#71778也影响了内联，特别是在typeof()可以传播给被调用者的情况下（例如通过方法参数）。在以前的.NET版本中，Type上的各种成员（如IsValueType）被转化为JIT的内在因素，这样JIT就可以为那些可以在编译时计算出答案的调用替换一个常量值。例如，这个。
[Benchmark]
public bool IsValueType() => IsValueType<int>();
private static bool IsValueType<T>() => typeof(T).IsValueType;
在.NET 6上的这个汇编代码的结果是
; Program.IsValueType()
mov eax,1
ret
; Total bytes of code 6
然而，稍微改变一下基准。
[Benchmark]
public bool IsValueType() => IsValueType(typeof(int));
private static bool IsValueType(Type t) => t.IsValueType;
而不再是那么简单了。
; Program.IsValueType()
sub rsp,28
mov rcx,offset MT_System.Int32
call CORINFO_HELP_TYPEHANDLE_TO_RUNTIMETYPE
mov rcx,rax
mov rax,[7FFCA47C9560]
cmp [rcx],ecx
add rsp,28
jmp rax
; Total bytes of code 38
实际上，作为内联的一部分，JIT失去了参数是一个常量的概念，并且未能传播它。这个PR修复了这个问题，因此在.NET 7上，我们现在可以得到我们所期望的。
; Program.IsValueType()
mov eax,1
ret
; Total bytes of code 6
标签：haystack,性能,current,改进,Vector,Vector128,byte,ref,NET From： https://blog.51cto.com/u_12517860/6101096