Feature #18611
closedPromote best practice for combining multiple values into a hash code
Description
User-defined hash methods often work by combining the hash code of several values into one. This requires some logic to combine the values. In our experience, users are making a variety of choices for the algorithm for this, and in many cases are picking an option which may not be the best for security and performance in multiple ways. It's also a shame that users are having to think about how to do this basic operation themselves.
For example, this hash method creates a single hash code by combining the hash value of three values that make up the object. The user has combined the values using the xor operator and multiplication by prime numbers to distribute bits. This is an ok way to combine multiple values into a hash code.
def hash
x.hash ^ (y.hash * 3) ^ (z.hash * 5)
end
But users have to know to do this, and they sometimes get it wrong, writing things like this.
def hash
x.hash ^ y.hash ^ z.hash
end
This isn't distributing the bits very well. A bad hash code may harm performance if it cause more collisions in a hash table. Collisions may also cause excess cache eviction, which would further harm performance. If performance is reduced in this way there's a potential security risk due to denial-of-service. (We don't think this is an immediate practical security problem, which is why we're discussing in the open issue tracker, not the security mailing list.)
The x.hash ^ (y.hash * 3) ^ (z.hash * 5)
pattern is still not ideal, as users have to manually write it, and it's a lot of logic to execute in the Ruby interpreter, when it could be possibly be done in native code instead. A better pattern we think is this:
def hash
[x, y, z].hash
end
This leaves the logic of creating a suitable and safe hash value to [...].hash
, which does it correctly.
Why doesn't everyone already use this pattern? Because it's not documented as the right thing to do. We want to present a couple of options for what could be done to encourage people to use this pattern or an equivalent, to help people write more concise and clear code that is also more performant and secure.
Document [...].hash
as best practice and optimise it¶
If we want people to use [...].hash
, we should say that in the documentation for Kernel#hash
as the best practice. Wording along the lines of
If you're implementing a hash code for a compound set of values, best practice is to combine them with
[...].hash
. For example....
This way people reading the documentation on Kernel#hash
get pointed in the clear, concise, performant, secure direction.
We can combine this recommendation with an optimisation to [...].hash
to remove the array allocation in implementation of Ruby without escape analysis and scalar replacement, similar to what is done for Array#min
and #max
. This way the best practice is even faster.
Introduce a new similar method, but specifically for the purpose so it is discoverable¶
A second option is to introduce a new method, specifically for this task, hash_objects(...)
. This is inspired By Java's Objects.hash(...)
. The reason for the new method is that it should make it more discoverable - if you go looking for a tool to combine hash values you'd find one. We'd still link to it from Kernel#hash
. This method would not require the array allocation removal optimisation, as it's just a simple call.
Examples of hash methods¶
Even the MRI codebase has some suboptimal hash methods we don't need to look very far for examples. For example lib lib/resolv.rb
, these two hash methods don't distribute the bits they combine
- https://github.com/ruby/ruby/blob/c445963575a8572f6b0baf7135093c128adab3b9/lib/resolv.rb#L1734
- https://github.com/ruby/ruby/blob/c445963575a8572f6b0baf7135093c128adab3b9/lib/resolv.rb#L1307
Both these examples could be replaced with either of our proposals.
A good example of someone already using best practice is this.
But this would still be faster with the optimisation we proposed, or using hash_objects(...)
, as that'd remove the array allocation and the hash
call.
Other things we've already done¶
We've proposed a RuboCop cop to try to catch the pattern we think is suboptimal https://github.com/rubocop/rubocop/pull/10441.
Co-authored with @sambostock (Sam Bostock).
Updated by Dan0042 (Daniel DeLorme) over 2 years ago
chrisseaton (Chris Seaton) wrote:
A better pattern we think is this:
def hash [x, y, z].hash end
Not a bad idea, but wouldn't this be even better?
def hash
[self.class, x, y, z].hash
end
Which is roughly what Struct does, I believe
X = Struct.new(:a, :b, :c)
Y = Struct.new(:a, :b, :c)
X.new(1,2,3).hash #=> 1941937414662583733
X.new(1,2,3).hash #=> 1941937414662583733
Y.new(1,2,3).hash #=> 1583914263362372853
And at the same time Struct also defines eql?
to follow the same rules as hash
. So maybe a better "best practice" would be to inherit from Struct when you want hash/eql based on a compound set of values. I think this makes the "Value Struct" proposed in #16122 more important, since you may not want that class to be Enumerable.
Updated by chrisseaton (Chris Seaton) over 2 years ago
Yes we could recommend adding class
to the mixture. That's an argument for hash_values
since if it has self
already and can fix in the class itself.
I think refactoring lots of work to use Struct
is a bit more radical. There are existing APIs that we may not want to modify like that.
Updated by Eregon (Benoit Daloze) over 2 years ago
Including the class is often (maybe even always?) unnecessary, and does impact performance.
Struct is special because it generates generic classes, so there it makes sense to include the class, but that's about the only case where it does IMHO.
I think [a, b, c].hash
is the best by far, could you open a PR to document that?
Adding a new method would prevent adopting it now and just delay solving this problem, I don't think it's a productive way if an existing way already works fine ([a, b, c].hash
).
(BTW, hash_objects
would still likely allocate an array (internal or Ruby-level) for the var-args, so that's worse than a literal array actually.)
Updated by byroot (Jean Boussier) over 2 years ago
Including the class is often (maybe even always?) unnecessary, and does impact performance.
Could you elaborate a bit more on this? In my mind #hash
should include all the elements that may change the result of #eql?
, and it's common (if not best practice) for #eql? / #==
to start with other.class == self.class
.
That particularly make sense when you have some kinds of value objects for which the class is an important metadata, e.g. trees of nodes etc.
Updated by Eregon (Benoit Daloze) over 2 years ago
I think an eql?
implementation should either not check the class, and assume it will be used a key with objects of the same class, or do return false unless other.is_a?(MyClass)
.
Another way to see this is why the other.class == self.class
is ignoring the singleton class? Because it does not matter in most cases.
So if one defines eql?
on a non-leaf class (or a class which has at least 1 subclass), I think they need to ask themselves do I want instances of different subclasses to be eql? or not.
I could imagine yes, for instance if a subclass is used to optimize some methods for a given well-known instance.
Updated by chrisseaton (Chris Seaton) over 2 years ago
Implemented in https://github.com/ruby/ruby/pull/5805
Updated by Eregon (Benoit Daloze) over 2 years ago
Regarding my last reply, I changed my mind, including the class is useful to avoid unintentional hash conflicts between unrelated classes for a Hash which contains keys of various types, more details here: https://github.com/ruby/ruby/pull/5805#discussion_r851650129
Updated by tenderlovemaking (Aaron Patterson) over 2 years ago
I think this is a good idea. Searching GitHub shows many example of the not-so-great XOR pattern, but also shows many people doing [a, b, c].hash
. It makes sense to me that we promote the later and optimize it as well.
Updated by sambostock (Sam Bostock) over 2 years ago
I found some interesting implementations while working on the Rubocop Cop, including some in Ruby itself. For example:
In related news, the cop has been merged into Rubocop 1.28, although it is worth noting it is not enabled by default.
Updated by ioquatix (Samuel Williams) over 2 years ago
This makes me happy, thanks everyone!