This is an archive of the discontinued LLVM Phabricator instance.

[libc++] [P0879] constexpr heap and partial_sort algorithms
ClosedPublic

Authored by Quuxplusone on Dec 17 2020, 9:31 PM.

Details

Reviewers
ldionne
Group Reviewers
Restricted Project
Commits
rG5386aa26277f: [libc++] [P0879] constexpr heap and partial_sort algorithms
Summary

Now the only ones we're still missing from P0879 are sort and nth_element.

(nth_element is actually not trivial, because the existing implementation uses a goto label.)

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Dec 17 2020, 9:31 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptDec 17 2020, 9:31 PM

Rebase on D93443. @ldionne ping (after D93443)!

ldionne requested changes to this revision.Jan 25 2021, 9:08 AM

Generally looks good, I'm just asking for a bit more manual testing. Thanks a lot for working on this, I love that we're removing dependencies on <random>.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp
26–34

Can you please also add a few dumb hand-written test cases? You know I love those, right?

Same for the other algorithms whose tests have been rewritten.

This revision now requires changes to proceed.Jan 25 2021, 9:08 AM
libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp
26–34

The trick for make_heap is that there are multiple possible outputs (theoretically): heapifying {1,2,3} might give you {3,1,2} or it might give you {3,2,1}. Both possibilities are equally conforming, even though I would guess that all implementations really do the same thing in practice.

How much do we care about that? Do we mind hard-coding one of the outputs as "blessed"?

Anyway, I'm resisting out of laziness — couldn't someone else add ad-hoc tests in a separate commit? — but maybe it'd help to see an example of the kind of test you're thinking of. I mean would it just be like this?

TEST_CONSTEXPR_CXX20 bool test_simple() {
    int a[] = {5,2,4,1,3};
    std::push_heap(a, a+5);
    int expected[] = {5,3,4,1,2};
    assert(std::equal(a, a+5, expected, expected+5));
    return true;
}

TEST_CONSTEXPR_CXX20 bool test_simple() {
    int a[] = {5,2,4,1,3};
    std::pop_heap(a, a+5);
    int expected[] = {4,2,3,1,5};
    assert(std::equal(a, a+5, expected, expected+5));
    return true;
}
ldionne added inline comments.Jan 25 2021, 12:46 PM
libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp
26–34

What I want is pretty trivial, just "unroll" a few cases from your loop so they are more explicit. I want the tests to be as dumb as possible, because imagine for instance if there was a mistake in your loop conditions and it never ran? The test would be useless. Having at least a few really dumb tests removes this sort of issue.

Of course, there's a balance to strike. It doesn't always make sense to push too far with this sort of defensive behavior, but here it's pretty easy. For make_heap, something like this would satisfy me:

{
    int input[] = {3, 4, 1, 2, 5};
    std::make_heap(Iter(input), Iter(input + 5));
    assert(std::is_heap(input, input + 5));
    std::pop_heap(input, input + 5); assert(input[4] == 5);
    std::pop_heap(input, input + 4); assert(input[3] == 4);
    std::pop_heap(input, input + 3); assert(input[2] == 3);
    std::pop_heap(input, input + 2); assert(input[1] == 2);
    std::pop_heap(input, input + 1); assert(input[0] == 1);
}

You can put that inside test() itself. Does that make sense to you?

Another way to think about this: Imagine you're a user and you try to use libc++'s std::make_heap. Imagine the very first and most basic thing you might write just to try it out. Wouldn't it be a huge embarrassment if it didn't work for some reason? Well, we might as well just check-in a few of the most common and dumb examples of how to use facilities to guard us from that.

Add "simple" ad-hoc tests at @ldionne's request.
Poke buildkite.

Poke buildbot. (The last build https://reviews.llvm.org/B86646 seems to have failed in a devopsy way, and clicking "Restart Builds" just tells me I haven't got permissions for that.)

Poke buildkite yet again. ( https://reviews.llvm.org/B86662 failed in the same way.)

Poke buildkite yet again. One day it'll finish a build.

Quuxplusone marked 2 inline comments as done.Jan 26 2021, 4:44 PM

@ldionne: I don't think buildkite is ever going to finish a build here. I propose that you approve this revision and I just go again and land it, and we'll see what happens with the buildbots after that. (If it somehow does break buildbots, we can revert it.) Thoughts?

ldionne accepted this revision.Jan 27 2021, 6:17 AM

@ldionne: I don't think buildkite is ever going to finish a build here. I propose that you approve this revision and I just go again and land it, and we'll see what happens with the buildbots after that. (If it somehow does break buildbots, we can revert it.) Thoughts?

I've restarted the failing job. I've been having a few issues with the builders for the past 2 days. The laptops are being overworked :-)

Let's land this once https://buildkite.com/llvm-project/libcxx-ci/builds/1140 has succeeded.

This revision is now accepted and ready to land.Jan 27 2021, 6:17 AM
This revision was landed with ongoing or failed builds.Jan 27 2021, 7:26 AM
This revision was automatically updated to reflect the committed changes.