What’s faster than Memcmp? | richardcocks

In this post I look at improvements in .NET and using Span for performance and portability.

I was examining portability issues in a code base that I wanted to migrate from .NET framework 4.8.1 to .NET8. I discovered use of msvcrt.dll. I quickly established it is a popular stackoverflow answer for a fast way to compare byte arrays in .NET

The answer as provided, and faithfully copied into codebases, is this:

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

A big performance improvement in modern .NET is the Span type. The documentation describes it as:

Provides a type-safe and memory-safe representation of a contiguous region of arbitrary memory.

That’s not a super helpful description, but the summary is that it’s stack-allocated rather than heap allocated.

Span has an extension method SequenceEqual(this ReadOnlySpan span, ReadOnlySpan other), and we’ll see how it fares.

    public static bool EqualsSpan(ReadOnlySpanbyte> b1, ReadOnlySpanbyte> b2)
    {
        return b1.SequenceEqual(b2);
    }

Let’s see how it stacks up against a couple of naive implementations, a for loop and using Enumerable.SequenceEquals:

    public static bool EqualsLoop(byte[] b1, byte[] b2)
    {

        if (b1.Length != b2.Length) return false;
        for (int i = 0; i  b1.Length; i++)
        {
            if (b1[i] != b2[i]) return false;
        }

        return true;
    }

    public static bool EqualsSequenceEqual(byte[] b1, byte[] b2)
    {
        return b1.SequenceEqual(b2);
    }

We compare using two identical arrays since this is typically the worst-case for equality checking, and we’re going to benchmark on a range of array sizes: 10 bytes, 1KB, 1MB and 1GB.

    [Params(10, 1_024, 1_048_576, 1073741824)]
    public int Length { get; set; }

    byte[] first;
    byte[] second;

    [GlobalSetup]
    public void Setup()
    {
        var r = new Random(0);

        first = new byte[Length];
        second = new byte[Length];

        r.NextBytes(first);
        Array.Copy(first, second, Length);
    }

The setup is straightforward, we fill the first array with random data, and copy the data to the second array.

Results

BenchmarkDotNet v0.14.0, Windows 10 (10.0.19045.5679/22H2/2022Update)
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET SDK 10.0.100-preview.2.25164.34
  [Host]               : .NET 9.0.3 (9.0.325.11113), X64 RyuJIT AVX2
  .NET 8.0             : .NET 8.0.14 (8.0.1425.11118), X64 RyuJIT AVX2
  .NET 9.0             : .NET 9.0.3 (9.0.325.11113), X64 RyuJIT AVX2
  .NET Framework 4.8.1 : .NET Framework 4.8.1 (4.8.9290.0), X64 RyuJIT VectorSize=256

The first notable result is that for very small arrays, the overhead of calling memcmp is a waste compared to a naive loop. In .NET Framework, the loop is overall fastest for 10 element arrays. This is not unexpected, but it’s important to note; don’t try to optimise if you actually have small arrays. The loop does not scale well at all however, and that advantage has completely disappeared by just 1000 elements.

The more biggest difference is between .NET framework and .NET 8. Even the loop is notably faster in .NET 8. There is a bizarre performance regression from .NET 8 to .NET 9 for 1GB arrays, which I will investigate separately to try to confirm that result, it may have been a glitch in the benchmark, given twice the memory allocations and twice the time taken.

When we look at IEnumerable.SequenceEqual, it is 500 times faster for our 1MB array in .NET 8 than in .NET framework. In .NET8 and .NET9, IEnumerable.SequenceEqual is faster than the version of memcmp I have on my machine.

There wasn’t a significant difference between ReadOnlySpan.SequenceEqual and IEnumerable.SequenceEqual, with the difference around the margin of error.

memcmp is still a little slower than SequenceEqual across the board. It’s still very fast, much faster than naive methods, but it’s clearly no longer necessary for achieving high performance for array comparisons. When the original stackoverflow answer was written, there was nothing available in .NET that could come close to that performance, as it was before Span was added to the runtime.

A benefit of the ReadOnlySpan implementation over using IEnumerable.SequenceEqual is that we can also trust that it still perform acceptably when we target .NET Framework.

Conclusion

If you’re using .NET 8 and don’t need to run in the .NET Framework runtime, don’t write your own utility function and just use IEnumerable.SequenceEqual, it’s incredibly fast and doesn’t need any external dependencies to just work.

If you’re on .NET Framework, then bring in System.Memory and use Span.SequenceEquals instead of relying on external C libraries. Make sure any calls to IEnumerable.SequenceEquals are checked to make sure they aren’t operating on large arrays.

Other considerations

If you regularly need to compare very large arrays and they are append-only and/or are compared more often than constructed, then it may make sense to avoid the comparison entirely by using a data structure that includes and maintains an order-sensitive hash of its contents. Most negative cases can be discounted through a hash comparison before doing the more expensive array comparison. Rebuilding this hash could be expensive for arrays that shuffle or remove items however.

Source Code

The source code to generate these results is available at https://github.com/richardcocks/memcomparison/ .

Pull requests always welcome.

Keep your files stored safely and securely with the SanDisk 2TB Extreme Portable SSD. With over 69,505 ratings and an impressive 4.6 out of 5 stars, this product has been purchased over 8K+ times in the past month. At only $129.99, this Amazon’s Choice product is a must-have for secure file storage.

Help keep private content private with the included password protection featuring 256-bit AES hardware encryption. Order now for just $129.99 on Amazon!

Help Power Techcratic’s Future – Scan To Support

If Techcratic’s content and insights have helped you, consider giving back by supporting the platform with crypto. Every contribution makes a difference, whether it’s for high-quality content, server maintenance, or future updates. Techcratic is constantly evolving, and your support helps drive that progress.

As a solo operator who wears all the hats, creating content, managing the tech, and running the site, your support allows me to stay focused on delivering valuable resources. Your support keeps everything running smoothly and enables me to continue creating the content you love. I’m deeply grateful for your support, it truly means the world to me! Thank you!