DData

[Ross Paterson]

On Mon, May 17, 2004 at 09:39:25AM +0100, Adrian Hey wrote:
> Here are the results for 2 tests..
> 
> Test1: Build a tree/finitemap of 1000000 pairs.
> Test2: As Test1, followed by deletion of all 1000000 pairs.
> 
> Pairs are inserted/deleted in numerical order [1,2..1000000]

Inserting in random order gives a less dramatic difference.
I changed your testData to

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.