Skip to content

Commit 31fea17

Browse files
matzclaude
matz
and
claude
committed
gc.c: replace gcnext gray linked list with fixed-size gray stack
remove per-object gcnext pointer from MRB_OBJECT_HEADER, saving one word (8 bytes on 64-bit) per object slot. the gray list for tri-color marking is replaced by a fixed-size stack (MRB_GRAY_STACK_SIZE=1024) in mrb_gc. when the stack overflows, a linear heap rescan recovers gray objects. object slot size: 48 -> 40 bytes (16.7% reduction on 64-bit). benchmarks show up to 12% RSS reduction on object-heavy workloads with neutral performance impact. Co-authored-by: Claude <noreply@anthropic.com>
1 parent 5d3aab8 commit 31fea17

8 files changed

Lines changed: 75 additions & 37 deletions

File tree

‎include/mruby/gc.h‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,10 @@ MRB_API void mrb_free_context(struct mrb_state *mrb, struct mrb_context *c);
2828
#define MRB_GC_ARENA_SIZE 100
2929
#endif
3030

31+
#ifndef MRB_GRAY_STACK_SIZE
32+
#define MRB_GRAY_STACK_SIZE 1024
33+
#endif
34+
3135
typedef enum {
3236
MRB_GC_STATE_ROOT = 0,
3337
MRB_GC_STATE_MARK,
@@ -38,8 +42,9 @@ typedef struct mrb_gc {
3842
struct mrb_heap_page *heaps; /* all heaps pages */
3943
struct mrb_heap_page *free_heaps;/* heaps for allocation */
4044
struct mrb_heap_page *sweeps; /* page where sweep starts */
41-
struct RBasic *gray_list; /* list of gray objects to be traversed incrementally */
42-
struct RBasic *atomic_gray_list; /* list of objects to be traversed atomically */
45+
struct RBasic *gray_stack[MRB_GRAY_STACK_SIZE]; /* stack of gray objects */
46+
size_t gray_stack_top; /* top index of gray stack */
47+
mrb_bool gray_overflow:1; /* gray stack overflowed; needs heap rescan */
4348
size_t live; /* count of live objects */
4449
size_t live_after_mark; /* old generation objects */
4550
size_t threshold; /* threshold to start GC */

‎include/mruby/hash.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
*/
1515
MRB_BEGIN_DECL
1616

17-
/* offset of `iv` must be 3 words */
17+
/* offset of `iv` must match struct RObject */
1818
struct RHash {
1919
MRB_OBJECT_HEADER;
2020
#ifdef MRB_64BIT

‎include/mruby/object.h‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,6 @@
99

1010
#define MRB_OBJECT_HEADER \
1111
struct RClass *c; \
12-
struct RBasic *gcnext; \
1312
enum mrb_vtype tt:8; \
1413
unsigned int gc_color:3; \
1514
unsigned int frozen:1; \
@@ -39,7 +38,7 @@ struct RFiber {
3938
};
4039

4140
#define mrb_static_assert_object_size(st) \
42-
mrb_static_assert(sizeof(st) <= sizeof(void*) * 6, \
43-
#st " size must be within 6 words")
41+
mrb_static_assert(sizeof(st) <= sizeof(void*) * 5, \
42+
#st " size must be within 5 words")
4443

4544
#endif /* MRUBY_OBJECT_H */

‎mrbgems/mruby-catch/src/catch.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ static const mrb_irep catch_irep = {
4949
/* Procedure object for catch method - used to identify catch blocks in call stack */
5050
mrb_alignas(8)
5151
static const struct RProc catch_proc = {
52-
NULL, NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
52+
NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
5353
{ &catch_irep }, NULL, { NULL }
5454
};
5555

‎src/cdump.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -487,7 +487,7 @@ mrb_dump_irep_cstruct(mrb_state *mrb, const mrb_irep *irep, uint8_t flags, FILE
487487
"extern\n"
488488
"#endif",
489489
initname);
490-
fprintf(fp, "NULL,NULL,MRB_TT_PROC,MRB_GC_RED,MRB_OBJ_IS_FROZEN,0,{&%s_irep_0},NULL,{NULL},\n}};\n", initname);
490+
fprintf(fp, "NULL,MRB_TT_PROC,MRB_GC_RED,MRB_OBJ_IS_FROZEN,0,{&%s_irep_0},NULL,{NULL},\n}};\n", initname);
491491
fputs("static void\n", fp);
492492
fprintf(fp, "%s_init_syms(mrb_state *mrb)\n", initname);
493493
fputs("{\n", fp);

‎src/class.c‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4206,7 +4206,7 @@ static const mrb_irep new_irep = {
42064206

42074207
mrb_alignas(8)
42084208
static const struct RProc new_proc = {
4209-
NULL, NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
4209+
NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
42104210
{ &new_irep }, NULL, { NULL }
42114211
};
42124212

@@ -4238,7 +4238,7 @@ static const mrb_irep neq_irep = {
42384238

42394239
mrb_alignas(8)
42404240
static const struct RProc neq_proc = {
4241-
NULL, NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
4241+
NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
42424242
{ &neq_irep }, NULL, { NULL }
42434243
};
42444244

‎src/gc.c‎

Lines changed: 60 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -121,7 +121,7 @@ struct free_obj {
121121

122122
struct RVALUE_initializer {
123123
MRB_OBJECT_HEADER;
124-
char padding[sizeof(void*) * 4 - sizeof(uint32_t)];
124+
char padding[sizeof(void*) * 3];
125125
};
126126

127127
struct RVALUE {
@@ -531,8 +531,12 @@ add_gray_list(mrb_gc *gc, struct RBasic *obj)
531531
}
532532
#endif
533533
paint_gray(obj);
534-
obj->gcnext = gc->gray_list;
535-
gc->gray_list = obj;
534+
if (gc->gray_stack_top < MRB_GRAY_STACK_SIZE) {
535+
gc->gray_stack[gc->gray_stack_top++] = obj;
536+
}
537+
else {
538+
gc->gray_overflow = TRUE;
539+
}
536540
}
537541

538542
static void
@@ -914,8 +918,8 @@ root_scan_phase(mrb_state *mrb, mrb_gc *gc)
914918
int i, e;
915919

916920
if (!is_minor_gc(gc)) {
917-
gc->gray_list = NULL;
918-
gc->atomic_gray_list = NULL;
921+
gc->gray_stack_top = 0;
922+
gc->gray_overflow = FALSE;
919923
}
920924

921925
mrb_gc_mark_gv(mrb);
@@ -964,13 +968,37 @@ root_scan_phase(mrb_state *mrb, mrb_gc *gc)
964968
#endif
965969
}
966970

971+
static void
972+
gc_gray_rescan(mrb_state *mrb, mrb_gc *gc)
973+
{
974+
mrb_heap_page *page = gc->heaps;
975+
976+
gc->gray_overflow = FALSE;
977+
while (page) {
978+
RVALUE *p = page->objects;
979+
RVALUE *e = p + MRB_HEAP_PAGE_SIZE;
980+
for (; p < e; p++) {
981+
if (is_gray(&p->as.basic) && p->as.basic.tt != MRB_TT_FREE) {
982+
if (gc->gray_stack_top >= MRB_GRAY_STACK_SIZE) {
983+
gc->gray_overflow = TRUE;
984+
return;
985+
}
986+
gc->gray_stack[gc->gray_stack_top++] = &p->as.basic;
987+
}
988+
}
989+
page = page->next;
990+
}
991+
}
992+
967993
static void
968994
gc_mark_gray_list(mrb_state *mrb, mrb_gc *gc) {
969-
while (gc->gray_list) {
970-
struct RBasic *obj = gc->gray_list;
971-
gc->gray_list = obj->gcnext;
972-
obj->gcnext = NULL;
973-
gc_mark_children(mrb, gc, obj);
995+
for (;;) {
996+
while (gc->gray_stack_top > 0) {
997+
struct RBasic *obj = gc->gray_stack[--gc->gray_stack_top];
998+
gc_mark_children(mrb, gc, obj);
999+
}
1000+
if (!gc->gray_overflow) break;
1001+
gc_gray_rescan(mrb, gc);
9741002
}
9751003
}
9761004

@@ -979,11 +1007,18 @@ incremental_marking_phase(mrb_state *mrb, mrb_gc *gc, size_t limit)
9791007
{
9801008
size_t tried_marks = 0;
9811009

982-
while (gc->gray_list && tried_marks < limit) {
983-
struct RBasic *obj = gc->gray_list;
984-
gc->gray_list = obj->gcnext;
985-
obj->gcnext = NULL;
986-
tried_marks += gc_mark_children(mrb, gc, obj);
1010+
while (tried_marks < limit) {
1011+
if (gc->gray_stack_top > 0) {
1012+
struct RBasic *obj = gc->gray_stack[--gc->gray_stack_top];
1013+
tried_marks += gc_mark_children(mrb, gc, obj);
1014+
}
1015+
else if (gc->gray_overflow) {
1016+
gc_gray_rescan(mrb, gc);
1017+
if (gc->gray_stack_top == 0) break;
1018+
}
1019+
else {
1020+
break;
1021+
}
9871022
}
9881023

9891024
return tried_marks;
@@ -1027,18 +1062,12 @@ final_marking_phase(mrb_state *mrb, mrb_gc *gc)
10271062
#endif
10281063

10291064
gc_mark_gray_list(mrb, gc);
1030-
mrb_assert(gc->gray_list == NULL);
1031-
gc->gray_list = gc->atomic_gray_list;
1032-
gc->atomic_gray_list = NULL;
1033-
gc_mark_gray_list(mrb, gc);
1034-
mrb_assert(gc->gray_list == NULL);
10351065
}
10361066

10371067
static void
10381068
prepare_incremental_sweep(mrb_state *mrb, mrb_gc *gc)
10391069
{
1040-
// mrb_assert(gc->atomic_gray_list == NULL);
1041-
// mrb_assert(gc->gray_list == NULL);
1070+
// mrb_assert(gc->gray_stack_top == 0);
10421071
gc->state = MRB_GC_STATE_SWEEP;
10431072
gc->sweeps = NULL;
10441073
gc->live_after_mark = gc->live;
@@ -1131,7 +1160,7 @@ incremental_gc(mrb_state *mrb, mrb_gc *gc, size_t limit)
11311160
flip_white_part(gc);
11321161
return 0;
11331162
case MRB_GC_STATE_MARK:
1134-
if (gc->gray_list) {
1163+
if (gc->gray_stack_top > 0 || gc->gray_overflow) {
11351164
return incremental_marking_phase(mrb, gc, limit);
11361165
}
11371166
else {
@@ -1190,7 +1219,8 @@ clear_all_old(mrb_state *mrb, mrb_gc *gc)
11901219
incremental_gc_finish(mrb, gc);
11911220
gc->generational = TRUE;
11921221
/* The gray objects have already been painted as white */
1193-
gc->atomic_gray_list = gc->gray_list = NULL;
1222+
gc->gray_stack_top = 0;
1223+
gc->gray_overflow = FALSE;
11941224
}
11951225

11961226
MRB_API void
@@ -1318,8 +1348,12 @@ mrb_write_barrier(mrb_state *mrb, struct RBasic *obj)
13181348
mrb_assert(!is_dead(gc, obj));
13191349
mrb_assert(is_generational(gc) || gc->state != MRB_GC_STATE_ROOT);
13201350
paint_gray(obj);
1321-
obj->gcnext = gc->atomic_gray_list;
1322-
gc->atomic_gray_list = obj;
1351+
if (gc->gray_stack_top < MRB_GRAY_STACK_SIZE) {
1352+
gc->gray_stack[gc->gray_stack_top++] = obj;
1353+
}
1354+
else {
1355+
gc->gray_overflow = TRUE;
1356+
}
13231357
}
13241358

13251359
/*

‎src/proc.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@ static const mrb_irep call_irep = {
3838

3939
mrb_alignas(8)
4040
static const struct RProc call_proc = {
41-
NULL, NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
41+
NULL, MRB_TT_PROC, MRB_GC_RED, MRB_OBJ_IS_FROZEN, MRB_PROC_SCOPE | MRB_PROC_STRICT,
4242
{ &call_irep }, NULL, { NULL }
4343
};
4444

0 commit comments

Comments
 (0)