trynova/nova

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 or HeapBigInt if an equal one already exists.
  • In general, make sure that (except for NaN and positive/negative zero), structural equality of Value maps to equality of JS values.
  • Implement Hash for BaseIndex and for all wrappers over one.

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.

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).
  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().