This is what I didn't touch this issue yet (maybe not a big problem). We can generalize the last issue as "compaction". I'll have more time to work on this in April. Although I am a bit busy right now with work on GCC6 release. Thanks, I really appreciate your opinion. This variant achieved the best average improvement and no any This is actually seventh variant of hash tables I tried in MRI.
#Level hashtab review code#
In many cases speed is achieved by methods which requires more memory.įor example, Intel compiler generates much bigger code than GCC toĪchieve better performance (this is most important competitive Is cheap and it will be much cheaper with new coming memory I consider the speed is the first priority these days (especially when memory Smaller memory usage is importantįor better code locality too (although a better code locality does not mean aįaster code automatically - the access patter is important too). Reading the responses to all of which I am going to answer, I see peopleĪre worrying about memory usage. In the proposed implementation, the table size can be decreased.
This evaluation excludes cases when the current hash table uses packedĮlements (up to 6). Is less, the new array size will be the same or will be smaller. Rebuilding means 100% of array element usage before it. Is because, when the hash table rebuilds, the element array Worst case scenario, memory usage will be about the same as for theĬurrent hash tables taking into account that the element size is nowġ/2 of the old size and the element array minimal usage is 50%. St_table_array4.mbox (89.5 KB) st_table_array4.mbox St_table_array2.mbox (102 KB) st_table_array2.mbox St_table_array.mbox (102 KB) st_table_array.mbox New-hash-table-benchmarks.patch (1.34 KB) new-hash-table-benchmarks.patch Strong_hash.patch (8.08 KB) strong_hash.patch But I am keen to learn and work onĭownload all files st-march31.patch (114 KB) st-march31.patch
#Level hashtab review Patch#
This is my first patch for MRI and may be my proposal and Or in a less convenient way as pull request changes ARM results areĪnalogous - no any benchmark performance degradation and about the The average performance improvement is more 50%. Make benchmark-each ITEM=bm_hash OPTS='-r 3 -v' COMPARE_RUBY='' The new implementation was benchmarked on 21 MRI hash table benchmarksįor two most widely used targets x86-64 (Intel 4.2GHz i7-4790K) and ARM Traversing elements by their inclusion order.Ī more detailed description of the proposed implementation can beįound in the top comment of the file st.c. Removes pointer chaising on the doubly linked lists used for O removing doubly linked lists and putting the elements into an arrayįor accessing to elements by their inclusion order.
To move from chaining hash tables to open addressing hash tablesĭue to their better fit to modern CPU memory organizations. Removing hash collision lists lets us avoid *pointer chasing*, aĬommon problem that produces bad data locality. O switching to open addressing hash tables for access by keys. The new hash table implementation achieves a better data locality Well to modern processor cache organization, which requires better The current implementation of Ruby hash tables does not fit So CPU is much faster at reading data stored close to each Reads one or a few lines of the cache from memory (or another level ofĬache). Modern processors have several levels of cache. Tables (major files st.c and include/ruby/st.h). Hello, the following patch contains a new implementation of hash
0 kommentar(er)
