<div dir="ltr">Hi All,<div><br></div><div>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:</div>
<div><a href="http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800">http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800</a></div><div><br></div><div><div>% g++ --version</div><div>g++ (GCC) 4.8.2</div></div><div>The bug is in libstdc++ -- also used by Clang -- that explains why I was getting the same issue from the 2 different compilers.</div>
<div><br></div><div>I downgraded to 4.8.1 and everything is working. I lost sooo much time on this, not to mention I completely freaked out :(</div><div><br></div><div>Sylvain</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Mon, Nov 25, 2013 at 12:27 PM, Sylvain Bougerel <span dir="ltr"><<a href="mailto:sylvain.bougerel.devel@gmail.com" target="_blank">sylvain.bougerel.devel@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<p dir="ltr">Paul,</p>
<p dir="ltr">You are right. I need to revisit both the explanation and the understanding of the crash.</p>
<p dir="ltr">The issue I am getting happens randomly and never happens with partial_sort().</p>
<p dir="ltr">I will investigate more. I will keep you updated.</p>
<p dir="ltr">Regards, <br>
Sylvain </p><div class="HOEnZb"><div class="h5">
<div class="gmail_quote">On Nov 25, 2013 10:57 AM, "Paul" <<a href="mailto:elegant_dice@yahoo.com" target="_blank">elegant_dice@yahoo.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div style="font-size:12pt;font-family:times new roman,new york,times,serif">Hi Sylvain,<br><br>I just saw this email by chance, not sure why it didn't show up bigger in the inbox...<br><br><br><a href="http://www.cplusplus.com/reference/algorithm/nth_element/" target="_blank">http://www.cplusplus.com/reference/algorithm/nth_element/</a><br>
<br>Quote: <br>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.<br><br>So your comment regarding Guarantees cannot be correct.<br>Please check your code again, I assume there is some other problem that is the source of the issue.<br><br>cheers,<br>Paul<br>
<div><span><br></span></div><div style="display:block"> <br> <br> <div style="font-family:times new roman,new york,times,serif;font-size:12pt"> <div style="font-family:times new roman,new york,times,serif;font-size:12pt">
<div dir="ltr"> <font face="Arial"> On Sunday, 24 November 2013 10:19 PM, Sylvain Bougerel <<a href="mailto:sylvain.bougerel.devel@gmail.com" target="_blank">sylvain.bougerel.devel@gmail.com</a>> wrote:<br> </font> </div>
<div><div><div><div dir="ltr">Hi Sebastien and others,<div><br clear="none"></div><div>I will retry with the new addresses.</div><div><br clear="none"></div><div>The real reason why I wanted the latest sources was to do performance comparisons between libkdtree++ and
spatial (<a rel="nofollow" shape="rect" href="https://sourceforge.net/projects/spatial/" target="_blank">https://sourceforge.net/projects/spatial/</a>).</div>
<div><br clear="none"></div><div>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.</div><div>
<br clear="none"></div><div>
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.</div><div><br clear="none"></div><div>In the KDTree::_M_optimize, the body in the version I have is:</div>
<div><br clear="none"></div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div>
<div>
{</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::nth_element(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div><div><br clear="none"></div>
<div>But it should be:</div>
<div><br clear="none"></div><div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div>
<div> {</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::partial_sort(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div></div><div><br clear="none">
</div><div>
(notice the change from std::nth_element to std::partial_sort)</div><div><br clear="none"></div><div>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 point sorted along the dimension __L % __K are strictly ordered around the pivot __m.</div>
<div><br clear="none"></div><div>In practice nth_element does "some" sorting around the pivot __m and this bug was not noticeable when inserting less than 10,000 elements. I started to get different results between some random nearest neighbor queries at 10,000 elements. At 1,000,000 elements, efficient_insert_and_optimize started to crash with Segmentation Faults on Linux.</div>
<div><br clear="none"></div><div><div>Replacing nth_element by partial_sort fixes the issues described above, because partial_sort enforces the guarantee needed here.</div></div><div><br clear="none"></div><div>If the current maintainers agree with the proposed changes, I'd like to request their good will to apply the changes on my behalf in the source. To top it off, I think, a long time ago (5 years may be?), I may have been the one proposing to replace a previous std::sort by std::nth_element (I remember a conversation with Paul on this)... So I might even have introduced the bug in the first place :(</div>
<div><br clear="none"></div><div>According to my current experiments, at the moment libkdtree++ cannot be assumed to maintain its invariant throughout the tree after a call to _M_optimize(). If you are a user of optimization in libkdtree++ with large data sets, then you have probably experienced this issue, if the code above is the one you are using.</div>
<div><br clear="none"></div><div>Best Regards,</div><div>Sylvain</div></div><div><br clear="none"><br clear="none"><div><div>On Sun, Nov 24, 2013 at 9:41 PM, Sebastian Ramacher <span dir="ltr"><<a rel="nofollow" shape="rect" href="mailto:sebastian+lists@ramacher.at" target="_blank">sebastian+lists@ramacher.at</a>></span> wrote:<br clear="none">
<blockquote style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>On 2013-11-24 21:20:25, Sylvain Bougerel wrote:<br clear="none">
> Thank you Sebastien, I will wait a bit then.<br clear="none">
<br clear="none">
</div>It should be back up:<br clear="none">
<a rel="nofollow" shape="rect" href="https://lists.debian.org/debian-infrastructure-announce/2013/11/msg00002.html" target="_blank">https://lists.debian.org/debian-infrastructure-announce/2013/11/msg00002.html</a><br clear="none">
<br clear="none">
Regards<br clear="none">
<span><font color="#888888">--<br clear="none">
Sebastian Ramacher<br clear="none">
</font></span><br clear="none">_______________________________________________<br clear="none">
libkdtree-devel mailing list<br clear="none">
<a rel="nofollow" shape="rect" href="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank">libkdtree-devel@lists.alioth.debian.org</a><br clear="none">
<a rel="nofollow" shape="rect" href="http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel</a><br clear="none"></blockquote>
</div><br clear="none"></div></div></div></div><br><div>_______________________________________________<br clear="none">libkdtree-devel mailing list<br clear="none"><a shape="rect" href="mailto:libkdtree-devel@lists.alioth.debian.org" target="_blank">libkdtree-devel@lists.alioth.debian.org</a><br clear="none">
<a shape="rect" href="http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel</a></div><br><br></div> </div> </div>
</div> </div></div></blockquote></div>
</div></div></blockquote></div><br></div>