performance - F# 处理复杂键(如数据结构中的 int*int*int)比 Ocaml 慢得多

Question

我把一个Ocaml程序转成F#，整体性能和Ocaml一样。

但是，为了达到这一点，我尝试用 Option 值替换异常。

该程序对具有 int*int*int 的列表、 map 等很有效。 (=三元组 ints )。

我有一个我不明白的性能泄漏。谁能解释我怎么做
在一个名为的函数内有 90% 的总执行时间

System.Tuple`3.System.Collections.IStructuralEquatable.Equals(
   object, class System.Collections.IEqualityComparer)

我能做些什么呢？

Answer 1

正如人们所指出的那样，没有代码很难诊断问题，但我会尽我所能:-)

你的问题让我运行了一个我计划运行一段时间的测试，这是为了测试作为关联容器键的引用类型与值类型的性能。我的假设是基于对 .net 运行时的模糊感觉，对于较小的键大小(您的 3 个整数)，值类型会胜出。我似乎错了([编辑]实际上进一步的测试证明它是正确的![/编辑])

让我们看一些代码(按照惯例，微性能测试，所以请谨慎对待):

我使用了 5 个不同风格的不同容器来存储整数(F# 足以为结构类型和记录创建相等性和比较器):

type KeyStruct(_1':int, _2':int, _3':int) = struct
    member this._1 = _1'
    member this._2 = _2'
    member this._3 = _3'
end

type KeyGenericStruct<'a>(_1':'a, _2':'a, _3':'a) = struct
    member this._1 = _1'
    member this._2 = _2'
    member this._3 = _3'
end

type KeyRecord = { _1 : int; _2 : int; _3 : int }

type KeyGenericRecord<'a> = { _1 : 'a; _2 : 'a; _3 : 'a }

加上我使用了原始元组 (int*int*int)

然后我创建了以下测试工具:

let inline RunTest<'a when 'a : equality> iterationCount createAssociativeMap (createKey:_->_->_->'a) =
    System.GC.Collect ()
    System.GC.WaitForFullGCComplete () |> ignore

    let data = [|
        for a in 0..99 do
            for b in 0..99 do
                for c in 0..99 do
                    yield a,b,c |]
    // shuffle
    let r = System.Random (0)
    for i = 0 to data.Length-1 do
        let j = r.Next (i, data.Length)
        let t = data.[i]
        data.[i] <- data.[j]
        data.[j] <- t

    let keyValues =
        data
        |> Array.mapi (fun i k -> k, 0.5-(float i)/(float data.Length))
        |> Array.toSeq

    let sw = System.Diagnostics.Stopwatch.StartNew ()
    let mapper = createAssociativeMap createKey keyValues
    let creationTime = sw.ElapsedMilliseconds

    let sw = System.Diagnostics.Stopwatch.StartNew ()
    let mutable checksum = 0.
    for i = 0 to iterationCount do
        let a, b, c = r.Next 100, r.Next 100, r.Next 100
        let key = createKey a b c
        checksum <- checksum + (mapper key)
    let accessTime= sw.ElapsedMilliseconds

    printfn "checksum %f elapsed %d/%d (%s)" checksum creationTime accessTime (typeof<'a>.Name)

let RunNTrials<'a when 'a : equality> = RunTest<'a> 1000000

然后用一些不同类型的关联容器运行它:

let createDictionary create keyValues = 
    let d = System.Collections.Generic.Dictionary<_,_> ()
    keyValues
    |> Seq.map (fun ((_1,_2,_3),value) -> create _1 _2 _3, value)
    |> Seq.iter (fun (key,value) -> d.[key] <- value)
    (fun key -> d.[key])

let createDict create keyValues =
    let d = 
        keyValues
        |> Seq.map (fun ((_1,_2,_3),value) -> create _1 _2 _3, value)
        |> dict
    (fun key -> d.[key])

let createMap create keyValues =
    let d = 
        keyValues
        |> Seq.map (fun ((_1,_2,_3),value) -> create _1 _2 _3, value)
        |> Map.ofSeq
    (fun key -> d.[key])

let createCustomArray create keyValues =
    let maxA = 1 + (keyValues |> Seq.map (fun ((a,_,_),_) -> a) |> Seq.max)
    let maxB = 1 + (keyValues |> Seq.map (fun ((_,b,_),_) -> b) |> Seq.max)
    let maxC = 1 + (keyValues |> Seq.map (fun ((_,_,c),_) -> c) |> Seq.max)

    let createIndex a b c = a * maxB * maxC + b * maxC + c

    let values : array<float> = Array.create (maxA * maxB * maxC) 0.
    keyValues
    |> Seq.iter (fun ((a,b,c),d) -> values.[createIndex a b c] <- d)

    (fun (a,b,c) -> values.[a * maxB * maxC + b * maxC + c])

let RunDictionary<'a when 'a : equality> = RunNTrials<'a> createDictionary 
let RunDict<'a when 'a : equality> = RunNTrials<'a> createDict
let RunMap<'a when 'a : comparison> = RunNTrials<'a> createMap
let RunCustomArray = RunNTrials<_> createCustomArray

并按如下方式运行测试:

printfn "Using .net's System.Collections.Generic.Dictionary"
RunDictionary (fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) 
RunDictionary (fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c })
RunDictionary (fun a b c -> KeyStruct(a, b, c))
RunDictionary (fun a b c -> KeyGenericStruct(a, b, c))
RunDictionary (fun a b c -> (a, b, c))

printfn "Using f# 'dict'"
RunDict (fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) 
RunDict (fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c })
RunDict (fun a b c -> KeyStruct(a, b, c))
RunDict (fun a b c -> KeyGenericStruct(a, b, c))
RunDict (fun a b c -> (a, b, c))

printfn "Using f# 'Map'"
RunMap (fun a b c -> { KeyRecord._1=a; _2=b; _3=c }) 
RunMap (fun a b c -> { KeyGenericRecord._1=a; _2=b; _3=c })
RunMap (fun a b c -> KeyStruct(a, b, c))
RunMap (fun a b c -> KeyGenericStruct(a, b, c))
RunMap (fun a b c -> (a, b, c))

printfn "Using custom array"
RunCustomArray (fun a b c -> (a, b, c))

并得到以下结果(校验和只是为了确保我没有做任何太愚蠢的事情)“elapsed n/m”是“elapsed {container creations time}/{container access time}”:

Using .net's System.Collections.Generic.Dictionary
checksum -55.339450 elapsed 874/562 (KeyRecord)
checksum -55.339450 elapsed 1251/898 (KeyGenericRecord`1)
checksum -55.339450 elapsed 569/1024 (KeyStruct)
checksum -55.339450 elapsed 740/1427 (KeyGenericStruct`1)
checksum -55.339450 elapsed 2497/2218 (Tuple`3)
Using f# 'dict'
checksum -55.339450 elapsed 979/628 (KeyRecord)
checksum -55.339450 elapsed 1614/1206 (KeyGenericRecord`1)
checksum -55.339450 elapsed 3237/5625 (KeyStruct)
checksum -55.339450 elapsed 3290/5626 (KeyGenericStruct`1)
checksum -55.339450 elapsed 2448/1914 (Tuple`3)
Using f# 'Map'
checksum -55.339450 elapsed 8453/2638 (KeyRecord)
checksum -55.339450 elapsed 31301/25441 (KeyGenericRecord`1)
checksum -55.339450 elapsed 30956/26931 (KeyStruct)
checksum -55.339450 elapsed 53699/49274 (KeyGenericStruct`1)
checksum -55.339450 elapsed 32203/25274 (Tuple`3)
Using custom array
checksum -55.339450 elapsed 484/160 (Tuple`3)

多次运行显示数字变化很小，但主要趋势确实存在。因此，我们主要测试是否发生装箱(在 map 和 dict 中)，然后是 GetHashCode () 实现(如果比完全类型化版本慢，则为通用版本；最糟糕的是 Tuple)，在 Map 的情况下是 CompareTo。

现在你的问题在哪里？如果所有时间都花在元组的 Equals 上，那么更改为 Record 类型可能会有所帮助!

但可能不是:-) [因为真的如果它是一个哈希容器，那么 GetHashCode 不应该引起很多冲突，它是一个 map ，那么它就是 CompareTo)

无论如何，在实际代码中，您显然会有不同的垃圾收集器影响等等，正如我所说的那样......

我做了一些进一步的测试，通过在 Tasks 中多次启动每个测试，并且每个测试一次又一次地并行(启动比我拥有的内核更多的任务)，然后花费平均时间来完成。

这样做的原因是为了考虑垃圾收集器的时间。

当我这样做时，非通用结构键的原始假设确实获胜。

如果有人真的很感兴趣并且不愿意进行更改，我可以发布代码，但实际上我认为我是唯一一个阅读此内容的人，因此更多只是我的个人笔记:-)