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

[Louis Wasserman]

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 at gmail.com
http://profiles.google.com/wasserman.louis


On Tue, Feb 22, 2011 at 9:10 PM, Johan Tibell <johan.tibell at gmail.com>wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110222/8d8651a0/attachment.htm>