On Tue, Feb 22, 2011 at 6:45 PM, Johan Tibell
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