4

我已经将一个Ocaml程序转换为F#，整体性能与Ocaml相同。

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

该程序与具有（=三的元组）的列表，地图等一起工作很多。int*int*intints

我有一个我不明白的性能泄漏。谁能解释我如何在一个名为的函数中拥有 90% 的总执行时间

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

我能做些什么呢？

4

1 回答 1

4

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

您的问题使我运行了一个我计划运行一段时间的测试，该测试是测试引用类型与值类型作为关联容器的键的性能。基于对 .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 不应该引起很多冲突，它是一个地图，那么它将是 CompareTo）

无论如何，在实际代码中，您显然会产生不同的垃圾收集器影响等，正如我所说的那样，把它当作它是什么......

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

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

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

如果有人真的有兴趣并且不愿意做出改变，我可以发布代码，但我真的认为我是唯一一个阅读这篇文章的人，所以这只是我的个人笔记:-)

于 2013-06-12T05:22:37.930 回答