From: Eric Wong <normalperson@...>
Date: 2014-09-11T06:23:51+00:00
Subject: [ruby-core:64950] Re: [ruby-trunk - Feature #9614] [Open] ordering of non-Hash items which use st_ internally

I forget, ordering is easy to add to ihash with ccan/list.

Work-in-progress, this is only for method entries with ihash ordered
doing "ruby -e exit" (loading rubygems)

Numbers from valgrind, so "bytes allocated" does not take into account malloc
overhead of particular malloc implementations:

st (original):
  total heap usage: 48,119 allocs, 19,169 frees, 8,106,443 bytes allocated

ihash-unordered
  total heap usage: 45,571 allocs, 19,501 frees, 8,038,885 bytes allocated

ihash-ordered:
  total heap usage: 45,571 allocs, 19,501 frees, 8,089,941 bytes allocated

The reduction in overall malloc/free calls is nice; but bytes allocated
is small because we're dealing with small elements.  This makes method
entries much bigger (1 pointer for hash chaining, 2 pointers for
list_node), but reduces the need to make separate allocations for
st_table_entry.

1. http://bogomips.org/ruby.git/patch/?id=3930d8172dea41cd
   ihash: initial implementation
2. http://bogomips.org/ruby.git/patch/?id=02334f26a0c2a1f5
   convert method entries to unordered ihash
3. http://bogomips.org/ruby.git/patch/?id=fcf8e764bcd5a1c1
   preserve ordering in method entries

git clone git://bogomips.org/ruby.git branch=ihash7

(I also started working on constants, but haven't added ordering, yet).

Running benchmark suite now, I expect uncached method entries for larger
classes/modules should be faster due to reduced indirection as described
in [ruby-core:62578]

For small (currently <=5) element tables, it is like st-packed and does a
linear search (which will cross cache lines, unfortunately)