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.