Ruby 垃圾回收原理浅析

zhuoerri · 2022年04月26日 · 最后由 WilliePatel 回复于 2025年05月08日 · 1273 次阅读

前言

本人水平有限,如有错误,欢迎指正和补充。

本文会用自问自答的形式,用【公司裁员】打比方,结合 Ruby 3.1 源码,科普 Ruby 垃圾回收的基本原理。内容包含:Ruby 内存模型,标记回收算法,分代回收,增量回收,碎片整理,最后借助最新的 Variable Width Allocation,列举一下 局部性原理。

Ruby 内存模型

Q: Ruby 对象在内存里是怎么存储管理的?

每个 Ruby 对象占用一个slot,一个slot 在 64 位的机器上占 40 字节,多个slot聚成一个 Rubypage。所有page组成了Ruby HEAP。如果 Ruby 对象太大,例如一个很长的 String,40 个字节放不下。则在总HEAP里 malloc 一块额外内存来存储。如下图,第一个slot指向了额外数据。

┌──────────────────────────────────────────────────────────────────────────────────┐
│                                                                                  │
│   HEAP  ┌────────────────────────────────────────────────────────────────────┐   │
│         │    RUBY HEAP                                                       │   │
│         │ ┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐  │   │
│         │ │ page              │ │ page              │ │ page              │  │   │
│         │ │                   │ │                   │ │                   │  │   │
│         │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │  │   │
│         │ │ │slot │   │slot │ │ │ │slot │   │slot │ │ │ │slot │   │slot │ │  │   │
│      ┌──┼─┼─┤     │   │     │ │ │ │     │   │     │ │ │ │     │   │     │ │  │   │
│      │  │ │ └─────┘   └─────┘ │ │ └─────┘   └─────┘ │ │ └─────┘   └─────┘ │  │   │
│      │  │ │                   │ │                   │ │                   │  │   │
│      │  │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │ │ ┌─────┐   ┌─────┐ │  │   │
│      │  │ │ │slot │   │slot │ │ │ │slot │   │slot │ │ │ │slot │   │slot │ │  │   │
│      │  │ │ │     │   │     │ │ │ │     │   │     │ │ │ │     │   │     │ │  │   │
│      │  │ └─┴─────┴───┴─────┴─┘ └─┴─────┴───┴─────┴─┘ └─┴─────┴───┴─────┴─┘  │   │
│      │  │                                                                    │   │
│      │  └────────────────────────────────────────────────────────────────────┘   │
│      │                                                                           │
│      │                                                                           │
│      │                                                                           │
│     ┌▼───────────────┐                                                           │
│     │ extra data     │                                                           │
│     │                │                                                           │
│     └────────────────┘                                                           │
│                                                                                  │
│                                                                                  │
└──────────────────────────────────────────────────────────────────────────────────┘

heap 和 page 的源码在 gc.c , 精简后如下

typedef struct rb_heap_struct {
    struct heap_page *free_pages;
    struct list_head pages;  /* 存放的所有pages, 指向了第一个page */
    struct heap_page *sweeping_page; /* 用来迭代每个pages的临时指针 */
    /* 省略 */
    size_t total_pages;      /* 总page数 */
    size_t total_slots;      /* 总slot数 */
} rb_heap_t;

struct heap_page {
    short total_slots;  /* page内总slot数 */
    short free_slots;  /* page内空闲的slot数 */
    /* 省略 */
    struct heap_page *free_next;  /* 下一个可用的page */
    RVALUE *start; /* page内第一个slot地址 */
    RVALUE *freelist; /* page内空闲的slot列表 */
    /* 省略 */
}

Q: 还是不懂,能打个比方吗?

可以用【公司裁员】来比喻 Ruby 垃圾回收。page可以看作公司【办公室】,slot 看作【工位】, Ruby对象看作【员工】,每个【员工】占一个【工位】。如果一个【工位】不够放私人物品,则在外部【储物柜】(总HEAP) 存放额外数据

Q: 如果【工位】(slot) 不够了?

裁掉对公司无用的【员工】(Ruby对象), 空出【工位】(slot) 给【新员工】(新Ruby对象)

Q: 如果裁员后【工位】(slot) 还是不够?

租更多的【办公室】(向操作系统要更多的 Rubypage)

Q: 什么时候退租【办公室】(page),还内存给操作系统?

空闲【工位】(slot) 的空置率最多 65%。如果裁员完空余【工位】(slot) 超过 65% 的,则超出 65% 的部分是可以退租的额度。Ruby 会在退租额度内,选择完全空置的【办公室】(page) 退租。Ruby 管这种完全空置的pagetomb page, 管还有 Ruby 对象的pageeden page.

是否还内存给操作系统的源码也在 gc.c, 精简后如下

/* 在确定了裁员名单后,正式裁员前。会调这个gc_marks_finish函数 */
static int
gc_marks_finish(rb_objspace_t *objspace)
{
  /* 省略 */

  size_t total_slots = heap_allocatable_pages * HEAP_PAGE_OBJ_LIMIT + heap->total_slots;
  size_t sweep_slots = total_slots - objspace->marked_slots; /* 总slot数减去保留的slot数,就是当前空闲的slot数 */
  size_t max_free_slots = (size_t)(total_slots * gc_params.heap_free_slots_max_ratio); /* heap_free_slots_max_ratio默认0.65, 总slot数乘以 0.65 就是空闲slot数的上限 */

  /* 省略 */

  /* 【裁员的slot数】 减去 【空置slot数上限】 , 再除以【每个page内单位slot数】这个单位。最后算出的heap_pages_freeable_pages 就是可以还给操作系统的page数量 */
  if (sweep_slots > max_free_slots) {
      heap_pages_freeable_pages = (sweep_slots - max_free_slots) / HEAP_PAGE_OBJ_LIMIT;
  }
  else {
      heap_pages_freeable_pages = 0;
  }
}

/* 裁员完毕后,会调这个 heap_pages_free_unused_pages函数 */
static void
heap_pages_free_unused_pages(rb_objspace_t *objspace)
{
  /* 省略 */

  /* 如果有退租slot数的额度*/
  if (has_pages_in_tomb_heap) {
        for (i = j = 1; j < heap_allocated_pages; i++) {
            struct heap_page *page = heap_pages_sorted[i];

            /* 如果还有退租slot数的额度,并且当前page是完全空置, 则退还page给操作系统 */
            if (page->flags.in_tomb && page->free_slots == page->total_slots) {
                heap_unlink_page(objspace, heap_tomb, page);
                heap_page_free(objspace, page);
            }

            /* 省略 */
        }
   }
}

Q: 怎么判断哪些【员工】(Ruby对象) 是无用的,需要被裁?

用标记回收算法,具体见下一节

标记回收算法

Q: 标记回收算法的流程是怎样的?

还是以公司裁员为例子,分两个阶段:

  1. 第一个阶段 Mark,标记有用。HR 从最顶层的总裁问起,觉得谁有用?总裁觉得副总裁 A 和副总裁 B 有用。HR 把副总裁 A 和副总裁 B 标记为有用。然后 HR 再去问副总裁 A 和副总裁 B,觉得谁有用?副总裁们觉得经理 C 和经理 D 有用........。以此类推,递归地标记有用和问下去。最后没有被问到的人,没有被标记有用的人,就可以准备裁了
  2. 第二个阶段 Sweep,回收工位。找到所有未标记有用的人,裁掉,让出【工位】(slot)。

标记回收的源码也在 gc.c, 精简后如下

/* 标记obj对象有用 */
static void
gc_mark_ptr(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  if (!gc_mark_set(objspace, obj)) return; /* 如果已经标记过,则return;否则标记成功,接着执行 */

  /* 省略 */

  gc_grey(objspace, obj); /* 把obj推入栈中,方便之后问它引用了哪些子对象, 觉得哪些子对象有用 */

  /* 省略 */
}

/* 推入栈中 */
static void
gc_grey(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  push_mark_stack(&objspace->mark_stack, obj);
}

/* 之后从栈中取出对象 */
static inline int
gc_mark_stacked_objects(rb_objspace_t *objspace, int incremental, size_t count)
{
  /* 省略 */

  while (pop_mark_stack(mstack, &obj)) {
     /* 省略 */

     /* 从栈中取出obj,再递归的标记obj引用了的子对象。gc_mark_children之后又会递归调用上面的 gc_mark_ptr 函数标记子对象*/
     gc_mark_children(objspace, obj);
  }

  /* 省略 */
}


/* 标记完后,对每个page调 gc_page_sweep 函数进行回收检查 */
static inline void
gc_sweep_page(rb_objspace_t *objspace, rb_size_pool_t *size_pool, rb_heap_t *heap, struct gc_sweep_context *ctx)
{
  /* 省略 */

  /* page内第一个slot的地址,存在p里 */
  p = sweep_page->start;

  /* page内用一个位图数组mark_bits来标记每个slot是否有用 */
  bits = sweep_page->mark_bits;

  /* 循环检查每个slot对应的位图 */
  for (i=0; i < HEAP_PAGE_BITMAP_LIMIT; i++) {
    bitset = ~bits[i];  /* 把位图取反,就是没有被标记的slot */
    if (bitset) {

        /* 如果取反的位图数组有未标记的slot,调gc_sweep_plane回收 slot, 函数定义见下方 */
        gc_sweep_plane(objspace, heap, (uintptr_t)p, bitset, ctx);
    }
    p += BITS_BITLENGTH;
  }

  /* 省略 */
}

static inline void
gc_sweep_plane(rb_objspace_t *objspace, rb_heap_t *heap, uintptr_t p, bits_t bitset, struct gc_sweep_context *ctx)
{
   /* 省略 */

   do {
        VALUE vp = (VALUE)p;

        /* 取反位图的右边最低位是1,说能原位图右边最低位是0,说明该位对应的slot没被标记,可以被回收 */
        if (bitset & 1) {
          /* 省略 */

          obj_free(objspace, vp) /* 删除slot上的变量,清空slot */

          /* 省略 */
        }

        /* 循环找下一个slot,取反位图bitset右移到下一位 */
        p += slot_size;
        bitset >>= slot_bits;
  }while (bitset);
}

Q: 每次裁员要从头问一遍所有人,有什么办法优化吗?

用 Ruby 2.1 新增的分代回收算法,具体见下一节

分代回收

Q: 分代回收算法的流程是怎样的?

还是以公司裁员打比方。分为【大裁员】(Major/Full) 和【小裁员】(Minor)。

【大裁员】(Major/Full) 还是和之前一样,问一遍所有人。

【小裁员】(Minor) 会默认一些【员工】(Ruby对象) 有用,跳过对这些【员工】(Ruby对象) 的标记和询问。

Q: 哪些【员工】(Ruby对象) 会默认有用?

被标记过 3 次的,即躲过三次裁员的【老员工】(Ruby 管这种对象叫old object) 默认有用。同时,【老员工】(old object) 觉得有用的子员工,也自动变为【老员工】, 形成了一个老员工帮。

例如,某个员工之前躲过了两次裁员。当第三次裁员时,HR 询问该员工觉得谁有用时,发现算上目前这次,该员工已经躲过三次裁员了,就把该员工标记为【老员工】(old object)。该员工觉得员工 A 和员工 B 有用,则 HR 把员工 A 和员工 B 也标记为【老员工】(old object)。以此类推,员工 A 和员工 B 又觉得员工 C 和员工 D 有用,则 HR 把员工 C 和员工 D 也标记为【老员工】.....

当第四次【小裁员】(minor) 时,HR 默认这帮老员工有用,跳过对这些老员工的标记和询问

Q: 上面的例子,如果在第三次裁员后,第四次裁员前,新招了一个新员工 E,某个【老员工】(old object) 觉得新员工 E 有用。但 HR 跳过了老员工的询问,不知道员工 E 有用,第四次裁员时误裁掉员工 E。怎么办?

【老员工】(old object) 主动给 HR 说,下次裁员时,强制询问我谁有用。HR 给【老员工】(old object) 标记下次【强制询问】的标签。等下次裁员结束,保住了员工 E 后,就可以清除【强制询问】的标签。

Ruby 里这种主动标记强制询问的方法叫 write barrier。Ruby 管这种主动标记强制询问的对象叫 write barrier protected object

Q: 所有的员工都会这么主动帮新员工吗?

很可惜,不会,因为要兼容第三方 c 扩展库。Ruby 给新函数加上了write barrier 行为,但第三方 c 扩展使用的可能是不带write barrier的老函数

Q: 那怎么办?

HR 把这些不主动的员工标记为【老油条】(Ruby 里叫 write barrier unprotected object或者shady)。就算【老油条】混成了【老员工】,HR 每次裁员时,还是要强制标记和询问【老油条】(write barrier unprotected object/shady)

分代回收的源码还是在 gc.c , 精简后如下

/* 标记开始函数 */
static void
gc_marks_start(rb_objspace_t *objspace, int full_mark)
{
  /* 是否大裁员 Major/Full */
  if (full_mark) {
    /* 大裁员 */
    objspace->flags.during_minor_gc = FALSE;


    for (int i = 0; i < SIZE_POOL_COUNT; i++) {
        /* 清空之前标记的【是否有用】【是否强制询问】【是否老员工】等标志 */
        rgengc_mark_and_rememberset_clear(objspace, SIZE_POOL_EDEN_HEAP(&size_pools[i]));
    }
  }
  else {
    /* 小裁员 */
    objspace->flags.during_minor_gc = TRUE;

    for (int i = 0; i < SIZE_POOL_COUNT; i++) {

       /* 先把需要【强制询问】或【老油条】的对象标记询问 */
       rgengc_rememberset_mark(objspace, SIZE_POOL_EDEN_HEAP(&size_pools[i]));
    }
  }

  /* 从顶层对象开始标记询问,gc_mark_roots会调用上一节源码里的 gc_mark_ptr */
  gc_mark_roots(objspace, NULL);
}

/* 清空各种标记位图数组 */
static void
rgengc_mark_and_rememberset_clear(rb_objspace_t *objspace, rb_heap_t *heap)
{
    struct heap_page *page = 0;

    /* mark_bits是【是否有用】的位图数组, uncollectible_bits是【是否老员工/old object】的位图数组, marking_bits是时是否【强制询问】的位图数组; pinned_bits先忽略,讲到碎片整理一节时再说 */
    list_for_each(&heap->pages, page, page_node) {
    memset(&page->mark_bits[0],       0, HEAP_PAGE_BITMAP_SIZE);
    memset(&page->uncollectible_bits[0], 0, HEAP_PAGE_BITMAP_SIZE);
        memset(&page->marking_bits[0],    0, HEAP_PAGE_BITMAP_SIZE);
        memset(&page->pinned_bits[0],     0, HEAP_PAGE_BITMAP_SIZE);

        /* 省略 */
    }
}

/* 标记【强制询问】或【老油条】对象 */
static void
rgengc_rememberset_mark(rb_objspace_t *objspace, rb_heap_t *heap)
{

        /* 省略 */

        /循环检查每个page/
        list_for_each(&heap->pages, page, page_node) { 
                if (page->flags.has_remembered_objects | page->flags.has_uncollectible_shady_objects) { 
                        RVALUE *p = page->start;

                        /* marking_bits 是【强制询问】的位图数组,uncollectible_bits是【老员工】的位图数组,wb_unprotected_bits 是【老油条】的位图数组 */
                        bits_t *marking_bits = page->marking_bits;
                        bits_t *uncollectible_bits = page->uncollectible_bits;
                        bits_t *wb_unprotected_bits = page->wb_unprotected_bits;

                        for (j=0; j<HEAP_PAGE_BITMAP_LIMIT; j++) { 
                                /* bits代表(【强制询问】或者(【老员工】并且【老油条】)) */
                                bits[j] = marking_bits[j] | (uncollectible_bits[j] & wb_unprotected_bits[j]);

                                /* 清空【强制询问】位图数组 */
                                marking_bits[j] = 0;
                        } 

                        /* 省略 */


                        for (j=1; j < HEAP_PAGE_BITMAP_LIMIT; j++) { 
                                bitset = bits[j];
                                /* 检查每个bits位图数组 */
                                rgengc_rememberset_mark_plane(objspace, (uintptr_t)p, bitset);
                                p += BITS_BITLENGTH;
                        } 
                } 
        } 
}

/* 询问有【强制询问】或【老油条】标签的对象 */
static inline void
rgengc_rememberset_mark_plane(rb_objspace_t *objspace, uintptr_t p, bits_t bitset)
{
    if (bitset) {
        do {
            if (bitset & 1) {
                VALUE obj = (VALUE)p;


                /* 标记询问有用的子对象,gc_mark_children 在上一节的源码里也出现过 */
                gc_mark_children(objspace, obj);
            }
            p += sizeof(RVALUE);
            bitset >>= 1;
        } while (bitset);
    }
}

/* 标记obj对象有用 */
static void
gc_mark_ptr(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  /* 检查是obj的父标对象是谁,即是谁觉得obj有用 */
  rgengc_check_relation(objspace, obj);

  if (!gc_mark_set(objspace, obj)) return; 

  /* 省略 */

  gc_grey(objspace, obj); 

  /* 省略 */
}

/* 检查obj的父标对象是谁,是谁觉得obj有用 */
static void
rgengc_check_relation(rb_objspace_t *objspace, VALUE obj)
{       
        const VALUE old_parent = objspace->rgengc.parent_object;

        /* 如果父标记对象是【老员工】old object */
        if (old_parent) {

                /* 省略 */

                /* 把当前对象obj也标记为【老员工】old object */
                RVALUE_AGE_SET_CANDIDATE(objspace, obj);
        }

        /* 省略 */
} 

/* 标记回收结束时,对page调用gc_setup_mark_bits函数 */
static void
gc_setup_mark_bits(struct heap_page *page)
{
    /* copy oldgen bitmap to mark bitmap */
    /* 把【老员工】uncollectible_bits位图数组复制给【是否有用】mark_bits位图数组,即老员工 old object默认有用 */
    memcpy(&page->mark_bits[0], &page->uncollectible_bits[0], HEAP_PAGE_BITMAP_SIZE);
}

/* 变量a引用了变量b,觉得变量b有用时,触发writebarrier, 把变量a标记为【强制询问】 */
void
rb_gc_writebarrier(VALUE a, VALUE b)
{
    /* 省略 */

    if (!RVALUE_OLD_P(a) || RVALUE_OLD_P(b)) {
        // do nothing
    }
    else {
        /* 如果a是【老员工】(old object),b不是【老员工】(old object), 则把a标记为【强制询问】 */
        gc_writebarrier_generational(a, b, objspace);
    }

    /* 省略 */
}


/* 把变量a标记为【强制询问】 */
static void
gc_writebarrier_generational(VALUE a, VALUE b, rb_objspace_t *objspace)
{
  /* 省略 */

  rgengc_remember(objspace, a);

  /* 省略 */
}

/* 把obj标记为【强制询问】 */
static int
rgengc_remember(rb_objspace_t *objspace, VALUE obj)
{
  /* 省略 */

  return rgengc_remembersetbits_set(objspace, obj);
}

/* 把obj标记为【强制询问】 */
static int
rgengc_remembersetbits_set(rb_objspace_t *objspace, VALUE obj)
{
    struct heap_page *page = GET_HEAP_PAGE(obj);
    bits_t *bits = &page->marking_bits[0]; /* 【强制询问】的位图数组是page内的 marking_bits */

   /* 省略 */

   page->flags.has_remembered_objects = TRUE;
   MARK_IN_BITMAP(bits, obj); /* 把obj对应的marking_bits位置标为1 */
   return TRUE;
}

Q: 【小裁员】(minor) 跳过【老员工】(old object) 减少了标记的时间。但【大裁员】(major/full) 依然要问一遍所有人,有什么办法优化【大裁员】(major/full) 吗?

用 Ruby 2.2 新加的增量回收算法,具体见下一节

增量回收

Q: 增量回收算法是怎么优化【大裁员】(major/full) 流程的?

【大裁员】(major/full) 需要问一遍所有人,这个客观事实是改不了的。增量回收算法的优化思路是:通过增量标记询问,尽量减少对员工们正常干活的阻塞。

在 Ruby 2.2 增量回收算法出现前。【大裁员】(major/full) 时,员工们都必须停下手头的工作,等裁员结果出来,才能继续工作。

Ruby 2.2 增量回收算法出来后。除了原先【已标记】(Ruby 叫black object) 和【未标记】(Ruby 叫white object) 这两种状态,HR 新增了一种【询问中】(Ruby 叫grey object) 状态。

例如,第一天 HR 把总裁标记为【询问中】(grey object),总裁觉得副总裁 A 和副总裁 B 有用。HR 把副总裁 A 和副总裁 B 标记为【询问中】,把总裁标记为【已标记】(black object)。就结束了第一天的标记,员工可以接着干活。 第二天,HR 在询问副总裁 A 和副总裁 B。副总裁们觉得经理 C 和经理 D 有用,HR 把经理 C 和经理 D 标记为【询问中】(grey object), 把副总裁们标记为【已标记】(black object)。结束了第二天的标记,员工可以接着干活。以此循环递归,每天增量的询问一些【询问中】的员工,直到没有【询问中】(grey object) 的员工。只剩【已标记】和【未标记】的员工。

Q: 和分代回收时同样的问题:如果某个员工 A 被标记为【已标记】(black object), 然后新招了一个员工 B,员工 A 觉得员工 B 有用。但因为 HR 不会再询问员工 A 了,不知道员工 B 有用,导致员工 B 被误裁,怎么办?

跟分代回收类似的解决方案,writebarrier。员工 A 主动把跟 HR 说把员工 B 从【未标记】(white object) 改为【询问中】(grey object)。实际上分代回收的【强制询问】和增量回收的【询问中】用的是同一个标记,同一个位图数组 marking_bits,因为两者的作用一致,都是让 HR 下次询问自己一次。

Q: 所有的员工都会主动帮新员工吗?

很可惜,不会,原因和分代回收时一样,为了兼容第三方 c 扩展库。必须用别的办法对付【老油条】(writebarrier unprotected object)

Q:那怎么办?

HR 在【大裁员】(major/full) 最终标记结束前,会最后再问一遍所有的【老油条】(writebarrier unprotected object),以防漏掉了哪个有用的员工。

增量回收的源码还是在 gc.c

/* 标记了有用 mark_bits, 没标记强询问 marking_bits 的就是black object*/
static inline int
RVALUE_BLACK_P(VALUE obj)
{
    return RVALUE_MARKED(obj) && !RVALUE_MARKING(obj);
}

#if 0
/* 标记了有用 mark_bits, 同时标记了下次强制询问 marking_bits的就是grey object */
static inline int
RVALUE_GREY_P(VALUE obj)
{
    return RVALUE_MARKED(obj) && RVALUE_MARKING(obj);
}
#endif

/* 还没被标记有用mark_bits的就是white object */
static inline int
RVALUE_WHITE_P(VALUE obj)
{
    return RVALUE_MARKED(obj) == FALSE;
}

/* 增量回收中,a觉得b有用的writebarrier函数 */
static void
gc_writebarrier_incremental(VALUE a, VALUE b, rb_objspace_t *objspace)
{
    gc_report(2, objspace, "gc_writebarrier_incremental: [LG] %p -> %s\n", (void *)a, obj_info(b));

    if (RVALUE_BLACK_P(a)) {
        if (RVALUE_WHITE_P(b)) {
            if (!RVALUE_WB_UNPROTECTED(a)) {
                /* 变量a是black,变量b是white时,把变量b标记为grey */
                gc_report(2, objspace, "gc_writebarrier_incremental: [IN] %p -> %s\n", (void *)a, obj_info(b));
                gc_mark_from(objspace, b, a);
            }
        }
        else if (RVALUE_OLD_P(a) && !RVALUE_OLD_P(b)) {
            if (!RVALUE_WB_UNPROTECTED(b)) {
                /* 变量a是老对象,变量b是新对象时,把变量b标记为老对象 */
                gc_report(1, objspace, "gc_writebarrier_incremental: [GN] %p -> %s\n", (void *)a, obj_info(b));
                RVALUE_AGE_SET_OLD(objspace, b);

                if (RVALUE_BLACK_P(b)) {
                    /* 如果变量b是black时,改为grey,下次强制询问 */
                    gc_grey(objspace, b);
                }
            }
            else {
                gc_report(1, objspace, "gc_writebarrier_incremental: [LL] %p -> %s\n", (void *)a, obj_info(b));
                /* 变量b是【老油条】writebarrier unprotected, 标记b为【老员工】old object */
                gc_remember_unprotected(objspace, b);
            }
        }

        /* 省略 */
    }
}

/* 标记结束前调用的函数 */
static int
gc_marks_finish(rb_objspace_t *objspace)
{
  #if GC_ENABLE_INCREMENTAL_MARK
  /* 省略 */

  /* 增量标记结束前,再询问一遍【老油条】writebarrier unprotected object, 以防漏掉有用变量 */
  /* gc_marks_wb_unprotected_objects 函数会再询问一遍所有writebarrier unprotected object */
  for (int i = 0; i < SIZE_POOL_COUNT; i++) {
    gc_marks_wb_unprotected_objects(objspace, SIZE_POOL_EDEN_HEAP(&size_pools[i]));
  }
  #endif
}

Q: 所以一个【员工】(Ruby对象) 总共有哪些标记?

是否有用 (mark_bits), 是否老员工 (uncollectible_bits), 是否老油条 (wb_unprotected_bits), 是否下次强制询问 (marking_bits), 是否钉子户 (pinned_bits)

Q: 裁员完后,不换一下工位,让员工间坐得更近,空出更多的【办公室】(page) 吗?

可以,Ruby 2.7 加了碎片整理算法,详情见下一节

碎片整理

Q: 碎片整理算法的流程是怎样的?

以公司裁员打比方,必须先进行一次【大裁员】(major/full) 后,再执行如下两个阶段:

  1. 第一阶段,转移工位。两个 HR,一个负责在左边,从左往右找空出的【工位】(slot), 另一个负责在右边,从右往左找【员工】(Ruby对象), 各自找到合适的【工位】(slot) 和【员工】(Ruby对象) 后,把员工转移到新工位,并在原工位上留下新工位的字条。以此循环,直到找不到合适的工位或员工,两个 HR 碰到了一起。
  2. 第二阶段,更新引用。通知所有员工,根据原工位留的字条,记一下对应员工的新工位。

具体例子见下图

6个工位,4个员工,A和B记得C和D在5和6号工位
                     ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
                        Before Compaction   │       
                     └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
               ┌─────┬─────┬─────┬─────┬─────┬─────┐
 Slot Index    │  1  │  2  │  3  │  4  │  5  │  6  │
               ├─────┼─────┼─────┼─────┼─────┼─────┤
Slot Contents  │  A  │  B  │Empty│Empty│  C  │  D  │
               │     │     │     │     │     │     │
               └─────┴─────┴─────┴─────┴─────┴─────┘
                  │     │                 ▲     ▲   
                  │     │                 │     │   
                  └─────┼─────────────────┘     │   
                        └───────────────────────┘  
第一阶段,C和D转移工位到3和4后,在原工位留下字条
                     ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
                         After Compaction   │       
                     └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
               ┌─────┬─────┬─────┬─────┬─────┬─────┐
 Slot Index    │  1  │  2  │  3  │  4  │  5  │  6  │
               ├─────┼─────┼─────┼─────┼─────┼─────┤
Slot Contents  │  A  │  B  │  D  │  C  │MOVED│MOVED│
               │     │     │     │     │TO 4 │TO 3 │
               └─────┴─────┴─────┴─────┴─────┴─────┘
                  │     │                 ▲     ▲   
                  │     │                 │     │   
                  └─────┼─────────────────┘     │   
                        └───────────────────────┘ 
第二阶段,员工A和B根据字条,更新一下记的员工C和D的工位位置
                     ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
                        After Ref Updates   │       
                     └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─        
               ┌─────┬─────┬─────┬─────┬─────┬─────┐
 Slot Index    │  1  │  2  │  3  │  4  │  5  │  6  │
               ├─────┼─────┼─────┼─────┼─────┼─────┤
Slot Contents  │  A  │  B  │  D  │  C  │MOVED│MOVED│
               │     │     │     │     │TO 4 │TO 3 │
               └─────┴─────┴─────┴─────┴─────┴─────┘
                  │     │     ▲     ▲               
                  │     │     │     │               
                  └─────┼─────┼─────┘               
                        └─────┘   

Q: 所有员工都会乖乖换工位吗?

很可惜,不会,原因和分代回收一样,为了兼容第三方 c 扩展库。碎片整理时会跳过这些【钉子户】(Ruby 内叫pinned object)

由于原理很简单,更多的难点是在为了升级第三方 c 扩展库,而提供的rb_gc_location, rb_data_type_struct中的dcompact回调函数指针等,本节省略源码解析

Q: 碎片整理除了空出更多的【办公室】(page), 还有别的好处吗?

有,根据局部性原理,能优化读取速度。

局部性原理

Q: 什么是局部性原理?

cpu 读取内存数据时,如果是读取相邻的顺序数据,更有机会被 L1,L2,L3 缓存命中,提高性能。

Q: 除了碎片整理,Ruby 垃圾回收中还有哪些优化用到了局部性原理吗?

Ruby 3.1 新加了 Variable Width Allocation, 但跟 jit 一样默认是关闭状态的实验特性。

原先一个【工位】(slot) 只有 40 字节,额外数据需要存储在外部 heap。Variable Width Allocation 的原理是,把【工位】(slot) 扩大到 40 字节,80 字节,160 字节,320 字节四种。虽然可能造成一定的空间浪费,但根据局部性原理,提高了性能。

详情见 Variable Width Allocation 的 redmine

https://bugs.ruby-lang.org/issues/18045

https://bugs.ruby-lang.org/issues/18239

Q: 除了垃圾回收,Ruby 中还有哪些优化用到了局部性原理吗?

Ruby 2.4 中用局部性原理优化了 Hash 的实现,详情见下面文章中 Hash changes 的科普 https://blog.heroku.com/ruby-2-4-features-hashes-integers-rounding

0 楼 已删除

这个 ASCII 图是用什么画的啊?

深入理解 Java 虚拟机:JVM 高级特性与最佳实践(第 3 版)这个书讲 java 的,一些原理类似

@drift hunters 想了解 Ruby 垃圾回收机制和 Ruby 内部实现更详尽的阐述 .

需要 登录 后方可回复, 如果你还没有账号请 注册新账号