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

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

数年前、私は動的プログラミングを使ってある問題を解決しました。

https://www.thanassis.space/fillupDVD.html

ソリューションは Python でコーディングされました。

視野を広げる一環として、最近 OCaml/F# を学び始めました。Python で書いた命令型コードを F# に直接移植し、そこから始めて関数型プログラミング ソリューションに向けて段階的に進んでいくことほど、試すのに良い方法はありません。

この最初の直接移植の結果は...当惑させるものです:

Pythonの場合:

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

FSharp の場合:

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

(上記の「モノ」に気づいた場合: Windows でも Visual Studio を使用してテストしましたが、速度は同じでした)。

控えめに言っても、困惑しています。Python は F# よりも速くコードを実行しますか? .NET ランタイムを使用してコンパイルされたバイナリは、Python の解釈されたコードよりも遅く実行されますか?!?!

VM (この場合は mono) の起動コストや、JIT が Python などの言語でどのように改善するかについては知っていますが、それでも... 速度低下ではなく、速度向上を期待していました。

何か間違ったことをしてしまったのでしょうか?

コードをここにアップロードしました:

https://www.thanassis.space/fsharp.slower.than.python.tar.gz

F# コードは、Python コードをほぼそのまま行ごとに翻訳したものであることに注意してください。

PS もちろん、F# が提供する静的型安全性など、他の利点もありますが、命令型アルゴリズムの速度が F# で低下するのであれば、控えめに言ってもがっかりです。

編集: コメントでリクエストされた直接アクセス:

Pythonコード:出典: github.com

FSharp コード:出典: github.com

ベストアンサー1

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

問題は、プログラムが 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# チームの皆様、これを自動的に修正する方法があれば、ぜひ実行してください。

おすすめ記事