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

GC頻発

卒研

たらいまわし関数を動かしたらGCが頻発してぜんぜん計算が進まない件。

(set! tak 
  (lambda (x y z)
   (cond ((< y x) (tak (tak (- x 1) y z)
                       (tak (- y 1) z x)
                       (tak (- z 1) x y)))
         (else y))))
(tak 15 5 0)

たとえばこんなのを評価した場合。cellをどんどん消費して、gcが発生して、cellが回収される。
具体的には一回にcellを500コ確保して、回収されたcellが300コ以下ならcellを増やすプログラムになっている。で、このときにたらいまわし関数を動かすとこんな動作をした。

 0. はじめに500コcellが確保される。
 1. たらいまわし関数を評価
 2. cellが0になる
 3. gc発生
 4. 250コくらいcellを回収
 5. 回収したcellが300コ以下なので、500コcellを追加で確保(cellの数は1000コ)
 6. cellが0になる
 7. gc発生
 8. 750コ!くらいcellを回収
 9. cellを追加で確保しない
 10. 6に戻る

この場合、1000コのcellでたらいまわし関数が評価できることになる。
省メモリなのはよいのだが、GCが頻発して計算が一向に進まない。この現象の解決案の論文はないのかなぁ。ほかの処理系での解決策はどうなっているのだろう。「一度に確保するcellの数を十分大きな値にする」とか、簡単な方法で回避しているのだろうか?

問題定義

一度に確保するcellの個数が少なく、大量に消費して大量に回収される処理でのGCの頻発を防ぐ方法。

回収の履歴とかを見て確保の条件を変えられないだろうか。大量にcellが回収されても追加で確保する条件って何だろ。