In D146421#4206608, @ldionne wrote:

Okay so unfortunately, that didn't fix the issue like we were expecting. I tried a few things and the only thing that reliably fixed the issue we were seeing was reverting 4eddbf9f10a6d1881c93d84f4363d6d881daf848 (aka D122780) entirely. I think I will need to get a reproducer before deciding what's the next step (i.e. whether the issue is sufficiently vexing that it's worth reverting or not).

Addressed review comments.

Addressed review comments.

Addressed review comments.

Pinging reviewers!

In D144538#4144200, @philnik wrote:

Please add a test that counts the number of comparisons to show that it actually only takes 2N log(N) comparisons.

Removed #include <iostream> as it is not required.

Updated the test used for testing the complexity of heap sort implementation.

Rebase to HEAD

Rebase to head

@ldionne : this diff is ready for submission. If you could do so, that would be great.

Rebase to HEAD

Corrected errors pointed out by the CI

In D122780#3978826, @smeenai wrote:

I'm not able to apply the latest version of the patch, and it looks like CI isn't either. Which revision is this patch based on top of?

Your stack still has D122858 in it, which is making arc patch unhappy locally, but even taking the raw patch and using git apply is failing for me.

Properly update the diff

Changed more std::move to _Ops::__iter_move

Changed to use _Ops::__iter_move instead of std::move.

Rebase to the HEAD revision

I would next rebase this change and redo the internal testing I did previously. Would post the rebased diff soon.

In D122780#3955522, @ldionne wrote:

In D122780#3955083, @nilayvaish wrote:

@ldionne : thanks for the accepting the change. We are trying to evaluate the effect of the change on Android APK's size. You might recall there were several comments about increased APK size in https://reviews.llvm.org/D113413 after it was submitted. I think it would be better if we are aware of the change in APK's size beforehand.

The evaluation is taking time, hopefully would get done soon.

Thanks for the update. We'll be eager to hear about the results if you are allowed to share them. Hopefully there is no prohibitive code size regression. If so, it may be worth investigating if externally instantiating some of these templates in the dylib could mitigate the regression. IIRC this optimization was only enabled for integer types, right?

@ldionne : thanks for the accepting the change. We are trying to evaluate the effect of the change on Android APK's size. You might recall there were several comments about increased APK size in https://reviews.llvm.org/D113413 after it was submitted. I think it would be better if we are aware of the change in APK's size beforehand.

Pinging @ldionne. Can you comment on the data that would help you to make the decision? I am trying to convince folks at Google on trying out this diff. The main question being asked is what data you would like to see?

In D122780#3850519, @ldionne wrote:

As it stands, we basically have to decide whether to optimize for randomly sorted data or to also take into account common patterns IIUC. That's not a super easy call to make, since we're talking about 40-50% improvements and 40-50% regressions in each case. I remember @Morwenn had mentioned pdqsort previously, and that seemed to be an algorithm that would handle both random data and also patterns properly. Would that solve the problems of this algorithm?

In D122780#3850519, @ldionne wrote:

It seems like you rebased onto main with the branchless sort changes and also re-ran the benchmarks against that. Looking at the results, it looks like this basically improves the performance by a fairly significant margin for randomly distributed integers, but seems to also decrease the performance quite a bit for integers with some sort of structure (e.g. already sorted, descending or ascending). In particular, I assume the reduction of branch mispredictions is not a huge factor anymore since we introduced branchless sorting, or am I off here? The fact that it doesn't seem to provide improvements across the board definitely make it a trickier change to vet, since we'll have to decide whether we want to make this tradeoff.

As it stands, we basically have to decide whether to optimize for randomly sorted data or to also take into account common patterns IIUC. That's not a super easy call to make, since we're talking about 40-50% improvements and 40-50% regressions in each case. I remember @Morwenn had mentioned pdqsort previously, and that seemed to be an algorithm that would handle both random data and also patterns properly. Would that solve the problems of this algorithm?

Sorry if this isn't super helpful, but I literally don't know how to make this call. I'd very much welcome the perspective of other folks who have given a lot of thought to sorting algorithms.

FWIW, making a major change to std::sort isn't a problem, as long as we have sufficient tests to validate its correctness, and that we are confident about its performance.

In D129716#3655911, @Mordante wrote:

Can you explain what the benefit of this change is? And why the different behaviour of std::same_as and std::is_void_v is not an issue. I'm not even sure we should call this an NFC patch.

In general it would be good to add this kind of information to the commit message/review description.

Pinging the reviewers!

In D122780#3532562, @philnik wrote:

Sorry it's taking so long. Louis doesn't have a lot of time currently and I think he should take a look first and say if we want to go this direction.

Pinging the reviewers again!

Can you take a look at the failed test?

Pinging the reviewers!

Pinging the reviewers!

Change block_size to enum.

Drop inline for __block_size

Move block_size to detail namespace
Include bits for libcpp_* functions.

Previous diff failed to apply. So uploading a new one.

Changes to address reviewer comments.

Ping!

Updated performance numbers:

Rebase

In D122858#3440050, @ldionne wrote:

I'm fine with this -- the main reason is that we will be touching most lines of this file in the near future with the other sort-related patches. But let's not take this as a precedent to start running clang-format on a file before every patch.

Address review comments.

Rebased since the small sort diff got submitted.

Minor comments, otherwise looks good to me.

Folks, this is a formatting only change to enable further changes. Please take a look.

In D122780#3420119, @philnik wrote:

Could you do the formatting changes in its own patch?

Fix a badly resolved merge.

Rebase

Rebase

This diff is based on https://reviews.llvm.org/D93233. We have other changes there (updates to fixed length sorting functions, bitonic sort) that we might consider later.

Louis, can you commit this for me?

Looks fine to me.

So I was writiing https://reviews.llvm.org/D114135 in parallel. I have added a test which fails with out the change. I am wondering if we should add it. Error message from the failed test below:

Can you explain when do we need to use _Comp_ref? Why is adding _Compare sufficient?

In D113413#3134968, @ldionne wrote:

Do you need someone to commit this for you? If so, please provide Author Name <email@domain> for attribution. Thanks!

Pinging @ldionne.

In D93233#3118424, @ldionne wrote:

In D93233#3101571, @nilayvaish wrote:

Hi ldionne@, I have question for you. Do the tests we have for libc++ ensure that the new implementation works well across all versions of the C++ standard? I want to make sure that I am not going to unintentionally break someone's standard-compliant code out there.

They should, however you're welcome to look at them - our tests are sometimes not up to our quality standards, so you should make sure they will catch all issues you can think about.

We do run those tests in C++03, C++11, C++14, C++17, C++20 and C++23 modes, if that was the sole intent of your question.

Move the depth check after the initial switch so that small sized sorts are not affected by the depth check.

Another attempt at uploading changes without formatting diff.

Remove formatting diffs from the diff. It seems Phabricator is unable to show the diffs between different commits.

Moved the diffs due to formatting by arc to a separate commit.

ldionne@, I am going to break this change into few parts and provide the benchmark results for each of the part separately. To begin with, I have posted: https://reviews.llvm.org/D113413 that makes the introsort change to the std::sort implementation.