Hmmmkay. I'm not entirely convinced, 'cause I've seen genuine (and benchmarked) speedups in applying some of these ideas to my TrieMap library, but I don't have any examples handy.
Louis Wasserman [email protected] http://profiles.google.com/wasserman.louis On Tue, Feb 22, 2011 at 9:10 PM, Johan Tibell <[email protected]>wrote: > On Tue, Feb 22, 2011 at 6:53 PM, Louis Wasserman > <[email protected]> wrote: > > Here's the approach I was attempting: a while back there was a proposal > to > > modify Data.Map to support a sort of zipper, including the following API: > > > > data Location k a -- represents a map with a "hole" at a particular key > > > > search :: k -> Map k a -> (Maybe a, Location k a) > > > > key :: Location k a -> k > > > > assign :: a -> Location k a -> Map k a > > clear :: Location k a -> Map k a > > > > and from here you might define > > > > insert :: k -> a -> Map k a -> Map k a > > insert k a m = case search k m of > > (_, loc) -> assign a loc > > > > The surprising thing was that this approach *increased* the speed of the > Map > > implementation by something like 7%. > > I'm pretty sure it was a decrease overall. The function under > discussion was something like insertWith. > > The direct implementation of insertWith was the fastest. The zipper > approach was 7% faster than using a naive composition of lookup and > insert to implement insertWith. The slowdown was most likely caused by > the extra O(log n) allocations required to create the zipper (in > essence that means reify the call stack of lookup). > > Johan >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
