Consider optimizing `StreamsComparer` for happy path

[stevenaw]

StreamsComparer currently compares the bytes of two streams and reports on the index of the first difference. It does this by reading the streams 4096 bytes at a time into buffers and comparing the arrays byte-by-byte.

Some of the new .NET APIs allow for vectorized equality checks on Span<byte>. It may be worth investigating if there's a performance benefit to check for buffer equality via MemoryExtenions.SequenceEquals() and falling back to a byte-by-byte check to determine the failure point if the two buffers are known to be unequal.

nunit/src/NUnitFramework/framework/Constraints/Comparers/StreamsComparer.cs

Lines 57 to 64 in c9fe0e7

	for (long readByte = 0; readByte < xStream.Length; readByte += BUFFER_SIZE)
	{
	binaryReaderExpected.Read(bufferExpected, 0, BUFFER_SIZE);
	binaryReaderActual.Read(bufferActual, 0, BUFFER_SIZE);
	for (int count = 0; count < BUFFER_SIZE; ++count)
	{
	if (bufferExpected[count] != bufferActual[count])

[jnm2]

I like the idea. Like you point out, https://docs.microsoft.com/en-us/dotnet/api/system.memoryextensions.sequenceequal doesn't determine the failure point, but I wonder if there's another API that would.

It's only available in .NET Standard 2.1 and .NET Core 2.1 and newer, so we'd need to add a new build target if we aren't targeting one of those already, or we have the lower perf option of using reflection or System.Linq.Expressions. (It's tricky to invoke span-based APIs with reflection because ref structs can't be boxed.)

[stevenaw]

I can double check, but I think this API should be available as far back as .NET45 via the System.Memory nuget package.

[stevenaw]

I did some experimenting with this recently and didn't notice much difference on my computer for already-in-memory streams like MemoryStream until reaching a surprisingly large threshold (I think it was around 100M), though it's possible something like a File or Network stream could see a benefit at lower sizes

[stevenaw]

I revisited the benchmarking and it did seem to make a big difference on both net48 + net8.0. I'm not sure what the issue was last time.

// dotnet run --configuration Release -f net8.0
| Method     | Size  | Mean     | Error     | StdDev    | Ratio |
|----------- |------ |---------:|----------:|----------:|------:|
| Original   | 32768 | 8.970 us | 3.0895 us | 0.1693 us |  1.00 |
| Vectorized | 32768 | 1.478 us | 0.3135 us | 0.0172 us |  0.16 |

// dotnet run --configuration Release -f net48
| Method     | Size  | Mean      | Error     | StdDev    | Ratio |
|----------- |------ |----------:|----------:|----------:|------:|
| Original   | 32768 | 17.206 us | 0.2320 us | 0.1937 us |  1.00 |
| Vectorized | 32768 |  1.511 us | 0.0107 us | 0.0095 us |  0.09 |

Benchmark

public class StreamsComparerBenchmark
{
    private const int BUFFER_SIZE = 4096;

    [Params(4096 * 8)]
    public int Size { get; set; }

    //private string? TempFileX { get; set; }
    private Stream? XStream { get; set; }
    //private string? TempFileY { get; set; }
    private Stream? YStream { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        var buffer = new byte[BUFFER_SIZE];

        XStream = new MemoryStream(Size);
        for (var i = 0; i < Size; i += BUFFER_SIZE)
            XStream.Write(buffer, 0, BUFFER_SIZE);
        XStream.Seek(0, SeekOrigin.Begin);

        YStream = new MemoryStream(Size);
        for (var i = 0; i < Size; i += BUFFER_SIZE)
            YStream.Write(buffer, 0, BUFFER_SIZE);
        YStream.Seek(0, SeekOrigin.Begin);

        //TempFileX = Path.GetTempFileName();
        //FillFile(TempFileX, Size);
        //XStream = File.OpenRead(TempFileX);

        //TempFileY = Path.GetTempFileName();
        //FillFile(TempFileY, Size);
        //YStream = File.OpenRead(TempFileY);

        //static void FillFile(string path, int size)
        //{
        //    var buffer = new byte[BUFFER_SIZE];
        //    using var fill = File.OpenWrite(path);

        //    for (var i = 0; i < size; i += BUFFER_SIZE)
        //        fill.Write(buffer, 0, BUFFER_SIZE);
        //}
    }

    [GlobalCleanup]
    public void Cleanup()
    {
        XStream?.Dispose();
        //if (TempFileX is not null)
        //    File.Delete(TempFileX!);

        YStream?.Dispose();
        //if (TempFileY is not null)
        //    File.Delete(TempFileY!);
    }

    [Benchmark(Baseline = true)]
    public bool Original()
    {
        var equal = Equal(XStream!, YStream!, IterativeEqual, out _);
        return equal == EqualMethodResult.ComparedEqual;
    }

    [Benchmark]
    public bool Vectorized()
    {
        var equal = Equal(XStream!, YStream!, VectorizedEqual, out _);
        return equal == EqualMethodResult.ComparedEqual;
    }

    public static int IterativeEqual(byte[] bufferExpected, byte[] bufferActual)
    {
        for (int count = 0; count < BUFFER_SIZE; ++count)
        {
            if (bufferExpected[count] != bufferActual[count])
            {
                return count;
            }
        }

        return -1;
    }

    public static int VectorizedEqual(byte[] bufferExpected, byte[] bufferActual)
    {
        if (MemoryExtensions.SequenceEqual<byte>(bufferExpected, bufferActual))
            return -1;

        for (int count = 0; count < BUFFER_SIZE; ++count)
        {
            if (bufferExpected[count] != bufferActual[count])
            {
                return count;
            }
        }

        return -1;
    }

    public static EqualMethodResult Equal(Stream xStream, Stream yStream, Func<byte[], byte[], int> needleFinder, out long? failurePoint)
    {
        failurePoint = null;
        bool bothSeekable = xStream.CanSeek && yStream.CanSeek;

        if (bothSeekable && xStream.Length != yStream.Length)
            return EqualMethodResult.ComparedNotEqual;

        byte[] bufferExpected = new byte[BUFFER_SIZE];
        byte[] bufferActual = new byte[BUFFER_SIZE];

        BinaryReader binaryReaderExpected = new BinaryReader(xStream);
        BinaryReader binaryReaderActual = new BinaryReader(yStream);

        long expectedPosition = bothSeekable ? xStream.Position : default;
        long actualPosition = bothSeekable ? yStream.Position : default;

        try
        {
            if (xStream.CanSeek)
            {
                binaryReaderExpected.BaseStream.Seek(0, SeekOrigin.Begin);
            }
            if (yStream.CanSeek)
            {
                binaryReaderActual.BaseStream.Seek(0, SeekOrigin.Begin);
            }

            int readExpected = 1;
            int readActual = 1;
            long readByte = 0;

            while (readExpected > 0 && readActual > 0)
            {
                readExpected = binaryReaderExpected.Read(bufferExpected, 0, BUFFER_SIZE);
                readActual = binaryReaderActual.Read(bufferActual, 0, BUFFER_SIZE);

                var failureIdx = needleFinder(bufferExpected, bufferActual);
                if (failureIdx > -1)
                {
                    failurePoint = readByte + failureIdx;
                    return EqualMethodResult.ComparedNotEqual;
                }

                readByte += BUFFER_SIZE;
            }
        }
        finally
        {
            if (xStream.CanSeek)
            {
                xStream.Position = expectedPosition;
            }
            if (yStream.CanSeek)
            {
                yStream.Position = actualPosition;
            }
        }

        return EqualMethodResult.ComparedEqual;
    }

    public static EqualMethodResult Equal_Original(Stream xStream, Stream yStream, out long? failurePoint)
    {
        failurePoint = null;
        bool bothSeekable = xStream.CanSeek && yStream.CanSeek;

        if (bothSeekable && xStream.Length != yStream.Length)
            return EqualMethodResult.ComparedNotEqual;

        byte[] bufferExpected = new byte[BUFFER_SIZE];
        byte[] bufferActual = new byte[BUFFER_SIZE];

        BinaryReader binaryReaderExpected = new BinaryReader(xStream);
        BinaryReader binaryReaderActual = new BinaryReader(yStream);

        long expectedPosition = bothSeekable ? xStream.Position : default;
        long actualPosition = bothSeekable ? yStream.Position : default;

        try
        {
            if (xStream.CanSeek)
            {
                binaryReaderExpected.BaseStream.Seek(0, SeekOrigin.Begin);
            }
            if (yStream.CanSeek)
            {
                binaryReaderActual.BaseStream.Seek(0, SeekOrigin.Begin);
            }

            int readExpected = 1;
            int readActual = 1;
            long readByte = 0;

            while (readExpected > 0 && readActual > 0)
            {
                readExpected = binaryReaderExpected.Read(bufferExpected, 0, BUFFER_SIZE);
                readActual = binaryReaderActual.Read(bufferActual, 0, BUFFER_SIZE);

                for (int count = 0; count < BUFFER_SIZE; ++count)
                {
                    if (bufferExpected[count] != bufferActual[count])
                    {
                        failurePoint = readByte + count;
                        return EqualMethodResult.ComparedNotEqual;
                    }
                }
                readByte += BUFFER_SIZE;
            }
        }
        finally
        {
            if (xStream.CanSeek)
            {
                xStream.Position = expectedPosition;
            }
            if (yStream.CanSeek)
            {
                yStream.Position = actualPosition;
            }
        }

        return EqualMethodResult.ComparedEqual;
    }

    /// <summary>
    /// Result of the Equal comparison method.
    /// </summary>
    public enum EqualMethodResult
    {
        /// <summary>
        /// Method does not support the instances being compared.
        /// </summary>
        TypesNotSupported,

        /// <summary>
        /// Method is appropriate for the data types, but doesn't support the specified tolerance.
        /// </summary>
        ToleranceNotSupported,

        /// <summary>
        /// Method is appropriate and the items are considered equal.
        /// </summary>
        ComparedEqual,

        /// <summary>
        /// Method is appropriate and the items are considered different.
        /// </summary>
        ComparedNotEqual,

        /// <summary>
        /// Method is appropriate but the class has cyclic references.
        /// </summary>
        ComparisonPending
    }
}

[stevenaw]

I'm proposing this as a good first issue. It should be a matter of wrapping this for loop in a call to MemoryExtensions.SequenceEqual<byte>() based on the above example benchmark.

nunit/src/NUnitFramework/framework/Constraints/Comparers/StreamsComparer.cs

Line 65 in 829e304

for (int count = 0; count < BUFFER_SIZE; ++count)

We already have decent test coverage over this but it could be helpful to perhaps add a test for a large (> 4096 byte) MemoryStream as part of this too:

nunit/src/NUnitFramework/tests/Constraints/EqualConstraintTests.cs

Line 79 in 829e304

public class StreamEquality

[mithileshz]

Hi, can I give this a go?

[OsirisTerje]

@mithileshz Sure

Ensure your changes is well covered in either existing or new unit tests :-)

[OsirisTerje]

@mithileshz Nice work! Can you add the benchmark results like @stevenaw showed above ?

[mithileshz]

@OsirisTerje Of course. Here it is for .net 8:

|     Method |  Size |     Mean |     Error |    StdDev | Ratio |
|----------- |------ |---------:|----------:|----------:|------:|
|   Original | 32768 | 9.925 us | 0.1707 us | 0.1513 us |  1.00 |
| Vectorized | 32768 | 1.643 us | 0.0286 us | 0.0238 us |  0.17 |

I am not sure how to run it in .net framework 4.8, will try that tomorrow and get back! :)

Benchmark:

public class StreamsComparerBenchmark
{
    private const int BUFFER_SIZE = 4096;

    [Params(4096 * 8)]
    public int Size { get; set; }
    private Stream? XStream { get; set; }
    private Stream? YStream { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        var buffer = new byte[BUFFER_SIZE];

        XStream = new MemoryStream(Size);
        for (var i = 0; i < Size; i += BUFFER_SIZE)
            XStream.Write(buffer, 0, BUFFER_SIZE);
        XStream.Seek(0, SeekOrigin.Begin);

        YStream = new MemoryStream(Size);
        for (var i = 0; i < Size; i += BUFFER_SIZE)
            YStream.Write(buffer, 0, BUFFER_SIZE);
        YStream.Seek(0, SeekOrigin.Begin);
    }

    [GlobalCleanup]
    public void Cleanup()
    {
        XStream?.Dispose();

        YStream?.Dispose();
    }

    [Benchmark(Baseline = true)]
    public bool Original()
    {
        var equal = Equal_Original(XStream!, YStream!, out _);
        return equal == EqualMethodResult.ComparedEqual;
    }

    [Benchmark]
    public bool Vectorized()
    {
        var equal = Equal_Enhanced(XStream!, YStream!, out _);
        return equal == EqualMethodResult.ComparedEqual;
    }

    public static EqualMethodResult Equal_Original(Stream xStream, Stream yStream, out long? failurePoint)
    {
        failurePoint = null;
        bool bothSeekable = xStream.CanSeek && yStream.CanSeek;

        if (bothSeekable && xStream.Length != yStream.Length)
            return EqualMethodResult.ComparedNotEqual;

        byte[] bufferExpected = new byte[BUFFER_SIZE];
        byte[] bufferActual = new byte[BUFFER_SIZE];

        BinaryReader binaryReaderExpected = new BinaryReader(xStream);
        BinaryReader binaryReaderActual = new BinaryReader(yStream);

        long expectedPosition = bothSeekable ? xStream.Position : default;
        long actualPosition = bothSeekable ? yStream.Position : default;

        try
        {
            if (xStream.CanSeek)
            {
                binaryReaderExpected.BaseStream.Seek(0, SeekOrigin.Begin);
            }
            if (yStream.CanSeek)
            {
                binaryReaderActual.BaseStream.Seek(0, SeekOrigin.Begin);
            }

            int readExpected = 1;
            int readActual = 1;
            long readByte = 0;

            while (readExpected > 0 && readActual > 0)
            {
                readExpected = binaryReaderExpected.Read(bufferExpected, 0, BUFFER_SIZE);
                readActual = binaryReaderActual.Read(bufferActual, 0, BUFFER_SIZE);

                for (int count = 0; count < BUFFER_SIZE; ++count)
                {
                    if (bufferExpected[count] != bufferActual[count])
                    {
                        failurePoint = readByte + count;
                        return EqualMethodResult.ComparedNotEqual;
                    }
                }
                readByte += BUFFER_SIZE;
            }
        }
        finally
        {
            if (xStream.CanSeek)
            {
                xStream.Position = expectedPosition;
            }
            if (yStream.CanSeek)
            {
                yStream.Position = actualPosition;
            }
        }

        return EqualMethodResult.ComparedEqual;
    }

    public static EqualMethodResult Equal_Enhanced(Stream xStream, Stream yStream, out long? failurePoint)
    {
        failurePoint = null;
        bool bothSeekable = xStream.CanSeek && yStream.CanSeek;

        if (bothSeekable && xStream.Length != yStream.Length)
            return EqualMethodResult.ComparedNotEqual;

        byte[] bufferExpected = new byte[BUFFER_SIZE];
        byte[] bufferActual = new byte[BUFFER_SIZE];

        BinaryReader binaryReaderExpected = new BinaryReader(xStream);
        BinaryReader binaryReaderActual = new BinaryReader(yStream);

        long expectedPosition = bothSeekable ? xStream.Position : default;
        long actualPosition = bothSeekable ? yStream.Position : default;

        try
        {
            if (xStream.CanSeek)
            {
                binaryReaderExpected.BaseStream.Seek(0, SeekOrigin.Begin);
            }
            if (yStream.CanSeek)
            {
                binaryReaderActual.BaseStream.Seek(0, SeekOrigin.Begin);
            }

            int readExpected = 1;
            int readActual = 1;
            long readByte = 0;

            while (readExpected > 0 && readActual > 0)
            {
                readExpected = binaryReaderExpected.Read(bufferExpected, 0, BUFFER_SIZE);
                readActual = binaryReaderActual.Read(bufferActual, 0, BUFFER_SIZE);

                if (MemoryExtensions.SequenceEqual<byte>(bufferExpected, bufferActual))
                {
                    readByte += BUFFER_SIZE;
                    continue;
                }

                for (int count = 0; count < BUFFER_SIZE; ++count)
                {
                    if (bufferExpected[count] != bufferActual[count])
                    {
                        failurePoint = readByte + count;
                        return EqualMethodResult.ComparedNotEqual;
                    }
                }
                readByte += BUFFER_SIZE;
            }
        }
        finally
        {
            if (xStream.CanSeek)
            {
                xStream.Position = expectedPosition;
            }
            if (yStream.CanSeek)
            {
                yStream.Position = actualPosition;
            }
        }

        return EqualMethodResult.ComparedEqual;
    }

    /// <summary>
    /// Result of the Equal comparison method.
    /// </summary>
    public enum EqualMethodResult
    {
        /// <summary>
        /// Method does not support the instances being compared.
        /// </summary>
        TypesNotSupported,

        /// <summary>
        /// Method is appropriate for the data types, but doesn't support the specified tolerance.
        /// </summary>
        ToleranceNotSupported,

        /// <summary>
        /// Method is appropriate and the items are considered equal.
        /// </summary>
        ComparedEqual,

        /// <summary>
        /// Method is appropriate and the items are considered different.
        /// </summary>
        ComparedNotEqual,

        /// <summary>
        /// Method is appropriate but the class has cyclic references.
        /// </summary>
        ComparisonPending
    }
}

[OsirisTerje]

Awesome!

The code above, you could add that to the Benchmark project.

[mithileshz]

Ah I wasn't aware there is a benchmark project! I have added it there too now. Thank you!

I'm still struggling with benchmarking in .net framework as I think I might not have the correct setup for it.