Skip to content

Commit e8ae922

Browse files
eileencodestenderlove
eileencodes
and
tenderlove
committed
Add a cache for class variables
This change implements a cache for class variables. Previously there was no cache for cvars. Cvar access is slow due to needing to travel all the way up th ancestor tree before returning the cvar value. The deeper the ancestor tree the slower cvar access will be. The benefits of the cache are more visible with a higher number of included modules due to the way Ruby looks up class variables. The benchmark here includes 26 modules and shows with the cache, this branch is 6.5x faster when accessing class variables. ``` compare-ruby: ruby 3.1.0dev (2021-03-15T06:22:34Z master 9e5105c) [x86_64-darwin19] built-ruby: ruby 3.1.0dev (2021-03-15T12:12:44Z add-cache-for-clas.. c6be009) [x86_64-darwin19] | |compare-ruby|built-ruby| |:--------|-----------:|---------:| |vm_cvar | 5.681M| 36.980M| | | -| 6.51x| ``` Benchmark.ips calling `ActiveRecord::Base.logger` from within a Rails application. ActiveRecord::Base.logger has 71 ancestors. The more ancestors a tree has, the more clear the speed increase. IE if Base had only one ancestor we'd see no improvement. This benchmark is run on a vanilla Rails application. Benchmark code: ```ruby require "benchmark/ips" require_relative "config/environment" Benchmark.ips do |x| x.report "logger" do ActiveRecord::Base.logger end end ``` Ruby 3.0 master / Rails 6.1: ``` Warming up -------------------------------------- logger 155.251k i/100ms Calculating ------------------------------------- ``` Ruby 3.0 with cvar cache / Rails 6.1: ``` Warming up -------------------------------------- logger 1.546M i/100ms Calculating ------------------------------------- logger 14.857M (± 4.8%) i/s - 74.198M in 5.006202s ``` Lastly we ran a benchmark to demonstate the difference between master and our cache when the number of modules increases. This benchmark measures 1 ancestor, 30 ancestors, and 100 ancestors. Ruby 3.0 master: ``` Warming up -------------------------------------- 1 module 1.231M i/100ms 30 modules 432.020k i/100ms 100 modules 145.399k i/100ms Calculating ------------------------------------- 1 module 12.210M (± 2.1%) i/s - 61.553M in 5.043400s 30 modules 4.354M (± 2.7%) i/s - 22.033M in 5.063839s 100 modules 1.434M (± 2.9%) i/s - 7.270M in 5.072531s Comparison: 1 module: 12209958.3 i/s 30 modules: 4354217.8 i/s - 2.80x (± 0.00) slower 100 modules: 1434447.3 i/s - 8.51x (± 0.00) slower ``` Ruby 3.0 with cvar cache: ``` Warming up -------------------------------------- 1 module 1.641M i/100ms 30 modules 1.655M i/100ms 100 modules 1.620M i/100ms Calculating ------------------------------------- 1 module 16.279M (± 3.8%) i/s - 82.038M in 5.046923s 30 modules 15.891M (± 3.9%) i/s - 79.459M in 5.007958s 100 modules 16.087M (± 3.6%) i/s - 81.005M in 5.041931s Comparison: 1 module: 16279458.0 i/s 100 modules: 16087484.6 i/s - same-ish: difference falls within error 30 modules: 15891406.2 i/s - same-ish: difference falls within error ``` Co-authored-by: Aaron Patterson <tenderlove@ruby-lang.org>
1 parent c9e02d8 commit e8ae922

File tree

15 files changed

+215
-19
lines changed

15 files changed

+215
-19
lines changed

‎benchmark/vm_cvar.yml

+20
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
prelude: |
2+
class A
3+
@@foo = 1
4+
5+
def self.foo
6+
@@foo
7+
end
8+
9+
("A".."Z").each do |module_name|
10+
eval <<-EOM
11+
module #{module_name}
12+
end
13+
14+
include #{module_name}
15+
EOM
16+
end
17+
end
18+
benchmark:
19+
vm_cvar: A.foo
20+
loop_count: 600000

‎class.c

+5
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
#include <ctype.h>
2828

2929
#include "constant.h"
30+
#include "debug_counter.h"
3031
#include "id_table.h"
3132
#include "internal.h"
3233
#include "internal/class.h"
@@ -43,6 +44,8 @@
4344
#define METACLASS_OF(k) RBASIC(k)->klass
4445
#define SET_METACLASS_OF(k, cls) RBASIC_SET_CLASS(k, cls)
4546

47+
RUBY_EXTERN rb_serial_t ruby_vm_global_cvar_state;
48+
4649
void
4750
rb_class_subclass_add(VALUE super, VALUE klass)
4851
{
@@ -1085,6 +1088,8 @@ do_include_modules_at(const VALUE klass, VALUE c, VALUE module, int search_super
10851088
VALUE super_class = RCLASS_SUPER(c);
10861089

10871090
// invalidate inline method cache
1091+
RB_DEBUG_COUNTER_INC(cvar_include_invalidate);
1092+
ruby_vm_global_cvar_state++;
10881093
tbl = RCLASS_M_TBL(module);
10891094
if (tbl && rb_id_table_size(tbl)) {
10901095
if (search_super) { // include

‎common.mk

+1
Original file line numberDiff line numberDiff line change
@@ -2458,6 +2458,7 @@ class.$(OBJEXT): {$(VPATH)}backward/2/stdarg.h
24582458
class.$(OBJEXT): {$(VPATH)}class.c
24592459
class.$(OBJEXT): {$(VPATH)}config.h
24602460
class.$(OBJEXT): {$(VPATH)}constant.h
2461+
class.$(OBJEXT): {$(VPATH)}debug_counter.h
24612462
class.$(OBJEXT): {$(VPATH)}defines.h
24622463
class.$(OBJEXT): {$(VPATH)}encoding.h
24632464
class.$(OBJEXT): {$(VPATH)}id.h

‎compile.c

+3-2
Original file line numberDiff line numberDiff line change
@@ -8668,8 +8668,9 @@ iseq_compile_each0(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *node, in
86688668
}
86698669
case NODE_CVAR:{
86708670
if (!popped) {
8671-
ADD_INSN1(ret, line_node, getclassvariable,
8672-
ID2SYM(node->nd_vid));
8671+
ADD_INSN2(ret, line_node, getclassvariable,
8672+
ID2SYM(node->nd_vid),
8673+
get_ivar_ic_value(iseq,node->nd_vid));
86738674
}
86748675
break;
86758676
}

‎debug_counter.h

+5
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,11 @@ RB_DEBUG_COUNTER(mc_inline_miss_same_cme) // IMC miss, but same CME
2424
RB_DEBUG_COUNTER(mc_inline_miss_same_def) // IMC miss, but same definition
2525
RB_DEBUG_COUNTER(mc_inline_miss_diff) // IMC miss, different methods
2626

27+
RB_DEBUG_COUNTER(cvar_inline_hit) // cvar cache hit
28+
RB_DEBUG_COUNTER(cvar_inline_miss) // miss inline cache
29+
RB_DEBUG_COUNTER(cvar_class_invalidate) // invalidate cvar cache when define a cvar that's defined on a subclass
30+
RB_DEBUG_COUNTER(cvar_include_invalidate) // invalidate cvar cache on module include or prepend
31+
2732
RB_DEBUG_COUNTER(mc_cme_complement) // number of acquiring complement CME
2833
RB_DEBUG_COUNTER(mc_cme_complement_hit) // number of cache hit for complemented CME
2934

‎gc.c

+36
Original file line numberDiff line numberDiff line change
@@ -3003,6 +3003,13 @@ cc_table_free(rb_objspace_t *objspace, VALUE klass, bool alive)
30033003
}
30043004
}
30053005

3006+
static enum rb_id_table_iterator_result
3007+
cvar_table_free_i(VALUE value, void * ctx)
3008+
{
3009+
xfree((void *) value);
3010+
return ID_TABLE_CONTINUE;
3011+
}
3012+
30063013
void
30073014
rb_cc_table_free(VALUE klass)
30083015
{
@@ -3114,6 +3121,10 @@ obj_free(rb_objspace_t *objspace, VALUE obj)
31143121
if (RCLASS_IV_INDEX_TBL(obj)) {
31153122
iv_index_tbl_free(RCLASS_IV_INDEX_TBL(obj));
31163123
}
3124+
if (RCLASS_CVC_TBL(obj)) {
3125+
rb_id_table_foreach_values(RCLASS_CVC_TBL(obj), cvar_table_free_i, NULL);
3126+
rb_id_table_free(RCLASS_CVC_TBL(obj));
3127+
}
31173128
if (RCLASS_SUBCLASSES(obj)) {
31183129
if (BUILTIN_TYPE(obj) == T_MODULE) {
31193130
rb_class_detach_module_subclasses(obj);
@@ -4557,6 +4568,9 @@ obj_memsize_of(VALUE obj, int use_all_types)
45574568
if (RCLASS_IV_TBL(obj)) {
45584569
size += st_memsize(RCLASS_IV_TBL(obj));
45594570
}
4571+
if (RCLASS_CVC_TBL(obj)) {
4572+
size += rb_id_table_memsize(RCLASS_CVC_TBL(obj));
4573+
}
45604574
if (RCLASS_IV_INDEX_TBL(obj)) {
45614575
// TODO: more correct value
45624576
size += st_memsize(RCLASS_IV_INDEX_TBL(obj));
@@ -9603,6 +9617,27 @@ update_cc_tbl(rb_objspace_t *objspace, VALUE klass)
96039617
}
96049618
}
96059619

9620+
static enum rb_id_table_iterator_result
9621+
update_cvc_tbl_i(ID id, VALUE cvc_entry, void *data)
9622+
{
9623+
struct rb_cvar_class_tbl_entry *entry;
9624+
9625+
entry = (struct rb_cvar_class_tbl_entry *)cvc_entry;
9626+
9627+
entry->class_value = rb_gc_location(entry->class_value);
9628+
9629+
return ID_TABLE_CONTINUE;
9630+
}
9631+
9632+
static void
9633+
update_cvc_tbl(rb_objspace_t *objspace, VALUE klass)
9634+
{
9635+
struct rb_id_table *tbl = RCLASS_CVC_TBL(klass);
9636+
if (tbl) {
9637+
rb_id_table_foreach_with_replace(tbl, update_cvc_tbl_i, 0, objspace);
9638+
}
9639+
}
9640+
96069641
static enum rb_id_table_iterator_result
96079642
update_const_table(VALUE value, void *data)
96089643
{
@@ -9674,6 +9709,7 @@ gc_update_object_references(rb_objspace_t *objspace, VALUE obj)
96749709
if (!RCLASS_EXT(obj)) break;
96759710
update_m_tbl(objspace, RCLASS_M_TBL(obj));
96769711
update_cc_tbl(objspace, obj);
9712+
update_cvc_tbl(objspace, obj);
96779713

96789714
gc_update_tbl_refs(objspace, RCLASS_IV_TBL(obj));
96799715

‎id_table.c

+3-3
Original file line numberDiff line numberDiff line change
@@ -92,7 +92,7 @@ rb_id_table_init(struct rb_id_table *tbl, int capa)
9292
return tbl;
9393
}
9494

95-
struct rb_id_table *
95+
MJIT_FUNC_EXPORTED struct rb_id_table *
9696
rb_id_table_create(size_t capa)
9797
{
9898
struct rb_id_table *tbl = ALLOC(struct rb_id_table);
@@ -223,7 +223,7 @@ hash_table_show(struct rb_id_table *tbl)
223223
}
224224
#endif
225225

226-
int
226+
MJIT_FUNC_EXPORTED int
227227
rb_id_table_lookup(struct rb_id_table *tbl, ID id, VALUE *valp)
228228
{
229229
id_key_t key = id2key(id);
@@ -253,7 +253,7 @@ rb_id_table_insert_key(struct rb_id_table *tbl, const id_key_t key, const VALUE
253253
return TRUE;
254254
}
255255

256-
int
256+
MJIT_FUNC_EXPORTED int
257257
rb_id_table_insert(struct rb_id_table *tbl, ID id, VALUE val)
258258
{
259259
return rb_id_table_insert_key(tbl, id2key(id), val);

‎include/ruby/internal/intern/variable.h

+1
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,7 @@ VALUE rb_mod_const_missing(VALUE,VALUE);
7272
VALUE rb_cvar_defined(VALUE, ID);
7373
void rb_cvar_set(VALUE, ID, VALUE);
7474
VALUE rb_cvar_get(VALUE, ID);
75+
VALUE rb_cvar_find(VALUE, ID, VALUE*);
7576
void rb_cv_set(VALUE, const char*, VALUE);
7677
VALUE rb_cv_get(VALUE, const char*);
7778
void rb_define_class_variable(VALUE, const char*, VALUE);

‎insns.def

+5-3
Original file line numberDiff line numberDiff line change
@@ -230,13 +230,15 @@ setinstancevariable
230230
/* Get value of class variable id of klass as val. */
231231
DEFINE_INSN
232232
getclassvariable
233-
(ID id)
233+
(ID id, IVC ic)
234234
()
235235
(VALUE val)
236236
/* "class variable access from toplevel" warning can be hooked. */
237237
// attr bool leaf = false; /* has rb_warning() */
238238
{
239-
val = rb_cvar_get(vm_get_cvar_base(vm_get_cref(GET_EP()), GET_CFP(), 1), id);
239+
rb_cref_t * cref = vm_get_cref(GET_EP());
240+
rb_control_frame_t *cfp = GET_CFP();
241+
val = vm_getclassvariable(GET_ISEQ(), cref, cfp, id, (ICVARC)ic);
240242
}
241243

242244
/* Set value of class variable id of klass as val. */
@@ -249,7 +251,7 @@ setclassvariable
249251
// attr bool leaf = false; /* has rb_warning() */
250252
{
251253
vm_ensure_not_refinement_module(GET_SELF());
252-
rb_cvar_set(vm_get_cvar_base(vm_get_cref(GET_EP()), GET_CFP(), 1), id, val);
254+
vm_setclassvariable(vm_get_cref(GET_EP()), GET_CFP(), id, val);
253255
}
254256

255257
/* Get constant variable id. If klass is Qnil and allow_nil is Qtrue, constants

‎internal/class.h

+8
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,12 @@ struct rb_iv_index_tbl_entry {
3131
VALUE class_value;
3232
};
3333

34+
struct rb_cvar_class_tbl_entry {
35+
uint32_t index;
36+
rb_serial_t global_cvar_state;
37+
VALUE class_value;
38+
};
39+
3440
struct rb_classext_struct {
3541
struct st_table *iv_index_tbl; // ID -> struct rb_iv_index_tbl_entry
3642
struct st_table *iv_tbl;
@@ -40,6 +46,7 @@ struct rb_classext_struct {
4046
struct rb_id_table *const_tbl;
4147
struct rb_id_table *callable_m_tbl;
4248
struct rb_id_table *cc_tbl; /* ID -> [[ci, cc1], cc2, ...] */
49+
struct rb_id_table *cvc_tbl;
4350
struct rb_subclass_entry *subclasses;
4451
struct rb_subclass_entry **parent_subclasses;
4552
/**
@@ -83,6 +90,7 @@ typedef struct rb_classext_struct rb_classext_t;
8390
#endif
8491
#define RCLASS_CALLABLE_M_TBL(c) (RCLASS_EXT(c)->callable_m_tbl)
8592
#define RCLASS_CC_TBL(c) (RCLASS_EXT(c)->cc_tbl)
93+
#define RCLASS_CVC_TBL(c) (RCLASS_EXT(c)->cvc_tbl)
8694
#define RCLASS_IV_INDEX_TBL(c) (RCLASS_EXT(c)->iv_index_tbl)
8795
#define RCLASS_ORIGIN(c) (RCLASS_EXT(c)->origin_)
8896
#define RCLASS_REFINED_CLASS(c) (RCLASS_EXT(c)->refined_class)

‎variable.c

+65-8
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,8 @@
3939
#include "ractor_core.h"
4040
#include "vm_sync.h"
4141

42+
RUBY_EXTERN rb_serial_t ruby_vm_global_cvar_state;
43+
4244
typedef void rb_gvar_compact_t(void *var);
4345

4446
static struct rb_id_table *rb_global_tbl;
@@ -3325,6 +3327,30 @@ cvar_overtaken(VALUE front, VALUE target, ID id)
33253327
}
33263328
}
33273329

3330+
static VALUE
3331+
find_cvar(VALUE klass, VALUE * front, VALUE * target, ID id)
3332+
{
3333+
VALUE v = Qundef;
3334+
CVAR_ACCESSOR_SHOULD_BE_MAIN_RACTOR();
3335+
if (cvar_lookup_at(klass, id, (&v))) {
3336+
if (!*front) {
3337+
*front = klass;
3338+
}
3339+
*target = klass;
3340+
}
3341+
3342+
for (klass = cvar_front_klass(klass); klass; klass = RCLASS_SUPER(klass)) {
3343+
if (cvar_lookup_at(klass, id, (&v))) {
3344+
if (!*front) {
3345+
*front = klass;
3346+
}
3347+
*target = klass;
3348+
}
3349+
}
3350+
3351+
return v;
3352+
}
3353+
33283354
#define CVAR_FOREACH_ANCESTORS(klass, v, r) \
33293355
for (klass = cvar_front_klass(klass); klass; klass = RCLASS_SUPER(klass)) { \
33303356
if (cvar_lookup_at(klass, id, (v))) { \
@@ -3338,6 +3364,20 @@ cvar_overtaken(VALUE front, VALUE target, ID id)
33383364
CVAR_FOREACH_ANCESTORS(klass, v, r);\
33393365
} while(0)
33403366

3367+
static void
3368+
check_for_cvar_table(VALUE subclass, VALUE key)
3369+
{
3370+
st_table *tbl = RCLASS_IV_TBL(subclass);
3371+
3372+
if (tbl && st_lookup(tbl, key, NULL)) {
3373+
RB_DEBUG_COUNTER_INC(cvar_class_invalidate);
3374+
ruby_vm_global_cvar_state++;
3375+
return;
3376+
}
3377+
3378+
rb_class_foreach_subclass(subclass, check_for_cvar_table, key);
3379+
}
3380+
33413381
void
33423382
rb_cvar_set(VALUE klass, ID id, VALUE val)
33433383
{
@@ -3357,25 +3397,42 @@ rb_cvar_set(VALUE klass, ID id, VALUE val)
33573397
}
33583398
check_before_mod_set(target, id, val, "class variable");
33593399

3360-
rb_class_ivar_set(target, id, val);
3400+
int result = rb_class_ivar_set(target, id, val);
3401+
3402+
// Break the cvar cache if this is a new class variable
3403+
// and target is a module or a subclass with the same
3404+
// cvar in this lookup.
3405+
if (result == 0) {
3406+
if (RB_TYPE_P(target, T_CLASS)) {
3407+
if (RCLASS_SUBCLASSES(target)) {
3408+
rb_class_foreach_subclass(target, check_for_cvar_table, id);
3409+
}
3410+
}
3411+
}
33613412
}
33623413

33633414
VALUE
3364-
rb_cvar_get(VALUE klass, ID id)
3415+
rb_cvar_find(VALUE klass, ID id, VALUE *front)
33653416
{
3366-
VALUE tmp, front = 0, target = 0;
3367-
st_data_t value;
3417+
VALUE target = 0;
3418+
VALUE value;
33683419

3369-
tmp = klass;
3370-
CVAR_LOOKUP(&value, {if (!front) front = klass; target = klass;});
3420+
value = find_cvar(klass, front, &target, id);
33713421
if (!target) {
33723422
rb_name_err_raise("uninitialized class variable %1$s in %2$s",
3373-
tmp, ID2SYM(id));
3423+
klass, ID2SYM(id));
33743424
}
3375-
cvar_overtaken(front, target, id);
3425+
cvar_overtaken(*front, target, id);
33763426
return (VALUE)value;
33773427
}
33783428

3429+
VALUE
3430+
rb_cvar_get(VALUE klass, ID id)
3431+
{
3432+
VALUE front = 0;
3433+
return rb_cvar_find(klass, id, &front);
3434+
}
3435+
33793436
VALUE
33803437
rb_cvar_defined(VALUE klass, ID id)
33813438
{

‎vm.c

+4-1
Original file line numberDiff line numberDiff line change
@@ -405,6 +405,7 @@ unsigned int ruby_vm_event_local_num;
405405

406406
rb_serial_t ruby_vm_global_constant_state = 1;
407407
rb_serial_t ruby_vm_class_serial = 1;
408+
rb_serial_t ruby_vm_global_cvar_state = 1;
408409

409410
static const struct rb_callcache vm_empty_cc = {
410411
.flags = T_IMEMO | (imemo_callcache << FL_USHIFT) | VM_CALLCACHE_UNMARKABLE,
@@ -484,7 +485,7 @@ rb_dtrace_setup(rb_execution_context_t *ec, VALUE klass, ID id,
484485
static VALUE
485486
vm_stat(int argc, VALUE *argv, VALUE self)
486487
{
487-
static VALUE sym_global_constant_state, sym_class_serial;
488+
static VALUE sym_global_constant_state, sym_class_serial, sym_global_cvar_state;
488489
VALUE arg = Qnil;
489490
VALUE hash = Qnil, key = Qnil;
490491

@@ -505,6 +506,7 @@ vm_stat(int argc, VALUE *argv, VALUE self)
505506
#define S(s) sym_##s = ID2SYM(rb_intern_const(#s))
506507
S(global_constant_state);
507508
S(class_serial);
509+
S(global_cvar_state);
508510
#undef S
509511
}
510512

@@ -516,6 +518,7 @@ vm_stat(int argc, VALUE *argv, VALUE self)
516518

517519
SET(global_constant_state, ruby_vm_global_constant_state);
518520
SET(class_serial, ruby_vm_class_serial);
521+
SET(global_cvar_state, ruby_vm_global_cvar_state);
519522
#undef SET
520523

521524
if (!NIL_P(key)) { /* matched key should return above */

0 commit comments

Comments
 (0)