[ruby-cvs:55898] normal:r48748 (trunk): struct: avoid all O(n) behavior on access

normal at ruby-lang.org normal at ruby-lang.org
Wed Dec 10 00:43:51 JST 2014


normal	2014-12-10 00:43:49 +0900 (Wed, 10 Dec 2014)

  New Revision: 48748

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=48748

  Log:
    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

  Added files:
    trunk/benchmark/bm_vm2_struct_big_aref_hi.rb
    trunk/benchmark/bm_vm2_struct_big_aref_lo.rb
    trunk/benchmark/bm_vm2_struct_big_aset.rb
    trunk/benchmark/bm_vm2_struct_small_aref.rb
    trunk/benchmark/bm_vm2_struct_small_aset.rb
  Modified files:
    trunk/ChangeLog
    trunk/iseq.c
    trunk/struct.c
    trunk/test/ruby/test_struct.rb


More information about the ruby-cvs mailing list