Page MenuHomePhabricator

[libc++][ranges] Implement modifying heap algorithms:
ClosedPublic

Authored by var-const on Jun 17 2022, 10:52 PM.

Details

Summary
  • ranges::make_heap;
  • ranges::push_heap;
  • ranges::pop_heap;
  • ranges::sort_heap.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a project: Restricted Project. · View Herald TranscriptJun 17 2022, 10:52 PM
Herald added subscribers: mgrang, mgorny. · View Herald Transcript
var-const requested review of this revision.Jun 17 2022, 10:52 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript

Use the actual patch number.

var-const added inline comments.Jun 17 2022, 10:58 PM
libcxx/include/__algorithm/make_heap.h
26–33

Note: a few of these existing internal functions were missing the _LIBCPP_HIDE_FROM_ABI annotation. I presume adding it won't cause any problems?

41

The main purpose of this function is to avoid leaking the __comp_ref_type quirk from this file (similarly for the other heap headers).

libcxx/include/__algorithm/ranges_pop_heap.h
43

Note: the Standard specifies that the range has to be non-empty in pop.heap:

Preconditions: The range [first, last) is a valid **non-empty** heap

However, our existing non-ranges version of pop_heap is simply a no-op for an empty range, and the same is true for GCC and MSVC. Please let me know whether you think being strict with this check adds any benefit.

Fix the CI.

var-const updated this revision to Diff 438243.Jun 19 2022, 8:12 PM

Rebase on main.

ldionne added inline comments.
libcxx/include/__algorithm/make_heap.h
26–33

It must have been because they didn't want to always_inline those functions back in the days. Adding it is the correct thing to do since we don't use always_inline for ABI anymore.

libcxx/include/__algorithm/ranges_make_heap.h
47

Probably applies elsewhere too.

libcxx/include/__algorithm/ranges_pop_heap.h
43

I would add a _LIBCPP_ASSERT to be strict about this. Users are likely to use the last element of the range after calling pop_heap (because that's the element they popped), and that would be UB if our pop_heap returns silently when the range is empty.

var-const added inline comments.Jun 20 2022, 12:30 PM
libcxx/include/__algorithm/ranges_pop_heap.h
43

Just to clarify, do you mean also adding it to the classic algorithm, or just to the ranges version? In the former case, would that require a release note?

huixie90 requested changes to this revision.Jun 27 2022, 10:23 AM
huixie90 added a subscriber: huixie90.
huixie90 added inline comments.
libcxx/include/__algorithm/make_heap.h
33

I think __sift_down does not use iter_move or iter_swap. This is not correct for ranges algorithms

libcxx/include/__algorithm/pop_heap.h
33

I believe this needs to call ranges::iter_move for the ranges version

40

same as above

43

I think this does not do the right thing for ranges overload

libcxx/include/__algorithm/push_heap.h
35–37

should use iter_move for ranges overload

libcxx/include/__algorithm/sort_heap.h
31

This won't call the ranges::iter_move for the ranges overload

This revision now requires changes to proceed.Jun 27 2022, 10:23 AM
var-const updated this revision to Diff 440536.Jun 28 2022, 1:58 AM
var-const marked 3 inline comments as done.

Address feedback.

libcxx/include/__algorithm/pop_heap.h
33

Thanks _a lot_ for finding this! I'd prefer to address this for all recently-implemented algorithms in a follow-up patch -- would that work for you?

libcxx/include/__algorithm/ranges_pop_heap.h
43

From offline discussion: we should add an assertion for the classic version as well. A release note is not necessary because it's undefined behavior.

huixie90 added inline comments.Jun 28 2022, 7:24 AM
libcxx/include/__algorithm/pop_heap.h
33

Yes. sounds good to me.
I am going to create a test utility which adapts our existing test_iterators, and simulate the proxy iterator behaviour (like zip iterator). and all permutation algorithms would test against these kinds of iterators

Fix the CI.

Fix the CI.

ldionne added inline comments.Jun 28 2022, 11:54 AM
libcxx/include/__algorithm/make_heap.h
40

I would suggest:

  1. Swapping the names __make_heap_impl and __make_heap.
  2. Inlining the new __make_heap_impl into the new __make_heap
  3. Removing __make_heap_impl, which isn't used anywhere anymore.

This gives:

template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
  _Comp_ref __comp_ref = __comp;

  using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
  difference_type __n = __last - __first;
  if (__n > 1) {
    // start from the first parent, there is no need to consider children
    for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
        std::__sift_down<_Compare>(__first, __comp_ref, __n, __first + __start);
    }
  }
}

I think the same comment applies to all the other heap algorithms.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.pop_heap.pass.cpp
10 ↗(On Diff #440683)

This is not needed -- we support basic assertions even when the "debug" mode is disabled.

It's kind of messy right now (I'm in the process of cleaning that up), but basically Debug Mode = heavyweight checks that change ABI and/or complexity, and Assertions = lightweight checks that don't impact ABI/complexity.

Debug Mode implies Assertions, but not the other way around. Here you only need to turn Assertions on with _LIBCPP_ENABLE_ASSERTIONS=1 to test this.

This comment applies to the other assert.FOO tests.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.ranges_pop_heap.pass.cpp
15–24 ↗(On Diff #440683)

I am not sure that the full synopsis is useful here. Also applies to other assert.FOO tests.

var-const updated this revision to Diff 441907.Jul 2 2022, 3:50 PM
var-const marked 2 inline comments as done.

Address feedback.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.pop_heap.pass.cpp
10 ↗(On Diff #440683)

Thanks!

var-const updated this revision to Diff 441917.Jul 2 2022, 7:03 PM

Fix order of includes.

LGTM. I think you changed some signatures of some __ function to take an "Tag" template argument in the partial_sort patch and this change might need to rebase that change?

libcxx/include/algorithm
276

unresolved merge conflicts?

In general looks good, but there are some small issues.

libcxx/include/__algorithm/make_heap.h
39–48

Maybe drop the inline while you're at it.

libcxx/include/__algorithm/push_heap.h
39

Can you put the break; on its own line?

53

You need to calculate __last - __first before the function call since they are moved from in this call.

libcxx/include/__algorithm/ranges_pop_heap.h
49

Here __first might be used in a moved from state.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp
44

I think it would be good to test with all iterator categories to see only random access and contiguous are valid.

218

I really would like to see the maximum complexity to be validated for all heap operations. Especially since they all have different complexities.

var-const updated this revision to Diff 442426.Jul 5 2022, 7:21 PM
var-const marked 13 inline comments as done.

Address feedback, fix the CI.

libcxx/include/__algorithm/make_heap.h
39–48

This seems like more than a purely mechanical change; I'd rather keep as is.

libcxx/include/__algorithm/push_heap.h
53

Thanks!

libcxx/include/algorithm
276

Sorry about that!

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp
44

This would apply to every test range algorithm test and make it more verbose without increasing coverage. The types from almost_satisfies_types.h are deliberately written to fall just short of meeting constraints of the type while satisfying all the prerequisite constraints; e.g. both RandomAccessIteratorNotDerivedFrom and RandomAccessIteratorBadIndex satisfy bidirectional_iterator. Thus, if RandomAccessIteratorNotDerivedFrom doesn't satisfy the constraints, it means that bidirectional_iterator and all the iterator concepts it refines don't satisfy, either.

218

I think this is valuable but I'd rather do a follow-up after we finished the initial implementation of range algorithms dedicated solely to testing complexity where possible.

huixie90 accepted this revision.Jul 6 2022, 2:48 AM

A few comments other than that LGTM! But I like to see the CI green before approving.

libcxx/include/__algorithm/push_heap.h
53

I would prefer not to use auto.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp
44

Fair point.

218

Should we add a note on the Status page as a reminder?

var-const updated this revision to Diff 443111.Jul 7 2022, 7:18 PM
var-const marked 2 inline comments as done.

Address feedback, fix the CI.

var-const added inline comments.Jul 7 2022, 7:57 PM
libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp
218

I'll get to this pretty soon -- I don't think there should be need for a TODO.

var-const updated this revision to Diff 443320.Jul 8 2022, 12:19 PM

Fix the CI, rebase on main.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 8 2022, 1:49 PM
This revision was automatically updated to reflect the committed changes.