DData

[Simon Marlow]

On 19 May 2004 11:28, Ross Paterson wrote:

> testData = take 100000 $ randomRs (0, 2^30-1) (mkStdGen 7)
> 
> (I have a slower machine), changed isEmpty to size to guarantee
> strictness, and got the following times (averaged over 50 runs each):
> 
>                 ins     ins+del
> Data.FiniteMap  4.783   8.304
> Data.Tree.AVL   4.561   6.895
> DData.Map       4.765   7.369
> DData.IntMap    4.952   7.742
> 
> (I tried to be fair by only using ! and UNPACK on Ints in each case,
> and compiling them all the same way: -O.)  I assume that Christian's
> results imply that IntMap is better for lookup, but it doesn't look
> very attractive here.

Unable to resist a good benchmark, I did my own measurements. Same
random input, but I did the timing in Haskell so I could factor out the
test data construction.  Results averaged over 10 runs:

               Insert   Lookup   Delete
AVL            0.88     0.35     0.89
FiniteMap      1.08     0.19     1.17
DData.Map      1.09     0.23     1.13
DData.IntMap   0.72     0.18     0.61

I UNPACKed the appropriate fields in Map and IntMap.

AVL loses out on lookup.  Probably due to the extra pair that needs to
be deconstructed at each node.

I don't know why DData.Map comes out worse than FiniteMap for lookup:
the implementations are the same, so perhaps the tree ends up
differently balanced?

Cheers,
	Simon