[前][次][番号順一覧][スレッド一覧]

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/

[前][次][番号順一覧][スレッド一覧]