Add `Hash`able wrappers for `Value`
Opened this issue · 2 comments
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:
- Making sure that it's impossible to represent two same values with different discriminants. See #288 and #289.
- See if we can ensure that, for primitive values with a heap data, two identical values always map to the same index. I.e, we don't allocate a new
HeapNumber
orHeapBigInt
if an equal one already exists. - In general, make sure that (except for
NaN
and positive/negative zero), structural equality ofValue
maps to equality of JS values. - Implement
Hash
forBaseIndex
and for all wrappers over one.
Footnotes
-
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 forSameValue
andSameValueZero
. ↩
I've been kind of thinking that we might either want to do one of:
- 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.
- 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-doorParallelVec<(Value, Value)>
that is a key-value parallel vector (basically whatwe have now).
- 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
NaN
s as equal, and so they hash f32.to_bits()
.