为什么在 F# 中使用引用大值的字段创建记录这么慢？

Question

在下面作为 .fsx 脚本执行的代码中，最后一行大约需要 30 秒才能完成。我假设由于记录是引用类型，所以最后一行只创建带有引用（不可变）大值的字段的记录，因此它应该非常快。为什么它很慢，我该如何解决？

type BigType = { Big: Set<int> }
type CollectionType = { BigVal: BigType; SmallVal: int }

let b = { Big = set [ 0 .. 999999 ] }
let mySet = set [ 0 .. 50 ]

#time

mySet |> Set.map (fun x -> { BigVal = b; SmallVal = x })

谢谢。

Answer 1

欢迎来到 F# 社区。

我猜每条新记录都在复制 b，尽管正如您所说，默认情况下记录是引用类型，但我不确定为什么会这样。

这种方法并不快：

let y = { BigVal = b; SmallVal = 0 }

mySet |> Set.map (fun x -> { y with SmallVal = x })

改用 class 会快得多：

type BigType = { Big: Set<int> }

let b = { Big = set [ 0 .. 999999 ] }

type CollectionType(smallVal: int) =
    interface System.IComparable with
        member __.CompareTo other =
            compare __.SmallVal (other :?> CollectionType).SmallVal

    member __.BigVal = b
    member __.SmallVal = smallVal

let mySet = set [ 0 .. 50 ]

#time

mySet |> Set.map (fun x -> CollectionType(x))

这不是一个完整的解决方案，因为有警告 FS0343: The type 'CollectionType' implements 'System.IComparable' explicitly but provides no corresponding override for 'Object.Equals'. An implementation of 'Object.Equals' has been automatically provided, implemented via 'System.IComparable'. Consider implementing the override 'Object.Equals' explicitly。

Answer 2

如果先转换为数组，则完全不需要时间：

mySet |> Set.toList |> List.map (fun x -> { BigVal = b; SmallVal = x })

所以创建记录所花费的时间是微不足道的。它慢的原因是记录在一个集合中。作为实现的一部分，集合需要将它们的项目相互比较，以确保没有重复值。 F# 通过比较内容来比较记录的结构。因此，正在比较的这些记录包含非常大的集合，需要很长时间才能进行比较。它们实际上是不同的记录，但在内存中的对象方面是相同的集合，但 F# 记录比较不知道，也不检查。

Answer 3

原因是 Set 是作为搜索树实现的，因此为了将一个项目插入到集合中，它会与一些现有项目进行比较。所以确实只创建了小记录，但是正在比较整套。

如果不知道您正在解决的确切问题，很难说出解决问题的最佳方法。但是，如果要求每个 CollectionType 值具有不同的 SmallVal，那么您可以按照 Scott 的建议进行操作，并实现仅查看 SmallVal 的自定义比较。不过你不需要 class，你可以用一条记录来做到这一点：

(* For records, you need to put CustomComparison in addition to implementing IComparable.
   And CustomComparison requires CustomEquality and its corresponding overrides. *)
[<CustomComparison; CustomEquality>]
type CollectionType =
    { BigVal: BigType; SmallVal: int }

    interface System.IComparable with
        member this.CompareTo(that) =
            match that with
            | :? CollectionType as that -> compare this.SmallVal that.SmallVal
            | _ -> -1

    override this.Equals(that) =
        match that with
        | :? CollectionType as that -> this.SmallVal = that.SmallVal
        | _ -> false

    override this.GetHashCode() = this.SmallVal

Answer 4

这里要注意的一件事是，您在 type CollectionType = { BigVal: BigType; SmallVal: int } 中定义字段的顺序会有所不同。如果你尝试：

type BigType = { Big: Set<int> }
type CollectionType = { SmallVal: int; BigVal: BigType; }
let b = { Big = set [ 0 .. 999999 ] }
let mySet = set [ 0 .. 50 ]
#time
mySet |> Set.map (fun x -> { BigVal = b; SmallVal = x })

取而代之的是实际时间：00:00:34.385 到实际时间：00:00:00.002.

注意：我最初担心这种行为不可靠，可能会在没有警告的情况下发生变化；然而，正如 nasosev 所发现的，此行为在 F# language specification 文档 4.1 版的第 8.15.3 节中有所描述。

为什么在 F# 中使用引用大值的字段创建记录这么慢？

Why is it so slow to create records with a field that references a big value in F#?

performance

memory

f#

reference

record