Comparing two byte arrays in .NET

Question

How can I do this fast?

Sure I can do this:

static bool ByteArrayCompare(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;
}

But I'm looking for either a BCL function or some highly optimized proven way to do this.

java.util.Arrays.equals((sbyte[])(Array)a1, (sbyte[])(Array)a2);

works nicely, but it doesn't look like that would work for x64.

Note my super-fast answer here.

Solution 1

User gil suggested unsafe code which spawned this solution:

// Copyright (c) 2008-2013 Hafthor Stefansson
// Distributed under the MIT/X11 software license
// Ref: http://www.opensource.org/licenses/mit-license.php.
static unsafe bool UnsafeCompare(byte[] a1, byte[] a2) {
  if(a1==a2) return true;
  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;
  }
}

which does 64-bit based comparison for as much of the array as possible. This kind of counts on the fact that the arrays start qword aligned. It'll work if not qword aligned, just not as fast as if it were.

It performs about seven timers faster than the simple for loop. Using the J# library performed equivalently to the original for loop. Using .SequenceEqual runs around seven times slower; I think just because it is using IEnumerator.MoveNext. I imagine LINQ-based solutions being at least that slow or worse.

Solution 2

You can use Enumerable.SequenceEqual method.

using System;
using System.Linq;
...
var a1 = new int[] { 1, 2, 3};
var a2 = new int[] { 1, 2, 3};
var a3 = new int[] { 1, 2, 4};
var x = a1.SequenceEqual(a2); // true
var y = a1.SequenceEqual(a3); // false

If you can't use .NET 3.5 for some reason, your method is OK.
Compiler\run-time environment will optimize your loop so you don't need to worry about performance.

Solution 3

P/Invoke powers activate!

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

static bool ByteArrayCompare(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;
}

Solution 4

There's a new built-in solution for this in .NET 4 - IStructuralEquatable

static bool ByteArrayCompare(byte[] a1, byte[] a2) 
{
    return StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2);
}

Solution 5

Span<T> offers an extremely competitive alternative without having to throw confusing and/or non-portable fluff into your own application's code base:

// byte[] is implicitly convertible to ReadOnlySpan<byte>
static bool ByteArrayCompare(ReadOnlySpan<byte> a1, ReadOnlySpan<byte> a2)
{
    return a1.SequenceEqual(a2);
}

The (guts of the) implementation as of .NET 5.0.0 can be found here.

I've revised @EliArbel's gist to add this method as SpansEqual, drop most of the less interesting performers in others' benchmarks, run it with different array sizes, output graphs, and mark SpansEqual as the baseline so that it reports how the different methods compare to SpansEqual.

The below numbers are from the results, lightly edited to remove "Error" column.

|        Method |  ByteCount |               Mean |            StdDev | Ratio | RatioSD |
|-------------- |----------- |-------------------:|------------------:|------:|--------:|
|    SpansEqual |         15 |           4.629 ns |         0.0289 ns |  1.00 |    0.00 |
|  LongPointers |         15 |           4.598 ns |         0.0416 ns |  0.99 |    0.01 |
|      Unrolled |         15 |          18.199 ns |         0.0291 ns |  3.93 |    0.02 |
| PInvokeMemcmp |         15 |           9.872 ns |         0.0441 ns |  2.13 |    0.02 |
|               |            |                    |                   |       |         |
|    SpansEqual |       1026 |          19.965 ns |         0.0880 ns |  1.00 |    0.00 |
|  LongPointers |       1026 |          63.005 ns |         0.5217 ns |  3.16 |    0.04 |
|      Unrolled |       1026 |          38.731 ns |         0.0166 ns |  1.94 |    0.01 |
| PInvokeMemcmp |       1026 |          40.355 ns |         0.0202 ns |  2.02 |    0.01 |
|               |            |                    |                   |       |         |
|    SpansEqual |    1048585 |      43,761.339 ns |        30.8744 ns |  1.00 |    0.00 |
|  LongPointers |    1048585 |      59,585.479 ns |        17.3907 ns |  1.36 |    0.00 |
|      Unrolled |    1048585 |      54,646.243 ns |        35.7638 ns |  1.25 |    0.00 |
| PInvokeMemcmp |    1048585 |      55,198.289 ns |        23.9732 ns |  1.26 |    0.00 |
|               |            |                    |                   |       |         |
|    SpansEqual | 2147483591 | 240,607,692.857 ns | 2,733,489.4894 ns |  1.00 |    0.00 |
|  LongPointers | 2147483591 | 238,223,478.571 ns | 2,033,769.5979 ns |  0.99 |    0.02 |
|      Unrolled | 2147483591 | 236,227,340.000 ns | 2,189,627.0164 ns |  0.98 |    0.00 |
| PInvokeMemcmp | 2147483591 | 238,724,660.000 ns | 3,726,140.4720 ns |  0.99 |    0.02 |

I was surprised to see SpansEqual not come out on top for the max-array-size methods, but the difference is so minor that I don't think it'll ever matter.

My system info:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-6850K CPU 3.60GHz (Skylake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=5.0.100
  [Host]     : .NET Core 5.0.0 (CoreCLR 5.0.20.51904, CoreFX 5.0.20.51904), X64 RyuJIT
  DefaultJob : .NET Core 5.0.0 (CoreCLR 5.0.20.51904, CoreFX 5.0.20.51904), X64 RyuJIT

View more solutions