bench.fs

type RefRecord = { I: int; J: int }

[<Struct>]
type StructRecord = { I: int; J: int }

type Benchmarks() =
    let rnd = Random()
    let next() = rnd.Next(Int32.MinValue, Int32.MaxValue)
    let n = 10000
    let refTupleList = List.init n (fun _ -> next(), next())
    let structTupleList = List.init n (fun _ -> struct (next(), next()))
    let refTupleArray = Array.init n (fun _ -> next(), next())
    let structTupleArray = Array.init n (fun _ -> struct (next(), next()))

    let refRecordList = List.init n (fun _ -> { RefRecord.I = next(); J = next() })
    let structRecordList = List.init n (fun _ -> { StructRecord.I = next(); J = next() })
    let refRecordArray = Array.init n (fun _ -> { RefRecord.I = next(); J = next() })
    let structRecordArray = Array.init n (fun _ -> { StructRecord.I = next(); J = next() })

    [<Benchmark>] member __.RefTupleList() = List.sortBy (fun (_, y) -> y) refTupleList |> ignore
    [<Benchmark>] member __.StructTupleList() = List.sortBy (fun struct (_, y) -> y) structTupleList |> ignore
    [<Benchmark>] member __.RefTupleArray() = Array.sortBy (fun (_, y) -> y) refTupleArray |> ignore
    [<Benchmark>] member __.StructTupleArray() = Array.sortBy (fun struct (_, y) -> y) structTupleArray |> ignore

    [<Benchmark>] member __.RefRecordList() = refRecordList |> List.sortBy (fun { J = j } -> j) |> ignore
    [<Benchmark>] member __.StructRecordList() = structRecordList |> List.sortBy (fun { J = j } -> j) |> ignore
    [<Benchmark>] member __.RefRecordArray() = refRecordArray |> Array.sortBy (fun { J = j } -> j) |> ignore
    [<Benchmark>] member __.StructRecordArray() = structRecordArray |> Array.sortBy (fun { J = j } -> j) |> ignore

[<EntryPoint>]
let main _ =
    BenchmarkRunner.Run<Benchmarks>() |> ignore
    0

results.md

BenchmarkDotNet=v0.10.5, OS=Windows 10.0.14393
Processor=Intel Core i7-4790K CPU 4.00GHz (Haswell), ProcessorCount=8
Frequency=3906256 Hz, Resolution=255.9996 ns, Timer=TSC
  [Host]     : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.6.1637.0
  DefaultJob : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.6.1637.0

Method	Mean	Error	StdDev
RefTupleList	790.8 us	6.827 us	6.386 us
StructTupleList	710.5 us	5.966 us	5.581 us
RefTupleArray	1,096.6 us	4.773 us	4.465 us
StructTupleArray	930.4 us	2.682 us	2.509 us
RefRecordList	780.0 us	2.056 us	1.923 us
StructRecordList	705.3 us	4.054 us	3.792 us
RefRecordArray	1,114.0 us	1.691 us	1.582 us
StructRecordArray	948.2 us	5.057 us	4.731 us

BenchmarkDotNet=v0.10.5, OS=Windows 10.0.14393
Processor=Intel Core i7-4790K CPU 4.00GHz (Haswell), ProcessorCount=8
Frequency=3906256 Hz, Resolution=255.9996 ns, Timer=TSC
 [Host]     : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
 DefaultJob : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0

Method	Mean	Error	StdDev
RefTupleList	696.2 us	3.686 us	3.448 us
StructTupleList	594.6 us	5.861 us	5.482 us
RefTupleArray	771.2 us	4.494 us	3.508 us
StructTupleArray	639.0 us	8.144 us	7.618 us
RefRecordList	696.6 us	4.432 us	3.928 us
StructRecordList	602.3 us	1.834 us	1.626 us
RefRecordArray	790.3 us	14.098 us	13.187 us
StructRecordArray	636.5 us	2.543 us	2.379 us

Each of the list/arrays has a different random set of numbers. That leaves the tests open to problems with chance "better" ordering for some of the test elements. Maybe change L10 so that you create one array with the all the random numbers you need, then generate the lists/arrays based on that common source. Can also be mitigated by having multiple runs (each iteration doesn't change the list), but you would need several runs to reduce the role that chance might play.

Otherwise, very interested in these results 😄 👍