バイナリサーチ実装されてたね

昨日svn updateしたらgc.cが更新されたので
なんぞやと思ったらbsearchが実装されてた。
ruby-devでちらっと知ってたんだけど、実装中のLazySweepが
思いっきりこけたので処理を追ってみた。
 

ソート

ソートしないと始まらないということで該当の箇所を見てみる。

static void
add_heap(void)
{
    RVALUE *p, *pend, *membase;
    long hi, lo, mid;
//省略
    /* A */
    lo = 0;
    hi = heaps_used;
    while (lo < hi) {
        mid = (lo + hi) / 2;
        membase = heaps[mid].membase;
        if (membase < p) {
            lo = mid + 1;
        }
        else if (membase > p) {
            hi = mid;
        }
        else {
            rb_bug("same heap slot is allocated: %p at %ld", p, mid);
        }
    }

    /* B */
    membase = p;
    
    /* C */
    if ((VALUE)p % sizeof(RVALUE) == 0)
        heap_slots += 1;
    /* D */
    else
        p = (RVALUE*)((VALUE)p + sizeof(RVALUE) - ((VALUE)p % sizeof(RVALUE)));
    
    /* E */
    if (hi < heaps_used) {
        MEMMOVE(&heaps[hi+1], &heaps[hi], struct heaps_slot, heaps_used - hi);
    }

    /* F */
    heaps[hi].membase = membase;
    heaps[hi].slot = p;
    heaps[hi].limit = heap_slots;
    pend = p + heap_slots;
//省略

A. lowとhiを用意して新しく確保した配列(Heap)を入れる配列の場所を決めてる。
B. 省略の部分で新しいHeapの配列を確保してるのでそのポインタを一時保存
C. pがRVALUEで割り切れたら、heap_slotsを1増やす。これはその前でmallocする時に余分に一個分確保してるから帳尻あわせ
D. もし割り切れなかったら、ずれてる分前にずらす。この処理の為に余分にmallocしてる。でも、なんでかは知らない。
  mallocでずれることがあるのかな。。。
E. Aで決めた場所に入れる為に後ろの要素を一個ずらす
F. 格納してFinish!
 

イナリサーチ

さて、丁寧にポインタ数値順で並べたHeapをバイナリサーチする。
使う場所はmarkの時に「このObjectってHeap領域にある?」って聞くところ。
consevetiveGCの主役みたいなやつ。

static inline int
is_pointer_to_heap(void *ptr)
{
    register RVALUE *p = RANY(ptr);
    register struct heaps_slot *heap;
    register long hi, lo, mid;

    if (p < lomem || p > himem) return Qfalse;
    if ((VALUE)p % sizeof(RVALUE) != 0) return Qfalse;

    /* check if p looks like a pointer using bsearch*/
    lo = 0;
    hi = heaps_used;
    /* A */
    while (lo < hi) {
        mid = (lo + hi) / 2;
        heap = &heaps[mid];

        /* B */
        if (heap->slot <= p) {

            /* C */
            if (p < heap->slot + heap->limit)
                return Qtrue;
            lo = mid + 1;
        }
        
        /* D */
        else {
            hi = mid;
        }
    }
    return Qfalse;
}

A. loがhiを超えるまで続ける
B. 真ん中のheapのpointerはmark対象のオブジェクト以上か?
C. あれば終わり。無かったら真中+1をloにする。
D. hiをloにする
 
あぁ、美しや。
 

追記

まつもとさんからコメントを頂いた。

ずらしてるのはslotの位置をRVALUEの倍数にする(ので、is_pointer_to_heap()でより速くチェックできる)ためです。

これは以下についてで

D. もし割り切れなかったら、ずれてる分前にずらす。この処理の為に余分にmallocしてる。でも、なんでかは知らない。
  mallocでずれることがあるのかな。。。

はRVALUEの倍数にしている処理で

static inline int
is_pointer_to_heap(void *ptr)
{
//省略
    if ((VALUE)p % sizeof(RVALUE) != 0) return Qfalse;

この部分の判断で使われているそう。
mallocでずれることあるのかというとんちんかんな事を書いてしまって恥ずかしい。。。