<feed xmlns='http://www.w3.org/2005/Atom'>
<title>ruby.git/benchmark/bm_vm2_struct_small_aref.rb, branch v2_4_0_preview2</title>
<subtitle>The Ruby Programming Language</subtitle>
<link rel='alternate' type='text/html' href='https://git.ruby-lang.org/ruby.git/'/>
<entry>
<title>struct: avoid all O(n) behavior on access</title>
<updated>2014-12-09T15:43:49+00:00</updated>
<author>
<name>normal</name>
<email>normal@b2dd03c8-39d4-4d8f-98ff-823fe69b080e</email>
</author>
<published>2014-12-09T15:43:49+00:00</published>
<link rel='alternate' type='text/html' href='https://git.ruby-lang.org/ruby.git/commit/?id=65651b34b1b5c2ef556ed44d5ebbd98838cfe8e6'/>
<id>65651b34b1b5c2ef556ed44d5ebbd98838cfe8e6</id>
<content type='text'>
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 &lt; N_REF_FUNC) {
	+	if (0 &amp;&amp; i &lt; 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 &gt;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
</content>
<content type='xhtml'>
<div xmlns='http://www.w3.org/1999/xhtml'>
<pre>
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 &lt; N_REF_FUNC) {
	+	if (0 &amp;&amp; i &lt; 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 &gt;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
</pre>
</div>
</content>
</entry>
</feed>
