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

One thing to notice here is that the order you define the fields in type CollectionType = { BigVal: BigType; SmallVal: int } makes a difference. If you try:

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 })

Instead the time taken goes from Real: 00:00:34.385 to Real: 00:00:00.002.

NB: I was originally concerned that this behaviour could not be relied on and might change without warning; however as nasosev has found this behaviour is described in the F# language specification see section 8.15.3 of version 4.1 of the document.

The reason is that Set is implemented as a search tree, so in order to insert an item into a set, it is compared against some of the existing items. So there are indeed only small records created, but whole sets are being compared.

It's hard to tell what the best way to fix the issue is without knowing the exact problem you're solving. But if it is a requirement that each CollectionType value has a different SmallVal, then you can do as Scott suggests and implement custom comparison that only looks at SmallVal. You don't need a class though, you can do it with a record:

(* 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

If you convert to an array first then it takes no time at all:

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

So the time that it take to create the records is insignificant. The reason it's slow is that the records are inside a set. Sets need to compare their items to each other as part of the implementation, to make sure there are no duplicate values. F# compares records structurally, by comparing their contents. So these records that are being compared contain very large sets that take a long time to compare. They are actually different records but the same set in terms of objects in memory, but the F# record comparison doesn't know that, and doesn't check.

Welcome to the F# community.

I'm guessing that each new record is copying b, although since records are reference types by default, as you say, I'm not sure why that would be.

This approach is no faster:

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

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

Using a class instead is much faster:

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))

This is not a complete solution, since there is a warning 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.