Page MenuHomePhabricator

dyaroshev (Denis Yaroshevskiy)
User

Projects

User does not belong to any projects.

User Details

User Since
Oct 6 2017, 3:12 PM (85 w, 1 d)

Recent Activity

Dec 17 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

Hooray! Thanks!

Dec 17 2018, 2:16 PM

Dec 15 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

LGTM.

Do you have commit access?

Dec 15 2018, 9:44 AM

Dec 14 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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

Dec 14 2018, 3:59 PM

Dec 12 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

@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.

Dec 12 2018, 2:41 PM

Dec 10 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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.

Dec 10 2018, 11:21 AM

Dec 9 2018

dyaroshev updated the diff for D53994: Fixing lower bound regression in certain situations..

Recreated the benchmarks in spirit of the sorting benchmarks.

Dec 9 2018, 8:24 AM

Dec 4 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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.

Dec 4 2018, 3:48 PM
dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

@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.

Dec 4 2018, 1:18 PM

Nov 28 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

Hi again. Just reminding about this review.

Nov 28 2018, 6:53 AM

Nov 20 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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.

Nov 20 2018, 4:16 AM

Nov 19 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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

Nov 19 2018, 2:51 AM

Nov 14 2018

dyaroshev added inline comments to D53994: Fixing lower bound regression in certain situations..
Nov 14 2018, 5:49 AM

Nov 13 2018

dyaroshev updated the diff for D53994: Fixing lower bound regression in certain situations..

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

Nov 13 2018, 4:33 PM
dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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

Nov 13 2018, 4:32 PM
dyaroshev updated the diff for D53994: Fixing lower bound regression in certain situations..

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

Nov 13 2018, 4:26 PM

Nov 12 2018

dyaroshev updated the diff for D53994: Fixing lower bound regression in certain situations..

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

Nov 12 2018, 4:20 PM

Nov 11 2018

dyaroshev updated the summary of D53994: Fixing lower bound regression in certain situations..
Nov 11 2018, 4:03 PM
dyaroshev updated the diff for D53994: Fixing lower bound regression in certain situations..

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.

Nov 11 2018, 3:50 PM
dyaroshev updated the summary of D53994: Fixing lower bound regression in certain situations..
Nov 11 2018, 3:49 PM
dyaroshev updated the diff for D53994: Fixing lower bound regression in certain situations..
Nov 11 2018, 3:21 PM

Nov 1 2018

dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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.

Nov 1 2018, 2:43 PM
dyaroshev updated the summary of D53994: Fixing lower bound regression in certain situations..
Nov 1 2018, 2:27 PM
dyaroshev added a comment to D53994: Fixing lower bound regression in certain situations..

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.

Nov 1 2018, 2:06 PM
dyaroshev created D53994: Fixing lower bound regression in certain situations..
Nov 1 2018, 12:53 PM

Oct 31 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Oct 31 2018, 4:12 PM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

Hi again.

Oct 31 2018, 3:57 PM

Oct 29 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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.

Oct 29 2018, 11:56 AM

Oct 27 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Oct 27 2018, 4:27 PM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

LGTM. Thanks so much for this change.

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

Oct 27 2018, 12:18 PM
dyaroshev added inline comments to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Oct 27 2018, 9:13 AM
dyaroshev updated the diff for D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

Updating tests according to review comments.

Oct 27 2018, 9:11 AM
dyaroshev added a comment to D53523: Add benchmark for std::set..

FYI, this patch fails to compile on my machine:

Oct 27 2018, 8:47 AM

Oct 26 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

@EricWF?

Oct 26 2018, 3:01 PM

Oct 25 2018

dyaroshev added inline comments to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Oct 25 2018, 11:13 AM

Oct 24 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

Hi again! What is the situation with this PR?

Oct 24 2018, 10:27 AM

Oct 16 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

@EricWF can we maybe merge it now?

Oct 16 2018, 4:02 PM

Oct 14 2018

dyaroshev added inline comments to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Oct 14 2018, 7:24 AM
dyaroshev updated the diff for D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Oct 14 2018, 7:22 AM

Oct 13 2018

dyaroshev added inline comments to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Oct 13 2018, 2:22 PM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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.

Oct 13 2018, 10:24 AM
dyaroshev updated the diff for D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

Forgotten _VSTD::

Oct 13 2018, 10:22 AM
dyaroshev updated the diff for D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

Simplifying the patch after review.

Oct 13 2018, 10:17 AM

Oct 10 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Oct 10 2018, 2:19 PM

Oct 1 2018

dyaroshev added inline comments to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Oct 1 2018, 11:34 AM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Oct 1 2018, 10:28 AM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Oct 1 2018, 10:07 AM
dyaroshev added inline comments to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Oct 1 2018, 9:28 AM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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.

Oct 1 2018, 9:09 AM

Sep 30 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Sep 30 2018, 3:27 PM
dyaroshev updated the diff for D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

Minor comments typos.

Sep 30 2018, 10:08 AM
dyaroshev updated the diff for D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
  • Addressed review comments.
  • Changed (I measured - the result performs identically) cast to __half_unsigned function
  • Added similar optimization and benchmarks to equal_range.
Sep 30 2018, 9:57 AM

Sep 29 2018

dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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

Sep 29 2018, 4:28 PM
dyaroshev added a comment to D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..

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.

Sep 29 2018, 2:46 PM
dyaroshev created D52697: Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using unsigned division by 2 when possible..
Sep 29 2018, 2:36 PM

Oct 30 2017

dyaroshev updated subscribers of D38653: Optimizing std::copy and related algorithms for std::reverse_iterator..
Oct 30 2017, 2:22 AM

Oct 29 2017

dyaroshev updated the summary of D39405: std::set_union accesses values after move..
Oct 29 2017, 11:26 PM
dyaroshev updated the diff for D39405: std::set_union accesses values after move..

I forgot the synopsis.

Oct 29 2017, 8:59 AM
dyaroshev created D39405: std::set_union accesses values after move..
Oct 29 2017, 8:52 AM

Oct 26 2017

dyaroshev updated the diff for D38653: Optimizing std::copy and related algorithms for std::reverse_iterator..
Oct 26 2017, 10:18 AM

Oct 10 2017

dyaroshev updated the diff for D38653: Optimizing std::copy and related algorithms for std::reverse_iterator..
Oct 10 2017, 10:40 AM

Oct 6 2017

dyaroshev updated the summary of D38653: Optimizing std::copy and related algorithms for std::reverse_iterator..
Oct 6 2017, 4:21 PM
dyaroshev created D38653: Optimizing std::copy and related algorithms for std::reverse_iterator..
Oct 6 2017, 4:20 PM