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

Johan Tibell johan.tibell at gmail.com
Wed Feb 23 04:10:31 CET 2011

On Tue, Feb 22, 2011 at 6:53 PM, Louis Wasserman
<wasserman.louis at gmail.com> 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).


More information about the Haskell-Cafe mailing list