* [PATCH] struct.c: speedup for big structs
@ 2015-06-22 22:00 Eric Wong
0 siblings, 0 replies; 3+ messages in thread
From: Eric Wong @ 2015-06-22 22:00 UTC (permalink / raw)
To: spew
use simple custom open-addressing hash for big structs.
Thanks to Sokolov Yura aka funny_falcon <funny.falcon@gmail.com>
in https://bugs.ruby-lang.org/issues/10585
---
struct.c | 134 +++++++++++++++++++++++++++++++++++++++++++++++----------------
1 file changed, 101 insertions(+), 33 deletions(-)
diff --git a/struct.c b/struct.c
index ff4501d..ae9653e 100644
--- a/struct.c
+++ b/struct.c
@@ -11,12 +11,13 @@
#include "internal.h"
#include "vm_core.h"
+#include "id.h"
VALUE rb_method_for_self_aref(VALUE name, VALUE arg, rb_insn_func_t func);
VALUE rb_method_for_self_aset(VALUE name, VALUE arg, rb_insn_func_t func);
VALUE rb_cStruct;
-static ID id_members;
+static ID id_members, id_back_members;
static VALUE struct_alloc(VALUE);
@@ -66,6 +67,90 @@ rb_struct_members(VALUE s)
return members;
}
+static void
+struct_set_members(VALUE klass, VALUE members)
+{
+ VALUE back = rb_ary_new();
+ members = rb_ary_dup(members);
+ if (RARRAY_LEN(members) <= 10) {
+ back = members;
+ } else {
+ long i, j, mask = 64;
+ VALUE name;
+ while (mask < RARRAY_LEN(members) * 5) mask *= 2;
+ rb_ary_resize(back, mask+1);
+ rb_ary_store(back, mask, INT2FIX(RARRAY_LEN(members)));
+ mask -= 2; /* mask = (2**k-1)*2 */
+ for (i=0; i<RARRAY_LEN(members); i++) {
+ name = RARRAY_AREF(members, i);
+
+ /* j = (id & (mask/2)) * 2 */
+ j = (SYM2ID(name) >> (ID_SCOPE_SHIFT - 1)) & mask;
+
+ for (;;) {
+ if (!RTEST(RARRAY_AREF(back, j))) {
+ rb_ary_store(back, j, name);
+ rb_ary_store(back, j + 1, INT2FIX(i));
+ break;
+ }
+ j = (j * 5 + 2) & mask; /* j=(((j/2)*5+1)&(mask/2))*2 */
+ }
+ }
+ }
+ rb_obj_freeze(back);
+ rb_ivar_set(klass, id_members, members);
+ rb_ivar_set(klass, id_back_members, back);
+ RB_GC_GUARD(members);
+}
+
+static inline int
+struct_member_pos(VALUE s, VALUE name)
+{
+ VALUE back = struct_ivar_get(rb_obj_class(s), id_back_members);
+ VALUE const * p;
+ long j, mask;
+
+ if (UNLIKELY(NIL_P(back))) {
+ rb_raise(rb_eTypeError, "uninitialized struct");
+ }
+ if (UNLIKELY(!RB_TYPE_P(back, T_ARRAY))) {
+ rb_raise(rb_eTypeError, "corrupted struct");
+ }
+
+ p = RARRAY_CONST_PTR(back);
+ mask = RARRAY_LEN(back);
+
+ if (mask <= 10) {
+ if (UNLIKELY(RSTRUCT_LEN(s) != RARRAY_LEN(back))) {
+ rb_raise(rb_eTypeError,
+ "struct size differs (%ld required %ld given)",
+ mask, RSTRUCT_LEN(s));
+ }
+ for (j=0; j<mask; j++) {
+ if (p[j] == name)
+ return j;
+ }
+ return -1;
+ }
+
+ if (UNLIKELY(RSTRUCT_LEN(s) != FIX2INT(RARRAY_AREF(back, mask-1)))) {
+ rb_raise(rb_eTypeError, "struct size differs (%d required %ld given)",
+ FIX2INT(RARRAY_AREF(back, mask-1)), RSTRUCT_LEN(s));
+ }
+
+ mask -= 3;
+ j = (SYM2ID(name) >> (ID_SCOPE_SHIFT - 1)) & mask;
+
+ for (;;) {
+ if (p[j] == name)
+ return FIX2INT(p[j + 1]);
+ if (!RTEST(p[j])) {
+ return -1;
+ }
+ j = (j * 5 + 2) & mask;
+ }
+}
+
static VALUE
rb_struct_s_members_m(VALUE klass)
{
@@ -101,16 +186,10 @@ not_a_member(ID id)
VALUE
rb_struct_getmember(VALUE obj, ID id)
{
- VALUE members, slot;
- long i, len;
-
- members = rb_struct_members(obj);
- slot = ID2SYM(id);
- len = RARRAY_LEN(members);
- for (i=0; i<len; i++) {
- if (RARRAY_AREF(members, i) == slot) {
- return RSTRUCT_GET(obj, i);
- }
+ VALUE slot = ID2SYM(id);
+ int i = struct_member_pos(obj, slot);
+ if (i != -1) {
+ return RSTRUCT_GET(obj, i);
}
not_a_member(id);
@@ -206,7 +285,7 @@ setup_struct(VALUE nstr, VALUE members)
long i, len;
OBJ_FREEZE(members);
- rb_ivar_set(nstr, id_members, members);
+ struct_set_members(nstr, members);
rb_define_alloc_func(nstr, struct_alloc);
rb_define_singleton_method(nstr, "new", rb_class_new_instance, -1);
@@ -253,7 +332,7 @@ struct_define_without_accessor(VALUE outer, const char *class_name, VALUE super,
klass = anonymous_struct(super);
}
- rb_ivar_set(klass, id_members, members);
+ struct_set_members(klass, members);
if (alloc) {
rb_define_alloc_func(klass, alloc);
@@ -722,13 +801,9 @@ rb_struct_init_copy(VALUE copy, VALUE s)
static VALUE
rb_struct_aref_sym(VALUE s, VALUE name)
{
- VALUE members = rb_struct_members(s);
- long i, len = RARRAY_LEN(members);
-
- for (i=0; i<len; i++) {
- if (RARRAY_AREF(members, i) == name) {
- return RSTRUCT_GET(s, i);
- }
+ int pos = struct_member_pos(s, name);
+ if (pos != -1) {
+ return RSTRUCT_GET(s, pos);
}
rb_name_error_str(name, "no member '% "PRIsVALUE"' in struct", name);
@@ -783,21 +858,13 @@ rb_struct_aref(VALUE s, VALUE idx)
static VALUE
rb_struct_aset_sym(VALUE s, VALUE name, VALUE val)
{
- VALUE members = rb_struct_members(s);
- long i, len = RARRAY_LEN(members);
-
- if (RSTRUCT_LEN(s) != len) {
- rb_raise(rb_eTypeError, "struct size differs (%ld required %ld given)",
- len, RSTRUCT_LEN(s));
+ int pos = struct_member_pos(s, name);
+ if (pos != -1) {
+ rb_struct_modify(s);
+ RSTRUCT_SET(s, pos, val);
+ return val;
}
- for (i=0; i<len; i++) {
- if (RARRAY_AREF(members, i) == name) {
- rb_struct_modify(s);
- RSTRUCT_SET(s, i, val);
- return val;
- }
- }
rb_name_error_str(name, "no member '% "PRIsVALUE"' in struct", name);
UNREACHABLE;
@@ -1104,6 +1171,7 @@ void
Init_Struct(void)
{
id_members = rb_intern("__members__");
+ id_back_members = rb_intern("__members_back__");
InitVM(Struct);
}
--
EW
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH] struct.c: speedup for big structs
@ 2015-06-22 22:16 Eric Wong
2015-06-30 20:11 ` Eric Wong
0 siblings, 1 reply; 3+ messages in thread
From: Eric Wong @ 2015-06-22 22:16 UTC (permalink / raw)
To: spew
use simple custom open-addressing hash for big structs.
Thanks to Sokolov Yura aka funny_falcon <funny.falcon@gmail.com>
in https://bugs.ruby-lang.org/issues/10585
---
struct.c | 155 +++++++++++++++++++++++++++++++++++++++++++++++++--------------
1 file changed, 122 insertions(+), 33 deletions(-)
diff --git a/struct.c b/struct.c
index ff4501d..fbde80d 100644
--- a/struct.c
+++ b/struct.c
@@ -11,12 +11,16 @@
#include "internal.h"
#include "vm_core.h"
+#include "id.h"
+
+/* only for struct[:field] access */
+#define AREF_HASH_THRESHOLD (10)
VALUE rb_method_for_self_aref(VALUE name, VALUE arg, rb_insn_func_t func);
VALUE rb_method_for_self_aset(VALUE name, VALUE arg, rb_insn_func_t func);
VALUE rb_cStruct;
-static ID id_members;
+static ID id_members, id_back_members;
static VALUE struct_alloc(VALUE);
@@ -66,6 +70,108 @@ rb_struct_members(VALUE s)
return members;
}
+static long
+struct_member_pos_ideal(VALUE name, long mask)
+{
+ /* (id & (mask/2)) * 2 */
+ return (SYM2ID(name) >> (ID_SCOPE_SHIFT - 1)) & mask;
+}
+
+static long
+struct_member_pos_probe(long prev, long mask)
+{
+ /* (((prev/2) * 5 + 1) & (mask/2)) * 2 */
+ return (prev * 5 + 2) & mask;
+}
+
+static void
+struct_set_members(VALUE klass, VALUE members)
+{
+ VALUE back;
+
+ members = rb_ary_dup(members);
+
+ if (RARRAY_LEN(members) <= AREF_HASH_THRESHOLD) {
+ back = members;
+ } else {
+ long i, j, mask = 64;
+ VALUE name;
+
+ while (mask < RARRAY_LEN(members) * 5) mask *= 2;
+
+ back = rb_ary_new2(mask + 1);
+ rb_ary_store(back, mask, INT2FIX(RARRAY_LEN(members)));
+ mask -= 2; /* mask = (2**k-1)*2 */
+
+ for (i=0; i<RARRAY_LEN(members); i++) {
+ name = RARRAY_AREF(members, i);
+
+ j = struct_member_pos_ideal(name, mask);
+
+ for (;;) {
+ if (!RTEST(RARRAY_AREF(back, j))) {
+ rb_ary_store(back, j, name);
+ rb_ary_store(back, j + 1, INT2FIX(i));
+ break;
+ }
+ j = struct_member_pos_probe(j, mask);
+ }
+ }
+ }
+ rb_obj_freeze(back);
+ rb_ivar_set(klass, id_members, members);
+ rb_ivar_set(klass, id_back_members, back);
+ RB_GC_GUARD(members);
+}
+
+static inline int
+struct_member_pos(VALUE s, VALUE name)
+{
+ VALUE back = struct_ivar_get(rb_obj_class(s), id_back_members);
+ VALUE const * p;
+ long j, mask;
+
+ if (UNLIKELY(NIL_P(back))) {
+ rb_raise(rb_eTypeError, "uninitialized struct");
+ }
+ if (UNLIKELY(!RB_TYPE_P(back, T_ARRAY))) {
+ rb_raise(rb_eTypeError, "corrupted struct");
+ }
+
+ p = RARRAY_CONST_PTR(back);
+ mask = RARRAY_LEN(back);
+
+ if (mask <= AREF_HASH_THRESHOLD) {
+ if (UNLIKELY(RSTRUCT_LEN(s) != RARRAY_LEN(back))) {
+ rb_raise(rb_eTypeError,
+ "struct size differs (%ld required %ld given)",
+ mask, RSTRUCT_LEN(s));
+ }
+ for (j = 0; j < mask; j++) {
+ if (p[j] == name)
+ return j;
+ }
+ return -1;
+ }
+
+ if (UNLIKELY(RSTRUCT_LEN(s) != FIX2INT(RARRAY_AREF(back, mask-1)))) {
+ rb_raise(rb_eTypeError, "struct size differs (%d required %ld given)",
+ FIX2INT(RARRAY_AREF(back, mask-1)), RSTRUCT_LEN(s));
+ }
+
+ mask -= 3;
+ j = struct_member_pos_ideal(name, mask);
+
+ for (;;) {
+ if (p[j] == name)
+ return FIX2INT(p[j + 1]);
+ if (!RTEST(p[j])) {
+ return -1;
+ }
+ j = struct_member_pos_probe(j, mask);
+ }
+}
+
static VALUE
rb_struct_s_members_m(VALUE klass)
{
@@ -101,16 +207,10 @@ not_a_member(ID id)
VALUE
rb_struct_getmember(VALUE obj, ID id)
{
- VALUE members, slot;
- long i, len;
-
- members = rb_struct_members(obj);
- slot = ID2SYM(id);
- len = RARRAY_LEN(members);
- for (i=0; i<len; i++) {
- if (RARRAY_AREF(members, i) == slot) {
- return RSTRUCT_GET(obj, i);
- }
+ VALUE slot = ID2SYM(id);
+ int i = struct_member_pos(obj, slot);
+ if (i != -1) {
+ return RSTRUCT_GET(obj, i);
}
not_a_member(id);
@@ -206,7 +306,7 @@ setup_struct(VALUE nstr, VALUE members)
long i, len;
OBJ_FREEZE(members);
- rb_ivar_set(nstr, id_members, members);
+ struct_set_members(nstr, members);
rb_define_alloc_func(nstr, struct_alloc);
rb_define_singleton_method(nstr, "new", rb_class_new_instance, -1);
@@ -253,7 +353,7 @@ struct_define_without_accessor(VALUE outer, const char *class_name, VALUE super,
klass = anonymous_struct(super);
}
- rb_ivar_set(klass, id_members, members);
+ struct_set_members(klass, members);
if (alloc) {
rb_define_alloc_func(klass, alloc);
@@ -722,13 +822,9 @@ rb_struct_init_copy(VALUE copy, VALUE s)
static VALUE
rb_struct_aref_sym(VALUE s, VALUE name)
{
- VALUE members = rb_struct_members(s);
- long i, len = RARRAY_LEN(members);
-
- for (i=0; i<len; i++) {
- if (RARRAY_AREF(members, i) == name) {
- return RSTRUCT_GET(s, i);
- }
+ int pos = struct_member_pos(s, name);
+ if (pos != -1) {
+ return RSTRUCT_GET(s, pos);
}
rb_name_error_str(name, "no member '% "PRIsVALUE"' in struct", name);
@@ -783,21 +879,13 @@ rb_struct_aref(VALUE s, VALUE idx)
static VALUE
rb_struct_aset_sym(VALUE s, VALUE name, VALUE val)
{
- VALUE members = rb_struct_members(s);
- long i, len = RARRAY_LEN(members);
-
- if (RSTRUCT_LEN(s) != len) {
- rb_raise(rb_eTypeError, "struct size differs (%ld required %ld given)",
- len, RSTRUCT_LEN(s));
+ int pos = struct_member_pos(s, name);
+ if (pos != -1) {
+ rb_struct_modify(s);
+ RSTRUCT_SET(s, pos, val);
+ return val;
}
- for (i=0; i<len; i++) {
- if (RARRAY_AREF(members, i) == name) {
- rb_struct_modify(s);
- RSTRUCT_SET(s, i, val);
- return val;
- }
- }
rb_name_error_str(name, "no member '% "PRIsVALUE"' in struct", name);
UNREACHABLE;
@@ -1104,6 +1192,7 @@ void
Init_Struct(void)
{
id_members = rb_intern("__members__");
+ id_back_members = rb_intern("__members_back__");
InitVM(Struct);
}
--
EW
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH] struct.c: speedup for big structs
2015-06-22 22:16 Eric Wong
@ 2015-06-30 20:11 ` Eric Wong
0 siblings, 0 replies; 3+ messages in thread
From: Eric Wong @ 2015-06-30 20:11 UTC (permalink / raw)
To: spew
Eric Wong <e@80x24.org> wrote:
> use simple custom open-addressing hash for big structs.
>
> Thanks to Sokolov Yura aka funny_falcon <funny.falcon@gmail.com>
> in https://bugs.ruby-lang.org/issues/10585
Will squash the following when I commit.
Freezing __members__ is necessary, but
RB_GC_GUARD isn't needed since __members__ already becomes an ivar.
diff --git a/struct.c b/struct.c
index fbde80d..eda5673 100644
--- a/struct.c
+++ b/struct.c
@@ -84,12 +84,13 @@ struct_member_pos_probe(long prev, long mask)
return (prev * 5 + 2) & mask;
}
-static void
+static VALUE
struct_set_members(VALUE klass, VALUE members)
{
VALUE back;
members = rb_ary_dup(members);
+ rb_obj_freeze(members);
if (RARRAY_LEN(members) <= AREF_HASH_THRESHOLD) {
back = members;
@@ -121,7 +122,8 @@ struct_set_members(VALUE klass, VALUE members)
rb_obj_freeze(back);
rb_ivar_set(klass, id_members, members);
rb_ivar_set(klass, id_back_members, back);
- RB_GC_GUARD(members);
+
+ return members;
}
static inline int
@@ -305,8 +307,7 @@ setup_struct(VALUE nstr, VALUE members)
const VALUE *ptr_members;
long i, len;
- OBJ_FREEZE(members);
- struct_set_members(nstr, members);
+ members = struct_set_members(nstr, members);
rb_define_alloc_func(nstr, struct_alloc);
rb_define_singleton_method(nstr, "new", rb_class_new_instance, -1);
^ permalink raw reply related [flat|nested] 3+ messages in thread
end of thread, other threads:[~2015-06-30 20:11 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-06-22 22:00 [PATCH] struct.c: speedup for big structs Eric Wong
-- strict thread matches above, loose matches on Subject: below --
2015-06-22 22:16 Eric Wong
2015-06-30 20:11 ` Eric Wong
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).