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

[Johan Tibell]

On Tue, Feb 22, 2011 at 6:45 PM, Johan Tibell <johan.tibell at gmail.com> wrote:
> 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

Initial numbers suggest that lookup gets 3% slower and insert/delete
6% slower. The upside is O(1) size.

Johan