A terrible hash map implementation

[SquidDev]

• Add several type classes for "indexable" types.
  • index: This provides .() and .?() getters.
  • mut_index: This provides a mutating setter .[]<-.
  • Add a set_index type class. This provides a setter .()<-, which returns an updated collection.
• Add hashable type class (in data/hash.ml), and instances for the basic types.
• Add a primitive mutable hash map (in data/hash/map.ml). There's a lot of work which could be done to improve this, but it's a good enough start for basic functionality.

[plt-amy]

I wonder if a HAMT implementation wouldn't be better?

[SquidDev]

But I guess it doesn't matter if everything's out of bounds for it..

Yeah, I'm fairly sure this is a safe optimisation as empty array can't be modified or indexed. Java does it, though I realise that's hardly a great commendation.

I wonder if a HAMT implementation wouldn't be better?

I don't know if it's worth having both? I definitely want some kind of mutable map structure, though am not exactly wedded to this particular design - might try out something closer to Lua's hash implementation.

[davidgarland]

If performance is your aim, I might recommend looking into robin hood hashing with backwards shift deletion. This also implies switching to open addressing and linear probing, which are better for cache. (Though, I think you ought to make the key/value pair into two individual arrays for the usual SoA benefits-- <$> on hashmaps would then no longer need to load the keys into cache as well, for instance, and the same goes for iterating over keys only.)

[SquidDev]

Thanks for the links David! I was vaguely aware of robin hood hashing, but those are articles were very useful.

I must confess this implementation was largely written from whatever I remember of algorithms courses, so is definitely not as sane as it should be. I definitely want to replace this with a better implementation.

That said, performance is a bit tricker - the backend spits out absolutely terrible Lua code, which means any memory optimisations are overshadowed by the number of closures/tables we're allocating for every call. I really need to fix this before doing any serious profiling:

-- map.[1] compiles to:
local tmp0 = _dot_28_290({
  hash = function(x) return x end,
  ["Hashable$agcy"] = {
    ["=="] = int_eq0,
    ["<>"] = function(bqq)
      return function(bqr)
        return bqq ~= bqr
      end
    end
  }
})(map)(1)

Looks like it's time to do some optimiser work again :D:.