Feature #16851
Ruby hashing algorithm could be improved using Tabulation Hashing
Description
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. For more details check the project report:
https://github.com/Ana06/ruby-tabulation/blob/master/latex/RubyTabulation_Project.pdf
Updated by jeremyevans0 (Jeremy Evans) 9 months ago
- Backport deleted (
2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN) - ruby -v deleted (
master) - Tracker changed from Bug to Feature
Updated by byroot (Jean Boussier) 9 months ago
This seems interesting. I'd suggest running the hash related benchmarks included in ruby's repo: https://github.com/ruby/ruby/tree/master/benchmark
Updated by matz (Yukihiro Matsumoto) 8 months ago
Interesting!! ana06 (Ana Maria Martinez Gomez) Do you need any help?
Matz.
Updated by ana06 (Ana Maria Martinez Gomez) 8 months ago
I'd suggest running the hash related benchmarks included in ruby's repo: https://github.com/ruby/ruby/tree/master/benchmark
For most of the benchmarks, this changes doesn't make much of a different because they are either too small hashes or use strings or symbols as keys and this is only implemented for the general keys (objects, integers, etc.). Another important detail is that in the way that it is implemented right now the filling of the random matrix may be being benchmaked (so I think that the result of a finished implementation may be even better).
It does make a difference in the bighash
benchmark. I have increased the number of elements inserted in the hash a bit to make the difference clearer. I have also added an extra benchmark, equivalent to this one but with objects instead of numbers as keys: https://github.com/ruby/ruby/commit/99e0c33655dec45a9b36850b6fe2cb36ef5f4d42
Those are the results for those two benchmarks with Simple tabulation and Quadratic Probing [ https://github.com/Ana06/ruby/tree/tabulation ]:
compare-ruby: ruby 2.8.0dev (2020-05-07T16:22:38Z master 7ded8fd29a) [x86_64-linux] built-ruby: https://github.com/Ana06/ruby/tree/tabulation Calculating -------------------------------------ยท compare-ruby built-ruby bighash_obj 0.079 0.099 i/s - 1.000 times in 12.591126s 10.078022s bighash 0.394 0.454 i/s - 1.000 times in 2.541103s 2.204265s Comparison: bighash_obj built-ruby: 0.1 i/s compare-ruby: 0.1 i/s - 1.25x slower bighash built-ruby: 0.5 i/s compare-ruby: 0.4 i/s - 1.15x slower
Those are the results for those two benchmarks with Simple tabulation and the current hash implementation (without Quadratic or Linear Probing) [ https://github.com/Ana06/ruby/tree/tabulation without 95f367a ]:
compare-ruby: ruby 2.8.0dev (2020-05-07T16:22:38Z master 7ded8fd29a) [x86_64-linux] built-ruby: https://github.com/Ana06/ruby/tree/tabulation without 95f367a Calculating ------------------------------------- compare-ruby built-ruby bighash_obj 0.081 0.094 i/s - 1.000 times in 12.271814s 10.585687s bighash 0.369 0.409 i/s - 1.000 times in 2.711338s 2.445082s Comparison: bighash_obj built-ruby: 0.1 i/s compare-ruby: 0.1 i/s - 1.16x slower bighash built-ruby: 0.4 i/s compare-ruby: 0.4 i/s - 1.11x slower
ana06 (Ana Maria Martinez Gomez) Do you need any help?
To finish it so that it can be integrated in production I do need some help. I am not sure where the good place to put this code is. Concretely:
- The filling of the random matrix shouldn't be done the first time it is needed, but it should be part of the "initialization" of Ruby (or the Hash class). But I don't know which is the best way to do this. Actually, this doesn't necessarily need to be done as I have implemented it. Simple Tabulation needs 64KB of random data. Ideally it could even be a shared memory section with other programs (I don't think we have to do something like this, but just pointing out that there may be an smarter solution).
- I have removed some functionality out by placing the Simple Tabulation code in the
any_hash
function directly. With that it is not allowed to overwrite the hash method for the hashing implementation (which maybe is ok, it is done for other objects already, related: https://bugs.ruby-lang.org/issues/16850). Using arrays as keys is also broken (at least not consistent with the previous behavior because the array id is now used). I would need some direction how to address these things (probably there is a better place to integrate this code).
There would still be some work to do, such as for example implement it for 32 bites (currently only implemented for 64). But this concretely shouldn't be a big deal.
Updated by mame (Yusuke Endoh) 3 months ago
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?
Updated by mame (Yusuke Endoh) 3 months ago
- Status changed from Open to Feedback
By replacing rb_obj_id
with other_func
, I cannot see any significant difference between the proposed patch and the current master. I believe that the large part of the performance improvement comes from the wrong omission of #hash
call. So, I set the ticket status as "Feedback".
Some advices:
- The current hash function does not simply return object_id. Instead, it mixes a random salt to make it difficult for attackers to predict hash values for security reason. You may use the initialization function to fill the random matrix.
- Not only it mixes the salt, but also it scrambles a hash value with some big primes. See the function mult_and_mix. You may want to try replacing the function with tabulation hashing.
- Before any performance measurement, please make sure it pass the test suite.