List.Equals performs full structural comparison for the same object.

F# list's List.Equals always performs full structural comparison, even if the two objects being compared are the same object.

Repro steps

open System.Diagnostics

let swList = Stopwatch.StartNew()
let l = [1..1000000]
for i in [1..100] do
    if l.Equals(l) = false then
        failwith "Not equal"
printfn $"List: {swList.Elapsed}"

let swArray = Stopwatch.StartNew()
let a = [|1..1000000|]
for i in [1..100] do
    if a.Equals(a) = false then
        failwith "Not equal"
printfn $"Array: {swArray.Elapsed}"

Expected behavior

List and array-based code should be equally quick.

Actual behavior
List is much slower:

List: 00:00:02.2389815
Array: 00:00:00.0114506

Known workarounds

Use object equality explicitly before using List.Equals
Use other collection types

Related information
#9348
#6175

This has been a point of discussion in the LISP, SML, OCaml, ... communities from the day I joined them :) It will still be being discussed in 3022 I'm sure.

For many practical purposes it is wise to add shortcut equality to an equality algorithm and other traversals (e.g. we use pointer equality in many places in the compiler).

However, adding it by default for a generic structural equality can make the structural equality semantically "dubious" (e.g. unreliable, subtle) and performance very sensitive to code changes.

For example, we generally expect

let result = ([x] = [x])

and

let xs = [x]
let result = (xs = xs)

to give the same result. But it's possible to have objects where "x.Equals(x)" will return false, raise an exception or not terminate. So adding shortcutting makes equality return true more often. Further in F#, some object identity is "up to the compiler", e.g. allocations of closures, tuples or, potentially, static constant lists like [x] above.

The arguments about this go back a very long way and there's no really perfect position. We decided in F# 1/2 that we didn't want optimization to affect execution wherever possible - unless you explicitly opt-in to using Object.ReferenceEquals or equivalent - and there's something in language spec about that.

So all in all I think this is in the category of "decided in F# 2.0" - we chose a point on the spectrum, fixed it, and that's that - changing it would help performance in some situations but it might be better to simply write a good guide to equality in the F# docs. The topic is big and important one and could cover things like how to implement your own equality (both explicit and .Equals), what the expected semantics should be for different kinds of equality, how and when to use Object.ReferenceEquals.

So I will close this as by design.

For reference - for those who are just diving into this topic, here is an example to illustrate what Don's saying:

open System

type MyReferenceType() =
    member x.Value = "Some Value"

    override x.Equals(y) =
        Object.ReferenceEquals(x, y)

    override x.GetHashCode() =
        System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(x)

let a = MyReferenceType()
let b = MyReferenceType()

// Comparison using structural equality (but overridden to be reference equality)
let result1 = ([a] = [b])

// Comparison using the same instance
let xs = [a]
let result2 = (xs = xs)

printfn "Result 1 (Different instances): %b" result1 // false
printfn "Result 2 (Same instance): %b" result2       // true

Navigation Menu

Repository navigation

`List.Equals` performs full structural comparison for the same object. #14672

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

List.Equals performs full structural comparison for the same object. #14672

Description

Activity

dsyme commented on Feb 1, 2023

psfinaki commented on Jan 10, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

`List.Equals` performs full structural comparison for the same object. #14672