Extend RuntimeHelpers.IsBitwiseEquatable to more types #75640

stephentoub · 2022-09-14T21:16:33Z

Today, RuntimeHelpers.IsBitwiseEquatable is hardcoded to a fixed list of types. This means that almost all of the vectorization we've done with arrays and spans is limited to just those types; developers can themselves use MemoryMarshal.Cast to convert spans of other types to spans of supported one, but it doesn't naturally happen.

This extends IsBitwiseEquatable a bit more. We already have a CanCompareBitsOrUseFastGetHashCode helper used by ValueType.Equals to determine whether structs that don't override Equals can be compared with the equivalent of memcmp. This extends that same helper to be used by IsBitwiseEquatable. However, IsBitwiseEquatable also needs to rule out types that implement IEquatable<T> (the existing helper doesn't because it's about the implementation of the object.Equals override where the interface doesn't come into play).

The upside of this is APIs like Array.IndexOf will now automatically vectorize with more types (and avoid all the boxing overhead and the like with object.Equals). The main downside is that types which provide their own equality implementation still don't benefit, which in turn means adding an IEquality<T> implementation could in the future be a deoptimization (we should consider some kind of attribute or marker interface a type can use to say "I promise my equality implementation is the same as a bitwise comparison"); plus, anyone who realizes they have a perf issue will have already added the interface implementation. We also currently constrain most of our MemoryExtensions methods to types that implement IEquatable<T>, so there are only a handful of public methods today that benefit from this.

Method	Toolchain	Mean	Ratio	Allocated	Alloc Ratio
IndexOf	\main\corerun.exe	13,711.25 ns	1.000	48000 B	1.00
IndexOf	\pr\corerun.exe	68.16 ns	0.005	-	0.00

CommonPrefixLength	\main\corerun.exe	13,005.48 ns	1.000	48000 B	1.00
CommonPrefixLength	\pr\corerun.exe	129.64 ns	0.010	-	0.00

SequenceEquals	\main\corerun.exe	13,342.51 ns	1.000	48000 B	1.00
SequenceEquals	\pr\corerun.exe	70.01 ns	0.005	-	0.00

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Linq;

[MemoryDiagnoser(displayGenColumns: false)]
[HideColumns("Job", "Error", "StdDev")]
public partial class Program
{
    static void Main(string[] args) => BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args);

    private MyColor[] _values1, _values2;

    [GlobalSetup]
    public void Setup()
    {
        _values1 = Enumerable.Range(0, 1_000).Select(i => new MyColor { R = (byte)i, G = (byte)i, B = (byte)i, A = (byte)i }).ToArray();
        _values2 = (MyColor[])_values1.Clone();
    }

    [Benchmark]
    public int IndexOf() => Array.IndexOf(_values1, new MyColor { R = 1, G = 2, B = 3, A = 4 });

    [Benchmark]
    public int CommonPrefixLength() => _values1.AsSpan().CommonPrefixLength(_values2);

    [Benchmark]
    public bool SequenceEquals() => _values1.AsSpan().SequenceEqual(_values2);
}

struct MyColor
{
    public byte R, G, B, A;
}

src/coreclr/vm/jitinterface.cpp

stephentoub · 2022-09-15T00:48:34Z

Ugh, fun:

Assert failure(PID 4956 [0x0000135c], Thread: 5712 [0x1650]): CONTRACT VIOLATION by CanCompareBitsOrUseFastGetHashCode at "D:\a\_work\1\s\src\coreclr\vm\comutilnative.cpp" @ 1649

MODE_COOPERATIVE encountered while thread is in preemptive state.

                        CONTRACT in CanCompareBitsOrUseFastGetHashCode at "D:\a\_work\1\s\src\coreclr\vm\comutilnative.cpp" @ 1649
VIOLATED-->  CONTRACT in getILIntrinsicImplementationForRuntimeHelpers at "D:\a\_work\1\s\src\coreclr\vm\jitinterface.cpp" @ 7169
                        CONTRACT in getMethodInfoHelper at "D:\a\_work\1\s\src\coreclr\vm\jitinterface.cpp" @ 7435
                        CONTRACT in UnsafeJitFunction at "D:\a\_work\1\s\src\coreclr\vm\jitinterface.cpp" @ 12716
                        CONTRACT in MethodDesc::JitCompileCodeLocked at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 935
                        CONTRACT in MethodDesc::JitCompileCodeLockedEventWrapper at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 770
                        CONTRACT in MethodDesc::JitCompileCode at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 650
                        CONTRACT in MethodDesc::PrepareILBasedCode at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 348
                        CONTRACT in MethodDesc::PrepareCode at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 318
                        CONTRACT in CodeVersionManager::PublishVersionableCodeIfNecessary at "D:\a\_work\1\s\src\coreclr\vm\codeversion.cpp" @ 1639
                        CONTRACT in MethodDesc::DoPrestub at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 2014
                        GCX_PREEMP_THREAD_EXISTS in PreStubWorker at "D:\a\_work\1\s\src\coreclr\vm\prestub.cpp" @ 1936
                        CONTRACT in DispatchCallSimple at "D:\a\_work\1\s\src\coreclr\vm\callhelpers.cpp" @ 178
                        CONTRACT in ThreadNative::KickOffThread_Worker at "D:\a\_work\1\s\src\coreclr\vm\comsynchronizable.cpp" @ 148
                        CONTRACT in ManagedThreadBase_DispatchInner at "D:\a\_work\1\s\src\coreclr\vm\threads.cpp" @ 7245
                        CONTRACT in ManagedThreadBase_FullTransition at "D:\a\_work\1\s\src\coreclr\vm\threads.cpp" @ 7493
                        CONTRACT in ThreadNative::KickOffThread at "D:\a\_work\1\s\src\coreclr\vm\comsynchronizable.cpp" @ 196

jkotas · 2022-09-15T01:32:24Z

MODE_COOPERATIVE

Changing the contract on CanCompareBitsOrUseFastGetHashCode from MODE_COOPERATIVE to MODE_ANY should fix this.

src/coreclr/vm/jitinterface.cpp

Today, RuntimeHelpers.IsBitwiseEquatable is hardcoded to a fixed list of types. This means that almost all of the vectorization we've done with arrays and spans is limited to just those types; developers can themselves use MemoryMarshal.Cast to convert spans of other types to spans of supported one, but it doesn't naturally happen. This extends IsBitwiseEquatable a bit more. We already have a CanCompareBitsOrUseFastGetHashCode helper used by ValueType.Equals to determine whether structs that don't override Equals can be compared with the equivalent of memcmp. This extends that same helper to be used by IsBitwiseEquatable. However, IsBitwiseEquatable also needs to rule out types that implement `IEquatable<T>` (the existing helper doesn't because it's about the implementation of the object.Equals override where the interface doesn't come into play). The upside of this is APIs like Array.IndexOf will now automatically vectorize with more types. The main downside is that types which provide their own equality implementation still don't benefit, which in turn means adding an `IEquality<T>` implementation could in the future be a deoptimization (we should consider some kind of attribute or marker interface a type can use to say "I promise my equality implementation is the same as a bitwise comparison"). We also currently constrain most of our MemoryExtensions methods to types that implement `IEquatable<T>`, so there are only a handful of public methods today that benefit from this.

src/coreclr/tools/Common/TypeSystem/IL/Stubs/RuntimeHelpersIntrinsics.cs

jkotas

LGTM modulo comments

stephentoub · 2022-09-16T13:52:44Z

/azp list

azure-pipelines · 2022-09-16T13:52:49Z

CI/CD Pipelines for this repository: runtime-coreclr outerloop runtime-coreclr jitstress runtime-coreclr jitstressregs runtime-coreclr jitstress2-jitstressregs runtime-coreclr gcstress0x3-gcstress0xc runtime-coreclr gcstress-extra runtime-coreclr r2r-extra runtime-coreclr jitstress-isas-x86 runtime-coreclr jitstress-isas-arm runtime-coreclr jitstressregs-x86 runtime-coreclr libraries-jitstressregs runtime-coreclr libraries-jitstress2-jitstressregs runtime-coreclr r2r runtime-coreclr runincontext runtime-coreclr crossgen2 runtime-libraries-coreclr outerloop runtime-libraries-coreclr outerloop-windows runtime-libraries-coreclr outerloop-linux runtime-libraries-coreclr outerloop-osx runtime runtime-libraries enterprise-linux runtime-libraries stress-http runtime-libraries stress-ssl runtime-dev-innerloop runtime-coreclr crossgen2 outerloop coreclr-release-outerloop-nightly runtime-coreclr crossgen2-composite runtime-jit-experimental runtime-coreclr libraries-jitstress dotnet-linker-tests runtime-coreclr ilasm runtime-coreclr crossgen2-composite gcstress runtime-staging runtime-coreclr pgo runtime-coreclr libraries-pgo Antigen runtime-community Fuzzlyn runtime-coreclr superpmi-replay runtime-wasm runtime-coreclr superpmi-diffs runtime-coreclr superpmi-asmdiffs-checked-release runtime-extra-platforms jit-cfg runtime-wasm-perf runtime-llvm runtime-coreclr jitstress-random runtime-coreclr libraries-jitstress-random runtime-android-grpc-client-tests runtime-wasm-libtests runtime-wasm-non-libtests runtime-android runtime-androidemulator runtime-ioslike runtime-ioslikesimulator runtime-linuxbionic runtime-maccatalyst

stephentoub · 2022-09-16T13:54:06Z

/azp run runtime-extra-platforms

azure-pipelines · 2022-09-16T13:54:28Z