Project

General

Profile

Feature #10585 ยป 0004-struct.c-speedup-for-big-structs.patch

funny_falcon (Yura Sokolov), 12/10/2014 02:31 PM

View differences:

struct.c
12 12
#include "internal.h"
13 13
#include "vm_core.h"
14 14
#include "method.h"
15
#include "id.h"
15 16

  
16 17
VALUE rb_method_for_self_aref(VALUE name, VALUE arg);
17 18
VALUE rb_method_for_self_aset(VALUE name, VALUE arg);
18 19

  
19 20
VALUE rb_cStruct;
20
static ID id_members;
21
static ID id_members, id_back_members;
21 22

  
22 23
static VALUE struct_alloc(VALUE);
23 24

  
......
66 67
    return members;
67 68
}
68 69

  
70
static void
71
struct_set_members(VALUE klass, VALUE members)
72
{
73
    VALUE back = rb_ary_new();
74
    members = rb_ary_dup(members);
75
    if (RARRAY_LEN(members) <= 10) {
76
	back = members;
77
    } else {
78
	long i, j, mask = 64;
79
	VALUE name;
80
	while (mask < RARRAY_LEN(members) * 5) mask *= 2;
81
	rb_ary_resize(back, mask+1);
82
	rb_ary_store(back, mask, INT2FIX(RARRAY_LEN(members)));
83
	mask -= 2;						/* mask = (2**k-1)*2 */
84
	for (i=0; i<RARRAY_LEN(members); i++) {
85
	    name = RARRAY_AREF(members, i);
86
	    j = (SYM2ID(name) >> (ID_SCOPE_SHIFT - 1)) & mask;	/* j = (id & (mask/2)) * 2 */
87
	    for (;;) {
88
		if (!RTEST(RARRAY_AREF(back, j))) {
89
		    rb_ary_store(back, j, name);
90
		    rb_ary_store(back, j + 1, INT2FIX(i));
91
		    break;
92
		}
93
		j = (j * 5 + 2) & mask;				/* j=(((j/2)*5+1)&(mask/2))*2 */
94
	    }
95
	}
96
    }
97
    rb_obj_freeze(back);
98
    rb_ivar_set(klass, id_members, members);
99
    rb_ivar_set(klass, id_back_members, back);
100
    RB_GC_GUARD(members);
101
}
102

  
103
static inline int
104
struct_member_pos(VALUE s, VALUE name)
105
{
106
    VALUE back = struct_ivar_get(rb_obj_class(s), id_back_members);
107
    VALUE const * p;
108
    long j, mask;
109

  
110
    if (UNLIKELY(NIL_P(back))) {
111
	rb_raise(rb_eTypeError, "uninitialized struct");
112
    }
113
    if (UNLIKELY(!RB_TYPE_P(back, T_ARRAY))) {
114
	rb_raise(rb_eTypeError, "corrupted struct");
115
    }
116

  
117
    p = RARRAY_CONST_PTR(back);
118
    mask = RARRAY_LEN(back);
119
    if (mask <= 10) {
120
	if (UNLIKELY(RSTRUCT_LEN(s) != RARRAY_LEN(back))) {
121
	    rb_raise(rb_eTypeError, "struct size differs (%ld required %ld given)",
122
		     mask, RSTRUCT_LEN(s));
123
	}
124
	for (j=0; j<mask; j++) {
125
	    if (p[j] == name)
126
		return j;
127
	}
128
	return -1;
129
    }
130
    if (UNLIKELY(RSTRUCT_LEN(s) != FIX2INT(RARRAY_AREF(back, mask-1)))) {
131
	rb_raise(rb_eTypeError, "struct size differs (%d required %ld given)",
132
		 FIX2INT(RARRAY_AREF(back, mask-1)), RSTRUCT_LEN(s));
133
    }
134
    mask -= 3;
135
    j = (SYM2ID(name) >> (ID_SCOPE_SHIFT - 1)) & mask;
136
    for (;;) {
137
	if (p[j] == name)
138
	    return FIX2INT(p[j + 1]);
139
	if (!RTEST(p[j])) {
140
	    return -1;
141
	}
142
	j = (j * 5 + 2) & mask;
143
    }
144
}
145

  
69 146
static VALUE
70 147
rb_struct_s_members_m(VALUE klass)
71 148
{
......
101 178
VALUE
102 179
rb_struct_getmember(VALUE obj, ID id)
103 180
{
104
    VALUE members, slot;
105
    long i, len;
106

  
107
    members = rb_struct_members(obj);
108
    slot = ID2SYM(id);
109
    len = RARRAY_LEN(members);
110
    for (i=0; i<len; i++) {
111
	if (RARRAY_AREF(members, i) == slot) {
112
	    return RSTRUCT_GET(obj, i);
113
	}
181
    VALUE slot = ID2SYM(id);
182
    int i = struct_member_pos(obj, slot);
183
    if (i != -1) {
184
	return RSTRUCT_GET(obj, i);
114 185
    }
115 186
    not_a_member(id);
116 187

  
......
243 314
    long i, len;
244 315

  
245 316
    OBJ_FREEZE(members);
246
    rb_ivar_set(nstr, id_members, members);
317
    struct_set_members(nstr, members);
247 318

  
248 319
    rb_define_alloc_func(nstr, struct_alloc);
249 320
    rb_define_singleton_method(nstr, "new", rb_class_new_instance, -1);
......
295 366
	klass = anonymous_struct(super);
296 367
    }
297 368

  
298
    rb_ivar_set(klass, id_members, members);
369
    struct_set_members(klass, members);
299 370

  
300 371
    if (alloc) {
301 372
	rb_define_alloc_func(klass, alloc);
......
764 835
static VALUE
765 836
rb_struct_aref_sym(VALUE s, VALUE name)
766 837
{
767
    VALUE members = rb_struct_members(s);
768
    long i, len = RARRAY_LEN(members);
769

  
770
    for (i=0; i<len; i++) {
771
	if (RARRAY_AREF(members, i) == name) {
772
	    return RSTRUCT_GET(s, i);
773
	}
838
    int pos = struct_member_pos(s, name);
839
    if (pos != -1) {
840
	return RSTRUCT_GET(s, pos);
774 841
    }
775 842
    rb_name_error_str(name, "no member '% "PRIsVALUE"' in struct", name);
776 843

  
......
825 892
static VALUE
826 893
rb_struct_aset_sym(VALUE s, VALUE name, VALUE val)
827 894
{
828
    VALUE members = rb_struct_members(s);
829
    long i, len = RARRAY_LEN(members);
830

  
831
    if (RSTRUCT_LEN(s) != len) {
832
	rb_raise(rb_eTypeError, "struct size differs (%ld required %ld given)",
833
		 len, RSTRUCT_LEN(s));
895
    int pos = struct_member_pos(s, name);
896
    if (pos != -1) {
897
	rb_struct_modify(s);
898
	RSTRUCT_SET(s, pos, val);
899
	return val;
834 900
    }
835 901

  
836
    for (i=0; i<len; i++) {
837
	if (RARRAY_AREF(members, i) == name) {
838
	    rb_struct_modify(s);
839
	    RSTRUCT_SET(s, i, val);
840
	    return val;
841
	}
842
    }
843 902
    rb_name_error_str(name, "no member '% "PRIsVALUE"' in struct", name);
844 903

  
845 904
    UNREACHABLE;
......
1146 1205
Init_Struct(void)
1147 1206
{
1148 1207
    id_members = rb_intern("__members__");
1208
    id_back_members = rb_intern("__members_back__");
1149 1209

  
1150 1210
    InitVM(Struct);
1151 1211
}
1152
-