[ruby-core:66790] [ruby-trunk - Feature #10575] [RFC] struct: avoid all O(n) behavior on access

Issue #10575 has been updated by Eric Wong.


 [e-mail] 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]

----------------------------------------
Feature #10575: [RFC] struct: avoid all O(n) behavior on access
https://bugs.ruby-lang.org/issues/10575#change-50366

* Author: Eric Wong
* Status: Closed
* Priority: Normal
* Assignee: Koichi Sasada
* Category: core
* Target version: current: 2.2.0
----------------------------------------
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

~~~diff
--- 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--------------------------------
struct_iseq-v1-r48725.patch (10.8 KB)


-- 
https://bugs.ruby-lang.org/