Performance of find methods, comparison with linear search

[Paul Harris]

On 11/21/07, Sylvain Bougerel <sylvain.bougerel.devel at gmail.com> wrote:

> Trying Renaud's original version I also get:
>  - snip -
>  <Stopwatch> kdtree [lap_iterative_linear_find_nearest]: 0s (0 clock ticks)
>  lap_iterative_linear_find_nearest = [ lap_iterative_linear_find_nearest 0 ];
>  <Stopwatch> kdtree [lap_recursive_linear]: 112.57s (112570000 clock ticks)
>  lap_recursive_linear = [ lap_recursive_linear 1.1257e+08 ];
>
> That's an amazing result, and when I try Paul's version I get (full log):

snip

snip

> <Stopwatch> kdtree [lap_iterative_linear_find_nearest]: 19.94s>
> Wow, it went from 0.0s to 19.94s for the
> lap_iterative_linear_find_nearest. This difference in the loop is:
>
> @@ -208,13 +212,17 @@
>    }
>    sw.lap("iterative_linear_find_within_range");
>
> -  triplet nearest = random_points[0];
> +
> +  std::cout << "PCH: " << clock() << std::endl;
> + triplet nearest = random_points[0];
> + int num_com_linear = 0;
>    for (int i = 0; i < N_PROBES; ++i)
>    {
>      for (int j = 0; j < N; ++j)
>      {
>        double d = distance(random_probes[i], random_points[j]);
> +      ++num_com_linear;
>        if (d < mindist)
>        {
>          mindist = d;
>
> I was surprised and I tried again without the counter...
>
> @@ -208,13 +212,17 @@
>    }
>    sw.lap("iterative_linear_find_within_range");
>
> + // std::cout << "PCH: " << clock() << std::endl;
>    triplet nearest = random_points[0];
>    int num_com_linear = 0;
>    for (int i = 0; i < N_PROBES; ++i)
>    {
>      for (int j = 0; j < N; ++j)
>      {
>        double d = distance(random_probes[i], random_points[j]);
> +      //++num_com_linear;
>        if (d < mindist)
>        {
>          mindist = d;
>
> And I still get the same results (around 19s). So I don't know how I
> can get these 0.0s at first. I'm puzzled.


the counter wasn't the key change.  the key change was that i printed
out the result.  before, the loop provided no side-effect at all, the
result was assigned within a scoped block and then never used.   i
believe the compiler was smart enough to optimise out the entire loop
as a noop



>
>
>
> Contrary to Paul, I do not believe that kdtree find_nearest is
> "normally" slow because of memory lookup. We do not allocate many
> things in this example. "triplet" only weight 12 octect of memory...
> 10000 of them does not represent much memory space.

snip details

>
> If you've never seen a valgrind output before, what it means is that
> there is simply NO significant hopping in memory. In other words, when
> you build your tree in a block, like in the precedent test, hopping in
> memory will not happen. Therefore, the long execution time we get for
> find_nearest() and find_within_range() may be due to an error in the
> algorithm.
>

very interesting, ok that factor is disproven.

>
> That's when I started to look deeper at find_nearest() and I realized
> the following:
> 1. The algorithm is recursive. Recursive is slower than iterative, so
> iterative would improve
>     performance.

possibly.  iteration has certainly helped in other situations, but it
depends on what the compiler can do too.   if it can do (for example)
tail recursion optimisation correctly then recursion can be quick too
(IIRC).

> 2. The algorithm seems to behave this way:
>        at each node, compare the hyperrectangle formed by the center
> point and the node value
>        with the current best hyperrectange. Then if the current best
> hyperrectangle intersect with
>        the left node and the right node value, continue in each node.

(nb: iirc, not doublechecking code)
respectively, yes.  only follow the branches that intersect with the hyperrect.
and as it does deeper and finds points closer to the target will
reduce the hyperrect.  the hyperrect (HR from now on) is passed by
reference, so as it recurses up and down the tree, the target search
area gets smaller and smaller, thus trimming the branches that will be
searched.

HR starts at a very large rect, and it gets smaller and smaller.

>     I think it's better to get the approximate best hyperrectangle
> during iterative deepening
>     search like when you want to insert the point (if it was an
> insertion). Now walk up the tree

i forget how it inserts points, so i cant comment on that.
interesting, i'll wait to see your implementation instead of
second-guessing

>     from that point on and go into the node that intersect the HYPERSPHERE only.
>     This is where the current algorithm looses efficiency IMHO.

not sure about hypersphere tho... one of the efficiencies comes from
the use of the hyperrect.  that way, there is only 1 dimension
compared at a time, nice and fast.  almost no multiple dimension
distance calculations required.   doesn't sphere intersection require
multiplications, additions to calculate distance from the center, and
comparison to the radius?  much more work than a single floating point
comparison at each tree branch.

> Please comment on this.
>
> During the weekend I will try to reimplement find_nearest taking these
> two points into consideration. I'll send you the result over the week
> end.
>

i'll wait to see, very interesting :)
Paul