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.

Fixed some compilation issues and reduced the number of changes in ordering of equivalent elements

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.

It seems that we can use _LIBCPP_HIDE_FROM_ABI with __bitsetsort_loop. Causes the compiler to report errors like the following:

• Fixed the implementation. No tests fail now: https://buildkite.com/llvm-project/libcxx-ci/builds/5917.
• Added _LIBCPP_HIDE_FROM_ABI to most functions.

In D93233#3046799, @ldionne wrote:

• Rebase onto main
• Keep the old std::sort implementation around for ABI compatibility
• Do not explicitly instantiate bitset sort in the library -- that ties our hands too much

Still left to do:

• Some tests are failing, they need to be investigated
• Do basic code size testing since we're not instantiating the sorts in the dylib anymore -- does it cause the size of user programs to blow up badly?
• Make sure I applied the diff correctly - I had to do it manually but the diff was generated weirdly, so I'm not sure the diff I applied is correct.
• We need to decide on the visibility of implementation detail functions. We probably want to sprinkle _LIBCPP_HIDE_FROM_ABI all around.

Ideally @minjaehwang if you could commandeer this again and make those fixes, that would be awesome. From here on, it should be fairly straightforward to make changes until we can ship this, since I should have handled most of the annoying libc++ specific things.

ymandel@, I do not have commit access to the repo. Can you commit this for me? Thanks!

In D109470#2992119, @ymandel wrote:

Any idea if there's a test for this matcher that should be updated?