[Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library

Johan Tibell johan.tibell at gmail.com
Wed Feb 23 03:45:57 CET 2011


On Tue, Feb 22, 2011 at 6:28 PM, Louis Wasserman
<wasserman.louis at gmail.com> wrote:
> Apologies!

Accepted. :)

> I was, in point of fact, working on such a patch, but I think I've been
> convinced that it's a legitimate position for a package to take.  (I'm also
> curious, Johann, about the approach you figured out that didn't cost a word
> per node!)

I'm working on a patch that provides O(1) size right now. The trick is
to define HashMap as:

data HashMap k v = HM {-# UNPACK #-} !Int !(Tree k v)

data Tree k v
    = Nil
    | Tip {-# UNPACK #-} !Hash
          {-# UNPACK #-} !(FL.FullList k v)
    | Bin {-# UNPACK #-} !Prefix
          {-# UNPACK #-} !Mask
          !(Tree k v)
          !(Tree k v)

And have insert, delete, and other operations that change the size
return both the updated tree and the size delta (-1, 0, or 1 in the
case of insert/delete). The size delta is then applied to the stored
size.

At the moment I'm trying to figure out the performance impact of
making this change.

Johan



More information about the Haskell-Cafe mailing list