From: Eric Wong Date: 2014-01-12T09:41:07+00:00 Subject: [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 wrote: > SASADA Koichi 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