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

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 wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis On Tue, Feb 22, 2011 at 9:10 PM, Johan Tibell wrote:

On Tue, Feb 22, 2011 at 6:53 PM, Louis Wasserman 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