Risk of hash collisions with Dry::Core::Memoizable

[JacobEvelyn]

Hello! I'm writing on behalf of the team behind MemoWise, a Ruby memoization gem that aims to provide fast memoized lookups. First of all, I wanted to say we're big fans of Dry::Core::Memoizable—had we known about it years ago we might not have ever written our gem and instead just used yours. 😄

In a recent push to increase performance, we took inspiration from Dry::Core::Memoizable and used Array#hash directly to produce our hash keys, rather than using array keys (which the hash has to compare using both Array#hash and a more expensive Array#eql? call). This is a really clever solution @flash-gordon came up with, and it made our gem much faster.

However, after discussions among our team we've decided we don't feel comfortable with this approach because of its risk of hash collisions: two different sets of method arguments could hash to the same integer, and our gem would return incorrect memoized results. While unlikely, collisions are not impossible (which is why hashes use both #hash and #eql? when comparing keys). This behavior would also be nondeterministic and hard for users to debug because Ruby uses pseudorandom hash functions so collisions will vary between different runs of the Ruby interpreter.

We haven't noticed any hash collisions ourselves, but because the bug would be subtle we can't be confident it hasn't already happened to us, and for the time being we do not consider this optimization safe. We wanted to let you know we plan to update MemoWise to use array hash keys again instead of directly calling .hash to produce integer keys, and give you the opportunity to similarly update Dry::Core::Memoizable if you agree with our conclusion. Please let us know what you decide to do! If you decide to remove Array#hash, we'll update our benchmarks to compare against the latest version of Dry::Core::Memoizable. If you decide not to, that's okay too—we'll just link to this issue explaining the differences between our gems.