Ping

Talked to @mclow.lists about this PR - he said that he's interested.

Those numbers didn't make sense to me. Tested my sort with std::merge - the suggested version gives a 10% win over the standard one.

Ok, last attempt to push this.

Ping.

Reminding about this PR.

Eric's comment.

Sorry for taking a long time - was busy.

From the comments on the optimiser bugs created I take that this type of code transformation is not feasible in a foreseeable future.
The reason is that this code structure has a non-canonical loop structure and optimiser really likes it's single entry loops.

Unfortunately switch based solution didn't work out - the degradation of 10% is not evenly distributed and, in fact, the results are even significantly worse than current implementation for the case when right hand side.

@DavidBolvansky solved the puzzle!
http://quick-bench.com/W5kTrvhSkufQQleyYsY9KTOmDrc

Reported this as an optimiser bug - maybe they'll have a suggestion: https://bugs.llvm.org/show_bug.cgi?id=42334

Reported switch not being removed as a bug: https://bugs.llvm.org/show_bug.cgi?id=42313 - this should be doable.

After multiple attempts I could not make the "if/switch" based version to produce a similar result.
Since there doesn't seem to be "is_constant_evaluated" in clang, I cannot write a constexpr enabled version of this function.
I can report this as an optimiser bug, if that would be useful.

In D63063#1536895, @lebedev.ri wrote:

Binary size increase (godbolt: https://godbolt.org/z/b1ZFTA):
For std::string the size grows from 394 assembly instructions to 465 instructions (18%).
For int - from 62 to 64 (3%).

Uhm.
I have a question:
you did notice that you are looking at libstdc++ implementation there?
https://godbolt.org/z/WGSQ6r

In D63063#1536732, @lebedev.ri wrote:

In D63063#1536710, @dyaroshev wrote:

In D63063#1535924, @lebedev.ri wrote:

Have you analyzed, how much is this a problem of the actual implementation (in libc++), and how much of the llvm optimization passes?
I.e. are there some obvious failures of the llvm opts?

I do not know how to get those. What do I look at?

Well, if "hey tool, give me all the optimizations that could be done here" was that easy :/

• Compile the code to .s (-c -S -o test.s), and analyze the produced assembly, interpret it "with your mind" and think if some particular assembly instruction sequences can be optimized into other, better/shorter/etc, assembly instruction sequences. This one is cpu architecture, cpu model/version specific, obviously.
• Compile the code to LLVM IR (-c -emit-llvm -S -o test.ll), and do the same at IR level.

In D63063#1535924, @lebedev.ri wrote:

Have you analyzed, how much is this a problem of the actual implementation (in libc++), and how much of the llvm optimization passes?
I.e. are there some obvious failures of the llvm opts?

Thank you, @mclow.lists
Please do not close this revision - I will try to make the optimiser produce the same code with ifs/whiles/switches.

Updated to add a missing '\n'
Not sure who to put as a reviewer.

Hooray! Thanks!

In D53994#1332035, @EricWF wrote:

LGTM.

Do you have commit access?

@ldionne this weekends are an ideal time for me to fix any review comments you might have.

@ldionne - can we please review/merge this? Christmas is coming and I won't have a computer where I can make changes for quite some time.

In D53994#1325493, @sbenza wrote:

In D53994#1319418, @dyaroshev wrote:

In D53994#1319307, @sbenza wrote:

re resize+iota, I don't see why not. That code is not part of the measurements.

Why do you think for lower bound it is beneficial to look for "not found elements"?

lower_bound, just like std::set/map will stop the search when they find the element, but will generally continue all the way if it is not there.
The access pattern is a little different when it is all misses.

Recreated the benchmarks in spirit of the sorting benchmarks.

In D53994#1319307, @sbenza wrote:

re resize+iota, I don't see why not. That code is not part of the measurements.

As for why 0...n, for integers it doesn't really what the values are. only that there are N distinct values. The initial ordering of those values is changed depending on the benchmark.
Note that for strings we don't use consecutive values as the value itself matters for operator<. That is, the first mismatched char is the one that matters and "sequential" strings would not be good for that.

For lower_bound you might want a different sequence, though. You might also want to check for values missing in the list. The way we do it for std::set is to have 0,2,...,N. We then search for 2*i for hits and 2*i+1 for misses.

In D53994#1319017, @ldionne wrote:

@dyaroshev Can you please rebase on top of master? There's been significant changes in algorithms.bench.cpp and the patch does not apply cleanly anymore.

Hi again. Just reminding about this review.

In D53994#1302906, @ldionne wrote:

In D53994#1302905, @ldionne wrote:

In D53994#1302663, @dyaroshev wrote:

Hi. Just wanted to know what's the status of this change.

I just want @jfb to take a quick look and if he's ok with the change, I'll commit it.

Also note that some people in the US are going to be out this week due to Thanksgiving, so it may wait until next week.

Hi. Just wanted to know what's the status of this change.

Ok - not adding context in git helped.
Which is unpleasant to read though.

Is there a known reason why it doesn't list 'test' in libcxx/algorithms/half_positive.pass.cpp??

Yes, you are right - another artefact of non-apliable patch, thanks.
FYI: updated the description in the test a bit too.

Yes, thank you, missed re-adding the test file.

Recreated the original patch - this was a false alarm as far as I understood it.
I listed everything I've done to tackle and understand the issue in the description of the PR.

In D53994#1284436, @ldionne wrote:

For simplicity, I did a wholesale revert of https://reviews.llvm.org/D52697 (as r345893) even though that patch included some benchmarks that are probably useful. Feel free to re-submit bits that do not impact the library on their own, but I think the algorithm should only be modified once the regression you found is understood and worked around.

In D53994#1284436, @ldionne wrote:

I did not participate in the original review, but my preference would be for https://reviews.llvm.org/D52697 to be reverted until the cause of the regression is understood and fixed. Unless other maintainers disagree.

I'm a bit uneasy with checking-in a fix to an issue that is not well understood -- this is the standard library, after all, and we run on all kinds of platforms in all kinds of environments. "It works on my machine" usually does not mean much.

FOUND IT! ! difference_type len = _VSTD::distance(first, __last); - should be size_t on the left
I don't know what happened - I ran benchmarks locally before merging!
I'm sorry - no idea why it didn't reproduce on my machine. Maybe I messed something up
I can do the patch tommorow. It will take a while to merge it (judging by this merge experience).
Do you want to maybe roll this back?
http://quick-bench.com/fcV9gaAWPeqB_3-AePOw9H2wxXU

Hi again.

In D52697#1279140, @EricWF wrote:

In D52697#1278285, @dyaroshev wrote:

I'm sorry, how do I merge this patch?

Do you have commit access? If not I can go ahead and merge it for you with your permission.

I'm sorry, how do I merge this patch?

In D52697#1278218, @EricWF wrote:

LGTM. Thanks so much for this change.

I'm still quite surprised about how much of a performance difference this make.

Updating tests according to review comments.

FYI, this patch fails to compile on my machine:

@EricWF?

Hi again! What is the situation with this PR?

@EricWF can we maybe merge it now?

__half_positve now just uses a cast to make_unsigned and other review issues.

Seems like you are not comfortable with some additional changes that I did. I removed all of them and just left what was 100% necessary - casting to size_t for positive ptrdiff_t.

Forgotten _VSTD::

Simplifying the patch after review.

Just wanted to know what is the current status of this PR.

My bad, size_t cast is faster: http://quick-bench.com/klty7gya6LMs5p8YVNSQ3bnUXcA

In D52697#1251168, @lebedev.ri wrote:

FWTW just adding an assume is *NOT* enough, sadly.
https://godbolt.org/z/v8fjnG

In D52697#1251063, @mclow.lists wrote:

I don't think there's a hurry to merge this.
The performance wins are nice - on a micro scale.
Do you have an example in a real app where this makes a difference?

Note: I'm not disparaging the work you've done.
Nor do I think this isn't worth pursuing.
I'm just looking at other approaches.

In D52697#1250525, @mclow.lists wrote:

We can tell the compiler that std::distance always returns >= 0.
The optimizer already knows a lot about various standard library calls.

Minor comments typos.

• Addressed review comments.
• Changed (I measured - the result performs identically) cast to __half_unsigned function
• Added similar optimization and benchmarks to equal_range.

Thanks for the quick review! I will address you comments tomorrow.

Unfortunately didn't manage to run a clang-format on my changes - it kept ignoring the library settings - so probably the formatting needs to be reviewed too.

I forgot the synopsis.