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