読者です 読者をやめる 読者になる 読者になる

Haskellでハマった - runhaskellを使うとリストがメモ化されない?あるいはモジュールにすると-O3でもリストがメモ化されない?

Haskell

Haskellを書いていて、久しぶりに言語自体について不可解な挙動にぶち当たった。普段Haskellを書いていて、言語について「なんだこれ」と思うことはまずない。ところが、今回の疑問点は自分の理解を遥かに超える内容だった。最初はTwitterで質問してみたのだが、誰にも答えて頂けなかったので、stackoverflowで質問した。すると、見事に解決しまったので紹介する。

質問が長い。でも丁寧に書いたつもり。下の方に和訳も用意した。英語を読むのが面倒な人はそっちを読んでほしい。(自分が書いた英語を和訳するとか意味が分からんね。)
http://stackoverflow.com/questions/25958007/

Why ghc changes the evaluation way due to the optimisation flag?

Hello, I've encountered a wired behaviour of the optimisation flags of ghc. The optimising flags seem to change the way of evaluation. In summary,

  • I wrote a code containing primes and isPrime defined by referring to the each other.
  • I found that the program works well with ghc -O3, but I could not use runhaskell to get the result. It costs too much time.
  • I noticed that when I used ghc -O1, the result appears instantly as -O3, but the executable compiled by ghc -O0 fails to calculate the result in a minute.
  • I used Debug.Trace.trace to find that primes is evaluated from its start every time when isPrime is called.
  • I moved the definition of primes and isPrime to another file Prime.hs. In the main file, I imported my Prime library. Unfortunately, the executable compiled by ghc -O3 does not calculate the result in a minute.

Here's the description. Please see the following code.

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

When I compile the code with ghc -O3, the executable calculates the correct result 68906 in 2 seconds.

 $ ghc -O3 test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
68906
./test  1.24s user 0.02s system 79% cpu 1.574 total

However, when I used -O0, I could not get the result in a minute. Be sure to remove the generated files in advance.

 $ rm -f ./test ./test.o ./test.hi
 $ ghc -O0 test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
^C
./test  64.34s user 0.94s system 94% cpu 1:08.90 total

I aborted. The flag -O1 works well as same as -O3.

So let us dive into investigation. I used Debug.Trace.trace. I traced the argument of isPrime.

import Debug.Trace

main :: IO ()
main = print $ length $ filter isPrime [10..30]

primes :: (Show a, Integral a) => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: (Show a, Integral a) => a -> Bool
isPrime n = trace (show n) $ n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

When the optimisation flag is -O3, (or -O1), the output is as follows.

10
11
3
5
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
7
30
6

This result is reasonable (note that the last line prints the number of the primes; 11, 13, 17, 19, 23, 29).

Here's the result with -O0 (or runhaskell)

10
11
3
5
3
12
13
3
5
3
14
15
3
16
17
3
5
3
18
19
3
5
3
20
21
3
22
23
3
5
3
24
25
3
5
3
26
27
3
28
29
3
5
3
7
3
30
6

This result is interesting to look into. 2 is already arranged at the head of primes. 3 and 5 are checked if isPrime again and again. When isPrime 11 is called, 3 is checked if a prime, and 5 is also checked, isPrime 3 is called again. Likewise, for almost every odd numbers, isPrime 3 and isPrime 5 is called again and again.

Thus I thought that when I use -O0, primes is not cached and constructed from [2] every time as isPrime is called. So the first question is why -O0 and -O1 changes the behavior of evaluation.

Here's another problem. Okay, okay, but I rarely use -O0 flag. In most case I use -O2 or -O3 optimisation flag so I thought that the above problem does not appear in many use case.

But when I moved the codes into another file, the problem again turns up. I just moved primes and isPrime to Prime.hs.

test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

Prime.hs:

module Prime where

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

In this time, I could not obtain the result with -O1 flag, or even with -O3 flag.

 $ ghc -O3 test.hs
[1 of 2] Compiling Prime            ( Prime.hs, Prime.o )
[2 of 2] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
^C
./test  62.41s user 0.88s system 92% cpu 1:08.23 total

hmm, I aborted again. I do not know whether this way has an effect to the result, I precompiled Prime.hs with -O3 in advance, but in vain. I hereby used Debug.Trace.trace and I saw 2 and 3 again and again with -O3 flag. In short, I could not create a Prime library because the evaluation way changes when primes and isPrime are moved into a module (which made me surprised) and -O3 does not make it work.

So the second question is, in spite of the -O3 flag, why the stuffs in a module are evaluated as compiled by -O0 flag?

I finally get tired of investigating into this wired behaviour. I concluded that I should not use a cross-referenced definition in a module. I gave up creating my Prime library and started to use Data.Numbers.Primes.

Thanks in advance.

http://stackoverflow.com/questions/25958007/

和訳も書いておく。

なぜghcは最適化オプションに伴って評価方法を変えるのか

こんにちは。ghcの最適化オプションの変な挙動を見つけたよ。最適化オプションによって評価方法が変わってるようなんだ。要約するとこうだ。

  • 相互に参照して定義された、primesとisPrimeを含むコードを書いた。
  • そのプログラムは、ghc -O3だとうまく動いた。だけど、runhaskellを使うと結果を得られなかった。時間が掛かり過ぎるんだ。
  • 次に、ghc -O1を使うと-O3でコンパイルしたのと同様に結果がすぐに出てくることを確認した。でも、ghc -O0でコンパイルした実行ファイルは、一分たっても結果をよこさなかった。
  • Debug.Trace.traceを使ってプロファイルしてみたところ、isPrimeが呼ばれる度にprimesが最初から計算されていることに気がついた。
  • 今度はprimesとisPrimeを他のファイル、Prime.hsに移動した。メインのファイルでそのPrimeライブラリーをインポートしたんだ。そうすると、ghc -O3でコンパイルしても、一分の間に計算できなかったんだ。

ここからは詳細を記述する。次のコードを見てくれ。

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

このコードをghc -O3でコンパイルすると、二秒もしないうちに正しい答えである68906が計算された。

 $ ghc -O3 test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
68906
./test  1.24s user 0.02s system 79% cpu 1.574 total

でもね、-O0でコンパイルすると、一分たっても結果を得られないんだ。ghcによって生成されるファイルを消すのに注意したよ。

 $ rm -f ./test ./test.o ./test.hi
 $ ghc -O0 test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
^C
./test  64.34s user 0.94s system 94% cpu 1:08.90 total

中断したよ。-O1オプションは-O3と同じように、うまくいくんだ。

何が起こっているのか、調査してみよう。私はDebug.Trace.traceを使った。isPrimeの引数をトレースしたんだ。

import Debug.Trace

main :: IO ()
main = print $ length $ filter isPrime [10..30]

primes :: (Show a, Integral a) => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: (Show a, Integral a) => a -> Bool
isPrime n = trace (show n) $ n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

最適化オプションが-O3 (や-O1) だと、出力はこんな感じだ。

10
11
3
5
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
7
30
6

この結果は理に適っているよ。(最後の行は素数の和を表示していることに注意してくれ: 11, 13, 17, 19, 23, 29)

お次は、-O0 (やrunhaskell) での結果だ。

10
11
3
5
3
12
13
3
5
3
14
15
3
16
17
3
5
3
18
19
3
5
3
20
21
3
22
23
3
5
3
24
25
3
5
3
26
27
3
28
29
3
5
3
7
3
30
6

この結果をよく見てみると、面白いよ。まず、コードを見ると、2は予めprimesの頭についているよね。3と5は、isPrimeで何度も何度も素数かどうか確認されるんだ。isPrime 11が呼ばれるとき、まず3が素数かどうか調べられて、そして5が素数か調べられる。そのときに、isPrime 3が再度呼ばれるんだ。同様に、ほとんどすべての奇数について、isPrime 3やisPrime 5が何度も何度も呼ばれるんだ。

だから私は、-O0を用いると、primesはキャッシュされなくて、isPrimeが呼ばれる度に[2]から構築されるんだと思った。最初の疑問は、なぜ-O0と-O1で評価の方法が変わるのかということだ

しかしここで、新しい問題が発生した。よろしい、よろしい、-O0なんてめったに使わないからね。ほとんどのケースで-O2や-O3の最適化オプションを使うから、上のような問題は現実問題では現れないと思ったんだ。

でも違ったよ。コードを他のファイルに移動しただけで、また問題が発生した。primesとisPrimeをPrime.hsに移動するだけなんだ。

test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

Prime.hs:

module Prime where

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

今度はなんと、-O1オプション、いや-O3オプションでさえも、結果を得ることが出来なかった。

 $ ghc -O3 test.hs
[1 of 2] Compiling Prime            ( Prime.hs, Prime.o )
[2 of 2] Compiling Main             ( test.hs, test.o )
Linking test ...
 $ time ./test
^C
./test  62.41s user 0.88s system 92% cpu 1:08.23 total

うーん、中断したよ。このやり方が結果に影響するかどうかは分からないけれど、予めPrime.hsを-O3でコンパイルしてみたんだ、ダメだったけどね。ここでまたDebug.Trace.traceを使ってみると、-O3オプションを使っても2と3が何度も何度も現れるんだ。要するに、primesとisPrimeをモジュールに移動するだけで(ここが一番驚いたんだけど)評価方法が変わるせいで、Primeライブラリーを作ることが出来なかった。-O3を使っても動かせなかったからね。

だから2つ目の質問はこうだ。-O3オプションを使ったにも関わらず、どうしてモジュールの中の物は-O0でコンパイルしたように評価されるんだい?

私はとうとう、この奇妙な動作を調査するのに疲れてしまった。モジュールの中で相互参照する定義は使うべきではないと結論づけた。私はPrimeライブラリーを作るのを諦めて、Data.Numbers.Primesを使うようにしたよ。

ありがとう。

http://stackoverflow.com/questions/25958007/

ここで読者に確認してほしいこと (1)

次のコードを-O0と-O1でコンパイルして比較せよ。(生成される.hi、.oをコンパイルする都度消すこと: 以下同様)

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

次のコードを-O0と-O1で比較せよ。

import Debug.Trace

main :: IO ()
main = print $ length $ filter isPrime [10..30]

primes :: (Show a, Integral a) => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: (Show a, Integral a) => a -> Bool
isPrime n = trace (show n) $ n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

次のtest.hsを-O3でコンパイルして実行せよ。
test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

Prime.hs:

module Prime where

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

test.hsとPrime.hsを次のように変更して、-O3でコンパイルして実行せよ。
test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [10..30]

Prime.hs:

module Prime where

import Debug.Trace

primes :: (Show a, Integral a) => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: (Show a, Integral a) => a -> Bool
isPrime n = trace (show n) $ n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

回答

stackoverflowで素晴らしい回答を得ることが出来た。ありがとう、Carl。stackoverflowには優れた人がたくさんいて素晴らしい。

What's going on here is in the following signature:

primes :: Integral a => [a]

The type class prevents primes from being memoized naively. primes :: [Int] is not the same as primes :: [Integer]. And no calculations can be shared, because GHC can't assume all instances of Num follow the same logic. Because of that, every use of primes ends up recalculating the list at the selected type.

But when you enable optimizations, GHC gets a fair bit smarter. When the only use of primes is in the same module as the definition, GHC can optimize it down to the concrete type it's used as. Then calculations are shared across uses of the list.

It only does this within module boundaries, though. Separate compilation of modules means that if primes is exported, it can't be specialized to a concrete type - GHC never knows if the next module it will compile might use primes at a different type.

The simplest way to resolve this is to give primes a concrete type. Then even the naive use of it memoizes.

http://stackoverflow.com/questions/25958007#answer-25960838

和訳してみよう。

ここで起こっていることは、次の型シグネチャのせいだ。

primes :: Integral a => [a]

この型クラスがのせいで、primesがメモ化されないんだ。primes :: [Int] と primes :: [Integer] は違うよね。だから計算は共有されない、どうしてかというと、GHCはNumのすべてのインスタンスが同じロジックに従うと決められないからなんだ。そのせいで、primesを使う度に、その型に対してリストを再計算する羽目になっているんだ。

でも、最適化を有効にすると、GHCはちょっとだけ賢くなる。primesが同じモジュールの中にあるときだけ、GHCは使われている具体的な型に対して最適化できる。そうすると、リストの計算結果は共有されるようになる。

でも、GHCがこれをやってくれるのはモジュールの中に限った話だ。別々のモジュールをコンパイルすると、もしprimesが別のモジュールにエクスポートされると、具体的な型に特定できなくなる。GHCは次にコンパイルしようとしているモジュールがprimesを他の型で使用するかもしれないといったことは分からないからね。

単純な解決方法は、具体的な型を指定すればいい。そうするとprimesはメモ化される。

http://stackoverflow.com/questions/25958007#answer-25960838

ここで読者に確認してほしいこと (2)

次のコードを-O0でコンパイルして実行せよ。

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

primes :: [Integer]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integer -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

再度、型シグネチャを次のように戻して-O0で実行せよ。

primes :: Integral a => [a]

isPrime :: Integral a => a -> Bool

次のtest.hsを-O0でコンパイルして実行せよ。
test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

Prime.hs:

module Prime where

primes :: [Integer]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integer -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

なんと、型クラスIntegral aではなくて、具体的にIntegerに限定するだけで、実行できるようになる。

解説

つまり、こういうことだ。
シグネチャ

primes :: Integral a => [a]

だと、primes :: [Int] と primes :: [Integer] の二通りの使い方がある。簡単にいえば、GHCはこの二通りの使い方のどちらで使われるか分からない。更に、Integralなものが他にある可能性もあるし(例えばユーザーが適当に作ったデータ型)、どういう使われ方をされるか分からないので、メモ化できない。
しかし、mainと同じファイルにprimesが書かれると、状況が簡単になる。つまり、そのファイルの中でprimesがどのように使われるか - [Int]か[Integer]か - といったことは、そのファイルを調べれば一つに分かる。よって、同じファイルでの使い方 ([Int]か[Integer]か) を見れば、メモ化できる。

そうなると、気になるのは次のコードだ。

main :: IO ()
main = do
  print $ length $ filter isPrime ([100000..1000000] :: [Int])
  print $ length $ filter isPrime ([100000..1000000] :: [Integer])

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

つまり、同じファイルなのだが、二通りの使い方をする場合。この場合は、実験してみたところ、メモ化される。すなわち、同じファイルで[Int]と[Integer]で使うことが分かるので、両方のprimesをメモ化するコードを吐くのだろう。


では、primesとisPrimeをモジュールにした時はどうなるか。ghcは、test.hsをコンパイルをする時に、まずインポートしているPrime.hsをコンパイルする。
Prime.hs:

module Prime where

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

ところが、この時点では、これらがIntegralのどの型で用いられるかが決定できない。(これは一見奇妙だ、test.hsのimport文を見てPrime.hsをコンパイルしているはずなのに、なぜtest.hsでの使われ方が分からないのか。まぁ簡単のためだろうか)
型が決定できないから、どういう型についてメモ化すればいいのか分からない。(ここのロジックもいささか危うい。IntegralなものがIntとIntegerであることくらい、分からないものなのだろうか。まぁそういうことなのだろう)
primes、isPrimeの型を

primes :: [Integer]
isPrime :: Integer -> Bool

とすると、当然使われ方はIntegerに決定されるので、メモ化されて効率よく実行できる。

モジュールの中で型クラスで束縛した型のリストには注意したほうが良いだろう。

解決策

では、モジュールの中で primes :: Integral a => [a] のようなものを書くのは諦めるか?実は諦める必要はなくて、非常に簡潔な解決策がある。教えてくれたchi、ありがとう。

Maybe a {-# SPECIALIZE primes :: Int #-} pragma could prod the optimizer to do a better job here. (Not really sure, though). – chi

http://stackoverflow.com/questions/25958007#comment40647503_25960838

このコメントの型は明らかに間違っていて、正しくはこうだ。

{-# SPECIALIZE primes :: [Int] #-}
{-# SPECIALIZE primes :: [Integer] #-}

つまり、このSPECIALIZEという特別なプラグマによって、ghcにprimesがおそらくこう使われるだろうということを伝えるのだ。

ここで読者に確認してほしいこと (3)

次のtest.hsを-O3でコンパイルして実行せよ。
test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime [100000..1000000]

Prime.hs:

module Prime where

{-# SPECIALIZE primes :: [Int] #-}
{-# SPECIALIZE primes :: [Integer] #-}
primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

プラグマの二行を消してみて、実行できるかどうか試してみよ。


この非常にシンプルな方法により、すべてが解決される。
実際、primesというパッケージHaskellにはあるが、そのprimesの定義には、これらのプラグマが書かれていることを確認することができる。


もちろん、SPECIALIZEで指定されていない使われ方には、メモ化されないことを期待するだろう。すなわち、最後の課題はこうだ。次のtest.hsを-O3でコンパイルして実行せよ。
test.hs:

import Prime

main :: IO ()
main = print $ length $ filter isPrime ([100000..1000000] :: [Int])

Prime.hs:

module Prime where

{-# SPECIALIZE primes :: [Integer] #-}
primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || (n `mod` p /= 0 && r)) True primes

上のような場合、ghcがPrime.hsをコンパイルする時点では、primesが[Int]で用いられるのは予期しない使われ方であって、メモ化はされない。
型クラスで型を束縛された物に対してSPECIALIZEプラグマを用いると、指定した型に対応するコードを生成する。これは一般に生成コードを長くするが、実行速度を速くする可能性がある。その上、今回のケースのようにメモ化されるようになることもある。

まとめ

モジュール内で型クラスで束縛した型を持つリストは、どのような型で使われるか分からないので、メモ化されない。SPECIALIZEプラグマで主な使われ方を指定する。もちろん、これで指定していない型で用いることはできる。しかしメモ化はされない。なぜなら、そのモジュールをコンパイルする時点では、SPECIALIZEプラグマで指定した型以外のどのような型で使われるか分からないからだ。
Haskellは、型クラスという優れたシステムを備えている。それは、私がHaskellを好む一つの理由だ。自らが定義したデータ型を、ある型クラスのインスタンスにするだけで、その型クラスのインスタンスならば使える関数を用いることができる。例えば、Ordのインスタンスにすればsortが使えるようになるといった具合だ。ある関数がどれだけ広い型に適用できるかを考えることは、 - 実際にはghcが教えてくれるのだが - とても楽しいことである。しかし、SPECIALIZEという、この楽しさと逆行するようなプラグマを使わざるを得ない場面があるという発見もまた、興味深いことである。