[ruby-core:42304] [ruby-trunk - Feature #5903] Optimize st_table (take 2)

Issue #5903 has been updated by Yura Sokolov.


Nobuyoshi Nakada wrote:
> Another question about packing.
> Why are PKEY_POS and PVAL_POS from the tail?

It allows hash values to be very close to each other, so that while loop in `find_packed_index` runs through them very fast and does not touch another cache line of cpu.
And only when it found equal hash it jumps to check key. This allows searching in packed hash be even slightly faster than in not packed hash of same size.

Initially I experiment with variable sized packed hashes, so that `num_bins` is used and they goes from tail to avoid division by 3.
With fixed size this could be simplified.

I pushed a commit which places PKEY_POS and PVAL_POS after hashes, but in forward order.

They could be placed altogether (like `i*3`, `i*3+1`, `i*3+2`). `remove_packed_entry` should be changed accordantly. I think, this could improve iteration over hash.
----------------------------------------
Feature #5903: Optimize st_table (take 2)
https://bugs.ruby-lang.org/issues/5903

Author: Yura Sokolov
Status: Open
Priority: Normal
Assignee: 
Category: core
Target version: 2.0.0


Given some of preparations to this patches already merged into ruby-trunk,
I suggest patches for improving st_table second time (first were #5789):

1) Usage of packing for st_table of any kind, not only for numeric hashes.

Most of hashes, allocated during page render in Rails are smaller than 6 entries.
In fact, during rendering "Issues" page of Redmine, 40% of hashes not even grows
above 1 entry. They are small options hashes, passed to numerous helper methods.

This patch packs hashes upto 6 entries in a way like numeric hashes from trunk.
Also it pack hashes of size 0 and 1 into `st_table` inself, so that there is no
need to allocate any "bins" at all.

https://github.com/ruby/ruby/pull/84.patch
https://github.com/ruby/ruby/pull/84

2) Usage of specialized pool for allocating st_table, st_table_entry structures
and st_table.bins of smallest size (11)

Usage of specialized pool for this allocations give great speedup for hash creation.
Also it gives countable reduction of memory consumption.

https://github.com/ruby/ruby/pull/83.patch
https://github.com/ruby/ruby/pull/83

First patch gives little overhead for creating hashes bigger than 6 entries when applied alone.
But both patches combined are not slower than ruby-trunk for hashes of any size.

Performance testing is here https://gist.github.com/1626602


-- 
http://bugs.ruby-lang.org/