GHCにおけるヒープとスタック

Haskell

先ほど、このような記事をQiitaに書いた。

Haskellを書いていて、再帰関数の終了条件設定をミスって無限ループさせてしまうことが何回かあったのだが、CPUだけでなくメモリも無限に持って行かれ、スワップを使い始めたあたりからキーボードへの応答も著しく鈍くなり、とにかく大変な目にあった。

どうやら再帰関数の実行によってサンクが無限増殖し、そいつがヒープメモリを肥大化させているようだったので、RTSオプションでヒープの上限を与える方法を調べたのだった。

さて、RTSオプションのドキュメントを読むと、以下のような記述があることに気付いた。

  • -Ksize [Default: 80% physical memory size] Set the maximum stack size for an individual thread to size bytes.
  • -Msize [Default: unlimited] Set the maximum heap size to size bytes.

-Mオプションはヒープメモリサイズの上限である。こいつがデフォルトで青天井なので、サンクの無限増殖で大変な目にあったのだった。

一方、-Kオプションはスタックサイズの上限であり、こいつはデフォルトで(物理メモリの8割という大容量とはいえ)上限が設定されている。

では、ヒープとスタックの違いはなんだろうか？と思って調べてみた。

結論から言うと、どうやら以下のようなことらしい。

  • ヒープはサンク(など)が置かれる
  • スタックはサンクを評価する時に使われる

上記のスレでは定番のfoldlを用いて説明されている。

遅延評価版のfoldlでは以下のように評価が進む。

  foldl add 0 [1,2,3,4]
= foldl add (add 0 1) [2,3,4]
= foldl add (add (add 0 1) 2) [3,4]
= foldl add (add (add (add 0 1) 2) 3) [4]
= foldl add (add (add (add (add 0 1) 2) 3) 4) []
= add (add (add (add 0 1) 2) 3) 4

ここで、addは(+)の別名とする(見やすさのため)。

上記で積み上がるaddの列は未評価の式、つまりサンクであり、ヒープに置かれる。よって、例えば

foldl add 0 $ repeat 0

とするとサンクの無限増殖によってヒープが肥大化する。この場合、いくらスタックサイズを制限してもどうしようもない。

さて、foldlの評価ではaddが積み上がったサンクがさらに評価されていくが、ここでadd(というか(+))は正格評価である。よって、

  1. (add X 4)を評価する。
  2. Xを評価する。そのためにaddと4は一旦脇においておく。
  3. Xは(add Y 3)である。これを評価する。
  4. Yを評価する。そのためにaddと3は一旦脇においておく。
  5. ...

となる。ここで、評価を進めるために「一旦脇においておく」場所が(多分)スタックとなる。よって、リストに要素が増えれば増えるほどスタックも深く、大きくなり、そのうち上限に当たって死ぬ。

同様の議論はHaskell-cafe Stack, Heap and GHCでもされていた。

ちなみに正格版のfoldl'では以下のように評価が進む。

  foldl' add 0 [1,2,3,4]
= foldl' add 1 [2,3,4]    -- (add 0 1)が評価される
= foldl' add 3 [3,4]      -- (add 1 2)が評価される
= foldl' add 6 [4]        -- (add 3 3)が評価される
= foldl' add 10 []        -- (add 6 4)が評価される
= 10

正格版ではサンクは肥大化しないし、評価も1ステップごとに行われるのでスタックも肥大化しない。よって、

foldl' add 0 $ repeat 0

としてもメモリは食われない。ただCPUがぶん回るだけである。