This is an archive of the discontinued LLVM Phabricator instance.

Add shift functions (P0769)
AbandonedPublic

Authored by zoecarver on Mar 29 2019, 9:02 PM.

Details

Reviewers
mclow.lists
ldionne
howard.hinnant
EricWF
Group Reviewers
Restricted Project
Summary

Adds shift_right and shift_left functions to algorythems as specified in P0769R2.

In this implementation, I use std::advance to shift the iterators instead of the proposed sample algorithm. This seems to work fine and be much faster, but there may be some reason not to do this which I am unaware of.

The document suggests that _only_ shift_left is a constexpr while all other functions/overloads are not. I think this is a typo, but I can update if needed (edit: emailed to inquire about this).

Diff Detail

Event Timeline

zoecarver created this revision.Mar 29 2019, 9:02 PM
mclow.lists requested changes to this revision.Mar 30 2019, 3:32 PM

I don't think that this is right. All advance does is update an iterator. No data is being moved here.

This revision now requires changes to proceed.Mar 30 2019, 3:32 PM
zoecarver updated this revision to Diff 193038.Mar 31 2019, 8:31 PM
zoecarver edited the summary of this revision. (Show Details)

Update:
I have re-implemented the shift algorithm. Now it uses a much more similar method to the example given in the paper.

Just so we are all on the same page, here is an example of what this patch does:

T arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto b = std::begin(arr);
auto e = std::end(arr);

auto left = shift_left(b, e, 5); // left = 5,6,7,8,9
auto right = shift_right(b, e, 5); // right = 0,1,2,3,4
auto empty = shift_right(left, left + 10, 5); // empty = <empty>

Thank you @mclow.lists for the tests and help implementing.

zoecarver updated this revision to Diff 193039.Mar 31 2019, 8:37 PM

Fix whitespace.

zoecarver marked 2 inline comments as done.Apr 5 2019, 9:27 AM
zoecarver added inline comments.
include/algorithm
5800

This needs to be constexpr (same with right_shift)

5803

Negative ranges are supported too.

zoecarver marked an inline comment as done.Apr 5 2019, 11:17 AM

Thoughts on manually (using for loops) decrementing / incrementing iterators vs std::next/std::advance?

include/algorithm
5803

Nevermind, that was an earlier revision. Negative values are UB.

zoecarver updated this revision to Diff 193920.Apr 5 2019, 11:29 AM

Make shift functions constexpr.

EricWF added a subscriber: EricWF.Apr 7 2019, 5:34 PM
EricWF added inline comments.
include/algorithm
5806

Can you write explicit braces to make it clear it's an empty loop?

zoecarver marked an inline comment as done.Apr 7 2019, 5:44 PM
zoecarver added inline comments.
include/algorithm
5806

For sure. A lot of the empty loops are formatted like this:

for (...)
    ;

Is that or braces preferred?

zoecarver updated this revision to Diff 194089.Apr 7 2019, 8:21 PM

Fix empty for loop braces

Friendly ping. Anything else need to be done on this?

zoecarver updated this revision to Diff 196379.Apr 23 2019, 7:45 PM

Fix spacing / formatting.

  • valid constexpr
  • much simpler implementation
  • correct implementation (one that actually works)
  • one implementation for all iterators (including forward iterators)
  • tests that are more clear (correct on inspection)
zoecarver updated this revision to Diff 212724.Jul 31 2019, 9:38 PM

Fix the complexity of shift_right. The only case where this function is more complex than the standard (assuming shift_left is also updated) is when n is greater than std::distance(first, last) - n.

ldionne requested changes to this revision.Aug 5 2019, 10:12 AM
ldionne added inline comments.
libcxx/include/algorithm
644 ↗(On Diff #212724)

You shouldn't implement the parallel version here, that should be in PSTL.

5693 ↗(On Diff #212724)

This should just be _LIBCPP_CONSTEXPR since it's a C++20 algorithm anyway.

5724 ↗(On Diff #212724)

Is this equivalent to std::advance(__first, std::distance(__first, __last) - __n)? If so, why not use that?

5734 ↗(On Diff #212724)

We're making multiple passes over the whole range to get things like __rbegin. I can't imagine that's the only way of implementing this algorithm, and if so, that was certainly not the intent of the paper.

Did you look at https://github.com/danra/shift_proposal/blob/master/shift_proposal.h?

This revision now requires changes to proceed.Aug 5 2019, 10:12 AM
zoecarver marked an inline comment as done.Aug 5 2019, 7:59 PM
zoecarver added inline comments.
libcxx/include/algorithm
5734 ↗(On Diff #212724)

I try not to look at the sample implementations, it's more fun that way :) In this case, the implementation is much more performant, so I will implement it (or something close).

ldionne added inline comments.Aug 6 2019, 12:50 PM
libcxx/include/algorithm
5734 ↗(On Diff #212724)

I understand, however this is a standard library. Even though it can be fun to implement stuff in the standard library, the primary goal of this software is not to be "fun to implement". Correctness and efficiency should be the primary motivations here -- let's keep that in mind.

I sound boring, I know :-)

Herald added a project: Restricted Project. · View Herald TranscriptJan 11 2021, 2:57 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver abandoned this revision.Jan 11 2021, 5:08 PM