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

SIODのGCリーディング(1) - GC Advent Calendar

Garbage Collection Advent Calendarの9日目の記事です。

CRubyのGCで特徴的なヒープの構造がSIODから受け継いだものか調べてみたいと思います。
その前に特徴的なヒープの構造についてちょっと説明しておきましょう。

HotspotVMなんかは、たとえば文字列みたいなオブジェクトは文字列自体も含めてJavaのヒープに格納するんですが、

CRubyの場合は、オブジェクトは固定のサイズとして管理されていて、はみ出すような大きなサイズのデータは別途Cライブラリ側のmalloc(3)を呼び出して確保するようになっています。

オブジェクト用mallocを言語処理系上に作ってしまうか、それともCライブラリ側のmallocに任せてしまうかの違いがあります。
後者の場合、フラグメンテーションに対する対策やキャッシュローカリティはmalloc側におまかせになるわけですね。
まつもとさんはよく「OS側のmalloc作ってる人の方が賢いだろうということでこういう設計にした」とおっしゃられていますが、良し悪しは別にしてGCとしてはわりと特殊な部類に入るのではないかと思っています(たぶん)。

前置きが長くなってしまいましたが、さっそくSIODをコードを見て行きましょう。

/* siod.h */
typedef struct obj* LISP;

どうやらCRubyでいうところの『struct RVALUE』は『struct obj』となるようです。

/* siod.h */
struct obj
{short gc_mark;
 short type;
 union {struct {struct obj * car;
                struct obj * cdr;} cons;
        struct {double data;} flonum;
        struct {char *pname;
                struct obj * vcell;} symbol;
    /* --- 省略 --- */
        struct {long dim;
                char *data;} string;
        struct {long dim;
                struct obj **data;} lisp_array;
        struct {FILE *f;
                char *name;} c_file;}
 storage_as;};

ほほー、この辺の構造はかなり似ていますね。
stringの辺りをみると、『char *data』となっています。
なるほど、たしかに中身の文字列は外出しっぽいですね。

ヒープを作っているところを見てみましょう。

/* slib.c */
long nheaps = 2;
LISP *heaps;

LISP allocate_aheap(void)
{long j,flag;
 LISP ptr,end,next;
 gc_kind_check();
 for(j=0;j<nheaps;++j)
   if (!heaps[j])
     {flag = no_interrupt(1);
      heaps[j] = (LISP) must_malloc(sizeof(struct obj)*heap_size);
      ptr = heaps[j];
      end = heaps[j] + heap_size;
      while(1)
      {(*ptr).type = tc_free_cell;
         next = ptr + 1;
         if (next < end)
           {CDR(ptr) = next;
            ptr = next;}
         else
           {CDR(ptr) = freelist;
            break;}}
      freelist = heaps[j];
      flag = no_interrupt(flag);
      return(sym_t);}
 return(NIL);}

ふむふむ、SIODでも『heaps』と複数系になっているのが興味深いですね。
heap_slotはありませんが、まあ、だいたい同じ構造になってるみたいですね。
拡張したら中のオブジェクトをfreelistで繋いで、と。なるほどなあ。

さて、このヒープ構造はmrubyにもしっかりと継承されていて、SIODのヒープ構造スピリッツが30年の時を経ても脈々と受け継がれていることがわかります。
SIOD、ソースコードが綺麗だし、なかなか面白いので、mark-sweepの辺りも読んでみようかと思います。