为什么 C# SIMD 的性能增益对于较大的阵列比微型阵列低？
Why is performance gain of C# SIMD low with larger arrays than tiny arrays?
我一直在自己编写一个深度学习库。在矩阵运算中，获得最佳性能对我来说是一个关键。我一直在研究编程语言及其在数字运算方面的表现。一段时间后，我发现 C# SIMD 与 C++ SIMD 的性能非常相似。所以，我决定用 C# 编写库。
首先，我测试了C# SIMD（我测试了很多东西，但是这里就不写了）。我注意到使用较小的数组 时效果更好 。使用更大的数组时效率不好。我认为这很荒谬。通常情况下，当它们越大时，就效率而言，它们工作得更快。
我的问题是"Why does vectorization work slower working with bigger arrays in C#?"
我将使用 BenchmarkNet 分享基准测试（由我自己完成）。
Program.Size = 10
| Method | Mean | Error | StdDev |
|------- |----------:|----------:|----------:|
| P1 | 28.02 ns | 0.5225 ns | 0.4888 ns |
| P2 | 154.15 ns | 1.1220 ns | 0.9946 ns |
| P3 | 100.88 ns | 0.8863 ns | 0.8291 ns |
Program.Size = 10000
| Method | Mean | Error | StdDev | Median |
|------- |---------:|---------:|---------:|---------:|
| P1 | 142.0 ms | 3.065 ms | 8.989 ms | 139.5 ms |
| P2 | 170.3 ms | 3.365 ms | 5.981 ms | 170.1 ms |
| P3 | 103.3 ms | 2.400 ms | 2.245 ms | 102.8 ms |
因此，如您所见，我将大小增加了 1000 倍，这意味着将数组的大小增加了 1000000 倍。 P2 一开始用了 154 ns。在第二次测试中，花费了 170 毫秒，这是我们预期的 1000 多倍。此外，P3 正好多了 1000 倍（100ns - 100ms）但是，我想在这里说的是 P1 是矢量化循环，其性能明显低于以前 。我想知道为什么。
请注意，P3 独立于本主题。 P1 是 P2 的向量化版本。因此，我们可以说矢量化的效率就他们花费的时间而言是 P2/P1。我的代码如下：
矩阵class:
public sealed class Matrix1
{
public float[] Array;
public int D1, D2;
const int size = 110000000;
private static ArrayPool<float> sizeAwarePool = ArrayPool<float>.Create(size, 100);
public Matrix1(int d1, int d2)
{
D1 = d1;
D2 = d2;
if(D1*D2 > size)
{ throw new Exception("Size!"); }
Array = sizeAwarePool.Rent(D1 * D2);
}
bool Deleted = false;
public void Dispose()
{
sizeAwarePool.Return(Array);
Deleted = true;
}
~Matrix1()
{
if(!Deleted)
{
throw new Exception("Error!");
}
}
public float this[int x, int y]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get
{
return Array[x * D2 + y];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set
{
Array[x * D2 + y] = value;
}
}
}
计划Class：
public class Program
{
const int Size = 10000;
[Benchmark]
public void P1()
{
Matrix1 a = Program.a, b = Program.b, c = Program.c;
int sz = Vector<float>.Count;
for (int i = 0; i < Size * Size; i += sz)
{
var v1 = new Vector<float>(a.Array, i);
var v2 = new Vector<float>(b.Array, i);
var v3 = v1 + v2;
v3.CopyTo(c.Array, i);
}
}
[Benchmark]
public void P2()
{
Matrix1 a = Program.a, b = Program.b, c = Program.c;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
c[i, j] = a[i, j] + b[i, j];
}
[Benchmark]
public void P3()
{
Matrix1 a = Program.a;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
a[i, j] = i + j - j;
//could have written a.Array[i*size + j] = i + j
//but it would have made no difference in terms of performance.
//so leave it that way
}
public static Matrix1 a = new Matrix1(Size, Size);
public static Matrix1 b = new Matrix1(Size, Size);
public static Matrix1 c = new Matrix1(Size, Size);
static void Main(string[] args)
{
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
a[i, j] = i;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
b[i, j] = j;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
c[i, j] = 0;
var summary = BenchmarkRunner.Run<Program>();
a.Dispose();
b.Dispose();
c.Dispose();
}
}
我向您保证 x[i,j] 不会影响性能。与使用 x.Array[i*Size + j]
相同
这可能不是故事的全部：OP 他们使用锯齿状数组将 P1 从 140 毫秒加速到 120 毫秒。
所以在大的情况下可能有一些额外的东西阻碍了它。我会使用性能计数器来调查和检查 ld_blocks_partial.address_alias（4k 别名 -> 负载对商店的错误依赖）。 And/or 查看您从 C# 分配器获得的内存地址，也许可以查看它们是否接近但不是完全相同的相对于 4k 边界的对齐方式。
我不认为在同一组中需要 3 个热缓存行会是个问题； L1d 在任何 CPU 上都是 8 向关联的，这将给 AVX 带来 >4 倍的加速（即使用 256 位 load/store 和 ALU）。但是，如果您的所有数组相对于 4k 边界具有相同的对齐方式，那么当您访问相同的索引时，它们将在 32kiB L1d 缓存中为相同的集合设置别名。
哦，这是一个理论：锯齿状数组交错页面遍历，而不是所有 3 个流（2 src 1 dst）同时到达一个新页面并且都具有需要步行的 TLB 失误。尝试确保您的代码使用 2M 大页面而不是仅仅 4k 以减少 TLB 未命中。 （例如，在 Linux 上，您将使用 madvise(buf, size, MADV_HUGEPAGE) 系统调用。）
检查 dtlb_load_misses.miss_causes_a_walk and/or dtlb_load_misses.stlb_hit 的性能计数器事件。有 TLB 预取，因此将它们交错放置可以让 TLB 预取并行处理一个或两个，而不是同时处理所有 3 个页面。
内存带宽的大容量瓶颈，不仅仅是 ALU
SIMD 不会增加可用内存带宽，只是您可以多快地获取 缓存 的数据 in/out。它增加了您在大多数时候实际可以 使用 的内存带宽。不过，用更少的指令完成相同的工作可以帮助 OoO exec 看得更远，更快地检测到 TLB 未命中。
大型数组的加速是有限的，因为标量已经接近主内存带宽的瓶颈。您的 C[i] = A[i]+B[i] 访问模式是 STREAM sum access pattern, 一个 ALU 操作的最大内存访问。 （一维与二维索引无关紧要，您仍然只是读/写连续内存并进行纯垂直 SIMD float 添加。在 P1 情况下明确。）
使用小矩阵（10x10 = 100 float = 400 字节 * (2 sources + 1 dst) = 1.2kB），你的数据可以在 L1d 缓存中保持热度，因此缓存未命中不会成为您的 SIMD 循环的瓶颈。
如果你的 src + dst 在 L1d 缓存中很热，你可以接近于标量 AVX 的 8 倍加速，每个向量有 8 个 32 位元素，假设 Haswell 或更高版本 CPU 具有峰值负载+每个时钟周期 2x 32 字节向量加载的存储吞吐量 + 1x 32 字节向量存储。
在实践中，对于小矩阵情况，您得到了 154.15 / 28.02 = ~5.5。
实际的缓存限制显然排除了这一点，例如Intel 的优化手册列出了 Skylake 的 L1d 缓存的 ~81 字节/时钟周期典型持续加载 + 存储带宽。但是对于 GP 整数加载 + 存储，对于 32 位操作数大小，Skylake 每个周期可以维持 2 次加载 + 1 次存储，with the right loop. 所以除了 load/store uop 吞吐量之外还有某种微架构限制会减慢向下矢量 load/store 有点。
你没有说你有什么硬件，但我猜是 Intel Haswell 或更高版本。 "Only" 5.5 倍加速可能是由于每次调用仅执行 12 或 13 次循环迭代的基准开销。
（100 个元素 / 8 elem/vec = 12.5。因此，如果您未完成最后 4 个元素，则为 12，如果您因为循环条件不是 i < Size * Size - sz + 1 而过度读取 4，则为 13）
Zen 的每个时钟 2x 16 字节内存操作（最多其中一个可以是存储）会同样减慢标量和 AVX。但是，从使用 movss / addss xmm, mem / movss 的每个向量 1 个元素到一次执行 4 个元素的相同微指令，您最多仍然可以获得 4 倍的加速。在 Zen 1 上使用 256 位指令仅意味着每条指令 2 微指令，每个时钟吞吐量限制同样为 2 微指令。使用 2-uop 指令可以提高前端吞吐量，但这不是这里的瓶颈。 （假设编译器可以在 5 微指令或更少的时间内进行循环，它可以每个时钟发出 1 个迭代器，并且由于 load/store 端口上的后端瓶颈甚至不能 运行 那么快。）
这些结果在 Zen 2 上也有意义，我认为：256 位 SIMD 执行单元和我认为 load/store 端口意味着当执行 8 倍的处理量时，您可以获得高达 8 倍的加速按照说明工作。
我一直在自己编写一个深度学习库。在矩阵运算中，获得最佳性能对我来说是一个关键。我一直在研究编程语言及其在数字运算方面的表现。一段时间后，我发现 C# SIMD 与 C++ SIMD 的性能非常相似。所以，我决定用 C# 编写库。
首先，我测试了C# SIMD（我测试了很多东西，但是这里就不写了）。我注意到使用较小的数组 时效果更好 。使用更大的数组时效率不好。我认为这很荒谬。通常情况下，当它们越大时，就效率而言，它们工作得更快。
我的问题是"Why does vectorization work slower working with bigger arrays in C#?"
我将使用 BenchmarkNet 分享基准测试（由我自己完成）。
Program.Size = 10
| Method | Mean | Error | StdDev |
|------- |----------:|----------:|----------:|
| P1 | 28.02 ns | 0.5225 ns | 0.4888 ns |
| P2 | 154.15 ns | 1.1220 ns | 0.9946 ns |
| P3 | 100.88 ns | 0.8863 ns | 0.8291 ns |
Program.Size = 10000
| Method | Mean | Error | StdDev | Median |
|------- |---------:|---------:|---------:|---------:|
| P1 | 142.0 ms | 3.065 ms | 8.989 ms | 139.5 ms |
| P2 | 170.3 ms | 3.365 ms | 5.981 ms | 170.1 ms |
| P3 | 103.3 ms | 2.400 ms | 2.245 ms | 102.8 ms |
因此，如您所见，我将大小增加了 1000 倍，这意味着将数组的大小增加了 1000000 倍。 P2 一开始用了 154 ns。在第二次测试中，花费了 170 毫秒，这是我们预期的 1000 多倍。此外，P3 正好多了 1000 倍（100ns - 100ms）但是，我想在这里说的是 P1 是矢量化循环，其性能明显低于以前 。我想知道为什么。
请注意，P3 独立于本主题。 P1 是 P2 的向量化版本。因此，我们可以说矢量化的效率就他们花费的时间而言是 P2/P1。我的代码如下：
矩阵class:
public sealed class Matrix1
{
public float[] Array;
public int D1, D2;
const int size = 110000000;
private static ArrayPool<float> sizeAwarePool = ArrayPool<float>.Create(size, 100);
public Matrix1(int d1, int d2)
{
D1 = d1;
D2 = d2;
if(D1*D2 > size)
{ throw new Exception("Size!"); }
Array = sizeAwarePool.Rent(D1 * D2);
}
bool Deleted = false;
public void Dispose()
{
sizeAwarePool.Return(Array);
Deleted = true;
}
~Matrix1()
{
if(!Deleted)
{
throw new Exception("Error!");
}
}
public float this[int x, int y]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get
{
return Array[x * D2 + y];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set
{
Array[x * D2 + y] = value;
}
}
}
计划Class：
public class Program
{
const int Size = 10000;
[Benchmark]
public void P1()
{
Matrix1 a = Program.a, b = Program.b, c = Program.c;
int sz = Vector<float>.Count;
for (int i = 0; i < Size * Size; i += sz)
{
var v1 = new Vector<float>(a.Array, i);
var v2 = new Vector<float>(b.Array, i);
var v3 = v1 + v2;
v3.CopyTo(c.Array, i);
}
}
[Benchmark]
public void P2()
{
Matrix1 a = Program.a, b = Program.b, c = Program.c;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
c[i, j] = a[i, j] + b[i, j];
}
[Benchmark]
public void P3()
{
Matrix1 a = Program.a;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
a[i, j] = i + j - j;
//could have written a.Array[i*size + j] = i + j
//but it would have made no difference in terms of performance.
//so leave it that way
}
public static Matrix1 a = new Matrix1(Size, Size);
public static Matrix1 b = new Matrix1(Size, Size);
public static Matrix1 c = new Matrix1(Size, Size);
static void Main(string[] args)
{
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
a[i, j] = i;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
b[i, j] = j;
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
c[i, j] = 0;
var summary = BenchmarkRunner.Run<Program>();
a.Dispose();
b.Dispose();
c.Dispose();
}
}
我向您保证 x[i,j] 不会影响性能。与使用 x.Array[i*Size + j]
这可能不是故事的全部：OP
所以在大的情况下可能有一些额外的东西阻碍了它。我会使用性能计数器来调查和检查 ld_blocks_partial.address_alias（4k 别名 -> 负载对商店的错误依赖）。 And/or 查看您从 C# 分配器获得的内存地址，也许可以查看它们是否接近但不是完全相同的相对于 4k 边界的对齐方式。
我不认为在同一组中需要 3 个热缓存行会是个问题； L1d 在任何 CPU 上都是 8 向关联的，这将给 AVX 带来 >4 倍的加速（即使用 256 位 load/store 和 ALU）。但是，如果您的所有数组相对于 4k 边界具有相同的对齐方式，那么当您访问相同的索引时，它们将在 32kiB L1d 缓存中为相同的集合设置别名。
哦，这是一个理论：锯齿状数组交错页面遍历，而不是所有 3 个流（2 src 1 dst）同时到达一个新页面并且都具有需要步行的 TLB 失误。尝试确保您的代码使用 2M 大页面而不是仅仅 4k 以减少 TLB 未命中。 （例如，在 Linux 上，您将使用 madvise(buf, size, MADV_HUGEPAGE) 系统调用。）
检查 dtlb_load_misses.miss_causes_a_walk and/or dtlb_load_misses.stlb_hit 的性能计数器事件。有 TLB 预取，因此将它们交错放置可以让 TLB 预取并行处理一个或两个，而不是同时处理所有 3 个页面。
内存带宽的大容量瓶颈，不仅仅是 ALU
SIMD 不会增加可用内存带宽，只是您可以多快地获取 缓存 的数据 in/out。它增加了您在大多数时候实际可以 使用 的内存带宽。不过，用更少的指令完成相同的工作可以帮助 OoO exec 看得更远，更快地检测到 TLB 未命中。
大型数组的加速是有限的，因为标量已经接近主内存带宽的瓶颈。您的 C[i] = A[i]+B[i] 访问模式是 STREAM sum access pattern, 一个 ALU 操作的最大内存访问。 （一维与二维索引无关紧要，您仍然只是读/写连续内存并进行纯垂直 SIMD float 添加。在 P1 情况下明确。）
使用小矩阵（10x10 = 100 float = 400 字节 * (2 sources + 1 dst) = 1.2kB），你的数据可以在 L1d 缓存中保持热度，因此缓存未命中不会成为您的 SIMD 循环的瓶颈。
如果你的 src + dst 在 L1d 缓存中很热，你可以接近于标量 AVX 的 8 倍加速，每个向量有 8 个 32 位元素，假设 Haswell 或更高版本 CPU 具有峰值负载+每个时钟周期 2x 32 字节向量加载的存储吞吐量 + 1x 32 字节向量存储。
在实践中，对于小矩阵情况，您得到了 154.15 / 28.02 = ~5.5。
实际的缓存限制显然排除了这一点，例如Intel 的优化手册列出了 Skylake 的 L1d 缓存的 ~81 字节/时钟周期典型持续加载 + 存储带宽。但是对于 GP 整数加载 + 存储，对于 32 位操作数大小，Skylake 每个周期可以维持 2 次加载 + 1 次存储，with the right loop. 所以除了 load/store uop 吞吐量之外还有某种微架构限制会减慢向下矢量 load/store 有点。
你没有说你有什么硬件，但我猜是 Intel Haswell 或更高版本。 "Only" 5.5 倍加速可能是由于每次调用仅执行 12 或 13 次循环迭代的基准开销。
（100 个元素 / 8 elem/vec = 12.5。因此，如果您未完成最后 4 个元素，则为 12，如果您因为循环条件不是 i < Size * Size - sz + 1 而过度读取 4，则为 13）
Zen 的每个时钟 2x 16 字节内存操作（最多其中一个可以是存储）会同样减慢标量和 AVX。但是，从使用 movss / addss xmm, mem / movss 的每个向量 1 个元素到一次执行 4 个元素的相同微指令，您最多仍然可以获得 4 倍的加速。在 Zen 1 上使用 256 位指令仅意味着每条指令 2 微指令，每个时钟吞吐量限制同样为 2 微指令。使用 2-uop 指令可以提高前端吞吐量，但这不是这里的瓶颈。 （假设编译器可以在 5 微指令或更少的时间内进行循环，它可以每个时钟发出 1 个迭代器，并且由于 load/store 端口上的后端瓶颈甚至不能 运行 那么快。）
这些结果在 Zen 2 上也有意义，我认为：256 位 SIMD 执行单元和我认为 load/store 端口意味着当执行 8 倍的处理量时，您可以获得高达 8 倍的加速按照说明工作。