CODEWITHSUNDEEP
c#arraysperformancemonosimd
ArekBulski
ArekBulski

Reputation: 5118

SSE instruction to check if byte array is zeroes C#

Suppose I have a byte[] and want to check if all bytes are zeros. For loop is an obvious way to do it, and LINQ All() is a fancy way to do it, but highest performance is critical.

How can I use Mono.Simd to speed up checking if byte array is full of zeroes? I am looking for cutting edge approach, not merely correct solution.

Upvotes: 4

Views: 1322

Answers (2)

DragonSpit
DragonSpit

Reputation: 470

The scalar implementation processes long's, which are 64-bit (8-bytes) at a time, and gets most of it's speedup from this parallelism, which is powerful.

The SIMD/SSE above code uses 128-bit SIMD/SSE (16-byte) instructions. When using the newer 256-bit (32-byte) SSE instructions, the SIMD implementation is about 10% faster. With AVX/AVX2 instructions at 512-bits (64-byte) in the latest processors, SIMD implementation using these should be even faster.

    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);
    }

An improved version (thanks to Peter's suggestion) is shown in the above code, is safe and has been integrated into the HPCsharp nuget package, for a 20% speedup using 256-bit SSE instructions.

Upvotes: 1

ArekBulski
ArekBulski

Reputation: 5118

Best code is presented below. Other methods and time measuring are available in 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;
    }
}

Eventually it was beaten by this code:

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;
    }
}

Time measurements (on 256MB array): 

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

Conclusions:

  • Mono.Simd has only a limited set of instructions. I found no instructions for computing scalar sum(vector) or max(vector). There is however vector equality operator returning bool.
  • Loop unrolling is a powerful technique. Even fastest code benefits a lot from using it.
  • LINQ is ungodly slow because it uses delegates from lambda expressions. If you need cutting edge performance then clearly that is not the way to go.
  • All methods presented use short circuit evaluation, meaning they end as soon as they encounter non-zero.
  • SIMD code was eventually beaten. There are other questions on SO disputing whether SIMD actually makes things faster.

Posted this code on Peer Review, so far 2 bugs found and fixed.

Upvotes: 6

Related Questions