Performance of find methods, comparison with linear search

[Sylvain Bougerel]

On 11/5/07, Renaud Detry <renaudjdetry at airpost.net> wrote:
> Hi all,
>
> I ran a couple of performance tests on libkdtree (pulled on
> Saturday). Experiments and results are attached, but the archive is
> also published at
>
>    http://www.montefiore.ulg.ac.be/~detryr/public/
> kdtree_perf_test.tar.gz
>
> in case the attachment doesn't go through.
>
>  From these tests, it seems that
>
> 1.- libkdtree find-within-range becomes faster than "dumb" linear search
>      when sets contain more than 1000 points. This doesn't take the tree
>      construction overhead into account.
>
> 2.- libkdtree find-nearest is slower than linear search, at least
>      for sets containing up to 100000 elements.
>
> I am very surprised by (2) :-/. I would think that there's something
> wrong in the way I do the test, but I can't find what...
>
> Can anyone comment on these?
>
> My personal interest in libkdtree is an optimized within-range search
> through sets of 100 to 500 points. From the previous comparisons, it
> seems that in this case libkdtree, and probably kdtrees in general,
> are not a better solution than linear search. Does this sound fair to
> you guys?
>
> A bit of details on the test files:
>
> kdtree_perf_test:
>    Makefile
>    Stopwatch.h
>    data-100000probes-figs:
>      non_optimized_vs_linear.loglog.pdf
>      ...
>    data-100000probes-sorted-asc-figs:
>      non_optimized_vs_linear.loglog.pdf
>      ...
>    data-100000probes-sorted-asc.m
>    data-100000probes.m
>    script.sh
>    test_kdtree.cpp
>
> test_kdtree.cpp is adapted from libkdtree/examples/test_kdtree.cpp
>
> script.sh calls test_kdtree several times to create the .m data files
> and plots.
>
> It's worth taking a look at
> data-100000probes-figs/non_optimized_vs_linear.loglog.pdf
>
> Two more remarks:
>
> - I tried modifying _M_find_nearest to avoid functional recursion, by
>    queuing "recursion jobs" in a fifo queue of elements of type
>
>      struct find_state
>      {
>        find_state(_Link_type n, _Region b, size_t l) :
>          n(n), b(b), l(l) {}
>        _Link_type n; _Region b; size_t l;
>      };
>
>    This gave a small speedup (about .5). The same change in
>    _M_find_within_range doesn't seem to make things any faster.
>
> - I made the modest changes to _M_find_nearest to allow searching the p
>    nearest elements. However, given the apparent performance of
>    _M_find_nearest, this won't be of any help to me. If you like, I can
>    send a patch tough.
>
> Cheers,
> Renaud.
>
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>

Hi Renaud,

I have had a conversation with another user. He pointed out the same
bad performance. We have to fix that immediately. I'am writting a
small test case too, to compile with gprof. I want to know what is
eating up so much CPU time. I am also gonna compare using the earliest
version of the library, to check that it doesn't come from the most
recent changes.

Sylvain