ruby-changes:71476
From: Peter <ko1@a...>
Date: Tue, 22 Mar 2022 22:42:59 +0900 (JST)
Subject: [ruby-changes:71476] a51f30c671 (master): [Feature #18634] Implement Arrays on Variable Width Allocation
https://git.ruby-lang.org/ruby.git/commit/?id=a51f30c671 From a51f30c6712798fc07e57f692d0d0e5ccc59acf1 Mon Sep 17 00:00:00 2001 From: Peter Zhu <peter@p...> Date: Tue, 15 Mar 2022 09:34:07 -0400 Subject: [Feature #18634] Implement Arrays on Variable Width Allocation This commit implements arrays on Variable Width Allocation. This allows longer arrays to be embedded (i.e. contents directly follow the object header) which improves performance through better cache locality. --- array.c | 191 +++++++++++++++++++++++++++++------- include/ruby/internal/abi.h | 2 +- include/ruby/internal/core/rarray.h | 21 +++- 3 files changed, 176 insertions(+), 38 deletions(-) diff --git a/array.c b/array.c index f47c1509ad..5512280f39 100644 --- a/array.c +++ b/array.c @@ -139,7 +139,7 @@ should_not_be_shared_and_embedded(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L139 } \ } while (0) -#define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \ +#define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? ary_embed_capa(ary) : \ ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : ARY_HEAP_CAPA(ary)) #define ARY_SET_CAPA(ary, n) do { \ assert(!ARY_EMBED_P(ary)); \ @@ -157,7 +157,7 @@ should_not_be_shared_and_embedded(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L157 assert(ARY_SHARED_ROOT_P(_value_)); \ RB_OBJ_WRITE(_ary_, &RARRAY(_ary_)->as.heap.aux.shared_root, _value_); \ } while (0) -#define RARRAY_SHARED_ROOT_FLAG FL_USER5 +#define RARRAY_SHARED_ROOT_FLAG FL_USER12 #define ARY_SHARED_ROOT_P(ary) (assert(should_be_T_ARRAY((VALUE)(ary))), \ FL_TEST_RAW((ary), RARRAY_SHARED_ROOT_FLAG)) #define ARY_SHARED_ROOT_REFCNT(ary) \ @@ -184,6 +184,34 @@ ARY_SET(VALUE a, long i, VALUE v) https://github.com/ruby/ruby/blob/trunk/array.c#L184 } #undef RARRAY_ASET +static long +ary_embed_capa(VALUE ary) +{ +#if USE_RVARGC + size_t size = rb_gc_obj_slot_size(ary) - offsetof(struct RArray, as.ary); + assert(size % sizeof(VALUE) == 0); + return size / sizeof(VALUE); +#else + return RARRAY_EMBED_LEN_MAX; +#endif +} + +static size_t +ary_embed_size(long capa) +{ + return offsetof(struct RArray, as.ary) + (sizeof(VALUE) * capa); +} + +static bool +ary_embeddable_p(long capa) +{ +#if USE_RVARGC + return rb_gc_size_allocatable_p(ary_embed_size(capa)); +#else + return capa <= RARRAY_EMBED_LEN_MAX; +#endif +} + #if ARRAY_DEBUG #define ary_verify(ary) ary_verify_(ary, __FILE__, __LINE__) @@ -205,7 +233,7 @@ ary_verify_(VALUE ary, const char *file, int line) https://github.com/ruby/ruby/blob/trunk/array.c#L233 else if (ARY_EMBED_P(ary)) { assert(!RARRAY_TRANSIENT_P(ary)); assert(!ARY_SHARED_P(ary)); - assert(RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX); + assert(RARRAY_LEN(ary) <= ary_embed_capa(ary)); } else { #if 1 @@ -447,7 +475,7 @@ ary_resize_capa(VALUE ary, long capacity) https://github.com/ruby/ruby/blob/trunk/array.c#L475 assert(!OBJ_FROZEN(ary)); assert(!ARY_SHARED_P(ary)); - if (capacity > RARRAY_EMBED_LEN_MAX) { + if (capacity > ary_embed_capa(ary)) { size_t new_capa = capacity; if (ARY_EMBED_P(ary)) { long len = ARY_EMBED_LEN(ary); @@ -573,7 +601,7 @@ rb_ary_cancel_sharing(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L601 ary_verify(shared_root); - if (len <= RARRAY_EMBED_LEN_MAX) { + if (len <= ary_embed_capa(ary)) { const VALUE *ptr = ARY_HEAP_PTR(ary); FL_UNSET_SHARED(ary); FL_SET_EMBED(ary); @@ -623,7 +651,7 @@ ary_ensure_room_for_push(VALUE ary, long add_len) https://github.com/ruby/ruby/blob/trunk/array.c#L651 rb_raise(rb_eIndexError, "index %ld too big", new_len); } if (ARY_SHARED_P(ary)) { - if (new_len > RARRAY_EMBED_LEN_MAX) { + if (new_len > ary_embed_capa(ary)) { VALUE shared_root = ARY_SHARED_ROOT(ary); if (ARY_SHARED_ROOT_OCCUPIED(shared_root)) { if (ARY_HEAP_PTR(ary) - RARRAY_CONST_PTR_TRANSIENT(shared_root) + new_len <= RARRAY_LEN(shared_root)) { @@ -699,9 +727,16 @@ rb_ary_shared_with_p(VALUE ary1, VALUE ary2) https://github.com/ruby/ruby/blob/trunk/array.c#L727 } static VALUE -ary_alloc(VALUE klass) +ary_alloc_embed(VALUE klass, long capa) { - NEWOBJ_OF(ary, struct RArray, klass, T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0)); + size_t size = ary_embed_size(capa); + assert(rb_gc_size_allocatable_p(size)); +#if !USE_RVARGC + assert(size <= sizeof(struct RArray)); +#endif + RVARGC_NEWOBJ_OF(ary, struct RArray, klass, + T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0), + size); /* Created array is: * FL_SET_EMBED((VALUE)ary); * ARY_SET_EMBED_LEN((VALUE)ary, 0); @@ -709,11 +744,20 @@ ary_alloc(VALUE klass) https://github.com/ruby/ruby/blob/trunk/array.c#L744 return (VALUE)ary; } +static VALUE +ary_alloc_heap(VALUE klass) +{ + RVARGC_NEWOBJ_OF(ary, struct RArray, klass, + T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0), + sizeof(struct RArray)); + return (VALUE)ary; +} + static VALUE empty_ary_alloc(VALUE klass) { RUBY_DTRACE_CREATE_HOOK(ARRAY, 0); - return ary_alloc(klass); + return ary_alloc_embed(klass, 0); } static VALUE @@ -730,10 +774,14 @@ ary_new(VALUE klass, long capa) https://github.com/ruby/ruby/blob/trunk/array.c#L774 RUBY_DTRACE_CREATE_HOOK(ARRAY, capa); - ary = ary_alloc(klass); - if (capa > RARRAY_EMBED_LEN_MAX) { + if (ary_embeddable_p(capa)) { + ary = ary_alloc_embed(klass, capa); + } + else { + ary = ary_alloc_heap(klass); + assert(!ARY_EMBED_P(ary)); + ptr = ary_heap_alloc(ary, capa); - FL_UNSET_EMBED(ary); ARY_SET_PTR(ary, ptr); ARY_SET_CAPA(ary, capa); ARY_SET_HEAP_LEN(ary, 0); @@ -751,7 +799,7 @@ rb_ary_new_capa(long capa) https://github.com/ruby/ruby/blob/trunk/array.c#L799 VALUE rb_ary_new(void) { - return rb_ary_new2(RARRAY_EMBED_LEN_MAX); + return rb_ary_new_capa(0); } VALUE @@ -794,9 +842,16 @@ rb_ary_new_from_values(long n, const VALUE *elts) https://github.com/ruby/ruby/blob/trunk/array.c#L842 } static VALUE -ec_ary_alloc(rb_execution_context_t *ec, VALUE klass) +ec_ary_alloc_embed(rb_execution_context_t *ec, VALUE klass, long capa) { - RB_EC_NEWOBJ_OF(ec, ary, struct RArray, klass, T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0)); + size_t size = ary_embed_size(capa); + assert(rb_gc_size_allocatable_p(size)); +#if !USE_RVARGC + assert(size <= sizeof(struct RArray)); +#endif + RB_RVARGC_EC_NEWOBJ_OF(ec, ary, struct RArray, klass, + T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0), + size); /* Created array is: * FL_SET_EMBED((VALUE)ary); * ARY_SET_EMBED_LEN((VALUE)ary, 0); @@ -804,6 +859,15 @@ ec_ary_alloc(rb_execution_context_t *ec, VALUE klass) https://github.com/ruby/ruby/blob/trunk/array.c#L859 return (VALUE)ary; } +static VALUE +ec_ary_alloc_heap(rb_execution_context_t *ec, VALUE klass) +{ + RB_RVARGC_EC_NEWOBJ_OF(ec, ary, struct RArray, klass, + T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0), + sizeof(struct RArray)); + return (VALUE)ary; +} + static VALUE ec_ary_new(rb_execution_context_t *ec, VALUE klass, long capa) { @@ -818,11 +882,14 @@ ec_ary_new(rb_execution_context_t *ec, VALUE klass, long capa) https://github.com/ruby/ruby/blob/trunk/array.c#L882 RUBY_DTRACE_CREATE_HOOK(ARRAY, capa); - ary = ec_ary_alloc(ec, klass); + if (ary_embeddable_p(capa)) { + ary = ec_ary_alloc_embed(ec, klass, capa); + } + else { + ary = ec_ary_alloc_heap(ec, klass); + assert(!ARY_EMBED_P(ary)); - if (capa > RARRAY_EMBED_LEN_MAX) { ptr = ary_heap_alloc(ary, capa); - FL_UNSET_EMBED(ary); ARY_SET_PTR(ary, ptr); ARY_SET_CAPA(ary, capa); ARY_SET_HEAP_LEN(ary, 0); @@ -934,7 +1001,7 @@ ary_make_shared(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L1001 else { long capa = ARY_CAPA(ary), len = RARRAY_LEN(ary); const VALUE *ptr; - NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0)); + VALUE shared = ary_alloc_heap(0); VALUE vshared = (VALUE)shared; rb_ary_transient_heap_evacuate(ary, TRUE); @@ -963,8 +1030,10 @@ ary_make_substitution(VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L1030 { long len = RARRAY_LEN(ary); - if (len <= RARRAY_EMBED_LEN_MAX) { - VALUE subst = rb_ary_new2(len); + if (ary_embeddable_p(len)) { + VALUE subst = rb_ary_new_capa(len); + assert(ARY_EMBED_P(subst)); + ary_memcpy(subst, 0, len, RARRAY_CONST_PTR_TRANSIENT(ary)); ARY_SET_EMBED_LEN(subst, len); return subst; @@ -1025,6 +1094,30 @@ rb_ary_s_try_convert(VALUE dummy, VALUE ary) https://github.com/ruby/ruby/blob/trunk/array.c#L1094 return rb_check_array_type(ary); } +/* :nodoc: */ +static VALUE +rb_ary_s_new(int argc, VALUE *argv, VALUE klass) +{ + VALUE ary; + + if (klass == rb_cArray) { + long size = 0; + if (argc > 0 && FIXNUM_P(argv[0])) { + size = FIX2LONG(argv[0]); + if (size < 0) size = 0; + } + + ary = ary_new(klass, size); + + rb_obj_call_init_kw(ary, argc, argv, RB_PASS_CALLED_KEYWORDS); + } + else { + ary = rb_class_new_instance_pass_kw(argc, argv, klass); + } + + return ary; +} + /* * call-seq: * Array.new -> new_empty_array @@ -1180,15 +1273,15 @@ ary_make_partial(VALUE ary, VALUE klass, (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/