DData

[Simon Marlow]

On 20 May 2004 16:34, Simon Marlow wrote:

> 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

And after eliminating some bogosity in the benchmark, I now get:

               Insert   Lookup   Delete
AVL            0.87     0.22     0.87
FiniteMap      1.07     0.17     1.11
DData.Map      1.08     0.16     1.02
DData.IntMap   0.65     0.16     0.61

So I declare that on random data, DData.Map has essentially the same
performance as FiniteMap.  IntMap is faster for insertion/deletion as
expected. AVL is better than FiniteMap for insertion/deletion but slower
for lookups.

Cheers,
	Simon