struct: avoid all O(n) behavior on access

This avoids O(n) on lookups with structs over 10 members.
This also avoids O(n) behavior on all assignments on Struct members.
Members 0..9 still use existing C methods to read in O(1) time

Benchmark results:

vm2_struct_big_aref_hi*	1.305
vm2_struct_big_aref_lo*	1.157
vm2_struct_big_aset*	3.306
vm2_struct_small_aref*	1.015
vm2_struct_small_aset*	3.273

Note: I chose use loading instructions from an array instead of writing
directly to linked-lists in compile.c for ease-of-maintainability.  We
may move the method definitions to prelude.rb-like files in the future.

I have also tested this patch with the following patch to disable
the C ref_func methods and ensured the test suite and rubyspec works

	--- a/struct.c
	+++ b/struct.c
	@@ -209,7 +209,7 @@ setup_struct(VALUE nstr, VALUE members)
		ID id = SYM2ID(ptr_members[i]);
		VALUE off = LONG2NUM(i);

	-	if (i < N_REF_FUNC) {
	+	if (0 && i < N_REF_FUNC) {
		    rb_define_method_id(nstr, id, ref_func[i], 0);
		}
		else {

* iseq.c (rb_method_for_self_aref, rb_method_for_self_aset):
  new methods to generate bytecode for struct.c
  [Feature #10575]
* struct.c (rb_struct_ref, rb_struct_set): remove
  (define_aref_method, define_aset_method): new functions
  (setup_struct): use new functions
* test/ruby/test_struct.rb: add test for struct >10 members
* benchmark/bm_vm2_struct_big_aref_hi.rb: new benchmark
* benchmark/bm_vm2_struct_big_aref_lo.rb: ditto
* benchmark/bm_vm2_struct_big_aset.rb: ditto
* benchmark/bm_vm2_struct_small_aref.rb: ditto
* benchmark/bm_vm2_struct_small_aset.rb: ditto

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@48748 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 101 insertions, 0 deletions

diff --git a/iseq.c b/iseq.c
index 8f84f88c14..15d1de698c 100644
--- a/iseq.c
+++ b/iseq.c
@@ -548,6 +548,107 @@ iseq_load(VALUE self, VALUE data, VALUE parent, VALUE opt)
     return iseqval;
 }
 
+rb_iseq_t *
+rb_method_for_self_aref(VALUE name, VALUE arg)
+{
+    VALUE iseqval = iseq_alloc(rb_cISeq);
+    rb_iseq_t *iseq;
+    VALUE path = rb_str_new2("<compiled>");
+    VALUE lineno = INT2FIX(1);
+    VALUE parent = 0;
+    VALUE misc, locals, params, exception, body, send_arg;
+    int flag = VM_CALL_FCALL | VM_CALL_ARGS_SIMPLE;
+
+    GetISeqPtr(iseqval, iseq);
+    iseq->self = iseqval;
+    iseq->local_iseq = iseq;
+
+    prepare_iseq_build(iseq, rb_sym2str(name), path, path, lineno, parent,
+		       ISEQ_TYPE_METHOD, &COMPILE_OPTION_DEFAULT);
+
+    misc = params = rb_hash_new(); /* empty */
+    locals = exception = rb_ary_new(); /* empty */
+    body = rb_ary_new();
+
+#define S(s) ID2SYM(rb_intern(#s))
+    /* def name; self[arg]; end */
+    rb_ary_push(body, lineno);
+    rb_ary_push(body, rb_ary_new3(1, S(putself)));
+    rb_ary_push(body, rb_ary_new3(2, S(putobject), arg));
+
+    /* {:mid=>:[], :flag=>264, :blockptr=>nil, :orig_argc=>1} */
+    send_arg = rb_hash_new();
+    rb_hash_aset(send_arg, S(mid), ID2SYM(idAREF));
+    rb_hash_aset(send_arg, S(flag), INT2FIX(flag));
+    rb_hash_aset(send_arg, S(blockptr), Qnil);
+    rb_hash_aset(send_arg, S(orig_argc), INT2FIX(1));
+
+    /* we do not want opt_aref for struct */
+    rb_ary_push(body, rb_ary_new3(2, S(opt_send_without_block), send_arg));
+    rb_ary_push(body, rb_ary_new3(1, S(leave)));
+#undef S
+
+    rb_iseq_build_from_ary(iseq, misc, locals, params, exception, body);
+    cleanup_iseq_build(iseq);
+
+    return iseq;
+}
+
+rb_iseq_t *
+rb_method_for_self_aset(VALUE name, VALUE arg)
+{
+    VALUE iseqval = iseq_alloc(rb_cISeq);
+    rb_iseq_t *iseq;
+    VALUE path = rb_str_new2("<compiled>");
+    VALUE lineno = INT2FIX(1);
+    VALUE parent = 0;
+    VALUE misc, locals, params, exception, body, send_arg;
+    int flag = VM_CALL_FCALL | VM_CALL_ARGS_SIMPLE;
+
+    GetISeqPtr(iseqval, iseq);
+    iseq->self = iseqval;
+    iseq->local_iseq = iseq;
+
+    prepare_iseq_build(iseq, rb_sym2str(name), path, path, lineno, parent,
+		       ISEQ_TYPE_METHOD, &COMPILE_OPTION_DEFAULT);
+
+    /* def name=(val); self[arg] = val; end */
+#define S(s) ID2SYM(rb_intern(#s))
+    misc = rb_hash_new(); /* empty */
+    locals = rb_ary_new3(1, S(val));
+    params = rb_hash_new();
+    exception = rb_ary_new(); /* empty */
+    body = rb_ary_new();
+
+    rb_hash_aset(params, S(lead_num), INT2FIX(1));
+
+    rb_ary_push(body, lineno);
+    rb_ary_push(body, rb_ary_new3(1, S(putnil)));
+    rb_ary_push(body, rb_ary_new3(1, S(putself)));
+    rb_ary_push(body, rb_ary_new3(2, S(putobject), arg));
+    rb_ary_push(body, rb_ary_new3(3, S(getlocal), INT2FIX(2), INT2FIX(0)));
+    rb_ary_push(body, rb_ary_new3(2, S(setn), INT2FIX(3)));
+
+    /* {:mid=>:[]=, :flag=>264, :blockptr=>nil, :orig_argc=>2} */
+    send_arg = rb_hash_new();
+    rb_hash_aset(send_arg, S(mid), ID2SYM(idASET));
+    rb_hash_aset(send_arg, S(flag), INT2FIX(flag));
+    rb_hash_aset(send_arg, S(blockptr), Qnil);
+    rb_hash_aset(send_arg, S(orig_argc), INT2FIX(2));
+
+    /* we do not want opt_aset for struct */
+    rb_ary_push(body, rb_ary_new3(2, S(opt_send_without_block), send_arg));
+
+    rb_ary_push(body, rb_ary_new3(1, S(pop)));
+    rb_ary_push(body, rb_ary_new3(1, S(leave)));
+#undef S
+
+    rb_iseq_build_from_ary(iseq, misc, locals, params, exception, body);
+    cleanup_iseq_build(iseq);
+
+    return iseq;
+}
+
 /*
  * :nodoc:
  */