Several changes to speed up the ShortcutsProvider:

Several changes to speed up the ShortcutsProvider:

(1) Bail immediately when BEST_MATCH is requested (as is the case for the AutocompleteClassifier) as the ShortcutsProvider does not currently allow matches to score highly enough to be "best".
(2) Check for input text that's a prefix of the shortcut in question, and mark the whole prefix as a match at once.  This reduces the number of cases where we have both lots of input words AND a long unclassified chunk of output string (the case where things are slow).
(3) Rewrite the general-case matching algorithm to be noticeably faster.  (Not sure of the complexity analysis but I think the worst case is more like O(n*n) than the previous O(m*n*n) and the average case should be much faster than that.  With the test profile and disabling the above two optimizations, typing a letter in my debug build resulted in a hang of about 2 seconds as opposed to several minutes.)

We could probably still do better; in particular, one optimization we could make for all the providers would be to provide them a conservative estimate of how many total characters would be visible in the omnibox dropdown and then have them trim the contents and description fields accordingly before matching.  However, a true conservative estimate -- which would assume that we had e.g. a string of 'i's -- would in the worst case still be several thousand characters wide, I don't want to do the plumbing work, and this optimization seems unnecessary at the moment anyway.

BUG=138242
TEST=none
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=148444

[mrossetti, 2012-07-25 22:18:36]

LGTM

Made a couple of suggestions.

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
File chrome/browser/autocomplete/shortcuts_provider.cc (right):

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
chrome/browser/autocomplete/shortcuts_provider.cc:190: WordMap
terms_map(CreateWordMapForString(term_string));
Perhaps immediately return if terms_map is empty.

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
chrome/browser/autocomplete/shortcuts_provider.cc:247: if (last_position <
text_lowercase.length()) {
You might comment on why this check is required.

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
chrome/browser/autocomplete/shortcuts_provider.cc:268:
find_words.equal_range(text_lowercase[last_position]));
Sweet!

[Peter Kasting, 2012-07-25 22:39:56]

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
File chrome/browser/autocomplete/shortcuts_provider.cc (right):

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
chrome/browser/autocomplete/shortcuts_provider.cc:190: WordMap
terms_map(CreateWordMapForString(term_string));
On 2012/07/25 22:18:36, mrossetti wrote:
> Perhaps immediately return if terms_map is empty.

Good catch, done.  I actually must do this lest I violate a DCHECK in
ClassifyAllMatchesInString().

https://chromiumcodereview.appspot.com/10831004/diff/4001/chrome/browser/auto...
chrome/browser/autocomplete/shortcuts_provider.cc:247: if (last_position <
text_lowercase.length()) {
On 2012/07/25 22:18:36, mrossetti wrote:
> You might comment on why this check is required.

OK.