Feature #10575
closed[RFC] struct: avoid all O(n) behavior on access
Description
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 {
Files
Updated by Anonymous almost 10 years ago
- Status changed from Open to Closed
- % Done changed from 0 to 100
Applied in changeset r48748.
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
Updated by funny_falcon (Yura Sokolov) almost 10 years ago
Couple of other struct optimizations in #10585
Updated by ko1 (Koichi Sasada) almost 10 years ago
Sorry for late.
Benchmark results:
vm2_struct_big_aref_hi* 1.305
...
how to read? seconds? compared ratio with non-opt version?
Updated by normalperson (Eric Wong) almost 10 years ago
speedup ratio (from benchmark/driver.rb)
Updated by normalperson (Eric Wong) almost 10 years ago
funny.falcon@gmail.com wrote:
Couple of other struct optimizations in #10585
Thanks. Btw, can you reproduce the issue in [ruby-core:66762]? I
cannot reproduce it anymore on 32-bit x86, so I'm not sure if further
digging is required [ruby-core:66764]