484928 - improve efficiency of IsVisited checks to speed up link coloring

Status: RESOLVED WORKSFORME

(Toolkit :: Places, enhancement, P3)

Description

[Dietrich Ayala (:dietrich)]

Attachment: wip

we make a *lot* of api/sql calls per page load for link coloring. i did some tests and found that a lot of pages have upwards of >50 links on a page.

30: http://www.google.com/
40: https://bugzilla.mozilla.org/show_bug.cgi?id=386104
69: http://www.mozilla.org/developer/
428: http://news.yahoo.com/s/ap/20090324/ap_on_bi_ge/geithner_regulations

we make a call to the database for almost* every single link on the page.

however:

1. many of the links are not visited, so we're hitting the db for something that's not there
2. in the case of page reloads and links shared across multiple pages of the same site, but we check the db repeatedly for their status

this patch caches links that have been asked about, and their visited status, for a short period of time, with the goal of reducing db traffic across multiple page visits at the same page or site.

page reloads benefit a lot from this. the mozilla.org/developer page for example, goes from 69 sql queries to zero on a reload.

an example of the effect on transitions in the same site is going from mozilla.com homepage to the firefox page:

going from mozilla.com (58 link checks) to /products/firefox (67 link checks) causes a total of 125 link checks. with this patch, the total number of link checks was 76, so almost 40% fewer calls for link coloring on the second page.

the patch needs work still, but is a working POC.

Comment 1

[Dietrich Ayala (:dietrich)]

could reduce memory usage by using the string URI as the hash key instead of the nsIURI.

Comment 2

[Dietrich Ayala (:dietrich)]

the * next to "almost" in the first comment is because we do check the lazy commit queue and redirect hashes for recent visits.

the lazy commit queue flushes a few seconds after each page visit, so likely will not yield the same success as the approach in this patch. actually, we might be able to remove that check, as it'd be redundant with this one.

Comment 3

[Dietrich Ayala (:dietrich)]

need to handle deletes. could take the simple route and just clear the cache for that case.

Comment 4

[Dietrich Ayala (:dietrich)]

should also put a hard cap on the cache size.

Comment 5

[Dietrich Ayala (:dietrich)]

heh, realized this will likely have either no effect on Tp, or will make it worse. the URIs in our page set for Tp are all top-site front pages, not multiple pages from the same site.

Comment 6

[Marco Bonardo [:mak]]

mh, visits in the last 2 minutes are added to the temp table, so they are already cached in memory really, those queries should all touch the memory table, probably the overhead is greater than an internal cache though.

Comment 7

[Shawn Wilsher :sdwilsh]

So, it'd be interested to see some data before we decide to take this:
1) shark profile before this change
2) shark profile after this change

I know IsVisited has shown up in profiles in the past, but I want to make sure that that is still true.

(In reply to comment #1)
> could reduce memory usage by using the string URI as the hash key instead of
> the nsIURI.
Looking at the implementation of nsURIHashKey, it looks like using the spec would be faster too.

(In reply to comment #3)
> need to handle deletes. could take the simple route and just clear the cache
> for that case.
Or just call RemoveEntry on the hash table.  No need to throw all that data away.

Also need to clear it when we do our idle expiration.

Comment 8

[Dietrich Ayala (:dietrich)]

(In reply to comment #6)
> mh, visits in the last 2 minutes are added to the temp table, so they are
> already cached in memory really, those queries should all touch the memory
> table, probably the overhead is greater than an internal cache though.

yeah recently visited links benefit the least of all scenarios, but likely will still benefit more than sql roundtrip. need to measure it.

Comment 9

[Dietrich Ayala (:dietrich)]

(In reply to comment #7)
> (In reply to comment #3)
> > need to handle deletes. could take the simple route and just clear the cache
> > for that case.
> Or just call RemoveEntry on the hash table.  No need to throw all that data
> away.

1. deletes do not occur often, especially now that expiration is done at flush time.

2. the data builds up again very rapidly: most shared links in a site are re-cached after a single pageload at that site.

so, the cost of finer-grained management of this short-lived cache is probably not worth the benefit.

Comment 10

[Shawn Wilsher :sdwilsh]

(In reply to comment #9)
> 1. deletes do not occur often, especially now that expiration is done at flush
> time.
but expiration is not the same as delete.  We are already covered with expiration when you clear the cache when we flush.  I'm thinking when a user or add-on explicitly deletes a URI.

Comment 11

[Dietrich Ayala (:dietrich)]

those kinds of deletes do not occur often, hence my assertion that we should just clear the whole cache on those relatively rare occasions.

Comment 12

[Shawn Wilsher :sdwilsh]

I guess I don't see the point.  It's going to be one line of code in either case, in the same places, no?  I don't see why doing more work helps us, especially when it's just a different function call.  Am I missing something?

Comment 13

[Dietrich Ayala (:dietrich)]

(In reply to comment #12)
> I guess I don't see the point.  It's going to be one line of code in either
> case, in the same places, no?  I don't see why doing more work helps us,
> especially when it's just a different function call.  Am I missing something?

it's just a line of code in the single URI example, so yeah could do this in that case. it's the bulk deletion scenarios that i was concerned about. so yeah will probably use both, depending on context.

Comment 14

[Dietrich Ayala (:dietrich)]

IsVisit() shows up in Shark, usually in the 0.1% area. i haven't sharked it w/ the patch applied yet.

maybe still worth doing even if the IsVisit time is small, since these are synchronous calls: speeding them up might yield overall improvements in page load time for these scenarios. i don't know enough about how the callers in content work to be able to say that for sure though.

Comment 15

[Boris Zbarsky [:bzbarsky]]

For what it's worth, I can certainly produce profiles here if desired.  But have you tried pushing this to try and seeing what Talos says, as a first cut?

Comment 16

[Dietrich Ayala (:dietrich)]

pushed a dummy patch and then this patch to the tryserver this morning. will report numbers back here when they're done.

Comment 17

[Dietrich Ayala (:dietrich)]

the mac numbers were inconsistent, the linux box only ran my dummy patch, and the windows boxes all timed out on Tp. i pushed again to see if it produces better numbers this time around.

Comment 18

[Dietrich Ayala (:dietrich)]

Attachment: wip

uses URI string as hash key instead of nsIURI

Comment 19

[Dietrich Ayala (:dietrich)]

tryserver is completely hosed.

Comment 20

[Dietrich Ayala (:dietrich)]

re-pushed to the tryserver today. this change had no detectable effect on Tp.

Comment 21

[Mark Finkle (:mfinkle) (use needinfo?)]

I'd love to see if this affects mobile Tp. Mobile is much more suspectible to SQL slowdown than desktop.

We don't quite have a try talos yet, but maybe soon.

Comment 22

[Dietrich Ayala (:dietrich)]

i'm skeptical of the Tp result from the tryserver. once the tree re-opens i'll do a trial landing of this to get some proper performance numbers.

Comment 23

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

I just kicked off two tryserver runs -- one a baseline without any patches, and one with a patch that just always returned false from IsVisited (but everything else still in place, so not fully disabling history).  Results:

       baseline novisited
xp01    192.91  189.28  -1.88%
xp02    193.05  188.70  -2.25%
vista01 393.15  416.58  << uhh, broken?
vista02 390.84  414.60  << uhh, broken?
tiger01 297.17  292.84  
tiger02 294.52  290.77
leop01  298.70  294.85
leop02  296.59  292.52
linux   224.13  221.40

So it's a small win, but it's noticeable -- this is also with clean profiles each time (I think?).  I think this would be a much bigger win with a profile with lots of history.  (I have no idea what's up with vista.  That's just broken.)

Dietrich's approach here is a good one, though I would also suggest keeping an in-memory hashtable of just the hostnames that we have history for.. that way we can avoid a db lookup entirely for things that won't be present.

Comment 24

[Dietrich Ayala (:dietrich)]

this will affect Ts as well, even moreso when restoring sessions.

Comment 25

[Dietrich Ayala (:dietrich)]

(In reply to comment #23)

thanks for running these vlad.

> So it's a small win, but it's noticeable -- this is also with clean profiles
> each time (I think?).  I think this would be a much bigger win with a profile
> with lots of history.  (I have no idea what's up with vista.  That's just
> broken.)

bingo. in an empty db, it's extremely fast to execute a query that returns zero results. however, the firefox 3.x user with default settings now has 90 - 180 days of history. 

and for restored sessions, the effect is magnified per restored tab.

> Dietrich's approach here is a good one, though I would also suggest keeping an
> in-memory hashtable of just the hostnames that we have history for.. that way
> we can avoid a db lookup entirely for things that won't be present.

instead of URLs you mean?

Comment 26

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

> > Dietrich's approach here is a good one, though I would also suggest keeping an
> > in-memory hashtable of just the hostnames that we have history for.. that way
> > we can avoid a db lookup entirely for things that won't be present.
> 
> instead of URLs you mean?

Right -- checking just the hostname lets you quickly throw away a whole swath of URLs, at least that's my thinking... always have the hashtable that represents the set of hostnames that you have any history for.  So flow would be something like:

1) Is hostname in hashtable?  If no, return FALSE.

2) Is URL in hot cache?  If yes, return cached value.

3) Query if URL is in database and cache the result.

4) If we've missed the hot cache a bunch of times recently, blow away the hot cache (e.g. less than 25% hit rate or something).  This can maybe be smarter, not sure how you want to do cache eviction here.

My thinking is that while browsing, most URLs will be either to the current site, or a bunch of scattered sites (outbound links, ads, etc.).  The hostname hashtable would have to contain the set of unique hostnames that are also in the database, so we'd have to make sure it's kept in sync, but that shouldn't be hard.  But it gives you a fast way to early-reject all the scattered outbound links.

Would be interesting to analyze our Tp4 set and see on each page how many links go to the same hostname as the page and how many go to a different one...  (or maybe the distribution between domain links or something).

Comment 27

[James May [:fowl2]]

Would it be possible to use an approach like the AdBlock Plus extension uses for filtering? 

That has to run on every request, not just links and seems pretty fast.

http://adblockplus.org/blog/investigating-filter-matching-algorithms

Comment 28

[Boris Zbarsky [:bzbarsky]]

Thing is, a typical page has many more links than requests.  For example, this very bug page has 214 links on it.  I can pretty much guarantee that there are fewer requests than that.  It's not exactly unique.  The CNN front page has 343 links.  The Google front page has 30 links (and 2 requests).  One of the pages in our pageload-performance-measurement page set has 33000 links as far as I know (and it's not a synthetic page by any means).

The adblock approach might still work, of course.  Or does "pretty fast" mean "I can't tell a difference with my eyes on most pages"?  If so, it might just be taking several hundred ms (below human perception threshold); when scaled up by an order of magnitude due to larger number of links, you suddenly have a problem.

Comment 29

[Shawn Wilsher :sdwilsh]

This bug is obsolete once bug 461199 lands, right?

Comment 30

[Dietrich Ayala (:dietrich)]

Not working on this, unassigning.

(In reply to comment #29)
> This bug is obsolete once bug 461199 lands, right?

Not necessarily. We're still doing hundreds of no-match SQL round-trips per page-load, which could be fairly easily avoided with a short-lived in-memory cache.

Comment 31

[Marco Bonardo [:mak]]

in the meanwhile bug 702810 introduced a more efficient query

Comment 32

[Marco Castelluccio [:marco]]

so, is this still something to pursue?

Comment 33

[Marco Bonardo [:mak]]

Reducing the number of queries may still be a win, not high priority atm.

Comment 34

[Dietrich Ayala (:dietrich)]

with pages like Yahoo News having >400 links per page, i think this is definitely worth doing at some point. every cycle counts.

Comment 35

[Wayne Mery (:wsmwk)]

(In reply to Dietrich Ayala (:dietrich) from comment #34)
> with pages like Yahoo News having >400 links per page, i think this is
> definitely worth doing at some point. every cycle counts.

and bugzilla queries :)
eg https://bugzilla.mozilla.org/buglist.cgi?list_id=11486295&product=Core&product=Firefox&query_format=advanced&resolution=---&short_desc=e10s&short_desc_type=allwordssubstr&order=component%2Cbug_id%20DESC&limit=0

Comment 36

[:Gijs (he/him)]

Echoing fxperf:p2 from the dep.

Comment 37

[:Felipe Gomes (needinfo for replies!)]

(not startup related: fxperf:p2 -> fxperf:p3)

Comment 38

[Stephanie Cunnane [:scunnane]]

At this point, we don't have a good solution for simultaneously fixing the current bug without regressing https://bugzilla.mozilla.org/show_bug.cgi?id=1506842.

Comment 39

[Stephanie Cunnane [:scunnane]]

To anyone who'd like to work on this bug, please consider talking with the Layout team to discuss possible ideas for making the timing for unvisited links similar to that of visited links.

Comment 40

[Emilio Cobos Álvarez [:emilio]]

Shouldn't bug 1593690 have helped quite a bit here?

Comment 41

[Marco Bonardo [:mak]]

bug 1593690 surely helped.
Though the idea here was to completely avoid a db roundtrip in some cases, e.g. unvisited case (through the use of a Bloom filter for example). But that may be a problem for the privacy leak issue, unless we delay all the notifications and send them in timed chunks.

Anyway it's also possible future use of mmapped IO may be enough to reduce the cost in most cases and make this an overengineered solution.

Comment 42

[Florian Quèze [:florian]]

Unless anyone saw recently a profile where this was an issue, I think we can close this old bug.