[ruby-core:59711] [RFC] ih: new internal hash table

Was: Subject: Re: [ruby-core:59581] Re: [ruby-trunk - misc #9188] r43870 make
 benchmark/bm_so_k_nucleotide.rb slow

Eric Wong <[e-mail]> wrote:
> SASADA Koichi <[e-mail]> wrote:
> > My concern is performance regression with huge entries of fstring table
> > with this technique. Maybe we can avoid such regression with smart data
> > structure (for example, do not use st).
> 
> Yes, st_table_entry is gigantic, I think we should go back to unordered
> st for things where order does not matter.  But we can probably do
> better for the fstring table, even.

I'm trying this new hash table out.  There should be other things to
convert, and it can probably be tuned more.  But it works, so far...

The design is based on st, but uses linked-list of cache-sized arrays
for chaining, so it's as if each bucket is an st-packed array.  The
top-level buckets are one big flat array, and metadata overhead should
be low (users define entry size, so key/val need not be
uintptr_t-sized).  Delete-while-iterating is probably be slower
than st, but I haven't tested that at all.

-------------------------------8<-----------------------------
ih: internal hash implementation + convert some larger tables

Introduce a new internal hash (ih) with minimal storage overhead for
use in internal tables where order does not matter.  Performance
does not seem greatly affected[1], but memory usage seems improved
with only a few large, relatively static tables converted.

Lightly tested, but passes "make check".

running: /usr/bin/time ./ruby -v -e exit

ruby 2.2.0dev (2014-01-12 trunk 44573) [x86_64-linux]
before:
0.02user 0.00system 0:00.02elapsed 96%CPU (0avgtext+0avgdata 7432maxresident)k
0inputs+0outputs (0major+1931minor)pagefaults 0swaps

after:
0.02user 0.00system 0:00.02elapsed 96%CPU (0avgtext+0avgdata 7196maxresident)k
0inputs+0outputs (0major+1874minor)pagefaults 0swaps

Note the reduction in resident memory and pagefaults.

[1] - my numbers seem to vary between runs, could be power
management...  Independent tests very welcome!

The following changes since commit 89a3450a5521922f1093307001c32b3bd5defc00:

  test_bigmath.rb: ignore on unrelated platforms (2014-01-12 08:20:39 +0000)

are available in the git repository at:

  git://80x24.org/ruby.git ih

for you to fetch changes up to 9984684ee7892ee86db9d39f266f273c0a155fe9:

  ih: internal hash implementation + convert some larger tables (2014-01-12 09:09:07 +0000)

----------------------------------------------------------------
Eric Wong (1):
      ih: internal hash implementation + convert some larger tables

 common.mk     |   5 +
 enc/unicode.c |  80 ++++++++---
 ih.c          | 449 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ih.h          |  82 +++++++++++
 ihcommon.c    |  25 ++++
 parse.y       | 157 +++++++++++++++-----
 st.c          |   9 +-
 string.c      | 101 ++++++++-----
 8 files changed, 815 insertions(+), 93 deletions(-)
 create mode 100644 ih.c
 create mode 100644 ih.h
 create mode 100644 ihcommon.c