No subject

<Stopwatch> kdtree [lap_find_nearest]: 1.11s (1110000 clock ticks)
lap_find_nearest = [ lap_find_nearest 1.11e+06 ];
# comparisons: 4215231
<Stopwatch> kdtree [lap_find_nearest_iterative]: 0.02s (20000 clock ticks)
lap_find_nearest_iterative = [ lap_find_nearest_iterative 20000 ];
# comparisons: 104192

so iterative does 100k comparisons, compared to the old 4.2M comparisons


<Stopwatch> kdtree [lap_find_nearest_opt]: 0.83s (830000 clock ticks)
lap_find_nearest_opt = [ lap_find_nearest_opt 830000 ];
# comparisons: 3139795
<Stopwatch> kdtree [lap_find_nearest_iterative_opt]: 0.01s (10000 clock ticks)
lap_find_nearest_iterative_opt = [ lap_find_nearest_iterative_opt 10000 ];
# comparisons: 57036

and once optimized, iterative improves down to 57k comparisons, and
old is down to 3M.



Second run:

<Stopwatch> kdtree [lap_find_nearest]: 0.75s (750000 clock ticks)
lap_find_nearest = [ lap_find_nearest 750000 ];
# comparisons: 2836602
<Stopwatch> kdtree [lap_find_nearest_iterative]: 0.02s (20000 clock ticks)
lap_find_nearest_iterative = [ lap_find_nearest_iterative 20000 ];
# comparisons: 96458

<Stopwatch> kdtree [lap_find_nearest_opt]: 0.97s (970000 clock ticks)
lap_find_nearest_opt = [ lap_find_nearest_opt 970000 ];
# comparisons: 3785707
<Stopwatch> kdtree [lap_find_nearest_iterative_opt]: 0.01s (10000 clock ticks)
lap_find_nearest_iterative_opt = [ lap_find_nearest_iterative_opt 10000 ];
# comparisons: 57160


Iterative was better with optimization, but this time the old method was not.




As for the counters and the 1 probe thing...
I added a map<> to count the number of times each nodes was checked...

This gave some interesting numbers:

$ ./test_kdtree 10000000 1
snip
# comparisons: 61795
Distcalc 134924136 x 174
Distcalc 135341416 x 158
Distcalc 136564896 x 46
Distcalc 138566576 x 14
Distcalc 143392976 x 12
Distcalc 155443216 x 20
Distcalc 161961896 x 12
Distcalc 183171056 x 6
<Stopwatch> kdtree [lap_find_nearest_iterative]: 0s (0 clock ticks)
lap_find_nearest_iterative = [ lap_find_nearest_iterative 0 ];
# comparisons: 472


NOTES: this is the unoptimised tree, and from a total of 472 distance
calculations, there are about 400 repeated distance calculations.  ie,
the node "134924136" had its distance calculated to the __val target
point 174 times!


onwards, the optimised run:

Distcalc 143148896 x 10
Distcalc 152897296 x 94
Distcalc 186148536 x 2
Distcalc 254828416 x 2
Distcalc 523212576 x 22
<Stopwatch> kdtree [lap_find_nearest_iterative_opt]: 0s (0 clock ticks)
lap_find_nearest_iterative_opt = [ lap_find_nearest_iterative_opt 0 ];
# comparisons: 148


this run was a lot better with a balanced tree.  but there was still
126 repeated distance calculations out of 148.


also note, I ran it through valgrind briefly and saw the following error:

==4243== Conditional jump or move depends on uninitialised value(s)
==4243==    at 0x804F0E1: KDTree::KDTree<3, triplet,
std::pointer_to_binary_function<triplet, int, double>,
std::less<double>, std::allocator<KDTree::_Node<triplet> >
>::find_nearest_iterative(triplet const&) (kdtree.hpp:588)
==4243==    by 0x804B530: main (test_kdtree.cpp:197)


There were similar messages when running perf_test.


So, onwards with the end-notes from Sylvain,

> Sylvain wrote:
> Note that:
> 1.    Optimize() makes the work harder for 2 very different
> algorithms. It can't be blamed on the recursive implementation
> anymore. Rather, there could be some issue with optimize().