💠 💰 👞 .NET / C＃中的SIMD概述 ⛰️ 👨‍🌾 🌖

快速浏览.NET Framework和.NET Core中的算法矢量化功能。本文适用于对这些技术一无所知的人。我还将说明，.NET实际上在本机开发方面并不落后于“真正的编译”语言。

我才刚刚开始学习矢量化技术。因此，如果社区成员发现明显的错误或对所描述的算法提出改进建议，我将不胜感激。

一些历史

SIMD出现在2015年的.NET Framework 4.6中。那时，添加了Matrix3x2，Matrix4x4，Plane，Quaternion，Vector2，Vector3和Vector4类型。他们允许矢量化计算。接下来是Vector <T>类型，它提供了更多的机会来对算法进行矢量化。但是，许多程序员仍然不满意，因为这些类型限制了编码人员的想法流，并且不允许在现代处理器中使用SIMD指令的全部功能。现在，在.NET Core 3.0 Preview中，我们有了System.Runtime.Intrinsics命名空间，该命名空间为指令选择提供了很大的自由度。要获得最高速度，您需要使用RyuJit并采用x64汇编或关闭Prefer 32-bit并选择AnyCPU汇编。我在Intel Core i7-6700 3.40 GHz（Skylake）CPU计算机上运行了所有基准测试。

汇总数组元素

我决定从经典任务开始，如果涉及矢量化，通常会首先执行。它涉及查找数组元素的总和。让我们编写此任务的四个实现以汇总Array的元素。

最明显的实现：

public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }

基于LINQ的实现：

 public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);

基于System.Numerics中的向量的实现：

 public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }

基于System.Runtime.Intrinsics命名空间中的代码的实现：

 public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }

我在计算机上对这4种方法进行了基准测试，并得到以下结果：

方法	ItemsCount	均值	失误	标准差	比例
天真	10	3.531 ns	0.0336 ns	0.0314纳秒	1.00
LINQ	10	76.925 ns	0.4166纳秒	0.3897 ns	21.79
向量	10	2.750纳秒	0.0210纳秒	0.0196 ns	0.78
本征	10	6.513 ns	0.0623 ns	0.0582 ns	1.84

天真	100	47.982 ns	0.3975纳秒	0.3524 ns	1.00
LINQ	100	590.414 ns	3.8808 ns	3.4402纳秒	12.31
向量	100	10.122 ns	0.0747 ns	0.0699 ns	0.21
本征	100	14.277 ns	0.0566 ns	0.0529 ns	0.30

天真	1000	569.910 ns	2.8297 ns	2.6469 ns	1.00
LINQ	1000	5,658.570 ns	31.7465 ns	29.6957 ns	9.93
向量	1000	79.598 ns	0.3498 ns	0.3272纳秒	0.14
本征	1000	66.970 ns	0.3937纳秒	0.3682纳秒	0.12

天真	10,000	5,637.571 ns	37.5050 ns	29.2814 ns	1.00
LINQ	10,000	56,498.987 ns	294.8776 ns	275.8287 ns	10.02
向量	10,000	772.900 ns	2.6802纳秒	2.5070 ns	0.14
本征	10,000	579.152 ns	2.8371 ns	2.6538 ns	0.10

天真	100,000	56,352.865 ns	230.7916 ns	215.8826 ns	1.00
LINQ	100,000	562,610.571 ns	3,775.7631 ns	3,152.9332 ns	9.98
向量	100,000	8,389.647 ns	165.9590 ns	227.1666 ns	0.15
本征	100,000	7,261.334 ns	89.6468 ns	69.9903 ns	0.13

显然，使用向量和内在函数的解决方案比明显的基于LINQ的解决方案要快得多。现在我们需要弄清楚这两种方法中发生了什么。

让我们更仔细地考虑Vectors方法：

向量

 public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }

int vectorSize =向量<int> .Count; -我们可以在向量中放置的4字节数字的数量。如果使用硬件加速，则此值显示我们可以在一个SIMD寄存器中放入多少个4字节数字。实际上，它显示了可以同时处理此类型的元素的数量。
accVector是累积函数结果的向量；
var v = new Vector <int>（array，i）; -从i索引开始，将数组中的数据加载到新的v向量中。数据的vectorSize将被完全加载；
accVector = Vector.Add（accVector，v）; -将两个向量相加。
例如，数组中有8个数字：{0、1、2、3、4、5、6、7}和vectorSize == 4。
然后在第一个循环迭代期间，accVector = {0，0，0，0}，v = {0，1，2，3}，加法后，accVector将保持：{0，0，0，0} + {0，1 ，2，3} = {0，1，2，3}。
在第二次迭代中，v = {4，5，6，7}，加法后accVector = {0，1，2，3} + {4，5，6，7} = {4，6，8，10}。
现在我们只需要获取所有向量元素的总和即可。为此，我们可以使用标量乘法乘以一个填充有一个的向量：int result = Vector.Dot（accVector，Vector <int> .One）;
然后得到：{4，6，8，10} * {1，1，1，1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28。
如有必要，那些不适合最后一个向量的数字将在末尾求和。

让我们看一下内部代码：

本征

 public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }

我们可以看到它就像Vectors，但有一个例外：

vectorSize由常量指定。这是因为此方法明确使用了与256位寄存器一起操作的Avx2指令。实际的应用程序应包括检查当前处理器是否支持Avx2。如果不是，则应调用另一个代码。看起来像这样：
```
 if (Avx2.IsSupported) { DoThingsForAvx2(); } else if (Avx.IsSupported) { DoThingsForAvx(); } ... else if (Sse2.IsSupported) { DoThingsForSse2(); } ... 
```
var accVector = Vector256 <int> .Zero; accVector声明为填充零的256位向量。
固定（int * ptr = Array）-指向数组的指针放在ptr中。
接下来是与Vectors中相同的操作：将数据加载到vector中并添加两个vector。
向量元素的求和使用以下方法：
- 在堆栈上创建一个数组：var temp = stackalloc int [vectorSize];
- 将向量加载到此数组中：Avx2.Store（temp，accVector）;
- 在循环中对数组元素求和。
接下来，汇总不适合最后一个向量的元素。

比较两个数组

我们需要比较两个字节数组。正是这一任务使我在.NET中学习SIMD。再次，让我们编写几种基准测试方法并比较两个数组：ArrayA和ArrayB。

最明显的解决方案：

 public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }

基于LINQ的解决方案：

 public bool LINQ() => ArrayA.SequenceEqual(ArrayB);

基于MemCmp功能的解决方案：

 [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;

基于System.Numerics中的向量的解决方案：

 public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }

基于内在的解决方案：

 public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } }

在计算机上运行基准测试的结果：

方法	ItemsCount	均值	失误	标准差	比例
天真	10,000	7,033.8 ns	50.636 ns	47.365 ns	1.00
LINQ	10,000	64,841.4 ns	289.157 ns	270.478 ns	9.22
向量	10,000	504.0 ns	2.406纳秒	2.251纳秒	0.07
Memcmp	10,000	368.1 ns	2.637 ns	2.466纳秒	0.05
本征	10,000	283.6 ns	1.135纳秒	1.061纳秒	0.04

天真	100,000	85,214.4 ns	903.868 ns	845.478 ns	1.00
LINQ	100,000	702,279.4 ns	2,846.609 ns	2,662.720 ns	8.24
向量	100,000	5,179.2 ns	45.337 ns	42.409 ns	0.06
Memcmp	100,000	4,510.5 ns	24.292 ns	22.723 ns	0.05
本征	100,000	2,957.0 ns	11.452 ns	10.712 ns	0.03

天真	1,000,000	844,006.1 ns	3,552.478 ns	3,322.990 ns	1.00
LINQ	1,000,000	6,483,079.3 ns	42,641.040 ns	39,886.455 ns	7.68
向量	1,000,000	54,180.1 ns	357.258 ns	334.180 ns	0.06
Memcmp	1,000,000	49,480.1 ns	515.675 ns	457.133 ns	0.06
本征	1,000,000	36,633.9 ns	680.525 ns	636.564 ns	0.04

我猜这些方法的代码很清楚，除了Intrinsics中的两行：

 var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }

在第一行中，比较两个向量的相等性，并将结果保存在areEqual向量中，如果va和vb中的对应元素相等，则将特定位置元素中的所有位都设置为1。因此，事实证明，如果字节向量va和vb相等，则areEquals中的所有元素都应等于255（11111111b）。由于Avx2.CompareEqual是_mm256_cmpeq_epi8的包装，我们可以访问Intel网站并查看此操作的伪代码：
MoveMask方法从矢量产生32位数字。向量中每32个单字节元素的高位是MoveMask结果中的位的值。伪代码在此处可用。

因此，如果va和vb中的某些字节不匹配，则areEqual中的相应字节将为0。因此，这些字节的高位也将为0。这意味着Avx2.MoveMask响应中的相应位也将为0，而areEqual将不等于equalsMask。

让我们看一个示例，假设矢量长度为8字节（以减少写入）：

令va = {100，10，20，30，100，40，50，100}，vb = {100，20，10，30，100，40，80，90}。
然后areEquals将为{255，0，0，255，255，255，0，0}。
MoveMask方法将返回10011100b，应将其与11111111b掩码进行比较。由于这些掩码不相等，因此va和vb向量也不相等。

计算元素在集合中出现的次数。

有时您需要计算集合中特定元素（例如整数）的出现次数。我们也可以加快该算法的速度。为了进行比较，让我们编写几种方法来搜索Array中的Item元素。

最明显的一个：

 public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }

使用LINQ：

 public int LINQ() => Array.Count(i => i == Item);

使用System.Numerics.Vectors中的向量：

 public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; }

使用内在函数：

 public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; }

在计算机上运行基准测试的结果：

方法	ItemsCount	均值	失误	标准差	比例
天真	10	8.844纳秒	0.0772纳秒	0.0603 ns	1.00
LINQ	10	87.456 ns	0.9496纳秒	0.8883纳秒	9.89
向量	10	3.140纳秒	0.0406纳秒	0.0380纳秒	0.36
本征	10	13.813 ns	0.0825 ns	0.0772纳秒	1.56

天真	100	107.310 ns	0.6975纳秒	0.6183 ns	1.00
LINQ	100	626.285 ns	5.7677 ns	5.3951 ns	5.83
向量	100	11.844 ns	0.2113纳秒	0.1873纳秒	0.11
本征	100	19.616纳秒	0.1018 ns	0.0903 ns	0.18

天真	1000	1,032.466 ns	6.3799 ns	5.6556 ns	1.00
LINQ	1000	6,266.605 ns	42.6585 ns	39.9028 ns	6.07
向量	1000	83.417 ns	0.5393纳秒	0.4780纳秒	0.08
本征	1000	88.358 ns	0.4921纳秒	0.4603纳秒	0.09

天真	10,000	9,942.503 ns	47.9732 ns	40.0598 ns	1.00
LINQ	10,000	62,305.598 ns	643.8775 ns	502.6972 ns	6.27
向量	10,000	914.967 ns	7.2959 ns	6.8246 ns	0.09
本征	10,000	931.698 ns	6.3444 ns	5.9346 ns	0.09

天真	100,000	94,834.804 ns	793.8585 ns	703.7349 ns	1.00
LINQ	100,000	626,620.968 ns	4,696.9221 ns	4,393.5038 ns	6.61
向量	100,000	9,000.827 ns	179.5351 ns	192.1005 ns	0.09
本征	100,000	8,690.771 ns	101.7078 ns	95.1376 ns	0.09

天真	1,000,000	959,302.249 ns	4,268.2488 ns	3,783.6914 ns	1.00
LINQ	1,000,000	6,218,681.888 ns	31,321.9277 ns	29,298.5506 ns	6.48
向量	1,000,000	99,778.488 ns	1,975.6001 ns	4,252.6877 ns	0.10
本征	1,000,000	96,449.350 ns	1,171.8067 ns	978.5116 ns	0.10

向量和本征方法在逻辑上完全重合，但在特定操作的实现上有所不同。这个想法如下：

创建掩码向量，其中每个元素中都存储有所需的编号；
在v向量中加载数组的一部分，并将其与掩码进行比较。结果，所有位将设置在areEqual的相等元素中。因为areEqual是一个整数数组，所以如果我们设置一个元素的所有位，我们将在该元素中获得-1（（int）（1111_1111_1111_1111_1111_1111_1111_1111b）== -1）;
从accVector中减去areEqual向量。然后，accVector将保存每个位置的所有v向量中item元素出现的次数（减乘以加号）。

本文的全部代码在GitHub上。

结论

我仅描述了用于计算矢量化的.NET功能的一小部分。要查看x86下.NET Core中可用的所有内部函数的完整更新列表，请转到源代码。方便的是，C＃文件中每个内在函数的摘要都在C世界中包含其名称。这有助于理解此内在函数的目的以及将现有C ++ / C算法转移到.NET的方法。 msdn上提供了System.Numerics.Vector文档。

我认为.NET比C ++具有很大的优势。由于JIT编译已在客户端计算机上进行，因此编译器可以为特定客户端处理器优化代码，从而提供最佳性能。同时，程序员可以使用一种语言和相同的技术来编写快速代码。

.NET / C＃中的SIMD概述

一些历史

汇总数组元素

比较两个数组

计算元素在集合中出现的次数。

结论

More articles: