DData

[Adrian Hey]

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?

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 :-)

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.

Regards
--
Adrian Hey