Slow when HTML + CSS is large

[peterbe]

When I run:

▶ time node bin/minimalcss.js https://www.peterbe.com/plog-original.html -o /dev/null

It steadily takes about 6-7 seconds. That's way too slow. Let's see what we can do.

[peterbe]

One thing I noticed was that there are a lot of low hanging fruit of re-using the "decision cache" if we just try to be a little smarter:

For example, that monster of a CSS file contains this:

.highlight .hll
.highlight
.highlight .c
.highlight .err
.highlight .k
.highlight .o
.highlight .cm
.highlight .cp
.highlight .c1
.highlight .cs
.highlight .gd
.highlight .ge
.highlight .gr
.highlight .gh
.highlight .gi
.highlight .go
.highlight .gp
.highlight .gs
...

There are about 60 of those. I know for a fact that there is document.querySelectorAll('.highlight').length===0 on that DOM. With that in mind there is no point trying document.querySelectorAll('.highlight .c') or document.querySelectorAll('.highlight .err'), etc.

One way to figure that out would be something like this:

if (selectorAsString.includes(' ')) {
  selectorParentAsString = selectorAsString.split(' ').slice(0, selectorAsString.split(' ').length - 1).join(' ');
  if (selectorParentAsString in decisionsCache) {
    if (!decisionsCache[selectorParentAsString]) {
      // No point continuing on!
      return false; // or, whatever we do when decide to NOT include it. 
    }
  }
}

[peterbe]

Another thing I noticed was that, for this CSS, the function reduceCSSSelector was called 4,449 of which 377 are repeated. A simple memoize would fix that.

[peterbe]

Bah! I implemented a solution. It looks like this:

            const selectorParentString = utils.selectorParentString(
              selectorString
            );
            if (selectorParentString !== null) {
              // Only proceed if the selector did have a parent.
              // E.g. selectorString was '.foo .bar'.
              // Now we can see if the decision cache has already concluded
              // that there is no '.foo' because if that's the case there's
              // no point proceeding to checking '.foo .bar'.
              if (selectorParentString in decisionsCache === false) {
                decisionsCache[
                  selectorParentString
                ] = isSelectorMatchToAnyElement(selectorParentString);
              }
              if (!decisionsCache[selectorParentString]) {
                // Indeeed! The parent was in the cache and it was concluded
                // that it is not matched to any element.
                decisionsCache[selectorString] = false;
              }
            }

I measured how many times the critical call gets called and the number went from 3,281 down to 2,793 and it didn't appear to make any difference in the total processing time.

[peterbe]

So I experimented with three different scenarios. Ran it a bunch of times:

1. master branch untouched:

real	0m6.418s
user	0m3.956s
sys	0m0.267s

real	0m6.220s
user	0m3.767s
sys	0m0.255s

real	0m6.827s
user	0m4.296s
sys	0m0.288s

real	0m6.890s
user	0m4.260s
sys	0m0.281s

real	0m7.077s
user	0m4.526s
sys	0m0.291s

real	0m6.078s
user	0m3.612s
sys	0m0.262s

2. master branch but replace return dom(selectorString).length > 0; with return false:

real	0m3.804s
user	0m1.109s
sys	0m0.220s

real	0m3.568s
user	0m1.111s
sys	0m0.224s

real	0m3.715s
user	0m1.073s
sys	0m0.209s

real	0m3.704s
user	0m1.074s
sys	0m0.212s

real	0m3.752s
user	0m1.121s
sys	0m0.209s

real	0m3.762s
user	0m1.114s
sys	0m0.211s

3. My experimental branch with the selectorParentString hack and some memoizations:

real	0m5.979s
user	0m3.269s
sys	0m0.263s

real	0m5.991s
user	0m3.440s
sys	0m0.272s

real	0m5.694s
user	0m3.217s
sys	0m0.251s

real	0m6.086s
user	0m3.435s
sys	0m0.281s

real	0m5.790s
user	0m3.197s
sys	0m0.255s

real	0m5.634s
user	0m3.123s
sys	0m0.250s

Squintig at those numbers; it seems my hack gives us a 0.5 second speed boost. Not impressive. Need to find out what's really causing it to slow down.

[peterbe]

Actually, I found that I can avoid even more expensive calls by splitting on ancestor selector too! E.g. from .ui.dropdown>.text to .ui.dropdown.
That reduced the total number of selectors that needs to be checked from 4,449 to 2,599.

[peterbe]

Hoping that cheerio has a faster way to find out if an element exists at all: cheeriojs/cheerio#1265

[peterbe]

@lahmatiy Hey, chatting here instead of Twitter.

I did some experiments and noticed that for a large CSS frameworks like Sematic-UI there are a LOT of CSS selectors like this:

.ui.comments > .reply.form {
  margin-top: 1em;
}
.ui.comments .comment .reply.form {
  width: 100%;
  margin-top: 1em;
}
.ui.comments .reply.form textarea {
  font-size: 1em;
  height: 12em;
}

So instead of doing document.querySelector('.ui.comments > .reply.form') and document.querySelector('.ui.comments .comment .reply.form') and document.querySelector('.ui.comments .reply.form textarea') (3 calls), I can just do this: document.querySelector('.ui.comments') and if that is falsy I can know there's no point bothering with .ui.comments ....

I store all lookups in an object. I call it the "decision cache". That helps me avoid doing too many document.querySelector(...) calls. E.g.

// Pseudo code
const decisions = {};

if (!document.querySelector('.ui.comments')) {
  decisions['.ui.comments > .reply.form'] = false;
  decisions['.ui.comments .comment .reply.form'] = false;
  decisions['.ui.comments .reply.form textarea'] = false;
}

At first I just did this: selector.split(/[>\s]+/); but that's too naive. For example, it totally doesn't work if the CSS seletor is .ui[class*='mobile reversed'].grid > .row. Hence my question in Twitter :)

[leeoniya]

hey @peterbe

thought you might be interested in a similar project of mine: https://github.com/leeoniya/dropcss

I also originally started with CSSTree, plus css-select and node-html-parser but could not get the performance i was expecting - a lot more back-story here: https://old.reddit.com/r/javascript/comments/bb7im2/dropcss_v100_an_exceptionally_fast_thorough_and/

it doesnt require Puppeteer, though you can easily use it if you need JS execution. i tried sending your html [1] and css [2] through and it finished in 130ms (no, that's not a typo). i originally came to give some advice, but then realized that there are optimizations all the way through the whole architecture of DropCSS (for which i had to ditch all deps), so i'm not sure how much it would help here : (

cheers!

[1] https://www.peterbe.com/plog-original.html
[2] https://www.peterbe.com/static/css/base.min.79787297dbf5.css

[peterbe]

I've been thinking, the puppeteer piece is ultimately just to get the DOM in the form of HTML. Suppose you already have the HTML as a string, how would minimalcss stack up?

On Fri, Apr 12, 2019 at 9:08 PM Leon Sorokin ***@***.***> wrote: hey @peterbe <https://github.com/peterbe> thought you might be interested in a similar project of mine: https://github.com/leeoniya/dropcss I also originally started with CSSTree, plus css-select <https://github.com/fb55/css-select> and node-html-parser <https://github.com/taoqf/node-html-parser> but could not get the performance i was expecting - a lot more back-story here: https://old.reddit.com/r/javascript/comments/bb7im2/dropcss_v100_an_exceptionally_fast_thorough_and/ it doesnt require Puppeteer, though you can easily use it <https://github.com/leeoniya/dropcss#javascript-execution> if you need JS execution. i ran tried sending your html [1] and css [2] through and it finished in 130ms (no, that's not a typo). i originally came to give some advice, but then realized that there are optimizations all the way through the whole architecture of DropCSS (for which i had to ditch all deps), so i'm not sure how much it would help here : ( cheers! [1] https://www.peterbe.com/plog-original.html [2] https://www.peterbe.com/static/css/base.min.79787297dbf5.css — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#287 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AABoczyudRj1S0y04KDATsQJx0_Kf4xnks5vgS30gaJpZM4Zlost> .

-- Peter Bengtsson Mozilla Services Engineering https://www.peterbe.com

[lahmatiy]

@peterbe You already parse a selector to AST, so you can split the selector (node list) by the first combinator if any, and then translate it to a string. You also can normalize a compound selector (e.g. .foo.bar and .bar.foo may became the same) and filter some parts (e.g. pseudos). I can write a code later if you need a help with it.

@leeoniya Did you try to switch off detailed parsing (anything except selectors)? It can boost CSS parsing.
To be honest, writing a CSS parser is not as simple as it looks like at first glance. Currently your solution fails in many cases. Some issues I found: https://codepen.io/anon/pen/zXdjNY). And that’s excluding escaping, string values in attribute selectors and content property, custom properties values, features that are coming soon (have no support by some or all browsers currently, e.g. :not(<selector-list>), nth-*(... of <selector-list>), :has(), :where(), nested rules etc). I believe that correctness should be over performance.

[leeoniya]

@lahmatiy

Did you try to switch off detailed parsing (anything except selectors)? It can boost CSS parsing.

yes i turned off a bunch or prelude parsing, and i used only visit: rule, you can see the earlier versions of DropCSS in its commit history/releases before v0.5.0. i don't think the parsing itself was the bottleneck, though it certainly helps to do it faster with much smaller data structures and less mem allocation. reducing the exponential growth of testing every selector against every html node obviously the major optimization - DropCSS has a similar decision cache for this.

Currently your solution fails in many cases. Some issues I found: https://codepen.io/anon/pen/zXdjNY).

i'll have to dig through that list and see what's worth handling, thanks!

And that’s excluding escaping, string values in attribute selectors and content property, custom properties values, features that are coming soon (have no support by some or all browsers currently, e.g. :not(), nth-*(... of ), :has(), :where(), nested rules etc).

the goal of DropCSS was to support the 99% use case, as is stated in the README. i've run it through my own CSS/HTML for several sizeable projects in addition to Bootstrap, Materialize, Semantic UI, Bulma, (and Tailwind with some meh pre-processing). That's a pretty wide swath of real-world cases. certainly it's easy to construct artificial but valid cases that trip it up, but this is design choice rather than an oversight.

I believe that correctness should be over performance.

for CSSTree - a CSS parser - of course correctness is number one, no one is arguing that :)

i'm excited to see how fast, thorough and compact you guys can get minimalcss while being fully spec compliant (both for html and css parsing).