Issue 29719569: Issue 6467 - Use Map object for caching filter matches (Closed)
|
Created:
March 10, 2018, 3:30 p.m. by Manish Jethani Modified:
March 13, 2018, 2:40 p.m. CC:
hub Base URL:
https://hg.adblockplus.org/adblockpluscore/ Visibility:
Public. |
DescriptionSee issue description at https://issues.adblockplus.org/ticket/6467
Patch Set 1 #
Total comments: 11
Patch Set 2 : Use typeof #MessagesTotal messages: 9
Patch Set 1 https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (left): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#oldc... lib/matcher.js:282: * Number of entries in resultCache There's no need for cacheEntries anymore. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:302: this.resultCache.clear(); We don't have to check the size here because we're not creating a new object. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) Assumption: an entry will never have a value of undefined. I checked and we're not setting the value to undefined (directly or indirectly) anywhere. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:420: if (this.resultCache.size >= CombinedMatcher.maxCacheEntries) Again, we don't have to create a new object every time we hit the cache size limit.
Could you please file the issue for it and move that long description with profiling into the issue? I played with those tests from the description locally and the difference between two approaches is not so sensitive, though it's clear that it's indeed an optimization. BTW, as I expected, around 80% of time is consumed to generate a random number, it would be better to reorganize the tests and exclude such slow operations. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:302: this.resultCache.clear(); On 2018/03/10 15:54:37, Manish Jethani wrote: > We don't have to check the size here because we're not creating a new object. I'm pretty sure that now it's even faster, tough if someone wants I will be very interested in the profiling results. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) On 2018/03/10 15:54:37, Manish Jethani wrote: > Assumption: an entry will never have a value of undefined. I checked and we're > not setting the value to undefined (directly or indirectly) anywhere. AFAIK our coding style says to rather use `typeof result != "undefined"`, though I find `result !== undefined` better. Let's discuss it in #eyeo-js.
On 2018/03/12 12:03:01, sergei wrote: > Could you please file the issue for it and move that long description with > profiling into the issue? Done. https://issues.adblockplus.org/ticket/6467 > I played with those tests from the description locally and the difference > between two approaches is not so sensitive, though it's clear that it's indeed > an optimization. Yes, it's more optimal and also cleaner (also consistent with the rest of the code in the same file which use Map objects). > BTW, as I expected, around 80% of time is consumed to generate > a random number, it would be better to reorganize the tests and exclude such > slow operations. Let me try that. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) On 2018/03/12 12:03:01, sergei wrote: > On 2018/03/10 15:54:37, Manish Jethani wrote: > > Assumption: an entry will never have a value of undefined. I checked and we're > > not setting the value to undefined (directly or indirectly) anywhere. > > AFAIK our coding style says to rather use `typeof result != "undefined"`, though > I find `result !== undefined` better. Let's discuss it in #eyeo-js. This is really not about coding style. The cache can have a legitimate entry with a value of null, which is equal to undefined using non-strict equality. If we want to find out if the cache actually has no entry for the given key, we have to compare with undefined using strict equality. The alternative would be to use Map.has but then we'd be doing an extra lookup, which is what I find is unnecessary.
On 2018/03/12 13:42:42, Manish Jethani wrote: > On 2018/03/12 12:03:01, sergei wrote: > > > > BTW, as I expected, around 80% of time is consumed to generate > > a random number, it would be better to reorganize the tests and exclude such > > slow operations. > > Let me try that. I've updated the issue description now with the random key generation moved out of the test loop. The new before and after times on my machine are ~4 seconds and ~900 milliseconds respectively.
On 2018/03/12 13:52:51, Manish Jethani wrote: > On 2018/03/12 13:42:42, Manish Jethani wrote: > > On 2018/03/12 12:03:01, sergei wrote: > > > > > > BTW, as I expected, around 80% of time is consumed to generate > > > a random number, it would be better to reorganize the tests and exclude such > > > slow operations. > > > > Let me try that. > > I've updated the issue description now with the random key generation moved out > of the test loop. The new before and after times on my machine are ~4 seconds > and ~900 milliseconds respectively. Yep, it's closer to my observations, additionally I have manually subtracted the time of looping by running the loop without `if (key in cache)`. https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) On 2018/03/12 13:42:42, Manish Jethani wrote: > On 2018/03/12 12:03:01, sergei wrote: > > On 2018/03/10 15:54:37, Manish Jethani wrote: > > > Assumption: an entry will never have a value of undefined. I checked and > we're > > > not setting the value to undefined (directly or indirectly) anywhere. > > > > AFAIK our coding style says to rather use `typeof result != "undefined"`, > though > > I find `result !== undefined` better. Let's discuss it in #eyeo-js. > > This is really not about coding style. The cache can have a legitimate entry > with a value of null, which is equal to undefined using non-strict equality. If > we want to find out if the cache actually has no entry for the given key, we > have to compare with undefined using strict equality. > > The alternative would be to use Map.has but then we'd be doing an extra lookup, > which is what I find is unnecessary. Please take a look around in this file, whenever one could use `!== undefined`, `typeof ...` is used. In addition typeof does not conflict with having null values because `typeof null` is "object". BTW, currently I cannot find that in the coding style but I'm pretty sure that it was there because I had written the same code several times and several times someone told me about that.
Patch Set 2: Use typeof https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) On 2018/03/12 17:48:31, sergei wrote: > On 2018/03/12 13:42:42, Manish Jethani wrote: > > On 2018/03/12 12:03:01, sergei wrote: > > > On 2018/03/10 15:54:37, Manish Jethani wrote: > > > > Assumption: an entry will never have a value of undefined. I checked and > > we're > > > > not setting the value to undefined (directly or indirectly) anywhere. > > > > > > AFAIK our coding style says to rather use `typeof result != "undefined"`, > > though > > > I find `result !== undefined` better. Let's discuss it in #eyeo-js. > > > > This is really not about coding style. The cache can have a legitimate entry > > with a value of null, which is equal to undefined using non-strict equality. > If > > we want to find out if the cache actually has no entry for the given key, we > > have to compare with undefined using strict equality. > > > > The alternative would be to use Map.has but then we'd be doing an extra > lookup, > > which is what I find is unnecessary. > > Please take a look around in this file, whenever one could use `!== undefined`, > `typeof ...` is used. In addition typeof does not conflict with having null > values because `typeof null` is "object". > > BTW, currently I cannot find that in the coding style but I'm pretty sure that > it was there because I had written the same code several times and several times > someone told me about that. Done.
LGTM https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) On 2018/03/12 18:59:21, Manish Jethani wrote: > On 2018/03/12 17:48:31, sergei wrote: > > On 2018/03/12 13:42:42, Manish Jethani wrote: > > > On 2018/03/12 12:03:01, sergei wrote: > > > > On 2018/03/10 15:54:37, Manish Jethani wrote: > > > > > Assumption: an entry will never have a value of undefined. I checked and > > > we're > > > > > not setting the value to undefined (directly or indirectly) anywhere. > > > > > > > > AFAIK our coding style says to rather use `typeof result != "undefined"`, > > > though > > > > I find `result !== undefined` better. Let's discuss it in #eyeo-js. > > > > > > This is really not about coding style. The cache can have a legitimate entry > > > with a value of null, which is equal to undefined using non-strict equality. > > If > > > we want to find out if the cache actually has no entry for the given key, we > > > have to compare with undefined using strict equality. > > > > > > The alternative would be to use Map.has but then we'd be doing an extra > > lookup, > > > which is what I find is unnecessary. > > > > Please take a look around in this file, whenever one could use `!== > undefined`, > > `typeof ...` is used. In addition typeof does not conflict with having null > > values because `typeof null` is "object". > > > > BTW, currently I cannot find that in the coding style but I'm pretty sure that > > it was there because I had written the same code several times and several > times > > someone told me about that. > > Done. I still think we should discuss whether we use typeof == "undefined" or !== undefined in IRC.
On 2018/03/13 13:56:41, sergei wrote: > LGTM Thanks! https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js File lib/matcher.js (right): https://codereview.adblockplus.org/29719569/diff/29719570/lib/matcher.js#newc... lib/matcher.js:414: if (result !== undefined) On 2018/03/13 13:56:41, sergei wrote: > On 2018/03/12 18:59:21, Manish Jethani wrote: > > On 2018/03/12 17:48:31, sergei wrote: > > > On 2018/03/12 13:42:42, Manish Jethani wrote: > > > > On 2018/03/12 12:03:01, sergei wrote: > > > > > On 2018/03/10 15:54:37, Manish Jethani wrote: > > > > > > Assumption: an entry will never have a value of undefined. I checked > and > > > > we're > > > > > > not setting the value to undefined (directly or indirectly) anywhere. > > > > > > > > > > AFAIK our coding style says to rather use `typeof result != > "undefined"`, > > > > though > > > > > I find `result !== undefined` better. Let's discuss it in #eyeo-js. > > > > > > > > This is really not about coding style. The cache can have a legitimate > entry > > > > with a value of null, which is equal to undefined using non-strict > equality. > > > If > > > > we want to find out if the cache actually has no entry for the given key, > we > > > > have to compare with undefined using strict equality. > > > > > > > > The alternative would be to use Map.has but then we'd be doing an extra > > > lookup, > > > > which is what I find is unnecessary. > > > > > > Please take a look around in this file, whenever one could use `!== > > undefined`, > > > `typeof ...` is used. In addition typeof does not conflict with having null > > > values because `typeof null` is "object". > > > > > > BTW, currently I cannot find that in the coding style but I'm pretty sure > that > > > it was there because I had written the same code several times and several > > times > > > someone told me about that. > > > > Done. > > I still think we should discuss whether we use typeof == "undefined" or !== > undefined in IRC. Yes, let's have that discussion. 
|
