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
    Yotam Barnoy
    @bluddy
    ok. pretty cool data structure. Looks better than a hashmap, so I'm good.
    Simon Cruanes
    @c-cube
    test for perf first!
    Yotam Barnoy
    @bluddy
    i will when i get a chance
    great library btw
    Simon Cruanes
    @c-cube
    containers? thanks! :)
    Yotam Barnoy
    @bluddy
    Just ran some quick benchmarks. Hashtries are impressive, at least for lookups: random lookups run almost at the speed of regular hashtables. Random inserts are just a tad faster than regular maps, which on my machine is around 6 times slower than hashtables. I tested with everything specialized for integers, so I'm sure the ratio vs regular maps will improve as bigger types are used. I also like how persistant hashtables are around 1/2 the insert speed of regular hashtables, but around the same lookup speed.
    Simon Cruanes
    @c-cube
    nice!
    also I've added an API for mutating hashtries (batch updates) and my benchmarks show that they lower the allocations