FSharp は Python よりもアルゴリズムの実行速度が遅い質問する

Question

私が電子メールで連絡を取ったジョン・ハロップ博士は、何が起こっているのかを説明してくれた。

問題は、プログラムが Python 用に最適化されているという点だけです。もちろん、プログラマーが一方の言語にもう一方の言語よりも精通している場合、これはよくあることです。F# プログラムを最適化する方法を規定する別の一連のルールを学習する必要があるだけです... いくつかの点が目に留まりました。たとえば、「for i=1 to n do」ループではなく「for i in 1..n do」ループを使用していること (一般的には高速ですが、ここでは重要ではありません)、配列インデックスを模倣するためにリストに対して List.mapi を繰り返し実行していること (これにより中間リストが不必要に割り当てられます)、および不必要に割り当てられる Dictionary 用の F# TryGetValue を使用していること (ref を受け入れる .NET TryGetValue は一般的には高速ですが、ここではそれほどではありません)

... しかし、本当の致命的な問題は、密な 2D マトリックスを実装するためにハッシュテーブルを使用していることでした。ハッシュテーブルの使用は、ハッシュテーブルの実装が非常に最適化されているため Python では理想的です (Python コードがネイティブコードにコンパイルされた F# と同じ速度で実行されるという事実からも明らかです)。しかし、特にデフォルト値を 0 にしたい場合には、密なマトリックスを表すには配列の方がはるかに優れています。

面白いのは、私が最初にこのアルゴリズムをコーディングしたとき、したテーブルを使用します - わかりやすくするために、実装を辞書に変更しました (配列境界チェックを回避することで、コードがシンプルになり、理解しやすくなりました)。

ジョンは私のコードを（戻って:-)）に変換しました配列バージョン、100倍の速度で動作します。

この話の教訓：

F# ディクショナリには作業が必要です... タプルをキーとして使用すると、コンパイルされた F# は解釈された Python のハッシュテーブルよりも遅くなります。
明白ですが、繰り返しても問題ありません。よりクリーンなコードは、場合によっては、はるかに遅いコードを意味します。

ありがとう、ジョン。本当に感謝しています。

編集: Dictionary を Array に置き換えることで、F# が最終的にコンパイル言語で期待される速度で実行されるようになったという事実は、Dictionary の速度の修正の必要性を否定するものではありません (MS の F# の人々がこれを読んでいることを願います)。他のアルゴリズムは辞書/ハッシュに依存しており、配列の使用に簡単に切り替えられません。Dictionary を使用するたびにプログラムが「インタープリタ速度」に苦しむのは、おそらくバグです。コメントで何人かが言っているように、問題が F# ではなく .NET Dictionary にある場合、これは... .NET のバグであると私は主張します。

編集2: アルゴリズムを配列に切り替える必要がない最も明確な解決策 (一部のアルゴリズムは単純にそれに適応しません) は、これを変更することです。

let optimalResults = new Dictionary<_,_>()

次のようにします:

let optimalResults = new Dictionary<_,_>(HashIdentity.Structural)

この変更により、F#のコードは2.7倍高速化され、ついにPython（1.6倍高速化）を上回りました。奇妙なのは、タプルがデフォルトで構造比較を使用するため、原則として、辞書によるキーの比較は同じです (構造の有無にかかわらず)。Harrop 博士は、速度の違いは仮想ディスパッチに起因する可能性があると理論づけています。「私の知る限り、.NET は仮想ディスパッチを最適化することはほとんどなく、仮想ディスパッチのコストは現代のハードウェアでは非常に高い。なぜなら、仮想ディスパッチは「計算された goto」であり、プログラムカウンターを予測できない場所にジャンプさせ、結果として分岐予測ロジックを弱体化させ、ほぼ確実に CPU パイプライン全体をフラッシュして再ロードすることになるからだ」。

わかりやすく言えば、ドン・サイム（下の3つの答えを見てください）、参照型キーを.NETコレクションと組み合わせて使用する場合は、構造ハッシュの使用を明示的にする必要があります。（以下のコメントで、Harrop博士も次のように言っています。いつも.NET コレクションを使用する場合は構造比較を使用します。

MS の F# チームの皆様、これを自動的に修正する方法があれば、ぜひ実行してください。

Answer 1