私は関数型プログラミングの初心者で、Haskell を学んでいます。演習として、1D 線形拡散方程式に陽的オイラー法を実装することにしました。以下のコードは正しく動作しますが、そのパフォーマンスには満足できません。実際、私はメモリ消費に関心があります。遅延評価に関連していると思いますが、メモリ使用量を減らす方法がわかりません。
アルゴリズムの考え方は非常にシンプルで、命令的な用語で明確にします: 「配列」を取り、すべての内部ポイントに値を追加します。これは、ポイント自体とそのポイントの値の組み合わせとして計算されます。隣人。境界点は特殊なケースです。
これが私の Euler1D.hs モジュールです。
module Euler1D
( stepEuler
, makeu0
) where
-- impose zero flux condition
zeroflux :: (Floating a) => a -> [a] -> [a]
zeroflux mu (boundary:inner:xs) = [boundary+mu*2*(inner-boundary)]
-- one step of integration
stepEuler :: (Floating a) => a -> [a] -> [a]
stepEuler mu u@(x:xs) = (applyBC . (diffused mu)) u
where
diffused mu (left:x:[]) = [] -- ignore outer points
diffused mu (left:x:right:xs) = -- integrate inner points
(x+mu*(left+right-2*x)) : diffused mu (x:right:xs)
applyBC inner = (lbc u') ++ inner ++ (rbc u') -- boundary conditions
where u' = [head u] ++ inner ++ [last u]
lbc = zeroflux mu -- left boundary
rbc = (zeroflux mu) . reverse -- right boundary
-- initial condition
makeu0 :: Int -> [Double]
makeu0 n = [ ((^2) . sin . (pi*) . xi) x | x <- [0..n]]
where xi x = fromIntegral x / fromIntegral n
そして、単純な Main.hs:
module Main where
import System ( getArgs )
import Euler1D
main = do
args <- getArgs
let n = read $ head args :: Int
let u0 = makeu0 n
let un = stepEuler 0.5 u0
putStrLn $ show $ sum un
比較のために、純粋な C 実装も作成しました。
ここで、十分に大きなサイズの array に対して Haskell 実装を実行しようとすると、次のnようになります。
$ time ./eulerhs 200000
100000.00000000112
real 0m3.552s
user 0m3.304s
sys 0m0.128s
比較のために、C バージョンはほぼ 2 桁高速です。
$ time ./eulerc 200000
100000
real 0m0.088s
user 0m0.048s
sys 0m0.008s
編集: Haskell バージョンはプロファイリング フラグを使用してコンパイルされており、C はそうではないため、この比較は実際には公平ではありません。
-O2プロファイリング フラグを使用して、または使用せずに両方のプログラムをコンパイルすると、 を増やすことができnます。この場合time ./eulerhs 1000000、0m2.236 秒かかりますが、time ./eulerc 10000000m0.293 秒しかかかりません。そのため、すべての最適化を行っても問題は残り、プロファイリングを行わないと、相殺されるだけです。また、Haskell プログラムのメモリ割り当ては、
n. これで多分OKです。
しかし、最悪なのはメモリ要件です。私の Haskell バージョンでは100MB 以上が必要です (C での最低限の見積もりは4MBです)。これが問題の原因かもしれないと思います。プロファイリング レポートによると、プログラムは GC で 85% の時間を費やしており、
total time = 0.36 secs (18 ticks @ 20 ms)
total alloc = 116,835,180 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
makeu0 Euler1D 61.1 34.9
stepEuler Euler1D 33.3 59.6
CAF:sum Main 5.6 5.5
makeu0それがとても高価なことを見て私は驚いた。これは遅延評価が原因であると判断しました (そのサンクが の最後までメモリに残っている場合stepEuler)。
私はこの変更を試しましたMain.hs：
let un = u0 `seq` stepEuler 0.5 u0
しかし、違いはわかりませんでした。でメモリ使用量を減らす方法がわかりませんstepEuler。だから、私の質問は次のとおりです。
- Haskell でリストを作成する方法/リスト内包表記を厳密に行う方法はありますか? この場合、怠惰にしておくメリットはありません。
- この場合、全体的なメモリ使用量を減らすにはどうすればよいですか? 私は何かを厳密にしなければならないと思いますが、何がわからないのですか。言い換えれば、
seqs と bangs をいくつか入れなければならない場合、どこに、なぜ? - そして最後に、最も重要なのは、そのようなコストのかかる構造を特定するための最善の戦略は何ですか?
Real World Haskellのプロファイリングと最適化に関する章を読みましたが、厳密であるべきものとそうでないものをどのように正確に決定できるかは不明のままです。
このような長い投稿をお許しください。
EDIT2：コメントでA. Rexが示唆したように、valgrindで両方のプログラムを実行してみました。そして、これが私が観察したことです。Haskell プログラム (
n=200000) の場合:malloc/free: 33 個の割り当て、30 個の解放、84,109 バイトが割り当てられました。... 55,712,980 バイトを確認しました。
そしてCプログラムの場合（小さな修正後）：
malloc/free: 2 つの割り当て、2 つの解放、3,200,000 バイトの割り当て。
したがって、Haskell ははるかに小さいメモリ ブロックを割り当てますが、頻繁に割り当て、ガベージ コレクションの遅延によりメモリに蓄積されたままになるようです。それで、私は別の質問があります：
- Haskellで多くの小さな割り当てを避けることは可能ですか? 基本的には、必要に応じてデータ構造のフラグメントだけでなく、データ構造全体を処理する必要があることを宣言します。