Issue 6956 - Move extension's style sheet generation into core

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 /**
  * @fileOverview Element hiding implementation.
  */
 
 const {ElemHideExceptions} = require("./elemHideExceptions");
 const {filterNotifier} = require("./filterNotifier");
 
 /**
+ * The maximum number of selectors in a CSS rule. This is used by
+ * <code>{@link createStyleSheet}</code> to split up a long list of selectors
+ * into multiple rules.
+ * @const {number}
+ * @default
+ */
+const selectorGroupSize = 1024;
+
+/**
  * Lookup table, active flag, by filter by domain.
  * (Only contains filters that aren't unconditionally matched for all domains.)
  * @type {Map.<string,Map.<Filter,boolean>>}
  */
 let filtersByDomain = new Map();
 
 /**
  * Lookup table, filter by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,Filter>}
@@ skipping 196 matching lines @@
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     if (!specificOnly)
       selectors = getUnconditionalSelectors().concat(selectors);
 
     return selectors;
   }
 };
+
+/**
+ * Splits a list of selectors into groups determined by the value of
+ * <code>{@link selectorGroupSize}</code>.
+ *
+ * @param {Array.<string>} selectors
+ * @yields {Array.<string>}
+ */
+function* splitSelectors(selectors)
+{
+  // Chromium's Blink engine supports only up to 8,192 simple selectors, and
+  // even fewer compound selectors, in a rule. The exact number of selectors
+  // that would work depends on their sizes (e.g. "#foo .bar" has a size of 2).
+  // Since we don't know the sizes of the selectors here, we simply split them
+  // into groups of 1,024, based on the reasonable assumption that the average
+  // selector won't have a size greater than 8. The alternative would be to
+  // calculate the sizes of the selectors and divide them up accordingly, but
+  // this approach is more efficient and has worked well in practice. In theory
+  // this could still lead to some selectors not working on Chromium, but it is
+  // highly unlikely.
+  // See issue #6298 and https://crbug.com/804179
+  for (let i = 0; i < selectors.length; i += selectorGroupSize)
+    yield selectors.slice(i, i + selectorGroupSize);
+}
+
+/**
+ * Creates element hiding CSS rules for a given list of selectors. Each rule
+ * contains no more than the maximum number of selectors as determined by the
+ * value of <code>{@link selectorGroupSize}</code>.
+ *
+ * @param {Array.<string>} selectors
+ * @yields {string}
+ */
+function* createRules(selectors)
+{
+  for (let selectorGroup of splitSelectors(selectors))

[Sebastian Noack, 2018/09/18 15:33:24]

Since splitSelectors() is only called from one code path (here), and isn't
exported either, why not just merge the logic of splitSelectors() and
createRules()?

[Manish Jethani, 2018/09/18 15:50:02]

I tried this and it seems to actually perform slightly worse. I think V8
optimizes smaller functions. Given that these two can be logically separated
(and there's no performance benefit of merging them), I'd rather leave it like
it is.

[Sebastian Noack, 2018/09/18 16:41:45]

V8 optimizes functions regardless of size, however, it only inlines small
functions. However, we could not only merge splitSelectors() and createRules()
but as well put the whole logic into createStyleSheet(). That way we'd get away
with neither using generators nor creating an array, avoiding a performance
penalty on older browser engines that don't optimize generators, as well as any
performance penalty caused by functions not being inlined by the JIT, and FWIW,
it will be less code as well.

[Manish Jethani, 2018/09/18 17:24:07]

There is a specific optimization in TurboFan called "small function" that marks
a function for compilation (not inlining) if it's small enough. Anyway, I'll
admit I don't know about the details.
OK, so I merged everything into one function and ran the test mentioned in the
issue comments. I opened 25 windows, 8 times (so the function was called 200
times).

All merged: 2328.1999970786273
Split up into three functions: 1946.2000061757863

I'm not really seeing any case for merging these three perfectly independent and
well documented functions.
Well, it will be one big function that is harder to grok than three small
functions that specialize in their individual tasks. I know that this is
subjective, but since there's no good case for performance here (except on older
browsers, which is still speculative), I'd say let's leave it as it is at least
for this change.

Regarding older browsers: where there's a tradeoff between older browsers and
either one of maintainability and mobile (latest V8), I would go for the latter.

[Sebastian Noack, 2018/09/18 17:40:54]

This appears rather odd to me. On which version of Chrome did you do that
benchmark? Mind also trying on Firefox at least?
Well, those 3 functions are trivial, and I might argue that it would even make
the code easier to understand to merge them (due to better code locality).
Of course, but I might disagree that splitting up this logic in 3 trivial
functions makes anything more maintainable, and at least test on current Chrome
stable (if you didn't yet) as well as on Firefox.

[Manish Jethani, 2018/09/18 17:47:46]

I did it on Chrome 71 (Canary). It's not going to be much different on stable
(version 69), but I'll try it out regardless. Also Firefox.

[Manish Jethani, 2018/09/18 19:51:57]

Alright, here we go.

The alternative version of the `createStyleSheet` function is this:

  function createStyleSheet(selectors)
  {
    let s = performance.now();
    let styleSheet = "";

     // Chromium's Blink engine supports only up to 8,192 simple selectors, and
    // even fewer compound selectors, in a rule. The exact number of selectors
    // that would work depends on their sizes (e.g. "#foo .bar" has a size of
2).
    // Since we don't know the sizes of the selectors here, we simply split them
    // into groups of 1,024, based on the reasonable assumption that the average
    // selector won't have a size greater than 8. The alternative would be to
    // calculate the sizes of the selectors and divide them up accordingly, but
    // this approach is more efficient and has worked well in practice. In
theory
    // this could still lead to some selectors not working on Chromium, but it
is
    // highly unlikely.
    // See issue #6298 and https://crbug.com/804179
    for (let i = 0; i < selectors.length; i += selectorGroupSize)
      styleSheet += selectors.slice(i, i + selectorGroupSize).join(", ") +
                    " {display: none !important;}\n";

    window.n += performance.now() - s;

    return styleSheet;
  }

You can comment out the `performance.now()` lines to make it pass the unit
tests.

On Chrome 69:

 - three functions with generators: 1743.899998255074
 - all merged: 2081.1999943107367

On Firefox 61:

 - three functions with generators: 838
 - all merged: 760

Given that most of our user base is on the latest version of V8, it's a
no-contest. Firefox will catch up. Also this is just a single run for Firefox
(whereas on Chrome I also did this on version 71 with similar results).

I encourage you to try it out yourself, for example on Firefox:

  for i in $(seq 25); do open -a firefox "http://example.com/?n=$i"; done

I did this 8 times, resulting in 200 calls to the function (no other windows
open).

At this point, considering this issue wasn't about optimizing these functions
but merely about copying them over in the first place, we should just land this
patch.

[Sebastian Noack, 2018/09/18 21:21:03]

I think the main target for any benchmark should always be the current stable
version. Sometimes there are bugs in Canary that might have a significant impact
on the performance, but once the bug has been fixed that performance benefit (or
penalty) will be gone.

On 2018/09/18 19:51:57, Manish Jethani wrote:
Thanks for benchmarking Chrome 69 and Firefox 61. I wouldn't argue for merging
the functions in order to trade in better performance on Firefox (and older
versions of Chrome) for worse performance on the current version of Chrome.
However, I might still argue that the code (now where I have seen how it would
look like), is simpler and easier to follow if those functions are merged, and
the performance benefit on Chrome is far from an order of magnitude, not to
mention that we cannot even explain where it comes from. Let's see what the
others say. If they disagree with me, I will not block this patch from landing.

[Manish Jethani, 2018/09/19 09:39:00]

A lot of the best programmers would disagree that one function doing multiple
things is easier to follow than multiple functions each doing one thing [1]

[1]:
https://softwareengineering.stackexchange.com/questions/308108/when-is-it-app...

But this is quite subjective. In any case, this is how I have always written
code. I can't even wrap my head around why one would want to _deliberately_
merge separate ideas composed of one another into one single idea. It's hard
enough to separate ideas in the first place; when they are already cleanly
separated, merging them back for no good reason doesn't make any sense to me. In
this case, for example, each of the functions has its own documentation that
clearly states what the function does.
As an aside, try `node --trace-opt` with any program to see which functions are
being optimized and why.

I tried this:

  let selectors = [];
  for (let i = 0; i < 20000; i++)
    selectors.push(".s" + i);

  let n = 100000;

  for (let i = 0; i < n; i++)
  {
    setTimeout(() =>
    {
      createStyleSheet(selectors);
    },
    Math.ceil(Math.random() * n));
  }

All three of `createStyleSheet`, `createRules`, and `splitSelectors` are
optimized because they're "hot and stable".
Fair enough.

[Manish Jethani, 2018/09/19 10:18:33]

Since I was modifying the `createStyleSheet` function itself to take the
performance measurements, I tried testing it a different way this time, by
adding the performance measurement code in the calling code
(adblockpluschrome/lib/contentFiltering.js):

  if (selectors.length > 0)
  {
    let startTime = performance.now();
    styleSheet = createStyleSheet(selectors);
    window.timeTaken += performance.now() - startTime;
  }

I ran the tests again.

Yup, it's settled. The version with three small functions is faster by ~20%
hands down.

[Manish Jethani, 2018/09/19 10:29:08]

Also:
https://arstechnica.com/information-technology/2013/08/ask-stack-is-it-ok-to-...

[Sebastian Noack, 2018/09/19 11:05:53]

I'm obviously not trying to argue that functions should generally be avoided and
that code should always be inlined if possible. But an algorithm that would
result into 6 lines of code if implemented in a single function, hardly calls
for being split up into 3 functions.

For reference, this is how a prime number checker would look like following your
practice:

  function* generateNumbers(start, stop)
  {
    for (let i = start; i < stop; i++)
      yield i;
  }

  function isDividable(divident, divisor)
  {
    return dividend % divisor == 0;
  }

  function isValid(num)
  {
    return num != 0 && num != 1;
  }

  function isPrime(num) {
    for (let i of generateNumbers(2, num))
      if (isDividable(num, i)) return false;
    return isValid(num);
  }

Is this any more readable than if you'd merge those functions? It's not, because
now when following the code execution path you have to jump from one function to
another going up and down in the source file, while the complexity split out is
trivial, so that it would be easier to read the code in place rather than
following function calls. IMO, this is exactly the same with the code here.

If it's really faster (on the current version of Chrome) when splitting up the
code like that, this is another story, but still a mystery to me. Just one more
idea why that might be: Perhaps it performs better if you move that long comment
out of the function body. I remember that V8 determines what a small function
(subject to particular optimizations) is among others based on the number of
characters in the function body.

[Manish Jethani, 2018/09/19 13:14:41]

If they are logically separate (as in, the programmer thinks of them as separate
operations), then why not? It should not depend on the number of lines of code.
This would be fine if it's a program for children to learn programming. It
depends on the context, to a great extent.
Well it seems more readable to me this way, maybe because I'm already looking
ahead to what we're going to do here to deduplicate the style sheet/rules.

Anyway, I've got a new idea for how to optimize the style sheets, and indeed we
may be maintaining a cache of the first 7 out of the 8-10 selector groups
(20,000 selectors / 1,024 group size), in which case this function would get
larger with more logic and then it's better to split it up into specialized
functions.
I thought maybe that was the case, maybe it is after all. But I also know that
the new V8 (TurboFan) doesn't take comments into account when deciding the size
of the function.

[Jon Sonesen, 2018/09/19 16:36:26]

FWIW I would say that Manish is right about context for splitting functions.
This depends on the complexity for sure. As an anecdote, I find Manish's
approach much easier when trying to learn a new or newish code base and that
having functions which combine multiple algorithms to make larger functions are
not very easy to learn from.

IMO one reason is that in a well documented code base where each function is
required to contain jsdoc strings, breaking a specific algorithm/s from a larger
function will illicit some level of documentation to be written about said
algorithm. This is helpful for someone like myself who has programming knowledge
but may be newer to the language.

 So if your goal is to make code *easier* to read for programmers then having a
single function makes sense. Conversely, if your goal is to make code more *time
efficient* to read for a newbie, splitting and documenting algorithms used by a
function is the preferable course.

My preference is for better documentation in general, so I think that splitting
certain functions is preferable. Especially if the algorithm makes significant
changes to data structures since it is much easier to know if you are going to
have side effects from a change if you don't have the one line that causes the
side effect buried in a 50-60 line function.

+    yield selectorGroup.join(", ") + " {display: none !important;}";
+}
+
+/**
+ * Creates an element hiding CSS style sheet from a given list of selectors.
+ * @param {Array.<string>} selectors
+ * @returns {string}
+ */
+function createStyleSheet(selectors)
+{
+  let styleSheet = "";
+
+  for (let rule of createRules(selectors))
+    styleSheet += rule + "\n";
+
+  return styleSheet;
+}
+
+exports.createStyleSheet = createStyleSheet;