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 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
    Simon Cruanes
    @c-cube
    (the benchmarks are in the containers' repo, just in case)
    Yotam Barnoy
    @bluddy
    Am I misremembering, or did you use to have some monadic code in containers? Is it gone?
    Simon Cruanes
    @c-cube
    It's not gone. What are you looking for?
    There are >>= combinators in at least CCList, CCOpt, CCResult, CCRandom
    Yotam Barnoy
    @bluddy
    ah ok, I was looking at CCMap. Wouldn't it make sense to add it to the other data structures?
    Also, the organization of 'core' and 'data' is really confusing. I never remember which is which, and end up going back and forth looking for (and missing) files when I'm seeking them. Would it make sense to just have one directory?
    Simon Cruanes
    @c-cube
    I don't think it makes sense for Map/Set (they are not really monads… or I missed sth)
    no, it doesn't really make sense, sorry ^^
    core/ is the core extension to stdlib
    data/ is an optional collection of data structures
    that are not directly in the stdlib
    Yotam Barnoy
    @bluddy
    Sorry -- didn't mean an actual monadic instance of Map. What I meant was to have a Traversable functor for these data structures, so you could run map_m on them etc. Haven't touched haskell in a while, so these concepts were a bit of a blur.
    Simon Cruanes
    @c-cube
    ah, I see. The issue is that I would need access to the structure's internals for implementing this kind of stuff (same as for implementing iterators)…
    Yotam Barnoy
    @bluddy
    oh. well, what would be the downside of including and modifying the stdlib implementation files?
    Simon Cruanes
    @c-cube
    1/ license 2/ desynchronisation
    3/ the types would become different
    Yotam Barnoy
    @bluddy
    So... no problem whatsoever. Awesome :smile:
    1. Can't really comment on. 2. not too hard to update with code as it changes, particularly if changes are minor and strategic 3. many of these types are different already since they're using functors
    Simon Cruanes
    @c-cube
    they're not! functors can preserve typing :-)
    Map.Make(String).t is a valid type now