On 24 May 2004 12:03, Adrian Hey wrote:
On Thursday 20 May 2004 5:04 pm, Simon Marlow wrote:
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.
Could you explain the bogosity you eliminated?
I did a full GC before running each part of the test to keep random GC effects to a minimum, and eliminated a couple of cases of badly optimised code in the test program.
The reason I ask is that those second results for lookup for AVL trees seem pretty reasonable to me, considering the AVL library is general purpose and not specialised for any kind of map. Currently the AVL implementation will have to read 3 heap records per tree node visited, vs. 2 for FiniteMap and DData.Map.
For the balanced tree implementations, I wouldn't expect to see any significant difference in lookup times (given the same degree of specialisation) and what differences there may be would most likely be due to differences in how well they managed to balance trees. (But I guess if random data is to be our benchmark, even simple unbalanced trees would probably look quite reasonable :-)
Of course, this isn't testing how well the balancing works. It is comparing raw performance of several balanced tree implementations, so measuring the overhead of balancing, if you like.
DData.IntMap is rather different from the other three, so I'm not sure exactly how well I would expect it to perform, but if you assume lookup time is proportional to the No. of heap records examined (seems to be reasonable comparing AVL and FiniteMap/DData.Map), then you'd expect a lookup time of about 0.08 for each if they were specialised for Int maps.
Yes, IntMap should get faster lookup. I looked at the code and managed to make a couple of improvements: adding a 'seq k $' at the beginning of lookup helps, and I fixed a small performance problem with the Word library, but interestingly these don't help the results. I still get 0.16s for the lookup test, so perhaps it is dominated by something else. Cheers, Simon