Getting the latest sources

[Paul]

Oh wow, good catch.

Note that I found a bug in msvc 2010's vector, related to the new cxx11
emplace methods, that was also a painful learning experience... Without the
quick bug fix from the compiler authors like you found ( I ended up
patching the standard headers on my own machine)

On Saturday, 21 December 2013, Sylvain Bougerel wrote:

> Hi All,
>
> I found the issue. After few weeks of recompiling, adding debug statements
> everywhere, and trying to understand why sometime std::nth_element() does
> not seem to behave well on my machine, I gave up. That's when I googled
> "nth_element gcc bug". And of course:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800
>
> % g++ --version
> g++ (GCC) 4.8.2
> The bug is in libstdc++ -- also used by Clang -- that explains why I was
> getting the same issue from the 2 different compilers.
>
> I downgraded to 4.8.1 and everything is working. I lost sooo much time on
> this, not to mention I completely freaked out :(
>
> Sylvain
>
>
> On Mon, Nov 25, 2013 at 12:27 PM, Sylvain Bougerel <
> sylvain.bougerel.devel at gmail.com> wrote:
>
> Paul,
>
> You are right. I need to revisit both the explanation and the
> understanding of the crash.
>
> The issue I am getting happens randomly and never happens with
> partial_sort().
>
> I will investigate more. I will keep you updated.
>
> Regards,
> Sylvain
> On Nov 25, 2013 10:57 AM, "Paul" <elegant_dice at yahoo.com> wrote:
>
> Hi Sylvain,
>
> I just saw this email by chance, not sure why it didn't show up bigger in
> the inbox...
>
>
> http://www.cplusplus.com/reference/algorithm/nth_element/
>
> Quote:
> The other elements are left without any specific order, except that none
> of the elements preceding nth are greater than it, and none of the elements
> following it are less.
>
> So your comment regarding Guarantees cannot be correct.
> Please check your code again, I assume there is some other problem that is
> the source of the issue.
>
> cheers,
> Paul
>
>
>
>   On Sunday, 24 November 2013 10:19 PM, Sylvain Bougerel <
> sylvain.bougerel.devel at gmail.com> wrote:
>  Hi Sebastien and others,
>
> I will retry with the new addresses.
>
> The real reason why I wanted the latest sources was to do performance
> comparisons between libkdtree++ and spatial (
> https://sourceforge.net/projects/spatial/).
>
> During the course of the performance comparisons, I insert 1000000 points
> in 3 or 9 dimensions and watch how the 2 libraries behave, on insertion and
> insertion with optimization.
>
> This has lead me to the discovery of one bug very important bug and its
> fix. Spatial originally (a year ago) suffered from the same issue, so I was
> able to identify it quickly.
>
> In the KDTree::_M_optimize, the body in the version I have is:
>
>       template <typename _Iter>
>         void
>         _M_optimise(_Iter const& __A, _Iter const& __B,
>                     size_type const __L)
>        {
>         if (__A == __B) return;
>         _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);
>         _Iter __m = __A + (__B - __A) / 2;
>         std::nth_element(__A, __m, __B, compare);
>         this->insert(*__m);
>         if (__m != __A) _M_optimise(__A, __m, __L+1);
>         if (++__m != __B) _M_optimise(__m, __B, __L+1);
>       }
>
> But it should be:
>
>       template <typename _Iter>
>         void
>         _M_optimise(_Iter const& __A, _Iter const& __B,
>                     size_type const __L)
>       {
>         if (__A == __B) return;
>         _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);
>         _Iter __m = __A + (__B - __A) / 2;
>         std::partial_sort(__A, __m, __B, compare);
>         this->insert(*__m);
>         if (__m != __A) _M_optimise(__A, __m, __L+1);
>         if (++__m != __B) _M_optimise(__m, __B, __L+1);
>       }
>
>  (notice the change from std::nth_element to std::partial_sort)
>
> Using nth_element here is a erroneous, because it does not guarantee that
> everything in the sequence [__A, __m) is lower than _m nor that everything
> in the sequence (__m, __B] is greater than __m. This is expected from the
> algorithm because it operates on a subset where the
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20131222/eefe46dd/attachment.html>