Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Hashable wrappers for Value #295

Open
andreubotella opened this issue Jul 11, 2024 · 2 comments
Open

Add Hashable wrappers for Value #295

andreubotella opened this issue Jul 11, 2024 · 2 comments

Comments

@andreubotella
Copy link
Collaborator

andreubotella commented Jul 11, 2024

Currently the implementations for Set and Map use vectors rather than hash tables, which makes them not ideal, due to Value not implementing Hash. This is in part due to JS values having multiple kinds of (even strict) equality, whereas there can only be one Hash implementation for a given type.

This could be solved, though, with wrapper structs over Value that provide a Hash implementation for each kind of equality1. This wrapper might also have to contain a pre-computed hash, if only for primitives with a heap data, since we won't have access to the agent inside the Hash implementation.

While this could be implementable right now, there are things that would ease that:

Footnotes

  1. Well, each kind of equality that forms an equivalence relation. There can't be a hash for triple-equals because NaN !== NaN, but there can be one for SameValue and SameValueZero.

@aapoalas
Copy link
Collaborator

I've been kind of thinking that we might either want to do one of:

  1. Never store floats and doubles in HashMaps and just say "that's dumb and you should feel bad". This lets us hash values directly. Floats and doubles would just do a linear search, boohoo.
  2. Always precalculate the hash of each Value at insertion time and then insert into HashMap<ValueHash, u32> where the u32 value points to an entry in a next-door ParallelVec<(Value, Value)> that is a key-value parallel vector (basically whatwe have now).

@andreubotella
Copy link
Collaborator Author

andreubotella commented Jul 11, 2024

  1. Never store floats and doubles in HashMaps and just say "that's dumb and you should feel bad". This lets us hash values directly. Floats and doubles would just do a linear search, boohoo.

For floats, the only values that are a problem are NaN, and only because they make equality not an equivalence relation. But since for regular JS values we're collapsing NaNs either way, we can override PartialEq and Hash so they do treat f32 NaNs as equal, and so they hash f32.to_bits().

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants