improve efficiency of IsVisited checks to speed up link coloring
Categories
(Toolkit :: Places, enhancement, P3)
Tracking
()
People
(Reporter: dietrich, Unassigned)
References
(Blocks 1 open bug)
Details
(Keywords: perf, Whiteboard: [TSnappiness][ts][Snappy:p3][snt-scrubbed])
Attachments
(1 file, 1 obsolete file)
9.47 KB,
patch
|
Details | Diff | Splinter Review |
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.
Reporter | ||
Comment 1•15 years ago
|
||
could reduce memory usage by using the string URI as the hash key instead of the nsIURI.
Reporter | ||
Comment 2•15 years ago
|
||
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.
Reporter | ||
Updated•15 years ago
|
Reporter | ||
Comment 3•15 years ago
|
||
need to handle deletes. could take the simple route and just clear the cache for that case.
Reporter | ||
Comment 4•15 years ago
|
||
should also put a hard cap on the cache size.
Reporter | ||
Comment 5•15 years ago
|
||
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•15 years ago
|
||
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•15 years ago
|
||
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.
Reporter | ||
Comment 8•15 years ago
|
||
(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.
Reporter | ||
Comment 9•15 years ago
|
||
(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•15 years ago
|
||
(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.
Reporter | ||
Comment 11•15 years ago
|
||
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•15 years ago
|
||
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?
Reporter | ||
Comment 13•15 years ago
|
||
(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.
Reporter | ||
Comment 14•15 years ago
|
||
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•15 years ago
|
||
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?
Reporter | ||
Comment 16•15 years ago
|
||
pushed a dummy patch and then this patch to the tryserver this morning. will report numbers back here when they're done.
Reporter | ||
Comment 17•15 years ago
|
||
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.
Reporter | ||
Comment 18•15 years ago
|
||
uses URI string as hash key instead of nsIURI
Reporter | ||
Comment 19•15 years ago
|
||
tryserver is completely hosed.
Reporter | ||
Comment 20•15 years ago
|
||
re-pushed to the tryserver today. this change had no detectable effect on Tp.
Comment 21•15 years ago
|
||
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.
Reporter | ||
Comment 22•15 years ago
|
||
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.
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.
Reporter | ||
Comment 24•15 years ago
|
||
this will affect Ts as well, even moreso when restoring sessions.
Reporter | ||
Comment 25•15 years ago
|
||
(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?
> > 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•15 years ago
|
||
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•15 years ago
|
||
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.
Reporter | ||
Updated•15 years ago
|
Comment 29•15 years ago
|
||
This bug is obsolete once bug 461199 lands, right?
Reporter | ||
Comment 30•14 years ago
|
||
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.
Updated•13 years ago
|
Comment 31•13 years ago
|
||
in the meanwhile bug 702810 introduced a more efficient query
Comment 32•13 years ago
|
||
so, is this still something to pursue?
Comment 33•13 years ago
|
||
Reducing the number of queries may still be a win, not high priority atm.
Reporter | ||
Updated•12 years ago
|
Reporter | ||
Comment 34•12 years ago
|
||
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•10 years ago
|
||
(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
Updated•7 years ago
|
Updated•6 years ago
|
Comment 36•6 years ago
|
||
Echoing fxperf:p2 from the dep.
Comment 37•5 years ago
|
||
(not startup related: fxperf:p2 -> fxperf:p3)
Updated•2 years ago
|
Comment 38•1 year ago
|
||
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•1 year ago
|
||
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.
Updated•1 year ago
|
Updated•1 year ago
|
Comment 40•1 year ago
|
||
Shouldn't bug 1593690 have helped quite a bit here?
Comment 41•1 year ago
|
||
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•8 months ago
|
||
Unless anyone saw recently a profile where this was an issue, I think we can close this old bug.
Description
•