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

[Johan Tibell]

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).

Johan