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

[Johan Tibell]

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