Ruby China

Ruby 垃圾回收原理浅析

zhuoerri · April 26, 2022 · Last by WilliePatel replied at May 08, 2025 · 1284 hits

前言

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

本文会用自问自答的形式，用【公司裁员】打比方，结合 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 管这种完全空置的page叫tomb page, 管还有 Ruby 对象的page叫eden 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

10 likes
0 Floor has deleted
ccmywish #1 April 26, 2022

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

lehug #3 April 26, 2022

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

1 likes
Omegle #5 March 18, 2024

nice post

mariaran #6 June 04, 2024

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

You need to Sign in before reply, if you don't have an account, please Sign up first.