[libcxx-dev] pdqsort and SRWLock on Windows
Michał Dominiak via libcxx-dev
libcxx-dev at lists.llvm.org
Wed Jul 17 14:24:28 PDT 2019
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/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.
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the libcxx-dev