Add a method consuming ReadOnlySpan<byte> to System.HashCode

[eiriktsarpalis]

Background and Motivation

Originally posted by @GrabYourPitchforks in #48410 (comment)

Undefined meaning they don't work today on all supported platforms, or meaning we won't promise they'll work in the future?

With very specific exceptions, they're explicitly not tested for this scenario today even on supported platforms, there are no guarantees about future behavior. See also #44497.

IMO a better course of action would be to add ROS<byte>-consuming APIs to System.HashCode. It could be used both by this and by a bunch of other scenarios, such as if we ever need to add randomized hash code calculation to other primitives like double.

Proposed API

namespace System
{
    public struct HashCode
    {
         public void Add(ReadOnlySpan<byte> value);
    }
}

Usage Examples

Useful in defining equality comparison for buffers, which has a few applications in libraries code. See #48410 for context.

Risks

None known.

cc @stephentoub

[GrabYourPitchforks]

Thanks! Might want to add an instance member as well so that hash codes of complex data types can be created.

[eiriktsarpalis]

Something like this you mean?

public struct HashCode
{
    public void Add(ReadOnlySpan<byte> ros);
}

[GrabYourPitchforks]

Yes. That would be required if we wanted to solve #4761 for complex key types like tuples. For instance, a collision-resistant hash code routine for ValueTuple<long, long> could be:

var hashCode = new HashCode();
hashCode.Add(in tuple.Item1); // call to internal API
hashCode.Add(in tuple.Item2); // call to internal API
return hashCode.ToHashCode();

With the following internal implementation APIs:

public struct HashCode
{
    internal void Add<T>(in T value) where T : INonPigeonholingHashCode;
}

internal interface INonPigeonholingHashCode
{
    void AddHashCodeTo(ref HashCode hashCodeCombiner);
}

public readonly struct Int64 : INonPigeonholingHashCode
{
    void INonPigeonholingHashCode.AddHashCodeTo(ref HashCode hashCodeCombiner)
    {
        // predicated on HashCode.Add(ROS<byte>) existing
        hashCodeCombiner.Add(MemoryMarshal.AsBytes(MemoryMarshal.AsReadOnlySpan(ref this, 1));
    }
}

[eiriktsarpalis]

Would it make sense to also add a generic overload that takes ReadOnlySpan<T>?

[GrabYourPitchforks]

Probably wouldn't do generic ROS<T> until there's a need for it. Then we'd need to have a whole discussion on what the appropriate behavior is: loop, try to convert to ROS<byte> if it's a bunch of integral primitives, etc.

[stephentoub]

I don't have a strong opinion, but is public static int GetHashCode(ReadOnlySpan<byte> ros); common enough that it's needed to enable a one-liner, rather than having someone write:

HashCode h = default;
h.Add(ros);
return h.ToHashCode();

? Or is the perf of that sufficiently different that it warrants a dedicated implementation?

[GrabYourPitchforks]

If there is a perf difference I imagine it'll be trivial. There's nothing stopping us from adding the one-shot later if people ask for it.

[ghost]

Tagging subscribers to this area: @eiriktsarpalis
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and Motivation

Originally posted by @GrabYourPitchforks in #48410 (comment)

Undefined meaning they don't work today on all supported platforms, or meaning we won't promise they'll work in the future?

With very specific exceptions, they're explicitly not tested for this scenario today even on supported platforms, there are no guarantees about future behavior. See also #44497.

IMO a better course of action would be to add ROS<byte>-consuming APIs to System.HashCode. It could be used both by this and by a bunch of other scenarios, such as if we ever need to add randomized hash code calculation to other primitives like double.

Proposed API

namespace System
{
    public struct HashCode
    {
         public int Add(ReadOnlySpan<byte> ros);
    }
}

Usage Examples

Useful in defining equality comparison for buffers, which has a few applications in libraries code. See #48410 for context.

Risks

None known.

cc @stephentoub

Author:	eiriktsarpalis
Assignees:	eiriktsarpalis
Labels:	api-ready-for-review, area-System.Linq, area-System.Runtime
Milestone:	-

[Sergio0694]

This would be very nice to have 😄

Related, we currently have the Microsoft.Toolkit.HighPerformance.Helper.HashCode<T>.Combine(ReadOnlySpan<T>) API as a workaround for the lack of this primitive in the BCL, supporting both managed and unmanaged types. For the former, I just run an unrolled DJB2 hash on the input span and then combine that with HashCode.Combine to make it non-deterministic, whereas for unmanaged types I have a vectorized implementation using Vector<T> (here), and combine the result with HashCode as before.
(Probably not the best possible collision-resistant solution ever as it's based on DJB2, but it's decent and it's quite fast compared to eg. a non-vectorized implementation or just doing HashCode.Combine(T) in a loop. This is especially important since this code is also internally used by StringPool to hash the input character sequences (source here), and minimizing that overhead is a priority).

If this API proposal gets approved I'd be happy to have the implementation in the HighPerformance converge to this on .NET 6 (plan to add a .NET 6 target to the package soon), and eventually just obsolete that if it becomes completely redundant with these new APIs in the BCL (depending on whether you also decide to add support for types other than byte as well).

[terrajobst]

Video

• We don't believe we'll ever need to add Add<T>(ReadOnlySpan<T> value)
• We don't want to constrain the implementation to do the same as calling Add<T>(T value) in a loop

namespace System
{
    public struct HashCode
    {
         public void Add(ReadOnlySpan<byte> value);
    }
}