List.contains performance

[jindraivanek]

Hi,
we've found that List.contains x xs is slower than List.exists (fun y -> x = y) xs, details in my blog post: https://jindraivanek.hashnode.dev/curious-case-of-listcontains-performance

Summary:

• List.contains is ~2x - ~14x slower based on type in my benchmark
• slowness is due to LanguagePrimitives.HashCompare.GenericEqualityIntrinsic call
• benchmark repo is here: https://github.com/jindraivanek/Benchmarks-list-contains/blob/master/Benchmarks/Program.fs
• benchmark table here: https://github.com/jindraivanek/Benchmarks-list-contains/blob/master/Benchmarks/BenchmarkDotNet.Artifacts/results/ListBenchmarks.ListTests-report-github.md

Would you be in favor to change List.contains implementation to

    let inline contains value source =
        source |> tryFind (fun x -> value = x) |> Option.isSome

?

Which turns out fastest from variants I tried. (In benchmark it is List.containsTryFind).

I can extend benchmarks with more cases if needed.

I can make PR for this.

--

Note:
Benchmarks was done on

BenchmarkDotNet=v0.13.4, OS=Windows 10 (10.0.19045.3208)
12th Gen Intel Core i7-12800H, 1 CPU, 20 logical and 14 physical cores
.NET SDK=8.0.100-preview.6.23330.14
  [Host]     : .NET 7.0.9 (7.0.923.32018), X64 RyuJIT AVX2 DEBUG
  DefaultJob : .NET 7.0.9 (7.0.923.32018), X64 RyuJIT AVX2

[vzarytovskii]

This would be a change in behaviour (not using generic equality anymore), thus a potentially breaking change. Needs to be investigated first, whether it behaves differently on any paths/different types, especially around tuples and types which have NaNs.

[T-Gro]

I was expecially afraid of the behavior around nan, the nightmare of possible equality optimizations.
Luckily, the alternative implementations (via tryFind or exists) are matching this, good.

In the end, I think this is failed inlining for the inner contains defined in the List.contains impl - it is recursive, so cannot be inlined.
It is clearer when renaming them to outerContains and innerContains - the outer was can be inlined (and therefore also type-specialized!), whereas the inner one cannot.

You can see in the what if impl that just a small adjustment makes it possible to inline the equality check as well as the value being searched for.

https://sharplab.io/#v2:DYLgZgzgPsCmAuACAlgO2G2iD2BXesATgMLarwCGaEiAbhcLlhHoQMZYC8AsAFCIDEcJIkKw2KVKiKlyVVDSwAPCAEZEPfoO0BbCvDYALRCvUB3ZPEN9t2qIgDaAXUQBaAHyIwDCLBu2Be0N1EBBEeHUPRC5EYMQoezRpEjJKamjw1T5/ASSZVPkaekZmVg4cxD5hSQxpHHx8uWoAdUN9AEkwOgYmRBZcdi4K6rRarGQIAFl9I2i4HQ052AXObpLhhAExCTyUpoVWjq7lNQ0K3RnjU0QLK3PBe2c3T29gX3vA2JCwiOeUKcuX3iiSkjTSBza8E6GQi2S0uVBe3BEEOUK6xV6/UGFRxvGqYgguGASFWeAISMKiFQFFQjmpqAA3ABWAB0AAYGfSXFVNgSifBUdDSQ0KS1IdD6XSacz2ZyaS4gA

This proposal makes sense to me - at least in the objective of making type specialization possible.

[T-Gro]

The behavior stays the same, the (=) operator also eventually leads into GenericEqualityIntrinsic.
But the important difference is that before doing so, it does have the capability to specialize on several known types and therefore avoid boxing etc.

[jindraivanek]

@T-Gro That's great, thanks! Nice trick with isMatch, moving outside rec function.

I added it to benchmarks, performance looks good, best of all variants: https://github.com/jindraivanek/Benchmarks-list-contains/blob/master/Benchmarks/BenchmarkDotNet.Artifacts/results/ListBenchmarks.ListTests-report-github.md

[Happypig375]

@T-Gro Let's just throw away the nan nonsense and consider them equal. fsharp/fslang-suggestions#1280

[vzarytovskii]

@T-Gro Let's just throw away the nan nonsense and consider them equal. fsharp/fslang-suggestions#1280

As a separate item for future probably. Not part of this change.