4

OcamlプログラムをF#に変換しましたが、全体的なパフォーマンスはOcamlと同じです。

ただし、この点に到達するために、例外をOption値で置き換えてみました。

このプログラムは、(=3 のタプル) を持つlist、mapsなどでよく機能します。int*int*intints

理解できないパフォーマンスリークがあります。と呼ばれる関数内で総実行時間の 90% を使用する方法を誰か説明できますか?

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

そして、私はそれについて何ができますか？

4

1 に答える 1

4

人々が指摘しているように、コードなしで問題を診断するのはかなり難しいですが、私は最善を尽くします:-)

あなたの質問により、しばらく実行する予定だったテストを実行することになりました。これは、参照型と値型のパフォーマンスを、連想コンテナーのキーとしてテストすることでした。私の仮説は、.net ランタイムに関する漠然とした感覚に基づいており、キーのサイズが小さい (3 つの int) 場合、値の型が勝つというものでした。私は間違っていたようです ([編集] 実際にさらなるテストを行った結果、それが正しいことが証明されました! [/編集])

いくつかのコードを見てみましょう (いつものように、マイクロ パフォーマンス テストなので、大まかに見てください):

int を格納するために、さまざまなフレーバーの 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))

そして、次の結果を得ました (チェックサムは、私が愚かなことをしていないことを確認するためのものです)。

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 に費やされている場合は、レコード型に変更すると役立つ可能性があります!

しかし、おそらくそうではありません:-) [実際にそれがハッシュコンテナーである場合、GetHashCode は多くの衝突を引き起こすべきではなく、それがマップである場合、それは CompareTo になります)

とにかく、実際のコードでは、明らかにガベージコレクターの影響などが異なります.

各テストをタスクで複数回開始し、それぞれを個別に並行して何度も繰り返し (コアよりも多くのタスクを開始)、完了するまでの平均時間をかけて、さらにテストを行いました。

これを行う理由は、ガベージ コレクターの時間を考慮に入れるためでした。

私がこれを行ったとき、非ジェネリック構造体キーの元の仮説が勝ちました。

誰かが本当に興味があり、変更を加えたくない場合は、コードを投稿できますが、これを読んでいるのは私だけだと思う​​ので、単なる個人的なメモです:-)

于 2013-06-12T05:22:37.930 に答える