<div dir="ltr">(Whoops. Sorry for the bad formatting on the Github link, it'd seem that I accidently middle-click-inserted spurious text while verifying the link was created correctly.)</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jul 17, 2019 at 11:24 PM Michał Dominiak <<a href="mailto:griwes@griwes.info">griwes@griwes.info</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi,</div><div dir="ltr"><br></div><div dir="ltr">On Wed, Jul 17, 2019 at 10:02 PM Louis Dionne via libcxx-dev <<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Note: Please include a subject line in emails sent to this list.<br>
<br>
I think the answer to both of your questions is that nobody has looked into it, quite simply.</blockquote><div><br></div><div>The author of pdqsort has asked me to remind you of an unresolved issue<br>they opened 5 years ago (<a href="https://bugs.llvm.org/show_bug.cgi?id=20837" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=20837</a>)<br>showing libc++'s std::sort has an O(n^2) worst case.<br><br>Neither the simple patch solving the issue nor the suggestion to use<br>pdqsort as a replacement was integrated, even after multiple requests<br>asking for follow-up by the author and community members. The issue is<br>still on "NEW" status as of today, and the reproduction is still there.<br><br>If the maintainers of libc++ are interested in pdqsort, in addition to<br>the source code at <a href="https://github.com/orlp/pdqsort" target="_blank">https://github.com/orlp/pdhttps://github.com/orlp/pdqsortqsort</a> there is also a<br>peer-reviewed article regarding its design. An unofficial pre-print is<br>available from <a href="https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0E" target="_blank">https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0E</a>.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I'd be curious to investigate replacing our current sort with a pdqsort. <a href="https://github.com/orlp/pdqsort" rel="noreferrer" target="_blank">https://github.com/orlp/pdqsort</a> seems to say this is a drop-in replacement for std::sort. This would have to be verified, however if that's true we can get into benchmark land and have some fun.<br>
<br>
Louis<br>
<br>
> On Jul 17, 2019, at 13:58, VALERIU SMERICA via libcxx-dev <<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a>> wrote:<br>
> <br>
> Hi. When will pdqsort come in libc++ (if not, why?) and why don't std::mutex and std::shared_mutex use SRWLock for Windows OS? Thanks.<br>
> _______________________________________________<br>
> libcxx-dev mailing list<br>
> <a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a><br>
> <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev</a><br>
<br>
_______________________________________________<br>
libcxx-dev mailing list<br>
<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev</a><br>
</blockquote></div></div>
</blockquote></div>