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

Question

假设我有一个 byte[] 并想检查所有字节是否为零。 For loop 是一种显而易见的方法，LINQ All() 是一种奇特的方法，但最高性能至关重要。

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

Answer 1

最佳代码如下。 full source 中提供了其他方法和时间测量。

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 只有一组有限的指令。我没有找到计算标量和（向量）或最大值（向量）的说明。但是有向量相等运算符返回 bool.
循环展开是一项强大的技术。即使是最快的代码也能从中获益良多。
LINQ 非常慢，因为它使用来自 lambda 表达式的委托。如果您需要尖端性能，那么显然这不是正确的选择。
所有介绍的方法都使用short circuit evaluation，这意味着它们一遇到非零就结束。
SIMD代码终于被打脸了。在 SO 上还有其他问题在争论 SIMD 是否真的让事情变得更快。

Posted this code 在同行评审中，到目前为止发现并修复了 2 个错误。

Answer 2

标量实现一次处理长整数，它是 64 位（8 字节），并从这种强大的并行性中获得大部分加速。

上面的SIMD/SSE代码使用了128位SIMD/SSE（16字节）的指令。使用较新的 256 位（32 字节）SSE 指令时，SIMD 实现速度大约快 10%。在最新的处理器中使用 512 位（64 字节）的 AVX/AVX2 指令，使用这些指令的 SIMD 实现应该更快。

    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% 的加速。

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

SSE instruction to check if byte array is zeroes C#

c#

arrays

mono

performance

simd