Consider using a Bloom filter for tracking visited links in GlobalHistory




4 years ago
4 years ago


(Reporter: mfinkle, Unassigned)


Firefox Tracking Flags

(Not tracked)


We currently use:

 SoftReference<Set<String>> mVisitedCache;

We might get reduced memory usage by switching to a BloomFilter. We should also consider dropping the use of a SoftReference, which Android controls the lifetime, and switch to something more explicitly controlled, like an LRUCache.

That way we can keep the data from being flushed and reloaded during a single page load. Android can kill other background stuff and we can keep the foreground data alive and in use without reloading from SQL.
Hey, this is my interview question!

Things that usually come up:

* Consider populating GlobalHistory on a per-domain basis. Capture the domains referenced by links in the page, cache DB contents by domain. If you're loading, it's unlikely that you'll need the user's entire browser history to color the page, given that almost every link will be to

* Yes, use a Bloom filter. Beware of the false positive/negative tradeoff. One of the reasons to use a Bloom filter is to allow for somewhat correct operation even if we have to throw away the accurate cache, so there are a few ways one could be applied here.

* Measure and assess whether we can do direct DB reads instead, or a batch read on page load with delayed link coloring.
OS: Mac OS X → Android
Hardware: x86 → All
Summary: Consider using a BloomFilter for tracking visited links in GlobalHistory → Consider using a Bloom filter for tracking visited links in GlobalHistory
You need to log in before you can comment on or make changes to this bug.