dry-rb / dry-rb/dry-core

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

Open
#63 2 comments 1 reaction 0 assignees View on GitHub
bug
Dominant language
Ruby
Stars
182
Forks
41
PR merge metrics
No merged PRs in 30d

Description

Hello! I'm writing on behalf of the team behind [`MemoWise`](https://github.com/panorama-ed/memo_wise), 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`](https://github.com/dry-rb/dry-core/blob/master/lib/dry/core/memoizable.rb#L134) 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](https://github.com/panorama-ed/memo_wise#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.

Contributor guide

Open the contributing guide

Research direction

Read lib/dry/core/memoizable.rb around line 134 and review the issue's hash-collision concern. Determine whether the memoization key strategy should change, then verify the decision with relevant memoization tests and benchmarks. Done means the project has a documented, agreed resolution and matching implementation or rationale.

Written by the indexing model from the issue text.

Assessment

Tech stack
ruby
Domain
tooling
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.