API proposal: SequenceEqual implementations for ReadOnlySequence<T>

[zlatanov]

I think it's rather unfortunate that ReadOnlySequences cannot be easily checked for value equality. The framework has such extension methods for Spans and ReadOnlySpans - SequenceEqual and the type that has Sequence in its name doesn't.

Implementing it efficiently is tricky because one needs to consider that segments may not be of the same size and even there can be empty segments that need to be ignored.

Proposed API

class MemoryExtensions
{
    static bool SequenceEqual<T>(this in ReadOnlySequence<T> x, in ReadOnlySequence<T> y);
    static bool SequenceEqual<T>(this in ReadOnlySequence<T> x, in ReadOnlySpan<T> y);
}

[scalablecory]

This seems reasonable to me, though I worry it may provide additional encouragement for people to directly use ReadOnlySequence.

[GrabYourPitchforks]

The API seems reasonable enough, but I don't understand the scenario for it. ReadOnlySequence<T> is generally used to represent a potentially large amount of data, and I can't think of many scenarios offhand where somebody would want to compare two potentially-large buffers for equality.

[zlatanov]

@GrabYourPitchforks My use case is not actually about large buffers but comes directly from the usage of SequenceReader.

Let's say you have an input that is abstracted from you using Pipelines (i.e. PipeReader). The reader part is exposed through SequenceReader over a ReadOnlySequence.

My use case is using AMQP 1.0 protocol and certain types in it which are cache-able by design, but I've done similar things for JSON payloads as well, where I need to compare property names without really needing to decode them as string.

The problem with the above example is when what you're trying to read occupies more than one segment. In the past when I've encountered such cases I usually rent memory, do copy, then release when done.

As a side note to this - almost every time I've needed to compare sequence of bytes, I've also needed a good hashing function for memory. I don't think anything like this exists as of now, am I right?

[scalablecory]

... I've done similar things for JSON payloads as well, where I need to compare property names without really needing to decode them as string ... The problem with the above example is when what you're trying to read occupies more than one segment. In the past when I've encountered such cases I usually rent memory, do copy, then release when done.

I'd generally recommend against operating directly on a ROS like this when you've got small tokens. It is typically very rare for a small token to cross a boundary and not worth it to complicate things to handle that with zero-copy -- it's really easy to actually write worse-performing code when doing so. For small tokens like JSON properties, I like to use an efficient helper method like so:

// return underlying Memory if possible. if the length crosses segments, copy to tempStorage and return that.
ReadOnlySpan<byte> ReadBytes(ref SequenceReader reader, int length, Span<byte> tempStorage);

And use it as:

SequenceReader reader = ...;
Span<byte> tempStorage = stackalloc byte[256];

ReadOnlySpan<byte> token = ReadBytes(ref reader, 10, tempStorage);

[GrabYourPitchforks]

As a side note to this - almost every time I've needed to compare sequence of bytes, I've also needed a good hashing function for memory. I don't think anything like this exists as of now, am I right?

There's the APIs in the System.Security.Cryptography namespace, but otherwise the framework doesn't provide a general-purpose hashing function over raw binary buffers. I don't think the framework would be able to choose a suitable default for collision resistance or digest size, and there would be concerns over whether the algorithm would need to be stable across framework versions. Contrast this to string.GetHashCode, which we say is good enough to be able to store string instances as keys within a Dictionary<string, ...>, but we make no hard guarantees as to the strength of the algorithm used under the covers, and we're free to change the algorithm between framework versions. (In the case of string.GetHashCode, the algorithm changes every time the process is torn down and restarted.)

[StephenCleary]

the framework doesn't provide a general-purpose hashing function over raw binary buffers.

Since this was written, hashing arbitrary binary buffers has been added in .NET 6 (HashCode). This is a "GetHashCode strength" kind of hash code, and not a strong (identity preserving) hash. For strong hashes, IncrementalHash is still the way to go