Feature #16851: Ruby hashing algorithm could be improved using Tabulation Hashing

• Status: Feedback
• Assignee: -
• Target version: -

[ana06 (Ana Maria Martinez Gomez)]

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

[jeremyevans0 (Jeremy Evans)]

• Tracker changed from Bug to Feature
• ruby -v deleted (master)
• Backport deleted (2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN)

[byroot (Jean Boussier)]

This seems interesting. I'd suggest running the hash related benchmarks included in ruby's repo: https://github.com/ruby/ruby/tree/master/benchmark

[matz (Yukihiro Matsumoto)]

Interesting!! @ana06 Do you need any help?

Matz.

[ana06 (Ana Maria Martinez Gomez)]

• Description updated (diff)

[ana06 (Ana Maria Martinez Gomez)]

@byroot (Jean Boussier)

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

@matz (Yukihiro Matsumoto)

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.

[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?

[mame (Yusuke Endoh)]

• 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.