Performance of find methods, comparison with linear search

[Sylvain Bougerel]

On Nov 26, 2007 9:05 AM, Paul Harris <paulharris at computer.org> wrote:
> 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.

Hi Paul,

This is some serious testing! Very informative!

It's clear now that optimize does improve performance. I have been
taking conclusions to early. I believe that the "bad" results I get
for optimize are due to the way the point are generated. You used
test_kdtree for your test. test_kdtree generate more points in some
places than others, and therefore produces a more imbalanced kdtree, I
suppose. perf_kdtree, on the contrary, generates points uniformly
across the space, and it's possible that the tree is already balanced
after construction...

This would explain the difference we get. When I will run your
test_kdtree, I therefore expect to get an improvement with
optimization too. And if you run perf_kdtree, you should get
equivalent performence whether it is optimized or not.

>
> 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)
>

Bad Sylvain ::slap::. I fixed it. Good idea, to run it with valgrind.


This was a great feedback. Now we know for sure that optimise() is
working and we can concentrate our efforts on the design. I have
already started making modifications, and pushing part of the
find_nearest_iterative() algorithm into an iterator called:
outward_iterator (I settled on that name at the moment).

I will rearrange find_within_range() in an iterative fashion also,
hopping to see some other performance improvements. Since it's getting
busier at work, you might have to wait for a couple of week or so...


- Sylvain