Closed Bug 414229 Opened 17 years ago Closed 17 years ago

Typing in location bar is extremely laggy since global frecency

Categories

(Firefox :: Address Bar, defect, P1)

Product:
Firefox
Component:
Address Bar
Type:
defect

Tracking

()

Status:
VERIFIED FIXED
Milestone:
Firefox 3 beta3

People

(Reporter: mossop, Assigned: Mardak)

References

Details

(Keywords: dogfood, perf, regression)

Attachments

(2 files)

sample patch
1.40 KB, patch
Details | Diff | Splinter Review
v1
4.65 KB, patch
Details | Diff | Splinter Review 
Since a short time ago (global frecency potentially) typing in the location bar has become extremely laggy, taking something like half a second for each character to appear. This is extremely irritating and I believe should block b3
Flags: blocking-firefox3?
Mardak had me check the database for how many entries had had the frecency calculated. It was 169 out of 21483
One possibility is that we're searching for wayyy too many results that we aren't even going to display. This is made worse by having a lot of results with frecency -1. When there's at least a few results with frecency > 0, the first chunk should be faster than the latter ones because of the frecency index.
Attached patch sample patch — — Splinter Review 
Mossop has tried a custom build that contains a patch to limit the results to just 25 pages. "That build is quite a lot better, still some laggyness but not too bad"

https://build.mozilla.org/tryserver-builds/2008-01-26_16:26-edward.lee@engineering.uiuc.edu-fast.adap.book.matc/
edward, thanks for jumping on this.

note, your patch actually changes a few nobs at once (chunk size, timeout, and stopping early.)

a whole bunch of suggestions / comments:

1)  let's make all three knobs prefs so that we can tune things.  as mentioned in other bug comments, 100 for the chunk size was a first guess.

2)  stopping early.  as both dietrich and edward are aware, we used to search the previous results.  we no longer do this, see recent checkin from edward (who did not disable this, but cleaned up the code around dietrich fix to disable it.)

when we were searching previously results, we did not stop early by design.  what was supposed to happen was we'd search and get through x of y total chunks.  then use would type some more, and we'd re-scan our previous results (for x chunks) and then resume chunking until we hit all of them.  if they continued to type, and we were done chunking, we'd rescan all the results and not do any sqlite queries.

now, we are not searching previous results, so we should do EXACTLY what edward has done, except limit by the following pref:  http://lxr.mozilla.org/seamonkey/search?string=browser.urlbar.maxRichResults.  This pref limits how many results we show in the UI, so we can stop searching when we hit that value.

nice work edward!  Please consider a separate spin off patch on this, and I'll quickly r= it.

stopping early might explain mossops problem, and has extra benefits:  for simple searches (h, ht, htt, http, you get the point) we want to stop early so that we do less work on each key stroke.

but, for non-simple matches (zorp) with no matches, we are going to have to search every chunk, right?  And that will not be helped by edward's patch because we will not be stopping early.  

here, we want to tune the chunk size (and possibly the timeout, but I feel 100ms is correct, based on the pre-frecency approach, which also used 100ms).

edward, can you make a second patch to make the chunk size a pref, and let mossop tune it and report back?

another thought:  mossop wrote "169 out of 21483" places had frecency.  say mossop types "zorp" and it is not found within the first chunk.  the second chunk will be 69 with frecency + 31 with -1 frecency, and the third (and beyond) chunks will all be frecency -1.

we should double check that the query (see mDBAutoCompleteQuery) performs well when all the places have -1 frecency.  I think it should, because we do:

...ORDER BY h.frecency DESC LIMIT ?2 OFFSET ?3

frecency is indexed, so I think sqlite will use the rowid as the secondary sort (which is fine.)  note, there is a bug about using visit_count and typed as the secondary and tertiary sorts.

a few more things:

1) we should double check that AutoCompleteTagsSearch() isn't killing us.
2) we used to only recalculate mLivemarkFeedItemIds and mLivemarkFeedURIs only when we could not reuse our current search.  but now, we are doing it on every keystroke.  we use those for determining if we show the star or not.  I suggest the following:

even if we can or can't re-use the search result, but we can re-use mLivemarkFeedItemIds and mLivemarkFeedURIs.  let's do something similar to nsNavHistory::GetNow(), and not invalidate those hashes unless it has been 3 seconds.  while I'm typing key strokes in the url bar, the values in those hashes are not going to change right?  

note, my gut tells me that this isn't really hurting us, so before we do this work we should measure how long it is taking us to recalculate those hash tables.

summary:

a) stopping early is good, especially for the initial key strokes for common searches!
b) 100 may be too big, especially when the term is not found, but not sure yet.
I'm tempted to suggest using browser.urlbar.maxRichResults, which would be great for h, ht, htt, http, but the smaller the value we use for chunk size, the more chunks it might take to get our 25.  tough decision!
c) spin off bug about keepin mLivemarkFeedItemIds and mLivemarkFeedURIs around so we don't re do it on every key stroke.

hope this massive rambling helps!  feel free to ping me for reviews.
> feel free to ping me for reviews.

or dietrich, who knows this mumbo jumbo as well, if not better, than me.
I'd question whether we really need to do anything for every single character typed. Can we not do a scheme where we wait till the user has paused before trying to do any searching, or does that have issues I'm unaware of?
(In reply to comment #4)
> now, we are not searching previous results, so we should do EXACTLY what edward
> has done, except limit by the following pref: 
> http://lxr.mozilla.org/seamonkey/search?string=browser.urlbar.maxRichResults. 
> This pref limits how many results we show in the UI, so we can stop searching
> when we hit that value.
How about people not using the rich results? (Actually.. I remember something about the pref going away, but it's still possible to get that display through the code?)
Attached patch v1 — — Splinter Review 
I haven't tested (or compiled.. build got cleared :() yet, but it seems reasonable. I'll give an update when it finishes building.
Assignee: nobody → edilee
Status: NEW → ASSIGNED
Attachment #299609 - Flags: review?(seth)
Blocks: 414252
> I'd question whether we really need to do anything for every single character
> typed. Can we not do a scheme where we wait till the user has paused before
> trying to do any searching, or does that have issues I'm unaware of?

when I wrote "every character" it was worst case scenario for a slow typist.  

doesn't the xul texbox for the url bar already have a timeout?  (I think the search box does, of 250 ms).  

the url bar should have one too, but we should double check!


see also bug #414252
> How about people not using the rich results? (Actually.. I remember something
> about the pref going away, but it's still possible to get that display through
> the code?)

I'm not really worrying about them.

There is no pref, but there is an add on (see https://addons.mozilla.org/en-US/firefox/addon/6227)

But, maybe I should worry.

we do use the non-rich one in the pref ui (autocomplete your home page pref) and the open location dialog (if the url bar is hidden).  there is a bug about switching to the rich results for these two uses, but I doubt we will see it for fx 3.


(In reply to comment #9)
> > I'd question whether we really need to do anything for every single character
> > typed. Can we not do a scheme where we wait till the user has paused before
> > trying to do any searching, or does that have issues I'm unaware of?
> when I wrote "every character" it was worst case scenario for a slow typist.  
If we do delay, the autocomplete results won't show up right away and less find-as-you-type. But I agree that there should be /some/ delay bigger than 0 so that it's not every character even if you're typing quickly.

The delay should probably change on how much is typed in. For really long inputs, it should probably wait longer.
(In reply to comment #9)
> doesn't the xul texbox for the url bar already have a timeout?  (I think the
> search box does, of 250 ms).  

There is no timeout in the xul, so unless it is in the autocomplete backend itself it's not there.
(In reply to comment #9)
> doesn't the xul texbox for the url bar already have a timeout?  (I think the
> search box does, of 250 ms).  
http://mxr.mozilla.org/seamonkey/source/browser/components/search/content/search.xml#75

that?
Hey neat. I opened up the dom inspector and added the timeout property to the #urlbar textbox node and it magically doesn't search until the timeout. ;)
Depends on: 414254
Depends on: 414257
Comment on attachment 299609 [details] [diff] [review]
v1

Patch moved to bug 414257
Attachment #299609 - Flags: review?(seth)
This affects all platforms, so OS -> All
OS: Mac OS X → All
Hardware: PC → All
(In reply to comment #18)
> Bug 413457 and bug 413497 could be duplicates.

I don't think so. Although the new two line autocomplete has never been as fast as the old one, the extreme lag discussed here started when the fix for bug 394038 (global frecency) was checked in on 2008-01-23, which was clearly after those two bugs were reported.
Keywords: dogfood, perf
Wouldn't the optimal behavior to be a very shallow search with every character, followed by a deeper search if you pause?

At the same time that I noticed the location bar becoming extremely laggy, I noticed many results which seemed to just be rather long resource URLs... (many, many google ad results, for instance.)  I'm unsure if searching such long URLs has any performance impact or not, but thought it might be worth mentioning.

(An example ad URL: http://pagead2.googlesyndication.com/pagead/ads?client=ca-pub-2357921960626041&dt=1201395466029&lmt=1201395465&alt_color=FFFFFF&format=468x15_0ads_al_s&output=html&correlator=1201395466027&channel=4610558790&url=http%3A%2F%2Fkol.coldfront.net%2Fthekolwiki%2Findex.php%3Ftitle%3DSpecial%3ASearch%26search%3Ddamage%2Babsorbtion&color_bg=FFFFFF&color_text=000000&color_link=0066CC&color_url=000000&color_border=FFFFFF&cc=100&ga_vid=1001149083.1201395466&ga_sid=1201395466&ga_hid=1099721289&flash=9&u_h=1024&u_w=1280&u_ah=999&u_aw=1280&u_cd=24&u_tz=-300&u_his=1&u_java=true&u_nplug=13&u_nmime=53)
regarding comment #20, it could be that embedded visits are making it into location bar results somehow.
Yes, something like that. I'm not sure how exactly this was handled before, but in a current build I often see URLs of individual frames in the autocomplete list, which were not present there before (IIRC).
(In reply to comment #20)
> (An example ad URL: ...
Tim: Do you have some way to query the sqlite db?
http://wiki.mozilla.org/Storage-Explorer
(Tools -> mozStorage Explorer -> select places.sqlite)

Do this query:
SELECT url, frecency, visit_type FROM moz_places h JOIN moz_historyvisits v ON v.place_id = h.id WHERE url LIKE '%googlesyndication%' AND frecency != 0 LIMIT 10

Are there any results?
Priority: -- → P1
Target Milestone: --- → Firefox 3 M11
Bug 414257 landed for 2008-01-28 builds, so comments about if it helped perf would be useful.
Depends on: 414426
(In reply to comment #24)
> Bug 414257 landed for 2008-01-28 builds, so comments about if it helped perf
> would be useful.

Performance has noticeably improved for me in todays nightly build. It still doesn't feel as fast as it was before, but it is close, at least for the common case that matching results are found.

But when no results are found, typing is still very laggy. I can see this for example when entering something like "ddddddddddddddddddddddddddddddddddd" (by typing, not copy/paste) into the location bar. Deleting this via backspace is equally slow as well.
(In reply to comment #24)
> Bug 414257 landed for 2008-01-28 builds, so comments about if it helped perf
> would be useful.

Performance has improved in some cases, but I suspect this is due to me having more frecencys calculated, I'm now up to nearly 600. Some searches the location bar is still very laggy, a case in point was searching for "laggy" trying to find this bug, so there are search results.
> But when no results are found, typing is still very laggy. I can see this for
> example when entering something like "ddddddddddddddddddddddddddddddddddd" (by
> typing, not copy/paste) into the location bar. Deleting this via backspace is
> equally slow as well.

Thanks for re-raising this issue.

I believe edward has a patch (or at least we discussed one?) that also limits the chunk size.  

currently (according to lxr), we have a chunk size of 100.

181 // number of places to search per chunk
182 // too big, and the UI will be unresponsive
183 // as we will be off searching the database.
184 // too small, and because of AUTOCOMPLETE_SEARCH_TIMEOUT
185 // results won't come back in fast enough to feel snappy.
186 #define AUTOCOMPLETE_SEARCH_CHUNK_SIZE 100

The autocomplete code has a timer that fires (every 100ms).  so with a small chunk size, each search should (I think) happen quickly enough that we don't lag the ui.

A smaller chunk size should help with this problem.  

together, with edward's change to add a 150 ms timeout to the url bar, should solve this problem.

edward, do we have a bug about making chunk size pref tunable?  if so, we should fix this and elmar to try again with a chunk size of 25 and his "dddd...dd" example.
Depends on: 414489
> do we have a bug about making chunk size pref tunable?

it looks like edward just logged one, see bug #414489
Here's a build that has chunk size of 5 for chunks meaning "how many results to display each update". Seth wants to change chunks back to meaning "how many pages to check each update" in which case we should use larger-than-5 chunks.

There's a mac build available right now.. so if anyone could comment on the performance there, that would be great.

https://build.mozilla.org/tryserver-builds/2008-01-28_20:24-edward.lee@engineering.uiuc.edu-fast.fast.adap/
> Seth wants to change chunks back to meaning "how many pages to check each 
> update" in which case we should use larger-than-5 chunks.

Yes, see bug #414489 comment #9.  

I think this is the true cause of lagging (in the "ddddd.....dddd" case with a large places.sqlite) and it explains why we didn't see it before global frecency landed.

The discussion is going on in that bug, but I'm bummed it took until now for me to spot the flaw.  but better now that after beta 3 ships!

Thanks to edward's comments for pointing it out.
Depends on: 414507
Regression, Regression, Regression

Sorry guys. the Beta 2 autocomplete is far better than the version in the latest nightly.

Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9b3pre) Gecko/2008012904 Minefield/3.0b3pre

The new version is so slow!
The new version does not find all occurences of strings typed.
The new version puts at the end of the list some of the most used URLs.
The new version does not classify URL by popularity.
The new version looks only at the start of words and won't accept strings like "t.m".
With the new version, I need to type more characters to filter the URL and finally find the one I'm looking for.

Overall, the awesome bar in trunk feels like going back to Firefox 2.0 for the features and is one thousand times slower that 3.0b2.

Please roll back to the version in 3.0b2.
> The new version is so slow!

2008012904 should have edward's fix for bug #414507

> The new version does not find all occurences of strings typed.

that could be bug #414581 (I'm hoping it is.)

> The new version puts at the end of the list some of the most used URLs.

If this is your first time running a b3 candidate, I wonder if this implies that your places all have frecency -1 and we haven't recalculated any.

> The new version looks only at the start of words and won't accept strings like
> "t.m".

I don't have this problem.  can you visit planet.mozilla.org and then try "t.m" again?

> The new version does not classify URL by popularity.

can you click on the url bar drop down (the down arrow in the url bar, to the right of the star?)

do those look like popular sites for you?  (as of right now, that shows us the top 20 places by frecency.

I'd be curious to know how many of your places have a frecency of -1.  do you feel comfortable using a sql add on or sql database browser and running some queries?

Ah! I see. When moving from 3.0b2 to 3.0b3 results needs to be reindexed.

Now it's fast!
Now it finds all occurences.
Now it classify the results based on popularity.
And now I can type string like "t.m".
Etc.

I reacted too quickly. Sorry.
>  When moving from 3.0b2 to 3.0b3 results needs to be reindexed.

dietrich just landed a fix to improve this by:

1) recalculating more on migration
2) recalculating more on idle.

See bug #414253.

That will be in tomorrow's build.

> I reacted too quickly. Sorry.

No worries.
(In reply to comment #23)
> (In reply to comment #20)
> > (An example ad URL: ...
> Tim: Do you have some way to query the sqlite db?

Sorry I didn't reply to this earlier.  The problem is now fixed, in that I don't see spurious results in the location bar results. (Even when explicitly typing "ads", which brought up tons before.)  It's also fixed in that I don't notice any lag.  ^_^  I could still install the storage-explorer and report the results back if it would be useful.


Does that mean this is RESO WFM or otherwise?
> Does that mean this is RESO WFM or otherwise?

I think this is fixed, and not WFM, thanks to edward's changes to:

a) move the LIKE compare out of SQL into C++, and just chunk purely by frecency
b) and, to a lesser extent, but still of value, the timeout on the url bar.

It would be useful to get feedback on numbers of urlbar.{maxRichResults,chunkSize,timeout} pref that work for people. (Right now those prefs don't work correctly as checked in.)

This build has those prefs working, but they also include some other patches:
https://build.mozilla.org/tryserver-builds/2008-01-30_01:58-edward.lee@engineering.uiuc.edu-multi.0stop.escap.adapt/

On my iBook G4 1.33 GHz, these prefs work well for me: maxRichResults = 10, chunkSize = 500, timeout = 50. Reduce the number of results we need to fetch before stopping (and not have the scrollbar appear). Large enough chunksize to likely have a result in the first chunk and not wait for 2nd chunk to return. Small enough timeout to feel like the dropdown is smoothly getting more results instead of chunks.

For those not sure about how the prefs affect chunking, try setting chunkSize to 1 and timeout to 1000 and type 'p'. You'll see one additional page show up every second.

List of patches in that build:
Bug 414285 - Refactor AutoCompleteTagsSearch token splitting code and persist tokens
Bug 401869 - Allow multiple words search in Auto-complete/Location Bar
Bug 414581 - Autocomplete shows no results for some words, sometimes
Bug 413784 - Search for a non-English term in the URL don't match
Bug 389465 - Places should decode URLs
Bug 395735 - Instrument the location bar auto-complete to report accuracy
Bug 406359 - Unify the logic for url bar searches and drop down items
Bug 414287 - Share search result processing logic as AutoCompleteProcessSearch
Bug 414288 - Simplify TagsSearch to be correct, clear, concise
Bug 414426 - Optimize SearchTags query by filtering out non-tags
Bug 395739 - adaptive learning (match entered text to selected item) in url bar autocomplete

FYI, the prefs will be working for beta 3 (not the nightlies for today). So no need to download that build unless you want to try out other stuff.
Mardak - should we mark this as fixed, then, or at least clear the blocking nom request?
From reports in the bug and on irc, this should be fixed. Clarifying title for why it was laggy to begin with.
Blocks: 394038
Status: ASSIGNED → RESOLVED
Closed: 17 years ago
Resolution: --- → FIXED
Summary: Typing in location bar is extremely laggy → Typing in location bar is extremely laggy since global frecency
Could please somebody test the fix with the profile uploaded to http://uploaded.to/?id=eb3vpd, and typing "hotmail" in the location bar.

With beta2 it froze my machine after the two letters "ho", but I don't know wether Beta2 contained already global frequency.

lg Clemens

Could people provide some feedback on the latest trunk about what values for the preferences work? There's 2 ends to consider: typing words that finds pages and typing words that don't find pages.

To effectively get this bug back, you could change chunkSize to a huge value like 100000, where location bar is laggy when it doesn't find results.

Or instead, you can change chunkSize to 10, but then you get bug 415489 in that results don't show up right away.

Try these preferences and tweak them a bit:

browser.urlbar.search.chunkSize 2000
browser.urlbar.search.timeout 50
browser.urlbar.maxRichResults 15

Are things responsive for you when you get matches and no matches?
Flags: blocking-firefox3? → blocking-firefox3+
I tested beta3 with my old profile and everything seems to work fine.
*** VERIFIED

Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9b3) Gecko/2008020514 Firefox/3.0b3
Asa and many others with somewhat-large (ok; huge!) histories have told me that this is indeed fixed; Verified.
Status: RESOLVED → VERIFIED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: