日々の流転

λ. 共通部分式の除去 (CSE, Common Subexpression Elimination)

命令型言語であっても共通部分式の除去が必ずしも性能を向上させるとは限らないが、純粋関数型言語では特にそうである。例えば、以下のようなリストの「冪集合演算」を考えてみる。

power :: [a] -> [[a]]
power []     = [[]]
power (x:xs) = power xs ++ map (x:) (power xs)

main :: IO ()
main = print (length (power [0..30]))

このpowerの二つ目の等式の右辺には power xs が二回現れているので、これを一度変数に束縛して以下のようにすることが考えられる。しかし、こうするとxssがなかなかGC対象にならないのでメモリを食いつぶしてしまう。

power :: [a] -> [[a]]
power []     = [[]]
power (x:xs) = xss ++ map (x:) xss
    where xss = power xs

このようなことを避けるためにGHCはCSEを行わない……のかな(?)。FAQの Does GHC do common subexpression elimination? には「同じ式が既に変数に束縛されている場合」にのみCSEを行うという "opportunistic CSE" について書いてあるが、ちょっと試した限りでは実際にこれが起こるのを確認できなかった。

いずれにしても、、プログラマは計算結果を共有したい時には明示的に変数に束縛すべきだろう。なお、-fno-cseオプションを使うことでCSEを完全に無効化出来るようだ。

より効率の良い冪集合演算

なお、冪集合演算については、より効率の良い定義が存在する。 ただし列挙される順序は異なるが。

power :: [a] -> [[a]]
power []     = [[]]
power (x:xs) = xss /\/ map (x:) xss
    where xss = power xs

-- interleave
(/\/) :: [a] -> [a] -> [a]
[]     /\/ ys = ys
(x:xs) /\/ ys = x : (ys /\/ xs)