572597 - Awesome-search is slow in Firefox Home

Status: VERIFIED FIXED

(Cloud Services Graveyard :: Firefox Home, defect)

Description

[Ed Lee :Mardak]

Sounds like the implementation for bug 567260 gives better results but is slower.

Sounds like the relevant changes are here:
http://hg.mozilla.org/services/fx-home/diff/2889a6755e88/User%20Interface/SearchResultsController.m#l1.196

The new code uses NSPredicate.evaluateWithObject for regular expression matching while the old code used NSString.rangeOfString for substring matches.

The high-level behavior of the new code is to find 20 results from history then 20 from bookmarks then 20 from tabs. The finding process within each data set will first check word boundary matching for the first bucket and if it doesn't match try for the substring bucket.

One idea is assuming that substring matching is fast, we can first check if all query tokens substring-match the title or url. If it does match, see if it should go into the boundary-match bucket or fallback-bucket. Basically this is predicating the expensive regex search with a simple first-pass substring.

The main difference from the old code is that we would still tokenize the input on spaces, but for single-word searches, it should be almost as fast as the old code. And according to Dan, it should almost feel like an order-of-magnitude difference.

This should be mostly some reordering of if statements and some logic changes. If this is fast enough, we won't need to do some more exotic custom character-processing logic.

As a reference, Firefox does this for boundary matching:
http://mxr.mozilla.org/mozilla-central/source/toolkit/components/places/src/SQLFunctions.cpp#118

It checks to see if the given 1-word token matches against tags then title then url and repeats for each additional token.

Dan has an idea for a one-pass-over-title/url idea where we walk over the title and match against all tokens at the same time. It's not quite one-pass as there'll need to be some backtracking if any of the tokens stop matching.

Comment 1

[Tony Chung [:tchung]]

this should be a blocker for home 1.0

Comment 2

[Ed Lee :Mardak]

http://hg.mozilla.org/services/fx-home/rev/51ce2e986d00
- dramatically improved search performance 

We went with the idea of predicating the regular expression matching with the must-faster substring matching. Only took a few minutes to try out and see huge improvements!

We also took out the artificial .5 second delay (made it almost 0) now that results are almost instantaneous even on 3G and iPod Touches.

Comment 3

[Tony Chung [:tchung]]

performance feels much better with searching.  marking verified on beta 13

Comment 4

[Tony Chung [:tchung]]

Moving FFHome-related bugs to new component -> Firefox Home