Data.Map improvement patch

[Milan Straka]

Hello,

> 
> On Mon, 2008-04-21 at 09:38 +0200, Milan Straka wrote:
> 
> > It is difficult to measure these things in Haskell for me (just adding a
> > SPECIALIZE of increasing/decreasing heap size can change order of execution
> > time), but anyway, here are times of 50000 sequential inserts, then 800000
> > lookups and 50000 deletes (the source is attached for the freaks):
> > Data.Set with \delta=4  180 300 72
> > Data.Set with \delta=5  208 304 76
> > Data.Map with \delta=4  212 328 84
> > Data.Map with \delta=5  256 324 88
> > IntSet                   56 356 48
> > IntMap                   56 360 48
> 
> Sorry, I'm confused, what are the columns here exactly?

Sorry, I should made myself more clear.
The first column is the time of 50000 sequential inserts ([1..50000]),
the second column is the time of 800000 lookups
  [bigger number because they are fast, 800k=16*50k],
the third column is the time od 50000 sequential deletes ([1..50000]).
Everything is measured in ms.

One can think of a test with random sequence -- the source can be modified
easily to support it. The results are (in the same formatting) 
Random seq; Data.Set with \delta=4  300 636 256
Random seq; Data.Set with \delta=5  300 644 256
Random seq; Data.Map with \delta=4  372 692 268
Random seq; Data.Map with \delta=5  376 700 272
Random seq; IntSet                  216 572 168
Random seq; IntMap                  228 584 176
As one should expect, they are inconclusive. Thats because when
the data inserted are truly random, the rebalancing is not really
needed. (What is more interesting is the time bloat of all tests.
I think it might be caused by being able to inline [1..50000] better
than random list... Maybe a list fusion? I do not really know.)


Hello,
Milan

PS: Here is a diff of the random test:

--- Test.hs     2008-04-21 09:33:55.000000000 +0200
+++ TestNew.hs  2008-04-21 13:17:21.000000000 +0200
@@ -8,10 +8,17 @@
 import System.CPUTime
+import System.Random
 
 force_list list = sum list
 {-# SPECIALIZE force_list::[Int]->Int #-}
 
+gen_rnd n = rnd (mkStdGen 42) (Map4.fromList [(b,0)|b<-[1..n]]) where
+  rnd g m | Map4.null m = []
+  rnd g m = let n = Map4.size m
+                (i,g') = randomR (0,n-1) g
+            in fst (Map4.elemAt i m) : rnd g' (Map4.deleteAt i m)
+
 test::Int->c->(Int->c->c)->(Int->c->Bool)->(Int->c->c)->(c->[Int])->IO ()
@@ -20,23 +27,23 @@
 test n cs insert find delete tolist = do
-        let ls=[1..n]
+        let ls=gen_rnd n
         ts<-force_list ls `seq` getCPUTime