21

現在、遅すぎるアルゴリズムの Scala 実装を最適化する必要があります。機能的な方法で実装され、値 ( val) と不変のデータ構造のみを使用します。私はすでに重要な関数をメモしているポイントにいます (そのため、私のコードには変更可能なマップがいくつかあります)。これにより、コードが 2 倍速くなり、次に何をすべきか疑問に思います。

したがって、私はソフトウェアの最適化に関する一般的なアドバイス (たとえば、最初にアルゴリズムを最適化する、プロファイラーを使用する、ベンチマークを実行するなど) ではなく、Scala 固有または JVM 固有の最適化アドバイスを求めています。

したがって、私の質問は、Scala コードを最適化しようとするとき、最初にどこを見るべきかということです。通常、速度低下の原因となる一般的な言語構造またはパターンは何ですか?

特に、次の点についてアドバイスを求めています。

  • ループの本体が実行されるたびにfor(...)匿名クラスが生成されるため、コンストラクトが遅いと読みました。本当ですか？匿名クラスが生成される場所は他にありますか? (例:無名関数で使用する場合)map()
  • 不変コレクションは、一般的な場合 (特にマップ構造に関して) 可変コレクションよりも大幅に遅くなりますか?
  • Scala 2.8、2.9、および 2.10 の間に大きなパフォーマンスの違いはありますか?
4

2 に答える 2

36

また、過去には多くの Scala コードを最適化する必要がありました。以下は完全なリストではなく、役立つかもしれないいくつかの実際的な観察です。

  • はい、 Scala 2.10 でも、forループを aに置き換える方が高速です。while詳細については、コメント内のリンクされたトークを参照してください。また、「for filtering」(反復しているコレクションに続く条件) を使用すると、条件のボックス化/ボックス化解除が発生し、パフォーマンスに大きな影響を与える可能性があることに注意してください (詳細については、この投稿を参照してください)。

  • イミュータブルかミュータブルかという質問は、実行しなければならない更新の回数によって簡単に答えられるものであり、ここで一般的な答えを出すのは (私にとって) 困難です。

  • これまでのところ、2.8、2.9、および 2.10 の間でパフォーマンスに大きな違いは見られませんでした。しかし、明らかにこれは当面の問題に依存します。たとえば、アルゴリズムで Range.sum を多用すると、大きな違いが見られます (2.10 では O(1) になっているため)。

  • Scala バージョンの代わりに対応する Java コレクションを使用すると、大幅な速度向上につながる可能性があることに気付きました (大まかな数字としては、5 ～ 10% のオーダーであると言えます)。たとえば、非常に具体的な問題のマイクロベンチマークで次の結果が得られました (表示されるのはランタイムです) (注: それを一般化しないでください。自分で実行してください)。

    ColtBitVector          min:      0.042    avg:      0.245    max:     40.120
JavaBitSet             min:      0.043    avg:      0.165    max:      4.306
JavaHashSet            min:      0.191    avg:      0.716    max:     12.624
JavaTreeSet            min:      0.313    avg:      1.428    max:     64.504
ScalaBitSetImmutable   min:      0.380    avg:      1.675    max:     13.838
ScalaBitSetMutable     min:      0.423    avg:      3.693    max:    457.146
ScalaSetImmutable      min:      0.458    avg:      2.305    max:      9.998
ScalaSetMutable        min:      0.340    avg:      1.332    max:     10.974

    当面の問題は、整数セットの単純な交差を計算することでした (非常に特定のサイズとセット数)。私が実証したいこと: 正しい/間違ったコレクションの選択は、大きな影響を与える可能性があります! 繰り返しになりますが、これらのデータ型のどれを選択するかを一般的にアドバイスするのは難しいと思います。なぜなら、これはこの特別な交差点の問題でのパフォーマンスを示すだけだからです (ただしHashSet、いくつかのケースでは、他の選択肢よりも Java を選択しました)。また、この共通部分の問題は可変データ型を必要としないことに注意してください。それにもかかわらず、不変の機能でもパフォーマンスの違いが生じる可能性があります (またSet、可変コレクションの方が大幅に高速だったのに対して、不変コレクションの方がBitSet）。したがって、状況によっては、最大のパフォーマンスを得るために、不変コレクションよりも可変コレクションを選択することをお勧めします (注意して使用してください)。

  • 変数を宣言するとprivate[this] var foo = ...、ゲッター/セッター関数の作成が妨げられ、高速になるはずだと言われました (免責事項: マイクロベンチマークで確認したことはありません)。

  • ジェネリック型を扱う場合@specialized、特定の型のバージョンを定義すると速度が向上します。

  • 私は一般化を避けようとしていますが、次のことを受け入れることができます: ネイティブ配列を使用してみてください。私のベンチマークの多くで、最終的に配列を使用することになりました。これは、JVM での実装を考えると理にかなっています。

  • 私の頭に浮かぶマイナーなポイント: コレクションの構築にはorigCollection.toSomeCollectionName、手動による構築とコンパニオン オブジェクト (つまりSomeCollectionName(origCollection :_*)) を使用した構築のいずれかの違いが見られました。多くの場合、後者は大幅に高速でした。

于 2013-02-27T16:03:47.607 に答える
3

コードを実行すると、多数のオブジェクトがインスタンス化されますか? caseたとえば、Scalaクラス、またはmap/flatMapのチェーンにより、膨大な数の「不要な」オブジェクトが作成される可能性があります。これにより、コードの速度が低下し、ガベージ コレクターの作業が増える可能性があります。

于 2013-02-27T13:02:03.883 に答える