Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
    Simon Cruanes
    @c-cube
    it's quiet in here, for now :)
    Simon Cruanes
    @c-cube
    might be moving to the mailing list at https://forge.ocamlcore.org/mail/?group_id=359
    Simon Cruanes
    @c-cube
    Yotam Barnoy
    @bluddy
    heya c-cube! How about a hashmap?
    Simon Cruanes
    @c-cube
    oh hey!
    what about them? :-)
    Simon Cruanes
    @c-cube
    @bluddy is there something CCHashtbl doesn't provide and that cannot be added on top of it?
    Yotam Barnoy
    @bluddy
    It would be nice to have a persistent map with a hashable interface on the functor, so that maps with large or just boxed keys could benefit from being inserted by their hash
    you can build it on top of a regular Map, but it takes some effort and would be nice to have pre-baked
    Simon Cruanes
    @c-cube
    have you looked at CCPersistentHashtbl?
    it's not Map-based, and is not thread-safe, but works very well otherwise
    otoh, indeed, we could do something based on IntMap (with keys being the hash, and leaves being lists of key/value pairs)
    Yotam Barnoy
    @bluddy
    right, that's what i was thinking of.
    is PersistentHashtbl using a diff-array as the backing for a hashtable?
    Simon Cruanes
    @c-cube
    it's based on the same technique as persistent arrays, indeed
    it looks like a regular hashtable but the array of buckets is backed by an 'undo' structure
    in benchmarks, if used linearly, it performs very well
    Yotam Barnoy
    @bluddy
    interesting. i should check it out
    in any case, it would be nice to also have the hashmap data structure
    Simon Cruanes
    @c-cube
    based on Map or patricia trees?
    (also note: weight-balanced trees, hashtrie)
    Yotam Barnoy
    @bluddy
    i think i remember patricia trees vs red-black trees not having that big of a performance difference other than for things like join operations
    Simon Cruanes
    @c-cube
    indeed
    Yotam Barnoy
    @bluddy
    i implemented my own private version on top of Map simply because that's what was available at the time
    Simon Cruanes
    @c-cube
    but what do you need it for? compared to persistentHashtbl or hashtrie?
    (I'm interested anyway, if you want to share your implem)
    Yotam Barnoy
    @bluddy
    oh wait... you have a hashtrie?
    so that's on top of a patricia tree?
    Simon Cruanes
    @c-cube
    it's a kind of HAMT-like structure, yes
    not based on patricia trees
    (so many combinations!)
    Yotam Barnoy
    @bluddy
    OK I didn't even know about HAMT's. Let me read up on it and see if I still want hashmaps :)
    Simon Cruanes
    @c-cube
    there's also a "hamt" library on opam