Project

General

Profile

Actions

Feature #10575

closed

[RFC] struct: avoid all O(n) behavior on access

Added by normalperson (Eric Wong) almost 8 years ago. Updated almost 8 years ago.

Status:
Closed
Priority:
Normal
Target version:
[ruby-core:66729]

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

struct_iseq-v1-r48725.patch (10.8 KB) struct_iseq-v1-r48725.patch normalperson (Eric Wong), 12/06/2014 12:31 AM
Actions

Also available in: Atom PDF