This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::stable_sort`.
ClosedPublic

Authored by var-const on Jun 15 2022, 1:26 AM.

Diff Detail

Event Timeline

var-const created this revision.Jun 15 2022, 1:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 15 2022, 1:26 AM
Herald added subscribers: mgrang, mgorny. · View Herald Transcript
var-const requested review of this revision.Jun 15 2022, 1:26 AM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 437077.Jun 15 2022, 1:27 AM

Use the actual patch number.

var-const added inline comments.Jun 15 2022, 1:28 AM
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
139

For some reason, the compiler fails to parse this construct as an initializer list of OrderedValues without this hint.

libcxx/test/support/almost_satisfies_types.h
304

This is copied from the sort patch.

Thanks for working on this! Some small remarks.

libcxx/include/__algorithm/ranges_stable_sort.h
40

Please remove the constexpr

libcxx/include/__algorithm/stable_sort.h
211

While you're at it.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
140

I would suggest to make the original_order member a simple integer sequence: 1, 2, 3, etc. That makes it easier to verify whether the output is correct. Identical values will have incrementing values.

151

Is the trailing comma allowed?

169

It would be good to validate stability in these tests too.

247

Here we can validate complexity. Obviously implementations can make different choices regarding when there's not "enough extra memory" but we can test the N log (N) for a small number of items.

256

Interesting since it's possible to allocate memory in constexpr functions.

Apply feedback from the sort patch where appropriate.

var-const updated this revision to Diff 437744.Jun 16 2022, 3:56 PM
var-const marked 5 inline comments as done.

Rebase on main, apply changes from the ranges::sort patch, address feedback.

libcxx/include/__algorithm/ranges_stable_sort.h
40

Thanks!

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
140

I started with that, but then I had the idea of enumerating each duplicate value instead (read those 31, 32, 33 as 3.1, 3.2, 3.3, etc.). I think it makes it more readable because following the numbering within a duplicate is much easier than following the numbering across all the elements. What do you think?

151

Yes. Removed it for redundancy.

169

To clarify, do you mean all the tests in test()? Or just the tests with a custom comparator?

247

Similar to the sort patch, I don't think we have a great way of doing this:

  • we can use the exact number of operations our implementation happens to perform (we have some precedent in e.g. test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp), but that would make it libc++-specific and, IMO, has limited usefulness;
  • simply testing for num_operations < N*log(N) isn't going to work because it's actually k*N*log(N), where k is an arbitrary constant;
  • the "proper" way would be to test with increasingly large inputs and applying some math to calculate the growth factor, but that seems like a sizable project in itself, even assuming it's worth the implementation effort.
256

I know that P0202 was adding constexpr to algorithms. At the time (in 2017), making stable_sort constexpr was infeasible:

Algorithms stable_partition, inplace_merge and stable_sort allocate memory, construct variables using placement new, use unique_ptr and do other things not acceptable in constexpr expressions. Making those algorithms constexpr seems to be a hard task that would require a lot of intrinsics. Those algorithms are not marked with constexpr in this wording.

I don't know if there's been any work in that direction since then. Perhaps it's ripe for a new paper?

philnik requested changes to this revision.Jun 20 2022, 2:59 AM

Nothing major, but I'd like to take another look after my comments have been addressed.

libcxx/include/__algorithm/ranges_stable_sort.h
42–43

Why is this not static but instead marked const?

43

Maybe name it __ranges_stable_sort_impl?

46

This probably also applies to ranges::sort.

libcxx/include/__algorithm/stable_sort.h
212

Would you be interested in removing std::get_temporary_buffer and std::return_temporary_buffer in a follow-up patch? It's deprecated and just forwards to new and delete.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
130–133

As always, I think this should work. I'm not yet fluent in spaceship operator.

138

Does it not work to just use std::array orig_in = {V{10, 101}, ...}?

188

Isn't this be unnecessary and even counter-productive?

214

Again, I don't think this should be here.

This revision now requires changes to proceed.Jun 20 2022, 2:59 AM
ldionne accepted this revision as: ldionne.Jun 20 2022, 11:09 AM
ldionne added a subscriber: ldionne.

I'll let others give final approval, but this LGTM.

libcxx/docs/Status/RangesAlgorithms.csv
77

Once you commit this, it'll be done, not under review.

Mordante added inline comments.Jun 22 2022, 10:43 AM
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
140

How do you feel about making the original_order a double and use 3.1?

Since the same constants written the same in the source there shouldn't be an issue with floating point rounding.

151

TIL, fun that it's allowed in some places.

169

I think it's mainly important for this test and the ones below.

247

Here http://eel.is/c++draft/stable.sort#5 lists the exact number of comparisons to do and that the number of projections is double of that. So I think we can use that value as an upper bound, for example with N = 10.

256

I didn't investigate the reason, but this is indeed what I expected :-)

Based on the unanimous consent in this poll https://github.com/cplusplus/papers/issues/1222#issuecomment-1159203566
the time is indeed ripe and a paper is already available.

var-const updated this revision to Diff 440453.Jun 27 2022, 6:51 PM
var-const marked 15 inline comments as done.

Address feedback

libcxx/include/__algorithm/ranges_stable_sort.h
42–43

Thanks for spotting!

43

I somewhat prefer the current version (name of the algorithm + fn to indicate that the function is contained within the function object + impl for disambiguation). I'd keep the current state unless you feel strongly about it.

46

Thanks! Fixed both.

libcxx/include/__algorithm/stable_sort.h
212

Yes, I can do this in a follow-up (unless you beat me to it :) ).

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
138

It does -- it just gives an easy way to make sure both arrays have the same number of elements (since they are long, it's easier to make a mistake).

140

I really like this, thanks -- makes the intention a lot clearer and looks better, too.

188

It's used to compare check the in array after it's sorted:

assert((in == std::array{A{1}, A{2}, A{3}}));

Perhaps I'm missing something?

214

Same -- it's necessary to compare arrays.

247

I'd rather do this in a follow-up. I think perhaps it would be good to have a dedicated test file for this, similar to the robust_against_copying_*.

256

Thanks for finding that paper!

Mordante accepted this revision as: Mordante.Jun 29 2022, 10:36 AM

Nothing major, but I'd like to take another look after my comments have been addressed.

LGTM, I leave the final approval to @philnik.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
247

Sounds good to me.

philnik accepted this revision.Jun 30 2022, 4:59 AM

LGTM.

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp
188

Ah OK, I missed that.

This revision is now accepted and ready to land.Jun 30 2022, 4:59 AM
This revision was automatically updated to reflect the committed changes.