Project

General

Profile

Actions

Feature #12142

closed

Hash tables with open addressing

Added by vmakarov (Vladimir Makarov) about 8 years ago. Updated over 3 years ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:74124]

Description

  Hello, the following patch contains a new implementation of hash 
 tables (major files st.c and include/ruby/st.h). 

   Modern processors have several levels of cache.    Usually,the CPU 
 reads one or a few lines of the cache from memory (or another level of 
 cache).    So CPU is much faster at reading data stored close to each 
 other.    The current implementation of Ruby hash tables does not fit 
 well to modern processor cache organization, which requires better 
 data locality for faster program speed. 

 The new hash table implementation achieves a better data locality 
 mainly by 

   o switching to open addressing hash tables for access by keys. 
     Removing hash collision lists lets us avoid *pointer chasing*, a 
     common problem that produces bad data locality.    I see a tendency 
     to move from chaining hash tables to open addressing hash tables 
     due to their better fit to modern CPU memory organizations. 
     CPython recently made such switch 
     (https://hg.python.org/cpython/file/ff1938d12240/Objects/dictobject.c). 
     PHP did this a bit earlier 
     https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html. 
     GCC has widely-used such hash tables 
     (https://gcc.gnu.org/svn/gcc/trunk/libiberty/hashtab.c) internally 
     for more than 15 years. 

   o removing doubly linked lists and putting the elements into an array 
     for accessing to elements by their inclusion order.    That also 
     removes pointer chaising on the doubly linked lists used for 
     traversing elements by their inclusion order. 

 A more detailed description of the proposed implementation can be 
 found in the top comment of the file st.c. 

 The new implementation was benchmarked on 21 MRI hash table benchmarks 
 for two most widely used targets x86-64 (Intel 4.2GHz i7-4790K) and ARM 
 (Exynos 5410 - 1.6GHz Cortex-A15): 

 make benchmark-each ITEM=bm_hash OPTS='-r 3 -v' COMPARE_RUBY='<trunk ruby>' 

 Here the results for x86-64: 

 hash_aref_dsym         1.094 
 hash_aref_dsym_long            1.383 
 hash_aref_fix          1.048 
 hash_aref_flo          1.860 
 hash_aref_miss         1.107 
 hash_aref_str          1.107 
 hash_aref_sym          1.191 
 hash_aref_sym_long             1.113 
 hash_flatten           1.258 
 hash_ident_flo         1.627 
 hash_ident_num         1.045 
 hash_ident_obj         1.143 
 hash_ident_str         1.127 
 hash_ident_sym         1.152 
 hash_keys              2.714 
 hash_shift             2.209 
 hash_shift_u16         1.442 
 hash_shift_u24         1.413 
 hash_shift_u32         1.396 
 hash_to_proc           2.831 
 hash_values            2.701 

 The average performance improvement is more 50%.    ARM results are 
 analogous -- no any benchmark performance degradation and about the 
 same average improvement. 

 The patch can be seen as 

 https://github.com/vnmakarov/ruby/compare/trunk...hash_tables_with_open_addressing.patch 

 or in a less convenient way as pull request changes 

 https://github.com/ruby/ruby/pull/1264/files 


 This is my first patch for MRI and may be my proposal and 
 implementation have pitfalls.    But I am keen to learn and work on 
 inclusion of this code into MRI. 

Files

st-march31.patch (114 KB) st-march31.patch vmakarov (Vladimir Makarov), 04/01/2016 03:37 AM
base.patch (93.8 KB) base.patch vmakarov (Vladimir Makarov), 04/29/2016 09:55 PM
hash.patch (4.48 KB) hash.patch vmakarov (Vladimir Makarov), 04/29/2016 09:55 PM
strong_hash.patch (8.08 KB) strong_hash.patch vmakarov (Vladimir Makarov), 04/29/2016 09:55 PM
city.patch (19.4 KB) city.patch vmakarov (Vladimir Makarov), 04/29/2016 09:55 PM
new-hash-table-benchmarks.patch (1.34 KB) new-hash-table-benchmarks.patch Missed new hash table benchmarks vmakarov (Vladimir Makarov), 04/30/2016 02:28 PM
size16.png (6.91 KB) size16.png Sizes of tables upto 16 elements vmakarov (Vladimir Makarov), 11/04/2016 09:22 PM
size256.png (6.95 KB) size256.png Sizes of tables upto 256 elements vmakarov (Vladimir Makarov), 11/04/2016 09:22 PM
size60000.png (7.59 KB) size60000.png Sizes of tables upto 60K elements vmakarov (Vladimir Makarov), 11/04/2016 09:23 PM
st_table_array.mbox (102 KB) st_table_array.mbox funny_falcon (Yura Sokolov), 11/04/2016 09:29 PM
st_table_array2.mbox (102 KB) st_table_array2.mbox (one line change - "security" fix) funny_falcon (Yura Sokolov), 11/05/2016 08:47 AM
st_table_array4.mbox (89.5 KB) st_table_array4.mbox funny_falcon (Yura Sokolov), 11/05/2016 04:58 PM

Related issues 2 (0 open2 closed)

Related to Ruby master - Feature #5903: Optimize st_table (take 2)Closednobu (Nobuyoshi Nakada)Actions
Related to Ruby master - Bug #13002: Hash calculations no longer using universal hashingClosednaruse (Yui NARUSE)Actions
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like1Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0