From: normalperson@...
Date: 2014-12-06T00:31:14+00:00
Subject: [ruby-core:66729] [ruby-trunk - Feature #10575] [Open] [RFC] struct: avoid all O(n) behavior on access

Issue #10575 has been reported by Eric Wong.

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

* Author: Eric Wong
* Status: Open
* 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

--- 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/