Curious case of List.contains performance

Some time ago, colleagues stumbled upon a case where List.contains was significantly slower than identical use of List.exists.

List.contains and List.exists are functions from F# standard library, where

• List.contains x xs check if the list xs contains element x

• List.exists predicate xs check if there is an element in the list xs that satisfy predicate condition.

List.contains being slower than List.exists is weird because it is a specific case of List.exists, and can be rephrased as List.contains x xs = List.exists (fun y -> x = y) xs.

Let's look at this problem in more detail.

Benchmarking

Comparing exists and contains function on lists of int, string and record with Benchmark.NET library we get:

We see that exists is faster than contains for all types. For string it is around 2 times faster, for record it is around 5 times faster, and for int it is around 14 times faster.

Decompiled code

One way to understand why exists is faster than contains is to look at the compiled code. To do that we can use a great tool called SharpLab. This tool compiles given code in F# or C# to CIL, and allows us to look at the decompiled version of CIL in C#. Let's look at a simple example for exists and contains for int:

List.contains function:

[1 .. 1000] |> List.contains 1

decompiled CIL code is as follows

using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using <StartupCode$_>;
using Microsoft.FSharp.Collections;
using Microsoft.FSharp.Core;

[assembly: FSharpInterfaceDataVersion(2, 0, 0)]
[assembly: AssemblyVersion("0.0.0.0")]

[CompilationMapping(SourceConstructFlags.Module)]
public static class @_
{
    [CompilationMapping(SourceConstructFlags.Value)]
    internal static FSharpList<int> arg@1
    {
        get
        {
            return $_.arg@1;
        }
    }

    [CompilationMapping(SourceConstructFlags.Value)]
    internal static FSharpList<int> source@1
    {
        get
        {
            return $_.source@1;
        }
    }

    [CompilerGenerated]
    internal static bool contains@1<a>(a e, FSharpList<a> xs1)
    {
        while (true)
        {
            if (xs1.TailOrNull == null)
            {
                return false;
            }
            FSharpList<a> fSharpList = xs1;
            FSharpList<a> tailOrNull = fSharpList.TailOrNull;
            a headOrDefault = fSharpList.HeadOrDefault;
            if (LanguagePrimitives.HashCompare.GenericEqualityIntrinsic(e, headOrDefault))
            {
                break;
            }
            a val = e;
            xs1 = tailOrNull;
            e = val;
        }
        return true;
    }
}

namespace <StartupCode$_>
{
    internal static class $_
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        internal static readonly FSharpList<int> arg@1;

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        internal static readonly FSharpList<int> source@1;

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal static int init@;

        static $_()
        {
            arg@1 = SeqModule.ToList(Operators.CreateSequence(Operators.OperatorIntrinsics.RangeInt32(1, 1, 1000)));
            source@1 = @_.arg@1;
            @_.contains@1(1, @_.source@1);
        }
    }
}

The important thing here is the call of LanguagePrimitives.HashCompare.GenericEqualityIntrinsic function. That's a function for comparing two values, regardless of their type. Because that function is generic, it contains runtime type checks and it is slower than = operator applied on two ints.

Implementation of GenericEqualityIntrinsic can be found here: https://github.com/dotnet/fsharp/blob/b4c26d84bc58a8d3abb2e7648ed7cc1e1cd7e25c/src/FSharp.Core/prim-types.fs#L1558

which just call GenericEqualityObj https://github.com/dotnet/fsharp/blob/b4c26d84bc58a8d3abb2e7648ed7cc1e1cd7e25c/src/FSharp.Core/prim-types.fs#L1436

List.exists function:

[1 .. 1000] |> List.exists (fun x -> x = 1)

decompiled CIL code is as follows

using System;
using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using Microsoft.FSharp.Collections;
using Microsoft.FSharp.Core;

[assembly: FSharpInterfaceDataVersion(2, 0, 0)]
[assembly: AssemblyVersion("0.0.0.0")]

[CompilationMapping(SourceConstructFlags.Module)]
public static class @_
{
    [Serializable]
    internal sealed class clo@1 : FSharpFunc<int, bool>
    {
        internal static readonly clo@1 @_instance = new clo@1();

        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal clo@1()
        {
        }

        public override bool Invoke(int x)
        {
            return x == 1;
        }
    }
}

namespace <StartupCode$_>
{
    internal static class $_
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal static int init@;

        static $_()
        {
            ListModule.Exists(@_.clo@1.@_instance, SeqModule.ToList(Operators.CreateSequence(Operators.OperatorIntrinsics.RangeInt32(1, 1, 1000))));
        }
    }
}

We see that ListModule.Exists function uses == to compare two ints. That's because = operator is inside lambda function (here compiled as @_.clo@1.@_instance), and the compiler knows it's used on ints.

Better List.contains implementation

We saw that List.exists works better than List.contains. How about we just redefine List.contains to use List.exists?

module List =
    let containsByExists value source =
        List.exists (fun x -> x = value) source

When we run benchmarks with this implementation we get:

Not much better.

If we return to SharpLab, we can see that LanguagePrimitives.HashCompare.GenericEqualityIntrinsic is still used:

using System;
using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using Microsoft.FSharp.Collections;
using Microsoft.FSharp.Core;

[assembly: FSharpInterfaceDataVersion(2, 0, 0)]
[assembly: AssemblyVersion("0.0.0.0")]

[CompilationMapping(SourceConstructFlags.Module)]
public static class @_
{
    [CompilationMapping(SourceConstructFlags.Module)]
    public static class List
    {
        [Serializable]
        internal sealed class contains@3<a> : FSharpFunc<a, bool>
        {
            public a value;

            [CompilerGenerated]
            [DebuggerNonUserCode]
            internal contains@3(a value)
            {
                this.value = value;
            }

            public override bool Invoke(a x)
            {
                return LanguagePrimitives.HashCompare.GenericEqualityIntrinsic(x, value);
            }
        }

        [CompilationArgumentCounts(new int[] { 1, 1 })]
        public static bool contains<a>(a value, FSharpList<a> source)
        {
            return ListModule.Exists(new contains@3<a>(value), source);
        }
    }
}

namespace <StartupCode$_>
{
    internal static class $_
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal static int init@;

        static $_()
        {
            @_.List.contains(1, SeqModule.ToList(Operators.CreateSequence(Operators.OperatorIntrinsics.RangeInt32(1, 1, 1000))));
        }
    }
}

Why? The reason is that the type of = operator in containsByExists is not known at the time of compilation. That's different from exists where the type of = operator is used outside of a function, in lambda parameter.

But there is a solution, we can use inlined function:

module List =
    let inline containsByExistsInline value source =
        List.exists (fun x -> x = value) source

When we run benchmarks with this implementation we get:

Yay! Much better. Now List.containsByExistsInline have comparable performance to List.exists.

Other collection types

Interestingly, this problem is not present in other collection types. It's probably because the implementation of exists and contains functions is different.

Array

Seq

Impementation

Implementation of Array.contains in F# compiler source code:

let inline contains value (array: 'T[]) =
    checkNonNull "array" array
    let mutable state = false
    let mutable i = 0

    while not state && i < array.Length do
        state <- value = array.[i]
        i <- i + 1

    state

https://github.com/dotnet/fsharp/blob/df3919d6940ca3ab63fa8f8fe7b1a511cf4cc96d/src/FSharp.Core/array.fs#L485

Implementation of Seq.contains in F# compiler source code:

let inline contains value (source: seq<'T>) =
    checkNonNull "source" source
    use e = source.GetEnumerator()
    let mutable state = false

    while (not state && e.MoveNext()) do
        state <- value = e.Current

    state

https://github.com/dotnet/fsharp/blob/97c2d3784e907862bf4266cb0ffd8d2788e0a54b/src/FSharp.Core/seq.fs#L681

Both implementations use explicit mutation and while cycle. Inlining of = operator works well here. Problem with List.contains is probably that it uses recursion, and = operator is not inlined.

Better solution?

Can we use a similar implementation for List.contains? Let's try:

let inline containsMutable value (source: list<_>) =
    let mutable xs = source
    let mutable state = false

    while (not state && not xs.IsEmpty) do
        state <- value = xs.Head
        xs <- xs.Tail

    state

Benchmark results:

It's better, but still not as good as List.containsByExistsInline.

Let's try something little different - use of List.tryFind function:

    let inline containsTryFind value (source: list<_>) =
        source |> List.tryFind (fun x -> value = x) |> Option.isSome

This looks good!

List.containsTryFind is even slightly better than List.containsByExistsInline.

Conclusion

We show that List.contains is much slower than List.exists. We analyzed the reason behind this, the usage of GenericEqualityIntrinsic, which is slower than inlined = operator for specific types. We present 2 possible faster implementations of List.contains, List.containsByExistsInline and List.containsTryFind, which is as fast as List.exists or better.

Resources

Full benchmark code can be found in the Benchmarks-list-contains repo.

Update 2023-08-02

I raised an issue about this in F# compiler repo, and Tomáš Grošup from F# compiler team find out alteration of original List.contains function that solves the issue:

let inline outerContainsWhatIf value source =
    let inline isMatch elem = elem = value
    let rec innerContainsWhatIf e xs1 =
        match xs1 with
        | [] -> false
        | h1 :: t1 -> isMatch h1 || innerContainsWhatIf e t1

    innerContainsWhatIf value source

The important thing here is isMatch function outside recursive inner function, that allow inlining of =. I added this function to benchmarks, and it turns out its the fastest variant:

And there is already PR with this change! 🎉