New issue
Advanced search Search tips

Issue 604848 link

Starred by 2 users
Status: Fixed
Owner: ----
Closed: Apr 2016
Cc:
sullivan@chromium.org
chrome-perf-bugs@google.com
Components:
EstimatedDays: ----
NextAction: ----
OS: Mac
Pri: 2
Type: Bug



Sign in to add a comment

Optimize URLPrefix::BestURLPrefix

Project Member Reported by a-...@yandex-team.ru, Apr 19 2016 
UserAgent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/49.0.2623.91 YaBrowser/16.4.0.6108 (beta) Safari/537.36

Steps to reproduce the problem:
URLPrefix::BestURLPrefix is function that is used in HistoryQuickProvider in history score calculation. It is called from ScoredHistoryMatch constructor for every HQP url candidate. 
Current implementation is not very effective and can take as much as 25% of HQP cpu time on average history as shown on screenshot from profiler. 
BestURLPrefix tries to match input url with several url prefixes and in the process of matching, it performs a lot of redundant lowercase conversions of input text and prefix.

What is the expected behavior?

What went wrong?
URLPrefix::BestURLPrefix is slower than it could be.

Did this work before? N/A 

Chrome version: 49.0.2623.91  Channel: n/a
OS Version: OS X 10.10.4
Flash Version: Shockwave Flash 21.0 r0

Comment 1 by a-...@yandex-team.ru, Apr 19 2016 

I tried to optimize BestURLPrefix and have lowered its cpu usage to ~7% of HQP. I think this change  can lower HQP Query time by 10-15%.
Please take a look at code, feel free to comment.
before_prefix_optimization.png
903 KB View Download
after_prefix_optimization.png
909 KB View Download

Comment 2 by csharrison@chromium.org, Apr 19 2016 

That looks great! Can you upload a patch with your optimization?

Comment 3 by erikc...@chromium.org, Apr 19 2016

Components: -UI UI>Browser>History
Labels: Performance
Status: Available (was: Unconfirmed)

Comment 4 by a-...@yandex-team.ru, Apr 20 2016 

Created change request https://codereview.chromium.org/1897403002.
Project Member

Comment 6 by bugdroid1@chromium.org, Apr 25 2016

Labels: merge-merged-2716
The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/921bb35bb2563ce87c583e3821db2192d2d7dc68

commit 921bb35bb2563ce87c583e3821db2192d2d7dc68
Author: a-v-y <a-v-y@yandex-team.ru>
Date: Sun Apr 24 08:15:23 2016

Optimize URLPrefix::BestURLPrefix

This is attempt to optimize URLPrefix::BestURLPrefix by reducing
number of redundant lowercase conversions. Also removed unused
URLPrefix::IsUrlPrefix function.

BUG= 604848 

R=pkasting@chromium.org, mpearson@chromium.org

Review URL: https://codereview.chromium.org/1897403002

Cr-Commit-Position: refs/heads/master@{#389401}

[modify] https://crrev.com/921bb35bb2563ce87c583e3821db2192d2d7dc68/components/components_tests.gyp
[modify] https://crrev.com/921bb35bb2563ce87c583e3821db2192d2d7dc68/components/omnibox/browser/BUILD.gn
[modify] https://crrev.com/921bb35bb2563ce87c583e3821db2192d2d7dc68/components/omnibox/browser/url_prefix.cc
[modify] https://crrev.com/921bb35bb2563ce87c583e3821db2192d2d7dc68/components/omnibox/browser/url_prefix.h
[add] https://crrev.com/921bb35bb2563ce87c583e3821db2192d2d7dc68/components/omnibox/browser/url_prefix_unittest.cc

Comment 7 by mpear...@chromium.org, Apr 28 2016

Components: UI>Browser>Omnibox
FYI, this change went out with canary 52.0.2716.0.  I can clearly see the improvement in the UMA graphs.  For example, the time it takes the omnibox to become responsive when the user types the first character in the omnibox (this is usually the slowest time of all, as it matches so much history) (histogram Omnibox.QueryTime2.1) has dropped about 30%.

Nice work!

Probably time to mark this bug as fixed (unless you have further improvement ideas).

Comment 8 by mpear...@chromium.org, Apr 28 2016 

For the record, Omnibox.ProviderTime2.HistoryQuick is down similarly (~20%) at the 95th percentile and Omnibox.CharTypedToRepaintLatency is down ~15% at the 95th percentile.  In other words, this small-scoped change moved all the metrics in a noticeable way.

Comment 9 by a-...@yandex-team.ru, Apr 29 2016 

I am glad that this changes are useful. 
You can close this bug. I will create another when I have new ideas.

BTW, I have created a sort of perftest to check impact of my changes. It is based on a HQP unittest and uses my History file to initialize HQP. After that I run different input queries on HQP several times. Do you think it is useful to add such test to chromium perftests? One that uses already filled History DB? 
Also I wanted to ask - do you use any perftests to measure providers performance? Or only data from histograms after changes are rolled out to canary?

Comment 10 by csharrison@chromium.org, Apr 29 2016

Cc: sullivan@chromium.org
Status: Fixed (was: Available)
Marking as fixed. Your perftest sounds like a good idea. I believe you can add new ones by adding to //tools/perf/benchmarks.

+sullivan@ in case I'm wrong, I've never added one before.

Comment 11 by sullivan@chromium.org, Apr 29 2016 

You can create unit-test-style perftests in the style of cc_perftests. Here's an example CL that adds some to the perf waterfall: https://codereview.chromium.org/962863002/

The big thing to remember is that every perf test needs an owner--someone we can cc on regressions and breakages if we can't figure out the problem.

Comment 12 by mpear...@chromium.org, Apr 29 2016 

>>>
Also I wanted to ask - do you use any perftests to measure providers performance? Or only data from histograms after changes are rolled out to canary?
>>>
I am not aware of any perftests that measure omnibox provider performance (or even omnibox performance in general).
►

Sign in to add a comment