DData

[Adrian Hey]

On Thursday 20 May 2004 11:32 am, Ross Paterson wrote:
> > Unfortunately, I think a large part of the time here is probably
> > accounted for by the time taken to generate the test data itself, if the
> > results on my machine are anything to go by. Using your test data
> > increases the execution time of the insertion test (for 100000 pairs)
> > from 0.39 seconds to 1.88 seconds for AVL trees.
>
> Building random data costs more, but random insertions are also more
> costly than ordered ones.  (With ordered insertions, the insertion path
> is much shorter than the average tree depth.)  Also, the difference
> varies between implementations.

I don't know if that's true for the trees used in FiniteMap, but for
AVL trees newly inserted elements always become leaves, so I would
guess that the insertion path is always about the same as the average
tree depth, regardless of order. In fact I find it hard to see how else
things could work, but without knowing the details of other implementations
I guess I can't say for sure.

One possible alternative explanation that occurs to me is that ordered
insertions give better cache behaviour. Typically the insertion path will
change little from one insertion to the next, so most of the nodes concerned
will likely be resident in cache already, as they were just created by the
previous insertion. So maybe the apparent difference between AVL trees and
FiniteMap in this case is really due almost entirely to differing heap
burn rate, rather than differences in the notional efficiency of the
rebalancing algorithm.

It would be good to try to establish a set of representative benchmarks
for the various tree types though. Trouble is with a garbage collected
language modern cached CPU's it's hard to be sure that benchmarks are
representative of the true costs in real progams. It's also hard to be
sure that the measured time for random data generation in isolation is
representative of the cost where it runs in the presence of other
cache disrupting code, for example. Every time I've tried to normalise
my results this way I get answers that don't seem to make much sense :-(

Regards
--
Adrian Hey