言語のGC機能と参照カウント (前編)

ReferenceCounting CircularReference

たまにはちゃんと書いたほうがいいかなと思って書いてみる。

あらまし

原始的な参照カウントベースのガーベジコレクションは、循環参照が発生すると、その参照に含まれるオブジェクトを回収できないという厄介な問題を抱えている。循環参照とは、1つ以上のオブジェクトが環状の参照関係を形成している状態のことで、このような参照を持つオブジェクトは、やがてルート (ある時点で言語ランタイムが管理しているすべてのスコープと考えてもいい) から辿りつけなくなって、解放されずにリークしてしまう。

f:id:moriyoshi:20080528151525p:image

この問題はいろんな LL 言語に見られる。

Perl の場合

use Devel::Peek qw(Dump);

sub make_circular {
    my $foo = {};
    my $bar = {};
    my $baz = {};
    $foo->{'bar'} = $bar;
    $bar->{'baz'} = $baz;
    $baz->{'foo'} = $foo; # <- ここをコメントアウトしてみると?
    return $foo;
}

Dump(make_circular);

for (0 ... 100000) {
    make_circular;
}

出力:

SV = RV(0x8181214) at 0x8194068
  REFCNT = 1
  FLAGS = (TEMP,ROK)
  RV = 0x8152c28
  SV = PVHV(0x8157190) at 0x8152c28
    REFCNT = 2
    FLAGS = (SHAREKEYS)
    IV = 1
    NV = 0
    ARRAY = 0x8174f10  (0:7,  1153
1:1)
    hash quality = 100.0%
    KEYS = 1
    FILL = 1
    MAX = 7
    RITER = -1
    EITER = 0x0
    Elt "bar" HASH = 0x80409109
    SV = RV(0x81811e0) at 0x8152b44
      REFCNT = 1
      FLAGS = (ROK)
      RV = 0x8152d48
      SV = PVHV(0x81571c0) at 0x8152d48
        REFCNT = 1
        FLAGS = (SHAREKEYS)
        IV = 1
        NV = 0
        ARRAY = 0x817d890  (0:7, 1:1)
        hash quality = 100.0%
        KEYS = 1
        FILL = 1
        MAX = 7
        RITER = -1
        EITER = 0x0
        Elt "baz" HASH = 0xffb60ff2
        SV = RV(0x818120c) at 0x8194050
          REFCNT = 1
          FLAGS = (ROK)
          RV = 0x815360c
 1185
 2142
 2736
 3198
 3759
 4221
 4650
 5112
 5574
 5838
 5838
 6432
 6894
 7356
 7818
 8280
 8709
 9303
 9897
[1]  + done       perl test.pl

メモリ使用量が減らないことは次のようにして確認できる*1。PS は Linux のディストリビューションでは標準の procps のものを使っている。

% perl test.pl &  PID=$! && while ps -o sz -p $PID | grep -v "SZ"; do :; done

PHP (5.2) の場合

<?php
function &make_circular() {
    $foo = array();
    $bar = array();
    $baz = array();
    $foo['bar'] = &$bar; # <- ここの参照をはずしてみると?
    $bar['baz'] = &$baz;
    $baz['foo'] = &$foo;
    return $foo;
}

$tmp = &make_circular();
debug_zval_dump($tmp);

for ($i = 100000; --$i >= 0;) {
    make_circular();
    printf("%d\n", memory_get_usage());
}
?>

出力:

array(1) refcount(1){
 ["bar"]=>
 &array(1) refcount(2){
   ["baz"]=>
   array(1) refcount(1){
     ["foo"]=>
     array(1) refcount(2){
       ["bar"]=>
       &array(1) refcount(2){
         ["baz"]=>
         array(1) refcount(1){
           ["foo"]=>
           array(1) refcount(2){
             ["bar"]=>
             *RECURSION*
           }
         }
       }
     }
   }
 }

9928
0656
1136
1616
2096
2576
3064
3568
4048
4528

Ruby の場合

Ruby は参照カウントではなくコンサバなマーク&スイープなGCを採用しているので、循環参照があってもきちんと回収はされる。(サンプルコードが悪いのは勘弁)

def make_circular
    foo = {}
    bar = {}
    baz = {}
    foo['bar'] = bar
    bar['baz'] = baz
    baz['foo'] = foo
    return foo
end

# GC.disable  # <- コメントをはずしてみると?

10000.times do
    make_circular()
end

% ruby test.rb &  PID=$! && while ps -o sz -p $PID | grep -v "SZ"; do :; done

出力:

  788
  887
  887
  ... (ずっと同じ値)

Python (CPython) の場合

CPython は循環参照検出つきの参照カウントベースのガーベジコレクションを採用しているので、ちょっと興味深い挙動が垣間見れる。

import gc

def make_circular():
    foo = {}
    bar = {}
    baz = {}
    foo['bar'] = bar
    bar['baz'] = baz
    baz['foo'] = foo # <- (1)
    return foo

# gc.disable() # <- (2)

for i in xrange(0, 1000000):
    make_circular()

まず、上のコードを例によって素直に走らせると、

% python test.py &  PID=$! && while ps -o sz -p $PID | grep -v "SZ"; do :; done
[1] 3968
  840
 1128
 1128
 1128
 1128
 1128
 ...

のようになって、きちんと循環コレクタ (cycle collector) が動いていることが分かる。

(2) のコメントを外すと、今度は

% python test.py &  PID=$! && while ps -o sz -p $PID | grep -v "SZ"; do :; done
[1] 4034
  841
 1389
 4574
 5159
 6914
 7824
10359
14129
 ...

のようにメモリ使用量はどんどん増えていく。

(1) をコメントアウトし、(2) のコメントを外した状態にすると、今度は

  938
 1128
 1128
 1128
 1128
 1128
 ...

という結果になる。gc.disable() で停止するのは循環コレクタで、循環コレクタが動いていなくても、従来通り参照カウントだけでオブジェクトの破棄タイミングが明らかな場合は都度解放するようになっているから。(厳密にいうと違うけど)

(中編につづく)

*1:mstat はビルドによっては使えないため