New issue
Advanced search Search tips

Issue 863135 link

Starred by 1 user

Issue metadata

Status: Untriaged
Owner: ----
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 3
Type: Bug



Sign in to add a comment

Optimize color_utils.cc

Project Member Reported by brucedaw...@chromium.org, Jul 12

Issue description

While investigating crbug.com/858944 I noticed ComputeThumbnailScore using more CPU time than I would have expected. Most of the CPU time is in the known-to-be-slow round() function so it would be easy to make this code run twice as fast or better.

1) We should be using float variables and constants instead of double. This gives the compiler more latitude to do multiplications in parallel. The extra precision (and size of the constants) is unnecessary for what are essentially 8-bit calculations.

2) We should use a faster function for rounding results. As shown in https://codereview.chromium.org/2096723003 (and the follow-up https://codereview.chromium.org/2466203002) it is easy to get faster rounding by going int(f + 0.49999997f) and the results will be identical (as long as the float that is one ULP smaller than 0.5f is never rounded, which is trivially provable). That is, we can make use of our domain specific knowledge to create a faster but identical round() function.

GetLuma is the bottleneck in this particular case and was added in https://codereview.chromium.org/1761183002, but a cleanup of all double-precision math in this function is tempting.

 
I'd prefer to speed up rounding by improving the implementation in the standard library if possible.  One thing I note is that your implementation rounds toward positive infinity, which is not always desirable in all the color utils code.

Judiciously converting doubles to floats, where the end results discard enough precision for this to be irrelevant, seems like a good change.
We currently use Microsoft's standard library on Windows (where I saw the slowdown) which we don't own. The other problem with optimizing std::round is that a generic round() function has to handle all sorts of messy edge cases.

> your implementation rounds toward positive infinity

It rounds to nearest, which is the same as std::round(). I think the int(f+constant) method misbehaves for negative numbers, and it doesn't round-to-nearest-even so it rounds 4.5 to 5.0 instead of 4.

Maybe the best fix is to get the compiler team to emit roundps instead of calling std::round. I don't know what the implications of that are but one would hope that it would produce the same results. I filed https://bugs.llvm.org/show_bug.cgi?id=38153 to request that.
I'm confused by "It rounds to nearest ... I think the int(f+constant) method misbehaves".  I was talking about the int(f+constant) method, and I was speaking about its behavior for negative numbers.  You might actually need a different constant in that case, I was just going off of "add ~0.5 and cast is a round-toward-positive-infinity move".
Okay, we're agreeing that it's broken for negatives, but describing it differently. I was confused by the "rounds towards positive infinity" comment because it rounds to nearest for positive numbers and for negative numbers it rounds to nearest but then adds 1.0 (roughly speaking). "rounds towards positive infinity" would be something different (0.1 would go to 1 and -1.1 would go to -1), but anyway.

I agree that if the function needs to handle negative numbers then it is messier.
crrev.com/c/1135550 changes all (well, almost all) of the double constants to float. However there are some functions with double inputs/outputs that I left alone which makes for some pathological cases. The obvious possibilities are:

1) Do nothing - don't land the change
2) Clean up the change to avoid mixing float/double and then land it
3) Clean up the exported functions to use float - this is my preference but I'm not sure how far down the rabbit hole the changes go

I like 3) because using double for pixel values is clearly excessive, but I worry about this expanding beyond what is justified.

There were some discussions about optimizing std::round but it uses tie-breaking rules that are incompatible with normal IEEE rounding, so that's tough. rint is more amenable to hardware acceleration but it is *incredibly* slow (worse than round) and you really need SSE 4.1 to make it fast, which does not yet have enough penetration (only ~81% of Chrome users) unless we do dynamic dispatch.

I think changing interfaces is preferable if we are reasonably confident the precision loss doesn't matter.
I'll take a look. If the numbers being processed are pixel values then floats are more than enough precision and any errors suggest undue sensitivity. If the numbers are non-pixel then I'd have to evaluate. Anyway, I'll see how it goes.

The one test failure I hit was when printing a float value - the ninth digit changed which upset the test, but did not otherwise matter. I resolved that.
Project Member

Comment 8 by bugdroid1@chromium.org, Jul 27

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c643d9b7761edb801545aeba54995679ce5a22ce

commit c643d9b7761edb801545aeba54995679ce5a22ce
Author: Bruce Dawson <brucedawson@chromium.org>
Date: Fri Jul 27 05:18:48 2018

Use float math in color_utils.cc

Switch from double to float in color_utils.cc. The HSL struct and
CalculateBoringScore still use double in their API because changing
those requires enough changes to justify being done in a different CL.

Note that SkColorToRgbaString intentionally uses a double precision
constant for 255 so that the calculation is done to double precision
so that spurious rounding in the result string is avoided.

Bug: 863135
Change-Id: Id5b678ed6e1c40475ec516bde2c902ba27bb783d
Reviewed-on: https://chromium-review.googlesource.com/1135550
Commit-Queue: Bruce Dawson <brucedawson@chromium.org>
Reviewed-by: Michael Wasserman <msw@chromium.org>
Reviewed-by: Mathieu Perreault <mathp@chromium.org>
Reviewed-by: Peter Kasting <pkasting@chromium.org>
Cr-Commit-Position: refs/heads/master@{#578543}
[modify] https://crrev.com/c643d9b7761edb801545aeba54995679ce5a22ce/chrome/browser/search/ntp_icon_source.cc
[modify] https://crrev.com/c643d9b7761edb801545aeba54995679ce5a22ce/chrome/browser/themes/theme_service.cc
[modify] https://crrev.com/c643d9b7761edb801545aeba54995679ce5a22ce/chrome/browser/themes/theme_service_unittest.cc
[modify] https://crrev.com/c643d9b7761edb801545aeba54995679ce5a22ce/chrome/browser/ui/views/payments/payment_request_views_util.cc
[modify] https://crrev.com/c643d9b7761edb801545aeba54995679ce5a22ce/ui/gfx/color_utils.cc
[modify] https://crrev.com/c643d9b7761edb801545aeba54995679ce5a22ce/ui/gfx/color_utils.h

Labels: Merge-Request-69
I'm going to merge the commit in comment 8 to the 69 branch, because it means we can avoid rewriting some other code that's been approved to land.  This is a pretty user-invisible low-level API change.
Project Member

Comment 10 by sheriffbot@chromium.org, Aug 14

Labels: -Merge-Request-69 Hotlist-Merge-Reject Merge-Reject-69
The bug is marked as P3 or Feature. It should not be merged as M69 is in beta. 
Please contact the approriate milestone owner if you have questions.
Owners: amineer@(Android), kariahda@(iOS), cindyb@(ChromeOS), govind@(Desktop)

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot
Labels: -Merge-Reject-69 Merge-Approved-69
Approving merge to M69 branch 3497 based on comment #9 and per offline chat with pkasting@.
Project Member

Comment 12 by bugdroid1@chromium.org, Aug 14

Labels: -merge-approved-69 merge-merged-3497
The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ee47257ddc6cce17ab25bad19e6746aebecd23f6

commit ee47257ddc6cce17ab25bad19e6746aebecd23f6
Author: Bruce Dawson <brucedawson@chromium.org>
Date: Tue Aug 14 00:28:07 2018

Use float math in color_utils.cc

Switch from double to float in color_utils.cc. The HSL struct and
CalculateBoringScore still use double in their API because changing
those requires enough changes to justify being done in a different CL.

Note that SkColorToRgbaString intentionally uses a double precision
constant for 255 so that the calculation is done to double precision
so that spurious rounding in the result string is avoided.

Bug: 863135
Change-Id: Id5b678ed6e1c40475ec516bde2c902ba27bb783d
Reviewed-on: https://chromium-review.googlesource.com/1135550
Commit-Queue: Bruce Dawson <brucedawson@chromium.org>
Reviewed-by: Michael Wasserman <msw@chromium.org>
Reviewed-by: Mathieu Perreault <mathp@chromium.org>
Reviewed-by: Peter Kasting <pkasting@chromium.org>
Cr-Original-Commit-Position: refs/heads/master@{#578543}(cherry picked from commit c643d9b7761edb801545aeba54995679ce5a22ce)
Reviewed-on: https://chromium-review.googlesource.com/1173574
Cr-Commit-Position: refs/branch-heads/3497@{#602}
Cr-Branched-From: 271eaf50594eb818c9295dc78d364aea18c82ea8-refs/heads/master@{#576753}
[modify] https://crrev.com/ee47257ddc6cce17ab25bad19e6746aebecd23f6/chrome/browser/search/ntp_icon_source.cc
[modify] https://crrev.com/ee47257ddc6cce17ab25bad19e6746aebecd23f6/chrome/browser/themes/theme_service.cc
[modify] https://crrev.com/ee47257ddc6cce17ab25bad19e6746aebecd23f6/chrome/browser/themes/theme_service_unittest.cc
[modify] https://crrev.com/ee47257ddc6cce17ab25bad19e6746aebecd23f6/chrome/browser/ui/views/payments/payment_request_views_util.cc
[modify] https://crrev.com/ee47257ddc6cce17ab25bad19e6746aebecd23f6/ui/gfx/color_utils.cc
[modify] https://crrev.com/ee47257ddc6cce17ab25bad19e6746aebecd23f6/ui/gfx/color_utils.h

Cc: ligim...@chromium.org
Labels: Hotlist-DesktopUIChecked
***UI Mass Triage***

If there is no pending work to be done here, please close the issue.
Labels: Hotlist-DesktopUIToolingRequired

Sign in to add a comment