[libcxx-dev] pdqsort and SRWLock on Windows

[Michał Dominiak via libcxx-dev]

(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.)

On Wed, Jul 17, 2019 at 11:24 PM Michał Dominiak <griwes at griwes.info> wrote:

> 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/46d55fe8/attachment.html>