(no subject)

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.

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

Hi,

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

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