7
\$\begingroup\$

My fundamental problem is how to check whether byte[] is full of zeroes. I posted a range of implementations (with timings) and one clearly beats others. In fact, it is so fast that I am having trouble believing it even works. I suggest taking a look at SO question page first. This is the winner code:

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

        while (b+15 < 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;
    }
}

Project references Mono.Simd assembly. I checked the code for following issues so far:

  • Pointer arithmetic. Adding 1 to pointer moves it 16 bytes ahead. However loop is unrolled 16 times so iteration processes 256 bytes at a time.
  • Array length is in bytes while b e are in 16 byte vectors.
  • Loop condition checks if last element b+15 is within the array. End pointer e points to just outside of array.
  • Loop processes 16 vectors so it moves pointer by 16 elements.
  • Tail is processed for up to 15 vectors, each 16 bytes, one byte at a time.

Is this code correct?

\$\endgroup\$
  • \$\begingroup\$ Your question -- "Is this code correct?" -- suggests that this is possibly broken code, which makes it off-topic. \$\endgroup\$ – BCdotWEB Oct 23 '15 at 9:07
  • 3
    \$\begingroup\$ @BCdotWEB I'm not so sure, the OP has no reason to doubt that the code works other than how fast it is. It looks like a fair amount of verification has been done. I get the feeling OP is looking to see if there are failure edge cases in their code, and is submitting in good faith that it works, which has come under the purview of code review before. \$\endgroup\$ – Nick Udell Oct 23 '15 at 13:19
  • 4
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Oct 23 '15 at 22:09
14
\$\begingroup\$

This code is broken

When unrolling you add all the Vector16b.

From github.com/mono:

[Acceleration (AccelMode.SSE2)]
public static unsafe Vector16b operator + (Vector16b va, Vector16b vb)
{
    Vector16b res = new Vector16b ();
    byte *a = &va.v0;
    byte *b = &vb.v0;
    byte *c = &res.v0;
    for (int i = 0; i < 16; ++i)
        *c++ = (byte)(*a++ + *b++);
    return res;
}

So the vectors are added index to index, and then truncated back to byte. A sequence of adds can then end up as 0, fx:

16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 = 256 

256 in binary is 0b100000000 and when you truncate that to byte you get 0b00000000.

You need to ensure that each individual Vector16b is equal to zero or use | instead of +.

\$\endgroup\$
2
\$\begingroup\$

This code does not process the entire array, because the calculation of e is horribly wrong.

Correct:

Vector16b* b = (Vector16b*)bytes;
Vector16b* e = (Vector16b*)(bytes + len - rem);
\$\endgroup\$
  • \$\begingroup\$ When adding 1 to b pointer, does it move one byte or one vector ahead? If one byte, I should correct the loop as well. \$\endgroup\$ – ArekBulski Oct 24 '15 at 0:43
  • \$\begingroup\$ @ArekBulski: It moves ahead by one vector (16 bytes). Not by one loop (16 vectors, 256 bytes), which you erroneously assumed. My calculation is byte-based, because the addition is done with bytes and not b. \$\endgroup\$ – Ben Voigt Oct 24 '15 at 0:48
  • \$\begingroup\$ @Arek: The fix should be very easy to test: Just pass in an array which is all false except for one byte at the halfway position (128*1024*1024). \$\endgroup\$ – Ben Voigt Oct 24 '15 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.