[API Proposal]: IBitwiseEquatable<T>

[stephentoub]

Background and motivation

Most of our vectorized implementations on MemoryExtensions check RuntimeHelpers.IsBitwiseEquatable to determine whether vectorization is feasible. Today, IsBitwiseEquatable is hardcoded to a finite list of primitive types; #75640 extends that further, but overriding Equals / implementing IEquatable<T> opts you out again. Developers can still get the vectorization benefits of these implementations, but it's awkward and unsafe, e.g. with a type like:

struct MyColor : IEquatable<T> { ... }

instead of:

ReadOnlySpan<MyColor> colors = ...;
MyColor value = ...;
return colors.IndexOf(value);

it's something more like:

ReadOnlySpan<MyColor> colors = ...;
MyColor value = ...;
return MemoryMarshal.Cast<MyColor, int>(colors).IndexOf(Unsafe.As<MyColor, int>(ref value));

and most importantly, it's something someone has to write code for on each use rather than it "just work"ing.

If we instead expose a way for a type to be annotated as "You can trust that my Equals override and/or IEquatable implementation are identical to bitwise equality semantics", then we can special-case IsBitwiseEquatable to recognize this annotation, and everything else just lights up.

API Proposal

namespace System;

public interface IBitwiseEquatable<T> : IEquatable<T>
{
    // no additional methods, it's just a marker interface
}

API Usage

struct MyColor : IBitwiseEquatable<MyColor>
{
    private byte R, G, B, A;

    public bool Equals(MyColor other) => R == other.R && G == other.G && B == other.B && A == other.A;

    public override bool Equals(object obj) => obj is MyColor c && Equals(c);

    public override int GetHashCode() => HashCode.Combine(R, G, B, A);
}

Alternative Designs

It could also be an attribute, e.g.

namespace System;

[AttributeUsage(AttributeTargets.Struct, Inherited = false, AllowMultiple = false)]
public sealed class BitwiseEquatableAttribute : Attribute
{
    public BitwiseEquatableAttribute() { }
}

that could then be applied to the type, e.g.

[BitwiseEquatable]
struct MyColor : IEquatable<MyColor>
{
    private byte R, G, B, A;

    public bool Equals(MyColor other) => R == other.R && G == other.G && B == other.B && A == other.A;

    public override bool Equals(object obj) => obj is MyColor c && Equals(c);

    public override int GetHashCode() => HashCode.Combine(R, G, B, A);
}

Risks

It's yet one more thing a developer implementing equality would need to think about. We'd probably want the C# compiler to emit it in some situations for records, and anything we do around #48733 should also factor it in. We might also want analyzers that try to flag types which implement IBitwiseEquality but don't integrate all fields into its Equals, don't do a simple field-by-field comparison or unsafe-cast-memcmp in their Equals, etc.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-memory
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

Most of our vectorized implementations on MemoryExtensions check RuntimeHelpers.IsBitwiseEquatable to determine whether vectorization is feasible. Today, IsBitwiseEquatable is hardcoded to a finite list of primitive types; #75640 extends that further, but overriding Equals / implementing IEquatable<T> opts you out again. Developers can still get the vectorization benefits of these implementations, but it's awkward and unsafe, e.g. with a type like:

struct MyColor : IEquatable<T> { ... }
...
instead of:
```C#
ReadOnlySpan<MyColor> colors = ...;
MyColor value = ...;
return colors.IndexOf(value);

it's something more like:

ReadOnlySpan<MyColor> colors = ...;
MyColor value = ...;
return MemoryMarshal.Cast<MyColor, int>(colors).IndexOf(Unsafe.As<MyColor, int>(ref value));

and most importantly, it's something someone has to write code for on each use rather than it "just work"ing.

If we instead expose a way for a type to be annotated as "You can trust that my Equals override and/or IEquatable implementation are identical to bitwise equality semantics", then we can special-case IsBitwiseEquatable to recognize this annotation, and everything else just lights up.

API Proposal

namespace System;

public interface IBitwiseEquatable<T> : IEquatable<T>
{
    // no additional methods, it's just a marker interface
}

API Usage

struct MyColor : IBitwiseEquatable<MyColor>
{
    private byte R, G, B, A;

    public bool Equals(MyColor other) => R == other.R && G == other.G && B == other.B && A == other.A;

    public override bool Equals(object obj) => obj is MyColor c && Equals(c);

    public override int GetHashCode() => HashCode.Combine(R, G, B, A);
}

Alternative Designs

No response

Risks

It's yet one more thing a developer implementing equality would need to think about. We'd probably want the C# compiler to emit it in some situations for records, and anything we do around #48733 should also factor it in.

Author:	stephentoub
Assignees:	-
Labels:	api-suggestion, area-System.Memory
Milestone:	8.0.0

[MichalPetryka]

The biggest issue is that bitwise equality is not just checking all fields, floating point data blocks it too but the thing that'd break it the most is padding between struct fields. With it being platform specific, it's impossible to verify it with an analyzer reliably.

I could rather see the VM being able to check it at runtime or going the other way around with the interfaces and having ISequentialEquatable that'd contain statics operating on spans of the type.

[stephentoub]

With it being platform specific, it's impossible to verify it with an analyzer reliably.

It wouldn't need to verify perfectly. It could flag provably wrong usage.

[MichalPetryka]

An attribute could force some sort of Auto layout with Pack 1 for it, although it'd be a bit awkward and wouldn't play nice with platforms that don't support unaligned loads.

[neon-sunset]

Would it be viable for this interface or attribute to indirectly but publicly expose https://github.com/dotnet/runtime/blob/main/src/coreclr/vm/comutilnative.cpp#L1642 ? So that violating CanCompareBits condition would be a compile time error and require user maybe do some additional work with analyzer hints instead while allowing for custom layout as long as it satisfies the condition?

[stephentoub]

To be clear, my intent wasn't to say "dear runtime, please always use memcmp regardless of whether it's valid", but rather "dear runtime, i'm ok if you use memcmp instead of my Equals". The latter doesn't require the runtime to use memcmp but rather just let's it, and it wouldn't if the type wasn't ammenable, just as it doesn't today in ValueType.Equals if the type's layout isn't ammenable. The analyzer I mention would be to help flag cases where they'd obviously have different semantics, e.g. Equals was only comparing one of multiple fields.

[jkotas]

Alternative Designs

Pattern-match the IL in the Equals method. No public APIs needed, just works, even for existing code.

[stephentoub]

Pattern-match the IL in the Equals method. No public APIs needed, just works, even for existing code.

That sounds fairly fragile, but if we can make it work well enough on enough cases, sure. Do we have existing examples outside of the JIT/compiler where we do that?

[jkotas]

E.g. ILLinker has quite a bit of IL pattern matching.

[stephentoub]

E.g. ILLinker has quite a bit of IL pattern matching.

Thanks, sure, I meant examples in the VM...?

[jkotas]

I do not see anything like this in the VM currently. We used to have it in the past (e.g. for CER). It is not that hard to add ad-hoc IL parser.

Or if we want to have all (fragile) optimizations under src\clr\jit, I guess we can figure out a way how to teach the JIT to do this sort of analysis.

[ericwj]

Pattern matching would be awesome. Especially for countless structs with just one field.

But how will this translate to C#? The following is still not out of the box available:

new ConsoleColor[0].AsSpan().IndexOfAnyExcept(ConsoleColor.Red)

Would it mean the type constraints where T : IEquatable<T>? on the members of MemoryExtensions should be dropped?

I found the current version of C# is actually able to distinguish between MemoryMarshal.IndexOf<T>(..) where T : IEquatable<T>? and MyEnumExtensions.IndexOf<E>(..) where E : struct, Enum which I believe was a problem before.

If MemoryExtensions.IndexOf<T> keeps its type constraint, it'd be possible to put some 600 lines of code like the following in another class and ship it:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int IndexOf<E>(this ReadOnlySpan<E> span, E other) where E : unmanaged, Enum => Unsafe.SizeOf<E>() switch {
    1 => MemoryMarshal.Cast<E, byte  >(span).IndexOf(Unsafe.As<E, byte  >(ref other)),
    2 => MemoryMarshal.Cast<E, ushort>(span).IndexOf(Unsafe.As<E, ushort>(ref other)),
    4 => MemoryMarshal.Cast<E, uint  >(span).IndexOf(Unsafe.As<E, uint  >(ref other)),
    8 => MemoryMarshal.Cast<E, ulong >(span).IndexOf(Unsafe.As<E, ulong >(ref other)),
    _ => throw new InvalidCastException()
};

Poke me if you want a copy of mine.

[stephentoub]

Would it mean the type constraints where T : IEquatable? on the members of MemoryExtensions should be dropped?

#75639 (comment)

[ericwj]

OK you're already considering that. Still, enums are a bit of a lost child imho here again. Here the JIT takes care of it and that is what IBitwiseEquatable is for, but I'm sure it'd be useful in various places as a type constraint regardless and enums fall short in these situations. Enums are great for intelligable debugging. Imho otherwise they're just numbers and it keeps annoying me that there is no way to treat them about equally as such. Requiring the switch above stinks. And at least the JIT in ilc has to ask Redhawk for help which causes them to be widened to uint iirc and that already massively reduces e.g. performance of IndexOf by a factor 2 or 4 depeding on the underlying type, plus depending on what assembly is generated dropping out of vectorization or a mere repne cmps style loop.

Is this as a larger issue on the radar anywhere? Or is it considered not possible? Is it just ECMA blocking any improvement in smarts about enums by the compiler/jit/runtime? Could they get IBitwiseEquatable and for all I care IBinaryInteger<E>?

[tannergooding]

Pattern-match the IL in the Equals method. No public APIs needed, just works, even for existing code.

@jkotas, how strongly do you feel about this approach?

Looking at marking this as ready-for-review and while some IL analysis for implicit light up via RuntimeHelpers.IsBitwiseEquatable would be nice; doing so would require it to be made public (#46017).

Notably the two approaches don't seem mutually exclusive, so we could have bother the marker interface for explicit opt-in and eventually add some VM support for implicit light up as well.

[jkotas]

If we believe that the pattern matching approach is viable, marking interface that has to be manually implement by users is unnecessary baggage. I do not think it makes sense to add this baggage as a quick fix that we will have to live with forever. We are here for the long run.

Also, the interface as proposed is not expressive enough. It does not compose using generics. For example, it is not possible to express that Vector<byte> is bitwise equatable, but Vector<float> is not. Or you cannot use it to express that ValueTuple<byte, byte> is bitwise equatable. The pattern matching approach does not have these problems.

[tannergooding]

If we believe that the pattern matching approach is viable,

We'll have many scenarios where the arbitrary IL analysis is "expensive", and potentially more expensive than any of the analysis we're doing today given it will typically require inlining and recursive analysis of each inlinee and I expect this cost will be the most prohibitive factor.

Consider for example that Equals(obj) is typically implemented as (obj is T other) && Equals(other). You then have Equals(T) that is often implemented as this == other. Record types will themselves also be implemented using Equals() recursively on each field by default.

The pattern matching will also get tripped up on some code. Consider some of the optimizations we've done in our own code to ensure things are maintainable or performant. That is, we have code that specializes per T, we have code that lights up using vectorization, etc.

Also, the interface as proposed is not expressive enough

I think we're going to hit some limitations no matter which approach we go with.

The marker-interface based approach allows opt in, but as you mentioned can't readily represent things like Vector128<T> which are only bitwise equatable if the T is bitwise equatable.

An attribute based approach is slightly more extensible. You could imagine having Vector128<[BitwiseEquatableIfBitwiseEquatable] T> (bad name, but somewhat matching how the [NotNullIfNotNull] attribute works for nullable-reference types).

You could also imagine having some well known static abstract method such that typeof(T).IsBitwiseEquatable could simply execute it and determine if the things is considered equatable or not. The common case would be constant true/false. Cases like Vector128<T> would return per T, but that is optimized in general by the JIT -- There would need to be the level of indirection since we don't have support for doing something like if (T is IBitwiseEquatable<T>) { T.Method(); } today. The JIT could still do it, however, and could be simplified if the language gets the ability to "bridge generic constraints" in the future (that is, call a more constrained API from a less constrained context after having done a relevant check).

There are many options, and none are perfect, but I expect we'll need more than just one given the complexities involved in such checks.

[jkotas]

We'll have many scenarios where the arbitrary IL analysis is "expensive"

The analysis should be significantly cheaper than JITing the Equals method and everything called by it.

I expect we'll need more than just one given the complexities involved in such checks.

I am not convinced about it. We do not need to do the optimization for 100% of the cases - we never do. It is enough to address 90+% of the cases and the IL pattern matching should be good enough for that. People should be always able use workarounds like MemoryMarshal.Cast for the complex cases that are not addressed by the runtime and when it is important to them.

[tannergooding]

The analysis should be significantly cheaper than JITing the Equals method and everything called by it.

Could you elaborate? It's certainly cheaper than jitting, but it basically requires doing the initial import of the IL and inlining of other methods to get basic control flow handled. That also involves one of the more expensive parts of inlining, which is all the token resolution.

[jkotas]

We will JIT or even inline the Equals method today and we are fine with how much it costs. I am saying that paying a fraction of this cost to perform this analysis is acceptable, it is not prohibitively expensive.

[tannergooding]

👍, if we were to do this I think it would be overall simpler to do it in the JIT where we already have the infrastructure to produce some basic blocks and do simple control flow analysis.

It may also fit into the long-standing issue/request to be able to "cache" simple heuristics about the compiled or analyzed code. Knowing if an Equals method is IBitwiseEquatable equivalent is one, tracking if a method is much cheaper than it appears such as due to large amounts of specialization or dead code elimination is another. There have been several other heuristics that have been discussed in the past as well.

One could imagine such heuristics being cached as part of crossgen as well, much as usage of Isa.IsSupported checks are for hardware intrinsics.

[MichalPetryka]

Would maybe introducing this API:

public static class RuntimeHelpers
{
    public static bool BitwiseEquals<T>(T left, T right) where T : unmanaged
}

and then pattern patching Equals to be:

public bool Equals(Guid guid) => RuntimeHelpers.BitwiseEquals(this, guid);

simplify things here? That way we wouldn't need to detect complex equals logic and the JIT would be able to emit the most efficient thing it can.