Saturday, July 28, 2012

Byte Array Comparison Benchmarks

I've recently been tasked with comparing files and hashes, I've wanted to see if there's anything I can do to speed things up.


So, I've looked around for other people's implementations (to save time) and wrote a quick benchmark.


We'll start with the slowest and get to the quickest.


1. ArrayEqualCompare Taken from here.

public bool Compare(byte[] array1, byte[] array2)
{
    return (array1 as IStructuralEquatable).Equals(array2,StructuralComparisons.StructuralEqualityComparer);
}



2. SequenceEqualCompare

public bool Compare(byte[] array1, byte[] array2)
{
    return Enumerable.SequenceEqual(array1, array2);
}



3.SimpleCompare

public bool Compare(byte[] a1, byte[] a2)
{
    if (a1.Length != a2.Length)
        return false;

    for (int i = 0; i < a1.Length; i++)
        if (a1[i] != a2[i])
            return false;

    return true;
}



4. unsafeByteCompare Taken from here.

public unsafe bool Compare(byte[] a, byte[] b)
{
    if (a.Length != b.Length) return false;
    int len = a.Length;
    unsafe
    {
        fixed (byte* ap = a, bp = b)
        {
            int* aip = (int*)ap, bip = (int*)bp;
            for (; len >= 4; len -= 4)
            {
                if (*aip != *bip) return false;
                aip++;
                bip++;
            }
            byte* ap2 = (byte*)aip, bp2 = (byte*)bip;
            for (; len > 0; len--)
            {
                if (*ap2 != *bp2) return false;
                ap2++;
                bp2++;
            }
        }
    }
    return true;
}



5. unsafeIntCompare Taken from here.

public unsafe bool Compare(byte[] b1, byte[] b2)
{
    if (b1 == b2) return true;
    if (b1 == null || b2 == null) return false;
    if (b1.Length != b2.Length) return false;
    int len = b1.Length;
    fixed (byte* p1 = b1, p2 = b2)
    {
        int* i1 = (int*)p1;
        int* i2 = (int*)p2;
        while (len >= 4)
        {
            if (*i1 != *i2) return false;
            i1++;
            i2++;
            len -= 4;
        }
        byte* c1 = (byte*)i1;
        byte* c2 = (byte*)i2;
        while (len > 0)
        {
            if (*c1 != *c2) return false;
            c1++;
            c2++;
            len--;
        }
    }
    return true;
}



6. unsafeSvensonCompare Taken from here.

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public unsafe bool Compare(byte[] strA, byte[] strB)
{

    int length = strA.Length;
    if (length != strB.Length)
    {
        return false;
    }
    fixed (byte* str = strA)
    {
        byte* chPtr = str;
        fixed (byte* str2 = strB)
        {
            byte* chPtr2 = str2;
            byte* chPtr3 = chPtr;
            byte* chPtr4 = chPtr2;
            while (length >= 10)
            {
                if ((((*(((int*)chPtr3)) != *(((int*)chPtr4))) || (*(((int*)(chPtr3 + 2))) != *(((int*)(chPtr4 + 2))))) || ((*(((int*)(chPtr3 + 4))) != *(((int*)(chPtr4 + 4)))) || (*(((int*)(chPtr3 + 6))) != *(((int*)(chPtr4 + 6)))))) || (*(((int*)(chPtr3 + 8))) != *(((int*)(chPtr4 + 8)))))
                {
                    break;
                }
                chPtr3 += 10;
                chPtr4 += 10;
                length -= 10;
            }
            while (length > 0)
            {
                if (*(((int*)chPtr3)) != *(((int*)chPtr4)))
                {
                    break;
                }
                chPtr3 += 2;
                chPtr4 += 2;
                length -= 2;
            }
            return (length <= 0);
        }
    }
}



7. unsafeCompare Taken from here.

public unsafe bool Compare(byte[] a1, byte[] a2)
{
    if (a1 == null || a2 == null || a1.Length != a2.Length)
        return false;
    fixed (byte* p1 = a1, p2 = a2)
    {
        byte* x1 = p1, x2 = p2;
        int l = a1.Length;
        for (int i = 0; i < l / 8; i++, x1 += 8, x2 += 8)
            if (*((long*)x1) != *((long*)x2)) return false;
        if ((l & 4) != 0) { if (*((int*)x1) != *((int*)x2)) return false; x1 += 4; x2 += 4; }
        if ((l & 2) != 0) { if (*((short*)x1) != *((short*)x2)) return false; x1 += 2; x2 += 2; }
        if ((l & 1) != 0) if (*((byte*)x1) != *((byte*)x2)) return false;
        return true;
    }
}



8. unsafeLongCompare taken from Here.

public unsafe bool Compare(byte[] a, byte[] b)
{
    if (a.Length != b.Length) return false;
    int len = a.Length;
    unsafe
    {
        fixed (byte* ap = a, bp = b)
        {
            long* alp = (long*)ap, blp = (long*)bp;
            for (; len >= 8; len -= 8)
            {
                if (*alp != *blp) return false;
                alp++;
                blp++;
            }
            byte* ap2 = (byte*)alp, bp2 = (byte*)blp;
            for (; len > 0; len--)
            {
                if (*ap2 != *bp2) return false;
                ap2++;
                bp2++;
            }
        }
    }
    return true;
}



9. memcmpCompare Taken from here.

[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count);

public bool Compare(byte[] b1, byte[] b2)
{
    // Validate buffers are the same length.
    // This also ensures that the count does not exceed the length of either buffer.  
    return b1.Length == b2.Length && memcmp(b1, b2, b1.Length) == 0;
}



You can find the test project at
https://github.com/drorgl/ForBlog/tree/master/CompareByteArray

And the benchmarks at
http://uhurumkate.blogspot.com/p/byte-array-comparison-benchmarks.html

1 comment:

  1. Hello! I cannot find the benchmark results anywhere... ??

    ReplyDelete