Performance of find methods, comparison with linear search

[Paul Harris]

> > Note, lap_iterative_linear_find_nearest resulted in zero clock ticks!
> > wtf?
>
> I think it would be a good thing to check what the clock() call
> returns before and after the lap_iterative_linear_find_nearest code
> bit, to be sure the problem isn't coming from the Stopwatch class.
>

I added this:
  std::cout << "PCH: " << clock() << std::endl;

to before and after the for() loop for lap_iterative_linear_find_nearest

And I got this result:
$ ./test_kdtree 100000 1000
--snip--
<Stopwatch> kdtree [lap_iterative_linear_find_within_range]: 0.71s
(710000 clock ticks)
lap_iterative_linear_find_within_range = [
lap_iterative_linear_find_within_range 710000 ];
PCH: 4160000
PCH: 4160000
<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]: 3.76s (3760000 clock ticks)
lap_recursive_linear = [ lap_recursive_linear 3.76e+06 ];


Then I moved
 triplet nearest = random_points[0];
to above the for loop, and added a
  std::cout << "PCH: " << nearest << std::endl;
below the for loop... I got this result

$ ./test_kdtree 100000 1000
--snip--
<Stopwatch> kdtree [lap_iterative_linear_find_within_range]: 0.71s
(710000 clock ticks)
lap_iterative_linear_find_within_range = [
lap_iterative_linear_find_within_range 710000 ];
PCH: 3220000
PCH: 3850000
PCH: (80.2105,29.7495,93.9004)
<Stopwatch> kdtree [lap_iterative_linear_find_nearest]: 0.63s (630000
clock ticks)
lap_iterative_linear_find_nearest = [
lap_iterative_linear_find_nearest 630000 ];
<Stopwatch> kdtree [lap_recursive_linear]: 3.77s (3770000 clock ticks)
lap_recursive_linear = [ lap_recursive_linear 3.77e+06 ];


much more realistic, though 0.63s was still faster than 0.95s for the
find_nearest_opt in this test.

Can you adjust the tests to ensure that they aren't optimised out
entirely?  Is this checked into the libkdtree++ repo yet?

thanks
Paul