Skip to content

Commit 2a02a71

Browse files
semenkosemenko
committed
The function "potentiallyApplicableRulesets" is hot, and its results are stable.
From profiling, this is *very* slow, and it's easy to see why. The calls look like: Loading www.nytimes.com -> Load every image (20+ images at graphics8.nytimes.com) Call potentiallyApplicableRulesets every time Return the same result every time :( Let's use a simple LRU cache to store those results. This adds the MIT-licensed LRU cache from: https://github.com/rsms/js-lru The cache isn't persistent (it's in memory, not LocalStorage or elsewhere), so we don't have to worry about stale data when the extension updates. Signed-off-by: Nick Semenkovich <semenko@alum.mit.edu>
1 parent 95c8ed3 commit 2a02a71

File tree

3 files changed

+268
-0
lines changed

3 files changed

+268
-0
lines changed

‎chromium/lru.js‎

Lines changed: 251 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,251 @@
1+
/**
2+
* A doubly linked list-based Least Recently Used (LRU) cache. Will keep most
3+
* recently used items while discarding least recently used items when its limit
4+
* is reached.
5+
*
6+
* Licensed under MIT. Copyright (c) 2010 Rasmus Andersson <http://hunch.se/>
7+
* See README.md for details.
8+
*
9+
* Illustration of the design:
10+
*
11+
* entry entry entry entry
12+
* ______ ______ ______ ______
13+
* | head |.newer => | |.newer => | |.newer => | tail |
14+
* | A | | B | | C | | D |
15+
* |______| <= older.|______| <= older.|______| <= older.|______|
16+
*
17+
* removed <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- added
18+
*/
19+
function LRUCache (limit) {
20+
// Current size of the cache. (Read-only).
21+
this.size = 0;
22+
// Maximum number of items this cache can hold.
23+
this.limit = limit;
24+
this._keymap = {};
25+
}
26+
27+
/**
28+
* Put <value> into the cache associated with <key>. Returns the entry which was
29+
* removed to make room for the new entry. Otherwise undefined is returned
30+
* (i.e. if there was enough room already).
31+
*/
32+
LRUCache.prototype.put = function(key, value) {
33+
var entry = {key:key, value:value};
34+
// Note: No protection agains replacing, and thus orphan entries. By design.
35+
this._keymap[key] = entry;
36+
if (this.tail) {
37+
// link previous tail to the new tail (entry)
38+
this.tail.newer = entry;
39+
entry.older = this.tail;
40+
} else {
41+
// we're first in -- yay
42+
this.head = entry;
43+
}
44+
// add new entry to the end of the linked list -- it's now the freshest entry.
45+
this.tail = entry;
46+
if (this.size === this.limit) {
47+
// we hit the limit -- remove the head
48+
return this.shift();
49+
} else {
50+
// increase the size counter
51+
this.size++;
52+
}
53+
};
54+
55+
/**
56+
* Purge the least recently used (oldest) entry from the cache. Returns the
57+
* removed entry or undefined if the cache was empty.
58+
*
59+
* If you need to perform any form of finalization of purged items, this is a
60+
* good place to do it. Simply override/replace this function:
61+
*
62+
* var c = new LRUCache(123);
63+
* c.shift = function() {
64+
* var entry = LRUCache.prototype.shift.call(this);
65+
* doSomethingWith(entry);
66+
* return entry;
67+
* }
68+
*/
69+
LRUCache.prototype.shift = function() {
70+
// todo: handle special case when limit == 1
71+
var entry = this.head;
72+
if (entry) {
73+
if (this.head.newer) {
74+
this.head = this.head.newer;
75+
this.head.older = undefined;
76+
} else {
77+
this.head = undefined;
78+
}
79+
// Remove last strong reference to <entry> and remove links from the purged
80+
// entry being returned:
81+
entry.newer = entry.older = undefined;
82+
// delete is slow, but we need to do this to avoid uncontrollable growth:
83+
delete this._keymap[entry.key];
84+
}
85+
return entry;
86+
};
87+
88+
/**
89+
* Get and register recent use of <key>. Returns the value associated with <key>
90+
* or undefined if not in cache.
91+
*/
92+
LRUCache.prototype.get = function(key, returnEntry) {
93+
// First, find our cache entry
94+
var entry = this._keymap[key];
95+
if (entry === undefined) return; // Not cached. Sorry.
96+
// As <key> was found in the cache, register it as being requested recently
97+
if (entry === this.tail) {
98+
// Already the most recenlty used entry, so no need to update the list
99+
return entry.value;
100+
}
101+
// HEAD--------------TAIL
102+
// <.older .newer>
103+
// <--- add direction --
104+
// A B C <D> E
105+
if (entry.newer) {
106+
if (entry === this.head)
107+
this.head = entry.newer;
108+
entry.newer.older = entry.older; // C <-- E.
109+
}
110+
if (entry.older)
111+
entry.older.newer = entry.newer; // C. --> E
112+
entry.newer = undefined; // D --x
113+
entry.older = this.tail; // D. --> E
114+
if (this.tail)
115+
this.tail.newer = entry; // E. <-- D
116+
this.tail = entry;
117+
return returnEntry ? entry : entry.value;
118+
};
119+
120+
// ----------------------------------------------------------------------------
121+
// Following code is optional and can be removed without breaking the core
122+
// functionality.
123+
124+
/**
125+
* Check if <key> is in the cache without registering recent use. Feasible if
126+
* you do not want to chage the state of the cache, but only "peek" at it.
127+
* Returns the entry associated with <key> if found, or undefined if not found.
128+
*/
129+
LRUCache.prototype.find = function(key) {
130+
return this._keymap[key];
131+
};
132+
133+
/**
134+
* Update the value of entry with <key>. Returns the old value, or undefined if
135+
* entry was not in the cache.
136+
*/
137+
LRUCache.prototype.set = function(key, value) {
138+
var oldvalue, entry = this.get(key, true);
139+
if (entry) {
140+
oldvalue = entry.value;
141+
entry.value = value;
142+
} else {
143+
oldvalue = this.put(key, value);
144+
if (oldvalue) oldvalue = oldvalue.value;
145+
}
146+
return oldvalue;
147+
};
148+
149+
/**
150+
* Remove entry <key> from cache and return its value. Returns undefined if not
151+
* found.
152+
*/
153+
LRUCache.prototype.remove = function(key) {
154+
var entry = this._keymap[key];
155+
if (!entry) return;
156+
delete this._keymap[entry.key]; // need to do delete unfortunately
157+
if (entry.newer && entry.older) {
158+
// relink the older entry with the newer entry
159+
entry.older.newer = entry.newer;
160+
entry.newer.older = entry.older;
161+
} else if (entry.newer) {
162+
// remove the link to us
163+
entry.newer.older = undefined;
164+
// link the newer entry to head
165+
this.head = entry.newer;
166+
} else if (entry.older) {
167+
// remove the link to us
168+
entry.older.newer = undefined;
169+
// link the newer entry to head
170+
this.tail = entry.older;
171+
} else {// if(entry.older === undefined && entry.newer === undefined) {
172+
this.head = this.tail = undefined;
173+
}
174+
175+
this.size--;
176+
return entry.value;
177+
};
178+
179+
/** Removes all entries */
180+
LRUCache.prototype.removeAll = function() {
181+
// This should be safe, as we never expose strong refrences to the outside
182+
this.head = this.tail = undefined;
183+
this.size = 0;
184+
this._keymap = {};
185+
};
186+
187+
/**
188+
* Return an array containing all keys of entries stored in the cache object, in
189+
* arbitrary order.
190+
*/
191+
if (typeof Object.keys === 'function') {
192+
LRUCache.prototype.keys = function() { return Object.keys(this._keymap); };
193+
} else {
194+
LRUCache.prototype.keys = function() {
195+
var keys = [];
196+
for (var k in this._keymap) keys.push(k);
197+
return keys;
198+
};
199+
}
200+
201+
/**
202+
* Call `fun` for each entry. Starting with the newest entry if `desc` is a true
203+
* value, otherwise starts with the oldest (head) enrty and moves towards the
204+
* tail.
205+
*
206+
* `fun` is called with 3 arguments in the context `context`:
207+
* `fun.call(context, Object key, Object value, LRUCache self)`
208+
*/
209+
LRUCache.prototype.forEach = function(fun, context, desc) {
210+
var entry;
211+
if (context === true) { desc = true; context = undefined; }
212+
else if (typeof context !== 'object') context = this;
213+
if (desc) {
214+
entry = this.tail;
215+
while (entry) {
216+
fun.call(context, entry.key, entry.value, this);
217+
entry = entry.older;
218+
}
219+
} else {
220+
entry = this.head;
221+
while (entry) {
222+
fun.call(context, entry.key, entry.value, this);
223+
entry = entry.newer;
224+
}
225+
}
226+
};
227+
228+
/** Returns a JSON (array) representation */
229+
LRUCache.prototype.toJSON = function() {
230+
var s = [], entry = this.head;
231+
while (entry) {
232+
s.push({key:entry.key.toJSON(), value:entry.value.toJSON()});
233+
entry = entry.newer;
234+
}
235+
return s;
236+
};
237+
238+
/** Returns a String representation */
239+
LRUCache.prototype.toString = function() {
240+
var s = '', entry = this.head;
241+
while (entry) {
242+
s += String(entry.key)+':'+entry.value;
243+
entry = entry.newer;
244+
if (entry)
245+
s += ' < ';
246+
}
247+
return s;
248+
};
249+
250+
// Export ourselves
251+
if (typeof this === 'object') this.LRUCache = LRUCache;

‎chromium/manifest.json‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
"scripts": [
77
"util.js",
88
"URI.js",
9+
"lru.js",
910
"rule_list.js",
1011
"rules.js",
1112
"background.js"

‎chromium/rules.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
// A cache for potentiallyApplicableRulesets
2+
// Size chosen /completely/ arbitrarily.
3+
var ruleCache = new LRUCache(2048);
4+
15
function Rule(from, to) {
26
//this.from = from;
37
this.to = to;
@@ -176,6 +180,15 @@ RuleSets.prototype = {
176180

177181
potentiallyApplicableRulesets: function(host) {
178182
// Return a list of rulesets that apply to this host
183+
184+
// Have we cached this result? If so, return it!
185+
var cached_item = ruleCache.get(host);
186+
if (cached_item !== undefined) {
187+
log(DBUG, "Rulseset cache hit for " + host);
188+
return cached_item;
189+
}
190+
log(DBUG, "Ruleset cache miss for " + host);
191+
179192
var i, tmp, t;
180193
var results = this.global_rulesets.slice(0); // copy global_rulesets
181194
if (this.targets[host])
@@ -201,6 +214,9 @@ RuleSets.prototype = {
201214
else
202215
for (var i = 0; i < results.length; ++i)
203216
log(DBUG, " " + results[i].name);
217+
218+
// Insert results into the ruleset cache
219+
ruleCache.set(host, results);
204220
return results;
205221
},
206222

0 commit comments

Comments
 (0)