478097 - Make location bar autocomplete faster

Status: RESOLVED FIXED

(Firefox :: Address Bar, defect, P3)

Description

[Shawn Wilsher :sdwilsh]

we can do better.  let's do it.

Comment 1

[Shawn Wilsher :sdwilsh]

Attachment: test harness

This is what I've been using as a test harness.  It creates a folder on your desktop when you run it, called perf-loc-ProfD, which is the profile folder for the test.  I've been basing this test on my places.sqlite, and picked out some results that I use frequently, and ones I do not use so frequently.  Additionally, there's a test for something that's a complete miss.

Posting this here so other folks can use it if they want.  Yes, it's crude, but it works.

Comment 2

[Shawn Wilsher :sdwilsh]

Attachment: test harness with test!

forgot to hg add the actual test - previous was just boilerplate.

Comment 3

[Shawn Wilsher :sdwilsh]

Attachment: v1.0

With this version, I'm seeing pretty much a 20±2% improvement across the board.  This is very very low risk too (no behavior change, just tickling the SQLite optimizer in the right way).

Comment 4

[Ed Lee :Mardak]

>+++ b/toolkit/components/places/src/nsNavHistoryAutoComplete.cpp
>+      "WHERE h.id NOT IN (SELECT id FROM moz_places_temp) "
What happens if we get rid of that? Any improvement/loss?

Functionality should be similar if not the same. Only difference would be if a moz_places page had a higher frecency than a moz_places_temp, but that seems unlikely from how we recalculate frecencies -- a newer visit would give it a higher value. Even then, it would be just a slight change in ordering.

Comment 5

[Shawn Wilsher :sdwilsh]

For what it is worth, I ran that and saw a negligible difference in speed (some faster, some slower, all very close (< 0.1%)).  I think it's probably best to keep it more accurate, even if it is a heuristic.

Comment 6

[Shawn Wilsher :sdwilsh]

Also - builds showing up here with this change:
https://build.mozilla.org/tryserver-builds/2009-02-11_14:[e-mail]-try-168754ca4f1/

Those experiencing slow location bars, it'd be nice to know if this helps.  Do note that this is built off of mozilla-central, not mozilla-1.9.1.  Shouldn't matter in terms of your places database, as there are very few changes between branch and m-c, but I wanted to note it.

Comment 7

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

i'm seeing a 15% improvement, investigating on other possible queries, but for now this looks like the best choice.

Comment 8

[Shawn Wilsher :sdwilsh]

For a point of reference, my 20±2% number was on an optimized build for OS X.

Comment 9

[Shawn Wilsher :sdwilsh]

Asking for blocking for pre-approval of this low-risk change.

Comment 10

[Mike Beltzner [:beltzner, not reading bugmail]]

We're not doing P3 blocking pre-approval anymore (drivers decided it was confusing, I was forced to agree) but find me or mconnor when the patch gets review and bake-time and we'll approve it pronto. Definitely wanted, and if we can get it for b3, bonus.

Comment 11

[Dietrich Ayala (:dietrich)]

Comment on attachment 361858 [details] [diff] [review]
v1.0

r=me, definitely worth trying and getting wider feedback on this. would be interested to see the results w/ the newer perf test harness you were working on yesterday.

Comment 12

[Shawn Wilsher :sdwilsh]

http://hg.mozilla.org/mozilla-central/rev/b32b31d8789a

Comment 13

[Shawn Wilsher :sdwilsh]

Comment on attachment 361858 [details] [diff] [review]
v1.0

This is low risk and a nice performance win, so requesting approval for 1.9.1

Comment 14

[Ed Lee :Mardak]

Attachment: performance script for error console

Here's a script to test the speed of the autocomplete from the error console. Just copy/paste in the whole thing and it'll report the min,avg,max times for a series of queries for both the first result as well as when it gets enough (12) results. (This might take minutes if you have a lot of history.)

For me, here are the results:

optimized query tryserver build:
Query: m First: 7,7,9 Finish: 7,7,9
Query: mo First: 7,7,8 Finish: 71,82,116
Query: moz First: 7,8,8 Finish: 83,93,116
Query: mozilla First: 7,7,8 Finish: 7,7,8
Query: mozilla bug First: 7,7,8 Finish: 110,113,118
Query: mozilla bugzilla First: 8,12,17 Finish: 8,12,17
Query: mozilla bugzilla f First: 8,16,22 Finish: 128,144,153
Query: mozilla bugzilla fa First: 8,20,24 Finish: 1063,1074,1087
Query: mozilla bugzilla fas First: 8,8,9 Finish: 29932,30481,31853

firefox 3.2 trunk:
Query: m First: 37,39,44 Finish: 37,39,44
Query: mo First: 9,12,16 Finish: 146,151,157
Query: moz First: 12,14,17 Finish: 149,151,153
Query: mozilla First: 8,13,17 Finish: 8,13,17
Query: mozilla bug First: 7,8,10 Finish: 246,248,251
Query: mozilla bugzilla First: 9,12,17 Finish: 9,12,17
Query: mozilla bugzilla f First: 8,8,9 Finish: 108,139,261
Query: mozilla bugzilla fa First: 7,8,11 Finish: 7,212,1032
Query: mozilla bugzilla fas First: 7,8,9 Finish: 7,10927,54605


firefox 3:
Query: m First: 10,13,26 Finish: 10,13,26
Query: mo First: 11,12,17 Finish: 113,118,133
Query: moz First: 10,11,14 Finish: 114,117,126
Query: mozilla First: 10,11,11 Finish: 10,11,11
Query: mozilla bug First: 10,10,11 Finish: 110,111,116
Query: mozilla bugzilla First: 10,10,11 Finish: 10,10,11
Query: mozilla bugzilla f First: 10,11,11 Finish: 119,121,125
Query: mozilla bugzilla fa First: 10,11,11 Finish: 915,935,955
Query: mozilla bugzilla fas First: 12,13,15 Finish: 13169,13221,13383

firefox 3.1 latest nightly:
Query: m First: 36,41,57 Finish: 36,41,57
Query: mo First: 8,8,8 Finish: 76,100,136
Query: moz First: 7,8,8 Finish: 96,114,140
Query: mozilla First: 7,8,8 Finish: 7,8,8
Query: mozilla bug First: 8,8,9 Finish: 86,192,249
Query: mozilla bugzilla First: 7,8,9 Finish: 7,8,9
Query: mozilla bugzilla f First: 7,8,9 Finish: 103,386,1074
Query: mozilla bugzilla fa First: 7,10,13 Finish: 9,1098,2203
Query: mozilla bugzilla fas First: 8,10,13 Finish: 9,46789,59689

I'm not sure what's going on with the results for the last query "mozilla bugzilla fas", for trunk and the 3.1 nightly. I know it's searching through all my history before stopping, but some reason trunk response with NO_MATCH and quits early in some cases, so probably just look at the MAX number instead of min/avg.

Huge speed regression from ff3 to 3.1 to search through all the history...

But a good improvement with this optimized query overall.

Comment 15

[Shawn Wilsher :sdwilsh]

Comment 14 is a good reason why we should take this for 3.1

Comment 16

[Ed Lee :Mardak]

(In reply to comment #14)
> optimized query tryserver build:
> Query: mozilla bugzilla fa First: 8,20,24 Finish: 1063,1074,1087
> Query: mozilla bugzilla fas First: 8,8,9 Finish: 29932,30481,31853
> 
> firefox 3:
> Query: mozilla bugzilla fa First: 10,11,11 Finish: 915,935,955
> Query: mozilla bugzilla fas First: 12,13,15 Finish: 13169,13221,13383
We do pretty good everywhere else compared to FF3 with this patch, and I know it's not this patch's regression when querying the whole database. But any idea what would cause searching through the whole history would be so much worse now?

Temp tables? Union? At least for my tests, I just started the profile, so there should be only a few temp table entries. Perhaps related to how we now LIMIT offset + chunkSize instead of just LIMIT chunkSize for the moz_places table... ?

I suppose another reason for getting rid of chunking with async? ;) Too bad I can't run the tests with my places.sqlite to see if it improves.

Comment 17

[Shawn Wilsher :sdwilsh]

SQLite's EXPLAIN would tell you why, mostly.  IIRC, it's because of the UNION with so many tables, even if they are empty.

Comment 18

[Ed Lee :Mardak]

Do you think it would be worth it to separate the all history query to have one for temp table and another for moz_places? A very crude estimate would be to always put temp table results before moz_places assuming we sync often enough. Temp should only have things updated/added since last sync, yeah?

This way we can just fetch all pages from temp and do moz_places LIMIT OFFSET like we did for FF3.

I suppose more complicated would be to fetch all results from the temp table and store them locally in nsNavHistory memory and figure out where we need to insert temp results (by frecency) relative to moz_places results.

Comment 19

[Shawn Wilsher :sdwilsh]

(In reply to comment #18)
We discussed this at length when we incorporated the temporary tables.  I don't recall all of the reasoning at this point, but this turned out to be the best solution.

With that said, we could probably remove "WHERE h.id NOT IN (SELECT id FROM moz_places_temp)" from the second query since we already check for duplicates anyway.  I imagine that will let sqlite get us results faster, but it'd need testing (and should go into a new bug).

Comment 20

[Ed Lee :Mardak]

I was looking into the behavior of the "WHERE h.id NOT IN (SELECT id FROM
moz_places_temp)" and noticed the opcodes being generated...

182|NotExists|26|185|13 // if reg13 doesn't exist in table26, goto 185
183|Integer|1|13        // reg13 = 1
184|Goto|0|186          // goto 186
185|Integer|0|13        // reg13 = 0
186|If|13|319           // if reg13 != 0, goto 319 (skip because it exists)
187|...                 // process row because it exists

I wonder why the opcodes emitted aren't just..

182|NotExist|26|184|13 // if reg13 doesn't exist in table26, goto 184
183|Goto|0|319         // skip because it exists
184|...                // process row because it didn't exist

No need to branch to a branch. Hopefully the sqlite engine optimizes that away anyway...

But in terms of performance gain, there isn't much (at least when there aren't any entries in moz_places_temp). But going down this path can lead to future improvements..

First results are for getting rid of the h.id NOT IN ...

build skip.exists:
Query: m First: 7,7,8 Finish: 7,7,8
Query: mo First: 7,7,8 Finish: 104,109,114
Query: moz First: 7,8,8 Finish: 102,110,115
Query: mozilla First: 7,7,8 Finish: 7,7,8
Query: mozilla bug First: 7,8,8 Finish: 102,110,114
Query: mozilla bugzilla First: 7,8,9 Finish: 7,8,9
Query: mozilla bugzilla f First: 7,8,10 Finish: 116,120,124
Query: mozilla bugzilla fa First: 7,7,8 Finish: 1036,1052,1083
Query: mozilla bugzilla fas First: 8,9,11 Finish: 32246,32414,32484

build trunk:
Query: m First: 7,8,10 Finish: 7,8,10
Query: mo First: 7,7,8 Finish: 100,105,110
Query: moz First: 7,7,8 Finish: 101,108,114
Query: mozilla First: 7,7,8 Finish: 7,7,8
Query: mozilla bug First: 7,8,8 Finish: 101,108,113
Query: mozilla bugzilla First: 7,7,8 Finish: 7,7,8
Query: mozilla bugzilla f First: 7,8,10 Finish: 113,119,125
Query: mozilla bugzilla fa First: 7,8,9 Finish: 1057,1084,1169
Query: mozilla bugzilla fas First: 8,10,11 Finish: 32017,32964,33228

In actual usage where you're visiting pages and stuff, there's potential for better gains.

Comment 21

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 361858 [details] [diff] [review]
v1.0

a191=beltzner

Comment 22

[Shawn Wilsher :sdwilsh]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/ccc79bb5762e

Comment 23

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

i can confirm this made my locationbar far less laggish then on previous builds with Shiretoko.