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