Performance of find methods, comparison with linear search

Sylvain Bougerel sylvain.bougerel.devel at gmail.com
Wed Nov 28 00:24:14 UTC 2007


On Nov 27, 2007 7:42 AM, Paul Harris <paulharris at computer.org> wrote:
\> debate for later ...   instead, could i please suggest that you first
> tackle the problem of the repeated distance calculations first?   that
> problem was demonstrated in the previous email, with the help of the
> #define KDTREE_CHECK_PERFORMANCE_COUNTERS
> Once that has been improved the find should be significantly faster
> and more efficient.
>

Well, I didn't think there was a problem. I thought that your
objective was to check the the result of optimisation: how many
"sibling nodes" would be visited for each "current nodes". And the
figures where positively conclusive.
(sibling nodes: they are visited during hypersphere intersection, they
are all the nodes and sub nodes that stem from the sibling of any
"current node".
current node: they are visited during hyperrectangle intersection,
they are all the nodes that lead directly to leaf where "value" should
have been inserted.)

So I really thought it was a find test. But it seems to me that you
want to check if node's distances are checked more than 1 time per
node. So I changed your code from:
			  ++compare_node_counts[(unsigned long)cur_node];
to:
			  ++compare_node_counts[(unsigned long)sibling_node];
during hypersphere intersection. And... I was surprised to discover
that each sibling node's distance is computed exactly 2 times! So I
fixed this too.

I also found a way to improve hypersphere intersection, by going
deeper first, instead of visiting useless nodes. It does even less
distances calculations on average, just a little faster. I'll be done
with the function and the design soon. I wont put the iterator, as
requested.

- Sylvain



More information about the libkdtree-devel mailing list