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

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 Date: Fri, Sep 26, 2008 at 11:57 AM Subject: Map / IntMap laziness (was: export toDescList from Data.Map) To: Evan Laforge Cc: libraries@haskell.org

On Fri, Sep 26, 2008 at 8:20 AM, Evan Laforge 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