Fwd: Map / IntMap laziness (was: export toDescList from Data.Map)

[apfelmus]

Scott Dillard wrote:
> (Sorry for the spam, but I don't understand why the body of my messages is
> being stripped. Something to do with the attachments?)

I'm reading it through gmane and it works for me...

> ---------- Forwarded message ----------
> From: Scott Dillard <sedillard at gmail.com>
> Date: Fri, Sep 26, 2008 at 11:57 AM
> Subject: Map / IntMap laziness (was: export toDescList from Data.Map)
> To: Evan Laforge <qdunkan at gmail.com>
> Cc: libraries at haskell.org
> 
> 
> 
> On Fri, Sep 26, 2008 at 8:20 AM, Evan Laforge <qdunkan at gmail.com> wrote:
> 
>> Of course, anything that boosts performance is a win.  Does anyone
>> know of any Map benchmarks?  I suppose I could write some, but I'd be
>> sort of surprised if someone else hasn't already done that.  Then we
>> could throw in all the various avl / redblack / whatever map variants
>> in there and see how they stack up.
> 
> 
> I'm sure everyone has a benchmark floating around. I've attached the one
> I've been using.  As we all know from following the shootout rankings, a
> single benchmark is pointless and misleading. Better to have targeted
> benchmarks for specific use patterns. The problem is that search trees are
> used in so many ways. I've divided it up into two domains: inputs and
> queries. Then you get a single micro-benchmark by picking one thing in each
> domain. Here's what I've got
> 
> Inputs :
>  - Random
>  - Random with duplicates
>  - Sequential
>  - The union of many small (100 or so) random sets
> 
> Queries :
>  - Sum all keys (or values)
>  - Sum a random subset of keys (may or may not be present in the map)
> 

[etc]

> 
> Yeah for that use-case I don't think you'll beat a good balanced binary
> tree, not in any language. A bit-trie won't really work because you could
> have duplicate entries (+/- 0) and they wouldn't be stored in sorted order.
> 
> Scott