On Tue, Feb 22, 2011 at 6:28 PM, Louis Wasserman
<[email protected]> 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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
