Cache autocomplete queries to make awesomebar open faster

VERIFIED FIXED

Status

defect
VERIFIED FIXED
10 years ago
9 years ago

People

(Reporter: mfinkle, Assigned: mfinkle)

Tracking

Trunk
x86
Linux
Bug Flags:
in-litmus -

Firefox Tracking Flags

(fennec1.0+)

Details

Attachments

(2 attachments, 4 obsolete attachments)

Posted patch patch (obsolete) — Splinter Review
When the awesomebar is opened, it executes a "" query to fill the list with recent visits/bookmarks. This query uses the places backend (including some SQLite queries) and can be slow.

We could cache queries in JSON instead of always hitting the backend. The result is a faster awesomebar.

This patch adds a caching replacement for the autocomplete service, which fallsback to the standard autocomplete service when needed. The patch will create an "autocomplete.json" cache file in the profile during a -silent launch and it will update the cache file as needed during the lifetime of the application - currently every 10 seconds as long as the autocomplete service is not busy at the time.

The patch provides a noticeable speedup on N900. I'll test on N810 as well. This might have a bigger impact on Windows Mobile.

The patch will only save the default query ("") to the cache file for now, but it will attempt to cache in memory all queries attempted by the user. We might want to change that.

More testing before a real review. Drive bys welcome. Thanks to Mardark for getting me started with code from his GoFaster add-on.
The improvement on the N810 is even better. My rough estimate shows nearly 1 second speedup on the first open of the awesomebar.

On both devices, I noticed that the text and favicons displayed in the awesomebar display faster with the patch - for any open of the awesomebar, not just the first.
Attachment #418845 - Flags: review?(gavin.sharp)
Attachment #418845 - Flags: review?(edilee)

Updated

10 years ago
tracking-fennec: --- → 1.0+

Comment 2

10 years ago
Mark:  Why are you using an array for the cache?

Comment 3

10 years ago
That was part of my original code to implement a MRU so that only a certain number of entries would be stored in the cache. So theoretically it would be capped and scanning a (small?) set of cache items for lookup isn't too bad. But we can do a plain hash for simpler lookup or a combination if we want both aspects.
Comment on attachment 418845 [details] [diff] [review]
patch

>diff --git a/components/AutoCompleteCache.js b/components/AutoCompleteCache.js

>+ * The Original Code is XPI Dialog Service.

huh? :)

>+// Lazily get the base Places AutoComplete Search
>+__defineGetter__("PACS", function() {

Could use XPCOMUtils.defineLazyGetter

>+// Gets a directory from the directory service
>+let _dirSvc = null;

for this too

>+var AutoCompleteUtils = {

>+  lookup: function lookup(query, newEntry) {
>+    // Remove any existing cached result
>+    let found;
>+    for (let pos = AutoCompleteUtils.cache.length; --pos >= 0; ) {
>+      if (AutoCompleteUtils.cache[pos].searchString == query) {
>+        found = AutoCompleteUtils.cache.splice(pos, 1)[0];
>+        break;
>+      }
>+    }
>+  
>+    // Re-append the existing entry or add the new one to the end
>+    let entry = newEntry || found;
>+    if (entry != null)
>+      AutoCompleteUtils.cache.push(entry);
>+  
>+    // Give the entry from cache or the newly added one
>+    return entry;

Seems to me like this would make more sense as:

let found = -1;
for (let pos = AutoCompleteUtils.cache.length; --pos >= 0; ) {
  if (AutoCompleteUtils.cache[pos].searchString == query) {
    found = pos;
    break;
  }
}

let entry = newEntry || AutoCompleteUtils.cache[found];

if (entry)
  AutoCompleteUtils.cache[found] = entry;

return entry;

Doesn't maintain the "keep newest lookup at the end" behavior, but that shouldn't matter too much compared to "always splice()/push() on lookup", especially if we limit the size of the cache... shouldn't we limit the size of the cache?

>+  // Use the base places search to get results
>+  fetch: function fetch(query, onResult) {
>+    // We're requested to start something new so stop any active queries
>+    AutoCompleteUtils.stop();

why not use "this"? (applies pretty much throughout the file)

>+  // Handle finished queries that might have completed a prefetch
>+  finish: function finish(query) {
>+    // Remove the prefetched value or a query that happened to be prefetched
>+    // except for the last entry because it was added to re-fetch fresh results
>+    let pos = AutoCompleteUtils.queries.indexOf(query);
>+    if (pos == 0 || pos != -1 && pos != AutoCompleteUtils.queries.length - 1)
>+      AutoCompleteUtils.queries.splice(pos, 1);

I don't understand this comment, or what this code is trying to do. Why is the last query special?

The prefetch logic in general confuses me - this patch triggers prefetches from startSearch if there's a cache hit, from finish(), and from stopSearch(), and I don't understand the logic behind any of those.

>diff --git a/components/BrowserCLH.js b/components/BrowserCLH.js

>+      let autoComplete = Components.classesByID["{a65f9dca-62ab-4b36-a870-972927c78b56}"].
>+                         getService(Ci.nsIAutoCompleteSearch);

Why is this using classesById?

Comment 5

10 years ago
(In reply to comment #4)
> Doesn't maintain the "keep newest lookup at the end" behavior
If we're caching and only want to speed up "", we could just only save the result of "" and always ask the base implementation for everything else. If we want to speed up other stuff but still only cache "", might as well use a dictionary for the cache. This simplifies looking for the "" entry to save too.

> >+  // Handle finished queries that might have completed a prefetch
> >+  finish: function finish(query) {
> >+    // Remove the prefetched value or a query that happened to be prefetched
> >+    // except for the last entry because it was added to re-fetch fresh results
> >+    let pos = AutoCompleteUtils.queries.indexOf(query);
> >+    if (pos == 0 || pos != -1 && pos != AutoCompleteUtils.queries.length - 1)
> >+      AutoCompleteUtils.queries.splice(pos, 1);
> I don't understand this comment, or what this code is trying to do. Why is the
> last query special?
This is cleaning up the prefetch array if the user happens to type something that we were going to prefetch but didn't have cached. It doesn't remove the last entry unless it happens to be the first entry because the newest prefetch entry gets added whenever the user types something -- this is actually a refetch to update the cache.

> The prefetch logic in general confuses me - this patch triggers prefetches from
> startSearch if there's a cache hit, from finish(), and from stopSearch(), and I
> don't understand the logic behind any of those.
cache hit: user has a result, so continuously update potentially stale cache
finish: same as above except it was a cache miss
stopSearch: user isn't searching anymore, so warm up the cache

The "prefetch" was actually more of a prefetch in my original code where I would prefetch all single letter queries. I guess it doesn't make as much sense in this context as all prefetches are now refetches.


I haven't gotten to limiting the size of the cache for my goFaster extension, but that would just check the size of the cache array and lop off the less used entries. If we do switch to a dictionary, it could keep track of how many items are in there and remove things randomly. Or again, if it's just caching "", no need to worry about cache size.
Posted patch patch 2 (obsolete) — Splinter Review
Updated for many of the review comments, but not all:
* added lazy getters
* changed to use "this" as much as I could
* stopped using classesById
* we don't need this service to load at app-startup
* stop adding queries to the prefetcher. we only deal with the empty query now

I need to work through the other changes to lookup to make sure things still work correctly.
Assignee: nobody → mark.finkle
Attachment #418845 - Attachment is obsolete: true
Attachment #418845 - Flags: review?(gavin.sharp)
Attachment #418845 - Flags: review?(edilee)
Posted patch patch 3 (obsolete) — Splinter Review
Builds on last patch. Removes ability to cache multiple queries. This patch only caches the default, empty query.
Attachment #421132 - Attachment is obsolete: true
Attachment #421197 - Flags: review?(gavin.sharp)
Attachment #421197 - Flags: review?(edilee)
Posted patch patch 4 (obsolete) — Splinter Review
This patch inlines some of the methods and renames "prefetch" to "update"
Attachment #421197 - Attachment is obsolete: true
Attachment #421311 - Flags: review?(gavin.sharp)
Attachment #421197 - Flags: review?(gavin.sharp)
Attachment #421197 - Flags: review?(edilee)

Comment 9

10 years ago
Comment on attachment 421311 [details] [diff] [review]
patch 4

>+++ b/components/AutoCompleteCache.js
>+var AutoCompleteUtils = {
>+  cache: null,
>+  query: "",
Should this whole file just special and constant propagate "" to AutoCompleteUtils.query?

>+  fetch: function fetch(query, onResult) {
>+    PACS.startSearch(query, "", null, {
>+      onSearchResult: function(search, result) {
..
>+        if (AutoCompleteUtils.isOngoing(result))
..
>+        AutoCompleteUtils.finish(query);
These could also be inlined now as well.

>+  startSearch: function(query, param, prev, listener) {
>+    // Keep the cache warm
>+    AutoCompleteUtils.update();
>+  stopSearch: function() {
>+    // Stop any active queries but fetch in the background to keep the cache warm
>+    AutoCompleteUtils.update();
Not sure how actively this needs to be done anymore. Now that we only cache "", it's probably overkill to refetch "" on every start/stop search. Also note that the original code only p/re-fetched if there was something needing to be updated whereas the new code will unconditionally refetch "".

>+++ b/components/BrowserCLH.js
>@@ -54,16 +54,18 @@ BrowserCLH.prototype = {
>+      let autoComplete = Cc["@mozilla.org/autocomplete/search;1?name=history"].
>+                         getService(Ci.nsIAutoCompleteSearch);
Curious, how does this know when to quit the browser? AutoComplete is async, so this chould return before the "" query is cached ?
(In reply to comment #9)
> (From update of attachment 421311 [details] [diff] [review])

> >+  query: "",
> Should this whole file just special and constant propagate "" to
> AutoCompleteUtils.query?

I can't parse that sentence

> >+        if (AutoCompleteUtils.isOngoing(result))
> ..
> >+        AutoCompleteUtils.finish(query);
> These could also be inlined now as well.

OK - I can do that

> >+  startSearch: function(query, param, prev, listener) {
> >+    // Keep the cache warm
> >+    AutoCompleteUtils.update();
> >+  stopSearch: function() {
> >+    // Stop any active queries but fetch in the background to keep the cache warm
> >+    AutoCompleteUtils.update();
> Not sure how actively this needs to be done anymore. Now that we only cache "",
> it's probably overkill to refetch "" on every start/stop search. Also note that
> the original code only p/re-fetched if there was something needing to be
> updated whereas the new code will unconditionally refetch "".

stopSearch doesn't seem to get fired much at all. I can remove the update call from there.

> >+++ b/components/BrowserCLH.js
> >@@ -54,16 +54,18 @@ BrowserCLH.prototype = {
> >+      let autoComplete = Cc["@mozilla.org/autocomplete/search;1?name=history"].
> >+                         getService(Ci.nsIAutoCompleteSearch);
> Curious, how does this know when to quit the browser? AutoComplete is async, so
> this chould return before the "" query is cached ?

Not sure really, but on Linux desktop and N900 the autocomplete.json and search.json (also created in the CLH) are both created during a -silent run.

Comment 11

10 years ago
(In reply to comment #10)
> (In reply to comment #9)
> > >+  query: "",
> > Should this whole file just special and constant propagate "" to
> > AutoCompleteUtils.query?
> I can't parse that sentence
Er. Missed a word :p special case AutoCompleteUtils.query and replace all instances with "" -- essentially doing a constant propagation.
(In reply to comment #11)
> (In reply to comment #10)
> > (In reply to comment #9)
> > > >+  query: "",
> > > Should this whole file just special and constant propagate "" to
> > > AutoCompleteUtils.query?
> > I can't parse that sentence
> Er. Missed a word :p special case AutoCompleteUtils.query and replace all
> instances with "" -- essentially doing a constant propagation.

I like having a variable and not just an empty string. I could make it an ALL CAPS variable.
Posted patch patch 5Splinter Review
Inlined two more functions (isOngoing and finish)
Attachment #421311 - Attachment is obsolete: true
Attachment #421434 - Flags: review?(gavin.sharp)
Attachment #421311 - Flags: review?(gavin.sharp)
I need to file a followup bug to add a bookmark listener to the code, so we can update when bookmarks are added or removed.

Filed bug 539450
Comment on attachment 421434 [details] [diff] [review]
patch 5

>diff --git a/components/AutoCompleteCache.js b/components/AutoCompleteCache.js

>+var AutoCompleteUtils = {

>+  // Handle finished queries that might have completed a re-fetch
>+  finish: function finish(query) {
>+  },

Get rid of this?

>+  init: function init() {

>+      // Make the empty query cache
>+      this.fetch("");

Might as well use AutoCompleteUtils.query here.

>+AutoCompleteCache.prototype = {

>+  startSearch: function(query, param, prev, listener) {

>+    // Strip out leading/trailing spaces and make multiple spaces one
>+    query = query.trim().replace(/\s+/g, " ");

query.trim() should be sufficient, since we currently only care to turn \s+ into "".

>+    let entry = null;
>+    if (AutoCompleteUtils.query == query)
>+      entry = AutoCompleteUtils.cache;
>+
>+    if (entry) {
>+      // On a cache-hit, give the results right away and fetch in the background
>+      done(entry);
>+    } else {
>+      // Otherwise, fetch the result, cache it, and pass it on
>+      AutoCompleteUtils.fetch(query, done);
>+    }

if (AutoCompleteUtils.query == query)
  done(AutoCompleteUtils.cache);
else
  AutoCompleteUtils.fetch(query, done);
Attachment #421434 - Flags: review?(gavin.sharp) → review+

Comment 16

10 years ago
(In reply to comment #15)
> query.trim() should be sufficient, since we currently only care to turn \s+
> into "".
Nod. This was originally for multi-word searches and pruned multiple spaces between words. Not so useful if we only care about "".

> >+    if (AutoCompleteUtils.query == query)
> >+      entry = AutoCompleteUtils.cache;
> >+    if (entry) {
> if (AutoCompleteUtils.query == query)
>   done(AutoCompleteUtils.cache);
Do we still need to check for non-nullness of the cache? Or assuming it got warmed up from the silent run, there should always be something cached.
adds gavin comments
adds a simple version to the cache file
pushed to default:
http://hg.mozilla.org/mobile-browser/rev/7401aae75f58
Status: NEW → RESOLVED
Last Resolved: 10 years ago
Resolution: --- → FIXED
verified FIXED on builds:

Mozilla/5.0 (X11; U; Linux armv7l; Nokia N900; en-US; rv:1.9.2pre) Gecko/20100114 Firefox/3.6pre Fennec/1.1a1pre

and

Mozilla/5.0 (X11; U; Linux armv6l; Nokia N8xx; en-US; rv:1.9.3a1pre) Gecko/20100114 Firefox/3.7a1pre Fennec/1.1a1pre
Status: RESOLVED → VERIFIED
Flags: in-litmus?
Flags: in-litmus? → in-litmus-
You need to log in before you can comment on or make changes to this bug.