From: mame@... Date: 2020-10-22T06:12:23+00:00 Subject: [ruby-core:100494] [Ruby master Feature#16851] Ruby hashing algorithm could be improved using Tabulation Hashing Issue #16851 has been updated by mame (Yusuke Endoh). > With that it is not allowed to overwrite the hash method for the hashing implementation (which maybe is ok It is far from okay... Your patch does not call #hash method at all. `make test` does not pass. ``` class Foo def hash raise end end h = { Foo.new => 1 } # raises nothing ``` I'm not familiar with the tabulation technique, but I guess it should use the result of `other_func` instead of `rb_obj_id`. I'm unsure if the performance measurement is affected by the omission of the call to #hash, but could you re-measure the benchmark after `make check` passed? ---------------------------------------- Feature #16851: Ruby hashing algorithm could be improved using Tabulation Hashing https://bugs.ruby-lang.org/issues/16851#change-88113 * Author: ana06 (Ana Maria Martinez Gomez) * Status: Open * Priority: Normal ---------------------------------------- I have implemented Linear Probing and Simple tabulation in Ruby: https://github.com/Ana06/ruby/compare/master...Ana06:tabulation I tested it using the following code: https://github.com/Ana06/ruby-tabulation/blob/master/benchmark_tabulation.rb It benchmarks the insertion of 600000 elements (by hashing their 64 bits ids) in an empty hash 100 times. Below are the times (in seconds) I got executing this code for different versions of the Ruby code: - master (without Simple Tabulation): 29.68 - master with Linear Probing (without Simple Tabulation): 99.76 - master with Quadratic Probing (without Simple Tabulation): 29.97 - master with Simple Tabulation: 15.76 - master with Linear Probing and Simple Tabulation: 24.23 - **master with Quadratic Probing and Simple Tabulation: 13.73** `master` refers to ruby 2.8.0dev: (2020-05-07T16:22:38Z master 7ded8fd) [x86_64-linux]. I tried with 8 x Intel i5-8265U. Although this is just a proof of concept and not something that could be already use in production, I think it proves the potential of Simple Tabulation to improve current Ruby implementation. It may be worthwhile to explore this idea further. What do you think? I did this as part of a project for my [Advanced Algorithms course](http://www.cs.columbia.edu/~andoni/advancedS20/index.html). For more details check the project report: https://github.com/Ana06/ruby-tabulation/blob/master/latex/RubyTabulation_Project.pdf -- https://bugs.ruby-lang.org/ Unsubscribe: