11

Haskell 関数があり、プログラムのすべての割り当ての 50% 以上が発生し、実行時間の 60% が GC に費やされています。小さなスタック ( -K10K) で実行しているので、スタック オーバーフローはありませんが、少ない割り当てでこの関数を高速化することはできますか?

ここでの目標は、行列とベクトルの積を計算することです。hmatrixたとえば、これはad自動微分パッケージを使用するより大きな関数の一部であるため、使用できません。したがって、のリストを使用する必要がありますNum。実行時に、Numeric.ADモジュールを使用すると、型がScalar Double.

listMProd :: (Num a) => [a] -> [a] -> [a]
listMProd mdt vdt = go mdt vdt 0
  where
    go [] _  s = [s]
    go ls [] s = s : go ls vdt 0
    go (y:ys) (x:xs) ix = go ys xs (y*x+ix)

基本的に、行列をループし、ベクトルの最後に到達するまでアキュムレータを乗算およ​​び加算し、結果を格納してから、ベクトルを再び再起動し続けます。quickcheckhmatrix の行列/ベクトル積と同じ結果が得られることを確認するテストがあります。

foldl、などで試しました。関数を高速化するものは何も試していません (また、スペース リークの原因となるfoldrものもあります)。foldr

プロファイリングを使用して実行すると、この関数がほとんどの時間と割り当てが費やされる場所であるという事実に加えて、パッケージからのデータ型でCellsある作成される負荷があることがわかります。Cellsad

実行する簡単なテスト:

import Numeric.AD

main = do
    let m :: [Double] = replicate 400 0.2
        v :: [Double] = replicate 4 0.1
        mycost v m = sum $ listMProd m v 
        mygrads = gradientDescent (mycost (map auto v)) (map auto m)
    print $ mygrads !! 1000

私のマシンでは、GC が 47% の時間ビジーであることがわかります。

何か案は？

4

1 に答える 1

7

非常に簡単な最適化はgo、アキュムレータ パラメータによって関数を厳密にすることです。関数は小さく、プリミティブな場合aはボックス化解除でき、常に完全に評価する必要があるためです。

{-# LANGUAGE BangPatterns #-}
listMProd :: (Num a) => [a] -> [a] -> [a]
listMProd mdt vdt = go mdt vdt 0
  where
    go [] _  !s = [s]
    go ls [] !s = s : go ls vdt 0
    go (y:ys) (x:xs) !ix = go ys xs (y*x+ix)

私のマシンでは、3〜4倍のスピードアップが得られます（ でコンパイル-O2）。

一方、中間リストは厳密であってはならないので、それらは融合する可能性があります。

于 2015-09-24T16:20:20.780 に答える