[libcxx-dev] pdqsort and SRWLock on Windows

[Michał Dominiak via libcxx-dev]

Hi,

On Wed, Jul 17, 2019 at 10:02 PM Louis Dionne via libcxx-dev <
libcxx-dev at lists.llvm.org> wrote:

> Note: Please include a subject line in emails sent to this list.
>
> I think the answer to both of your questions is that nobody has looked
> into it, quite simply.


The author of pdqsort has asked me to remind you of an unresolved issue
they opened 5 years ago (https://bugs.llvm.org/show_bug.cgi?id=20837)
showing libc++'s std::sort has an O(n^2) worst case.

Neither the simple patch solving the issue nor the suggestion to use
pdqsort as a replacement was integrated, even after multiple requests
asking for follow-up by the author and community members. The issue is
still on "NEW" status as of today, and the reproduction is still there.

If the maintainers of libc++ are interested in pdqsort, in addition to
the source code at
https://github.com/orlp/pdhttps://github.com/orlp/pdqsortqsort
<https://github.com/orlp/pdqsort> there is also a
peer-reviewed article regarding its design. An unofficial pre-print is
available from https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0E
.


> I'd be curious to investigate replacing our current sort with a pdqsort.
> https://github.com/orlp/pdqsort 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.
>
> Louis
>
> > On Jul 17, 2019, at 13:58, VALERIU SMERICA via libcxx-dev <
> libcxx-dev at lists.llvm.org> wrote:
> >
> > 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.
> > _______________________________________________
> > libcxx-dev mailing list
> > libcxx-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev
>
> _______________________________________________
> libcxx-dev mailing list
> libcxx-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/libcxx-dev/attachments/20190717/cddd45eb/attachment.html>