926139 - [meta] Next-level favicon loading and storage

Status: RESOLVED INCOMPLETE

(Firefox for Android Graveyard :: Favicon Handling, defect)

Description

[Richard Newman [:rnewman]]

This is a follow-on from Bug 914296.

There's a lot about how we currently do favicon loading that's less than perfect. Brain-dumping:

* We don't track enough failure cases in transient or persistent storage. This leads to redundant work being done when those failure cases reoccur.

* We don't behave correctly in the presence of redirects (see comments in Bug 914296).

* We don't do expiration, and neither do we adequately track caching logic.

* We use the shitty Android HttpClient layer, and probably do so incorrectly. Sync already does a bunch of work here to (a) use a better HttpClient version, and (b) set up pooling etc.

* Callers that have more knowledge about favicons (e.g., the URL!) should be sure to pass it to the loading code to avoid having to hit the DB or the network. This might just be an audit with a thumbs-up, or we might find that we're doing something stupid, like not fetching the favicon URL in the history list and instead grabbing it from the memory cache or the DB.

* The loading code should do the very best it can to not create AsyncTasks, because they contend for the background thread, occupy lots of memory, cause needless context switches, and otherwise make people cry when we load lots of pages in reftests. If we know the URL, and we're on a background thread already (fetching from the DB), we should look straight into the memory cache. If we don't find what we want, we should directly insert a favicon listener into the favicon system -- which can be chained or executed sanely. This whole mess of UiAsyncTask/doInBackground/onPostExecute/onCanceled is ridiculously heavyweight, as Bug 926129 showed.

* We ought to batch more. Decoupling the loading code from UiAsyncTask could help with that, and I imagine aligns well with Sriram and Lucas's work on Smoothie -- having separate tasks results in stupid database access profiles.

* The whole idea of storing blobs in the DB, keeping scaled versions only in-memory, would probably benefit from reconsidering. (The same goes for thumbnails.)

Chris, Margaret: do you have more ideas?

Comment 1

[Wesley Johnston (:wesj)]

We should file separate bugs for these issues. I don't want more mega patches :)

Comment 2

[Richard Newman [:rnewman]]

Yeah, this is a meta bug for a reason :D

I'm hoping that here we can capture broad thoughts, and then we can file actionable bugs to address them.

Comment 3

[Sriram Ramasubramanian [:sriram]]

Simplest thought to update the views only if its not recyled:
http://developer.android.com/training/improving-layouts/smooth-scrolling.html

This could be used with current AsyncTask and with Smoothie (I guess smoothie does it already).

Comment 4

[Chris Kitching [:ckitching]]

(In reply to Richard Newman [:rnewman] from comment #0)
> * We don't track enough failure cases in transient or persistent storage.
> This leads to redundant work being done when those failure cases reoccur.

Where should we store this information?
If we store the fact that a particular favicon URL has failed in the database, we have to do a comparable amount of work to fetch the fact that a failure has happened than we would have to do to determine that no favicon is locally available.

Last I heard, the hope was that storing failures would mean us not having to do as much work when scrolling the list views - unfortunately, since the work done there is, at worst, database access, we don't save anything by doing database access to determine if we need to do database access.
Alas.

Of course, something useful can nevertheless be done in this direction, just be careful that the extra work involved with tracking this information isn't larger than the saving you get.

> * We don't behave correctly in the presence of redirects (see comments in
> Bug 914296).

Comment 82/83, for those of you who don't fancy reading the full epic.
Our behaviour has transitioned from "Failes entirely" to "Fails on weirdly-designed websites". Needs fixing, but is probably less important than the other things mentioned here.
Also, was filed as Bug 925878.

> * We don't do expiration, and neither do we adequately track caching logic.

What do you mean here?

Things in the in-memory cache expire nicely. I assume you're referring to the persistent-storage cache? That needs to be changed quite urgently - at the moment favicons are cached forever. Should instead obey the caching directives the server provides, or at least do something sort of sensible to prevent the favicons table from growing without limit.

> * Callers that have more knowledge about favicons (e.g., the URL!) should be
> sure to pass it to the loading code to avoid having to hit the DB or the
> network. This might just be an audit with a thumbs-up, or we might find that
> we're doing something stupid, like not fetching the favicon URL in the
> history list and instead grabbing it from the memory cache or the DB.

If this is done correctly, the perfformance gains might be significant.
Certainly, we should be able to kill off the hack that is Favicons.getSizedFaviconForPageFromLocal - which was only added as a way to keep TwoLinePageRows happy.
Ideally, the favicon system should be queried with the favicon URL. That said, if this is not available, the existing code will behave as well as it can in terms of caching results. (It's not worth doing extra mucking about in the database to find the favicon URL just so you can give it to the favicons system if you really don't know it.)
So, actually, in the case of TwoLinePageRows, we might be stuck with this behaviour - unless we have them also track the favicon URL from the database.

It might also be worth considering tracking local favicons using their id field in the favicons table, instead of the favicons url.

Also, under no circumstances should queries for favicons be routed through the "combined_with_favicons" view which is, after the giant patch, now unused.
Queries on that view take, at best, time linear in the size of the history database...

> * The loading code should do the very best it can to not create AsyncTasks,
> because they contend for the background thread, occupy lots of memory, cause
> needless context switches, and otherwise make people cry when we load lots
> of pages in reftests. If we know the URL, and we're on a background thread
> already (fetching from the DB), we should look straight into the memory
> cache. If we don't find what we want, we should directly insert a favicon
> listener into the favicon system -- which can be chained or executed sanely.
> This whole mess of UiAsyncTask/doInBackground/onPostExecute/onCanceled is
> ridiculously heavyweight, as Bug 926129 showed.

Perhaps the best solution here is our own task scheduler controlling a thread pool to do the required loads. This will allow for better parallelism.
That said, specialised thread pools are, in general, something to be avoided. However, completely changing the entire app's slightly eccentric threading model just so we can write the favicon caching system my way is probably not sensible. :P

> * We ought to batch more. Decoupling the loading code from UiAsyncTask could
> help with that, and I imagine aligns well with Sriram and Lucas's work on
> Smoothie -- having separate tasks results in stupid database access profiles.

A simple way to do extra batching would be to have the aforementioned task scheduler launch tasks at regular intervals (If any work exists to be done), and the rest of the time just aggregate tasks into a queue.
That way, every request splurged into the favicons system in a short period is handled in one big database query, instead of the current craziness with thousands of AsyncTasks.

Smoothie's batching is nice, but the way it never loads anything while the list is in motion is something that will, I suspect, make the UX people sad. If you scroll down slowly favicons will never appear!

> * The whole idea of storing blobs in the DB, keeping scaled versions only
> in-memory, would probably benefit from reconsidering. (The same goes for
> thumbnails.)

A good solution might be to store favicons in a memory-mapped file on disk and store offsets into this file in the favicons database. Don't write your own caching when the kernel can do it for you!

> Chris, Margaret: do you have more ideas?

The new cache provides hooks which will be useful for solving Bug 914058. It seems important that it be known that the memcaching part of that problem is already solved and need not be solved again (We no longer have multiple favicon caches. Let's keep it that way. :P)
Unclear if that one really counts as something this bug covers, since it depends on Bug 748100.


Also of note is Bug 914027, which adds, among other things, the ability attempt to load the next favicon if the first one provided fails. Can unbitrot on request. (I suspect the current focus is to get the ICODecoder landed before it, though.)

Comment 5

[Richard Newman [:rnewman]]

(In reply to Chris Kitching [:ckitching] from comment #4)

> Last I heard, the hope was that storing failures would mean us not having to
> do as much work when scrolling the list views - unfortunately, since the
> work done there is, at worst, database access, we don't save anything by
> doing database access to determine if we need to do database access.
> Alas.

There are better approaches -- for example, can we compute and persist a bloom filter for favicon non-presence, and test that?


> Of course, something useful can nevertheless be done in this direction, just
> be careful that the extra work involved with tracking this information isn't
> larger than the saving you get.

Indeed.

> > * We don't do expiration, and neither do we adequately track caching logic.
> 
> What do you mean here?
> 
> Things in the in-memory cache expire nicely. I assume you're referring to
> the persistent-storage cache? That needs to be changed quite urgently - at
> the moment favicons are cached forever. Should instead obey the caching
> directives the server provides, or at least do something sort of sensible to
> prevent the favicons table from growing without limit.

Yes, those are the two things I meant: we need to evict favicons from the database, and we ought additionally to evict them according to HTTP cache directives.


> Perhaps the best solution here is our own task scheduler controlling a
> thread pool to do the required loads. This will allow for better parallelism.
> That said, specialised thread pools are, in general, something to be
> avoided. However, completely changing the entire app's slightly eccentric
> threading model just so we can write the favicon caching system my way is
> probably not sensible. :P

I'd be happy with a single executor that batches every request that arrived since the last time it ran. We do something similar to this in Sync -- non-cached favicon load requests go into a queue, and a worker grabs the entire contents of the queue whenever it's done with its task. This gives us batch DB inputs for free, avoids having thread context switching/affinity bullshit, etc.

Comment 6

[Sriram Ramasubramanian [:sriram]]

I tried using Smoothie with nalexander's patch.
The Smoothie uses a threadpool that requires the work to be done in loadItem(). This is usually a call like "Favicons.getFavicon(url)". However, the current change to Favicons made the methods to return a taskId instead. So, loadItem() needs some way of waiting for the AsyncTask to return a result. I tried using a Future to bridge the gap [1]. This is not efficient (I was just trying to see if Smoothie worked with new code). I guess, it's better to start working on this bug, and removing the LoadAsyncTask.

[1]. Basically a call like Favicons.getFavicons(url) will spin a Future. This Future will return the result when it's ready, as this will also be the OnFaviconLoadedListener.

Comment 7

[Chris Kitching [:ckitching]]

(In reply to Sriram Ramasubramanian [:sriram] from comment #6)
> I tried using Smoothie with nalexander's patch.
> The Smoothie uses a threadpool that requires the work to be done in
> loadItem(). This is usually a call like "Favicons.getFavicon(url)". However,
> the current change to Favicons made the methods to return a taskId instead.
> So, loadItem() needs some way of waiting for the AsyncTask to return a
> result. I tried using a Future to bridge the gap [1]. This is not efficient
> (I was just trying to see if Smoothie worked with new code). I guess, it's
> better to start working on this bug, and removing the LoadAsyncTask.
> 
> [1]. Basically a call like Favicons.getFavicons(url) will spin a Future.
> This Future will return the result when it's ready, as this will also be the
> OnFaviconLoadedListener.

I'm not sure which patch you're talking about or what you're trying to do, but,

As rnewman can probably explain more effectively than I can, one of the main advantages of using something like Smoothie is the ability to batch-load favicons without needing to do the vastly overheadful thing of spawning number-of-favicons-we-want many AsyncTasks.

On an unrelated note, there was at one point (and can readily be again) support for the favicon system loading favicons synchronously. Simply add a parameter to Favicons.getSizedFaviconForPageFromLocal which specifies the thread to do the work on, add overrides to make this parameter default to the background thread, and have it run the LoadFaviconTask on the calling thread.
You almost certainly don't want to do this.

Again, rnewman is the person to talk to for a more coherent explanation, but it sounds like the approach you're using might miss the goals of this bug, and be irritating to implement, so just make sure it's going to actually be better before going ahead with it.

Comment 8

[Richard Newman [:rnewman]]

(In reply to Sriram Ramasubramanian [:sriram] from comment #6)

> (I was just trying to see if Smoothie worked with new code). I guess, it's
> better to start working on this bug, and removing the LoadAsyncTask.

Concur.


> The Smoothie uses a threadpool that requires the work to be done in
> loadItem().

We shouldn't be using a threadpool: it will only cause contention. The work we're doing can be conceptually divided as follows:

1. Do we have a Bitmap of the right size in memory? If so, grab it and assign it directly. No other work is done. This is synchronous: the work to coordinate multiple threads for this will vastly outweigh the actual work being performed.

2. If that cache lookup fails, we're going to need to do DB work... but we want to precisely control when that happens, so let's track that we want favicon X at size Y, and allow the favicons module to decide how to do the work. This is asynchronous and slow.

3. We no longer need a favicon, so let's cancel an outstanding fetch.


Currently we implement *all* of these using AsyncTasks. We should not.


The implementation of 2/3, I contend, should be:

* A queue of URL/size/delegate (future) tuples.

* A consumer thread that blocks on the queue, grabbing its entire contents whenever it wakes, issuing database requests *for all at once*. This is the best way to hit the DB.

* The grabbed results can then be parsed, scaled, and cached, either in a second thread or in the consumer thread -- depends on whether memory bandwidth is the constraining factor, or whether we'll get a speedup by reading from the DB while we're copying bytes from mem to mem. This is easy enough to tune. We skip the processing of the results if the request was canceled in the meantime.

* Finally, the delegate/future for each request can be notified on the appropriate (UI?) thread -- "hey, your favicon is ready". If the request was canceled, we don't bother doing this (but it's still in the cache in case the user scrolls back).


This is a batching task queue, trivially implementable on top of Java's Executor framework. (We do something similar to this for record processing in Sync, albeit in a much more complicated way.)

Extending this model to re-scale items that are already cached (without going to the DB), implementing a kind of priority switch, is an exercise for the reader.


It might be possible for you to bend Smoothie to provide the execution queue for the favicon layer. Without looking at the code, it's hard to speculate.

Comment 9

[Sriram Ramasubramanian [:sriram]]

This is the apt solution :)

Comment 10

[Richard Newman [:rnewman]]

(In reply to Sriram Ramasubramanian [:sriram] from comment #9)
> This is the apt solution :)

^5

Comment 11

[Sriram Ramasubramanian [:sriram]]

And the solution is pretty similar to what Smoothie does. It constructs Future's and gives it to an Executor. The loadItem() is basically Future's call(). The returned Bitmap is given to UI thread.

1. Now, instead of using an AsyncTask, we need to do all the Favicon work inside the loadItem() call.
This would be like

loadItem(url) {
   return Favicons.getFavicon(url);
}

Favicons wouldn't return the taskId, but the actual result. Also, Favicons would work on the thread that the method is called on.

or.

2. Smoothie shouldn't worry about the Future's. Favicons will maintain it's thread and do the job. (This feels redundant).

If we go by approach (1), then the favicon loading for the url bar will fail. (And any other place -- as they will be blocking on the UI thread).

Comment 12

[BMO Automation]

We have completed our launch of our new Firefox on Android. The development of the new versions use GitHub for issue tracking. If the bug report still reproduces in a current version of [Firefox on Android nightly](https://play.google.com/store/apps/details?id=org.mozilla.fenix) an issue can be reported at the [Fenix GitHub project](https://github.com/mozilla-mobile/fenix/). If you want to discuss your report please use [Mozilla's chat](https://wiki.mozilla.org/Matrix#Connect_to_Matrix) server https://chat.mozilla.org and join the [#fenix](https://chat.mozilla.org/#/room/#fenix:mozilla.org) channel.