SSE指令用于检查字节数组是否为零 C#

Question

SSE指令用于检查字节数组是否为零 C#

4

假设我有一个byte[]字节数组，并且想要检查所有字节是否都是零。使用循环是一种显而易见的方法，而使用LINQ All()是一种花哨的方法，但最高性能非常关键。

如何利用Mono.Simd来加速检查字节数组是否全为零？我正在寻找尖端的方法，而不仅仅是正确的解决方案。

- ArekBulski

在对.NET应用程序进行性能测试时，您应该确保运行几次并跳过第一次，因为JIT可能会介入。如果您想谈论绝对最快的性能，那么您也应该指定硬件...使用BenchmarkDotNet来运行不同的候选项并报告结果是理想的，因为它确保以尽可能准确的方式运行候选项，并且其输出包括运行参数，如硬件，GC模式等。 - Joe Amenta

2个回答

1

标量实现处理 long 类型数据，每次处理 64 位（8 字节），并且从这种并行性中获得了大部分速度提升，这种并行性非常强大。

SIMD/SSE 代码使用 128 位 SIMD/SSE（16 字节）指令。当使用较新的 256 位（32 字节）SSE 指令时，SIMD 实现速度可以提高约 10%。在最新的处理器中，使用 AVX/AVX2 指令时，使用 SIMD 实现应该会更快，可以达到 512 位（64 字节）。

    private static bool ZeroDetectSseInner(this byte[] arrayToOr, int l, int r)
    {
        var zeroVector = new Vector<byte>(0);
        int concurrentAmount = 4;
        int sseIndexEnd = l + ((r - l + 1) / (Vector<byte>.Count * concurrentAmount)) * (Vector<byte>.Count * concurrentAmount);
        int i;
        int offset1 = Vector<byte>.Count;
        int offset2 = Vector<byte>.Count * 2;
        int offset3 = Vector<byte>.Count * 3;
        int increment = Vector<byte>.Count * concurrentAmount;
        for (i = l; i < sseIndexEnd; i += increment)
        {
            var inVector  = new Vector<byte>(arrayToOr, i          );
            inVector     |= new Vector<byte>(arrayToOr, i + offset1);
            inVector     |= new Vector<byte>(arrayToOr, i + offset2);
            inVector     |= new Vector<byte>(arrayToOr, i + offset3);
            if (!Vector.EqualsAll(inVector, zeroVector))
                return false;
        }
        byte overallOr = 0;
        for (; i <= r; i++)
            overallOr |= arrayToOr[i];
        return overallOr == 0;
    }

    public static bool ZeroValueDetectSse(this byte[] arrayToDetect)
    {
        return arrayToDetect.ZeroDetectSseInner(0, arrayToDetect.Length - 1);
    }

上面的代码展示了一个改进版本（感谢Peter的建议），它是安全的，并已集成到HPCsharp nuget包中，使用256位SSE指令可以获得20%的加速。

- DragonSpit

2

为什么你要在累加器中使用 |=，但每次迭代仍然检查累加器呢？将一两个缓存行的向量合并到一个 pcmpeqb / pmovmskb / test/ jnz 循环中进行 |= 操作是有意义的。但是，在找到前一个全为零时，您希望启动一个新的 orVector，以打破依赖链。如果按照编写的方式进行编译，则最多每个周期限制为1个向量（通过 orVector 的数据依赖性），而不是像现代 x86 可以做到的每个时钟周期 2x 16字节加载（自 K10 以来的 AMD，自 Sandybridge 以来的 Intel）。或者在 Haswell 及更高版本上每个时钟周期 2x 32字节加载。 - Peter Cordes

1

在源代码中手动展开循环的顶部，执行 orVector = new Vector<byte>(arrayToOr, i);，然后对于后续向量执行 orVector |= new Vector<byte>(arrayToOr, i+1);；... i + 2 等。在此循环的底部，测试其是否为非零。 - Peter Cordes

1

感谢您的解释 - 对我帮助很大，让它更加具体。使用256位（32字节）SSE安全C#实现的此方法使速度提高了另外10％，总共提高了20％，而以上未展开的标量实现。您能否进一步阐述此方法如何没有依赖关系，因为它将所有读取向量连接成单个orVector？我实现了单独/多个orVectors，但仅在与您的建议相比获得最小的性能提升。 - DragonSpit

1

它在单个循环迭代的主体内具有依赖关系，但在循环迭代之间打破了依赖关系。因此没有循环传递的依赖关系（除了指针增量）。这使得乱序执行可以重叠不同迭代中的工作，因为它们是独立的依赖链。（分支预测/推测执行避免等待基于加载+ALU结果的循环外条件分支的控制依赖性。即分支推测打破数据依赖关系。） - Peter Cordes

很抱歉没有发布最新版本，尤其是因为这个库是开源的。现在已经发布了最新版本。 - DragonSpit

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ArekBulski · Accepted Answer

以下是最佳代码。其他方法和时间测量可在完整源代码中找到。

static unsafe bool BySimdUnrolled (byte[] data)
{
    fixed (byte* bytes = data) {
        int len = data.Length;
        int rem = len % (16 * 16);
        Vector16b* b = (Vector16b*)bytes;
        Vector16b* e = (Vector16b*)(bytes + len - rem);
        Vector16b zero = Vector16b.Zero;

        while (b < e) {
            if ((*(b) | *(b + 1) | *(b + 2) | *(b + 3) | *(b + 4) |
                *(b + 5) | *(b + 6) | *(b + 7) | *(b + 8) |
                *(b + 9) | *(b + 10) | *(b + 11) | *(b + 12) | 
                *(b + 13) | *(b + 14) | *(b + 15)) != zero)
                return false;
            b += 16;
        }

        for (int i = 0; i < rem; i++)
            if (data [len - 1 - i] != 0)
                return false;

        return true;
    }
}

最终，这段代码战胜了它：

static unsafe bool ByFixedLongUnrolled (byte[] data)
{
    fixed (byte* bytes = data) {
        int len = data.Length;
        int rem = len % (sizeof(long) * 16);
        long* b = (long*)bytes;
        long* e = (long*)(bytes + len - rem);

        while (b < e) {
            if ((*(b) | *(b + 1) | *(b + 2) | *(b + 3) | *(b + 4) |
                *(b + 5) | *(b + 6) | *(b + 7) | *(b + 8) |
                *(b + 9) | *(b + 10) | *(b + 11) | *(b + 12) | 
                *(b + 13) | *(b + 14) | *(b + 15)) != 0)
                return false;
            b += 16;
        }

        for (int i = 0; i < rem; i++)
            if (data [len - 1 - i] != 0)
                return false;

        return true;
    }
}

时间测量（在256MB数组上）：

LINQ All(b => b == 0)                   : 6350,4185 ms
Foreach over byte[]                     : 580,4394 ms
For with byte[].Length property         : 809,7283 ms
For with Length in local variable       : 407,2158 ms
For unrolled 16 times                   : 334,8038 ms
For fixed byte*                         : 272,386 ms
For fixed byte* unrolled 16 times       : 141,2775 ms
For fixed long*                         : 52,0284 ms
For fixed long* unrolled 16 times       : 25,9794 ms
SIMD Vector16b equals Vector16b.Zero    : 56,9328 ms
SIMD Vector16b also unrolled 16 times   : 32,6358 ms

结论：

Mono.Simd只有一组有限的指令。我没有找到计算标量和（向量）或最大值（向量）的指令。但是，它有一个返回布尔值的向量相等运算符。
循环展开是一种强大的技术。即使是最快的代码也会从使用它中受益。
LINQ非常缓慢，因为它使用来自lambda表达式的委托。如果您需要尖端性能，那么这显然不是正确的选择。
所有介绍的方法都使用短路评估，意味着它们一旦遇到非零就结束。
SIMD代码最终被击败了。SO上还有其他问题争议SIMD是否真的可以加速。

在Peer Review上发布了此代码，到目前为止已发现并修复了2个错误。