Slick.match is SLOW

[markiz]

Walking over whole DOM to look for a selector match is an overkill.

There're at least two better solutions:

1. Launch the search from the given NODE over the REVERSED selector with cut off first part (it usually looks like * !~ ) -- saves ~50% of time in my benchmark. If it matches anything -- selector does what we want to.
   • Pros: no problems with compatibility
2. Write a separate matcher or find a way to reuse existing finders (though, I couldn't figure it out myself)
   • Pros: the fastest way -- saves ~75% of time in my benchmark
   • Cons: not so DRY

I've got some code but it's very-very dirty (I'm not a js-er, actually) but I can add it as a proof of concept via gist if you need.

WDYT?

[markiz]

https://gist.github.com/740386 -- threw up a gist. I know you could write it better but that's the basic idea.

[subtleGradient]

Yep, you discovered our secret, you win this awesome iPhone emoticon: 

Seriously though, Slick.js is only at 1.0. In order to get it released on time we purposefully chose to focus our efforts on the selectors first. We are planning to greatly awesomize the marcher for Slick.js 1.1.0 or whatever our next major release is.

[subtleGradient]

Well, it's not like we didn't think about the marcher at all. We constricted the innards of Slick.js to have the raw power needed to get the awesome matcher working later.

[fabiomcosta]

Dude thanks! awesome to see that. I need time to go deep into this.

Looks like you've got some great ideas for the project, would love to see more of them.

Please be patient cause gonna need sometime to see what's the best way to integrate this into the code.

Cya around.

[fabiomcosta]

Hi i've improved the matcher by using the native matchesSeletor function from the browser. Check it out and see what you guys think:

fabiomcosta@7b6e897

I would like to give credits to @mattcoz who helped on this implementation.

[fabiomcosta]

By the way, markiz, the problem with your implementation is that it doesnt cover all the reverse combinators nor all the regular combinators by now, but it looks promissing.

[markiz]

Yeah, my implementation honestly sucks; I just needed to make sure I'm right and matching should go faster :p

[qbolec]

I was thinking today about the same issue and found this thread.
I like the simplicity of proposed algorithm, and frankly can not provide a working code with better one but wanted to share my ideas.

Idea 1:

The patch suggested by @markiz uses dynamic programming, while I believe matching against a selector can be done in a greedy way. The idea is that instead of hierarchy which contains only ancestors of a node we should build a longer list which contains also "left siblings" at each level. That is we should go trough a path from the node to the root which flows to the left if possible and if there is no left brother then up. This way we get the list of all nodes which are really important to tell if the node matches or not.
So for example if the three looked like this:

<div id="one">
   <span id="a">a</span>
   <div id="two">
      <span id="b" class="cool">b</span>
   </div>
</div>

and we are interested in node #b, then the "extended hierarchy" would look like this:
span#b.cool ; div#two , span#a ; div#one
where I used ; to separate levels and , to separate siblings.
It is quite obvious that this can be done with nondeterministic finite automata, which leads (more or less) to the dynamic programming solution presented by markiz.
It could probably be even solved by simple regexp matching at this point if we convert selector into regular expression (for example "div #a + div .cool" could become something like "div[^;]; . #a[^;]div[^;]+;. .cool" -- you get the idea).
The problem I have with this approach is that the complexity is O(|H|_|E|) where |H| is the length of extended hierarchy, and |E| is the length of the expression.
It is probably fast enough for most cases, since |H| is usually a small constant, but I'd like to do it even faster.
I believe that there are two important kinds of combinators :

1. " " and "~" for which the greedy approach works fine
2. "+" and ">" which glue together two (or more) selectors so that they have to be always matched together
   I believe that it is possible to make an O(|E|_|G| + |H|) algorithm where |G| is the size of the largest group of simple selectors glued by "+" or ">" (usually not more than 2). The algorithm would simply go from right to left through the extended hierarchy in a single pass trying to match glued groups one by one, never going back.
   So in the example of "div #a + div .cool" we have three groups : "div" , then "#a + div", and finally ".cool".
   We start by matching "div" to "div#one".
   Then we continue to go left through the hierarchy looking for "#a + div".
   Each time we find something matching to #a we check if the next element matched div.
   Once we find a match (div#two , span#a), we continue with the last group, which is ".cool".

Idea 2:

In the patch proposed by @markiz the loop for (var kk = 0; kk < toCheck.length; kk++) is run too many times for my taste.
I believe it is possible to factor this loop out, and during the loop for (var k = 0; k < hierarchySize; k++) only find the first and the last index of hierarchy array to be scanned. This way each iteration of "for (var k" will work in the constant time, and only after the loop is finished, we have to scan a slice of hierarchy. This way the complexity drops from |H|^2 to |H|.
I don't yet have idea how to handle the case with siblings, but I am not even sure if the current implementation (with overwriting hierarchy[k] each time) is correct.

[markiz]

It's so weird to revisit your own code after two years have passed :)
As per @fabiomcosta Slick now uses native matchers on webkit and firefox (ie10 has msMatchesSelector, although code path for it is commented out in Slick.Finder.js), so for all practical purposes it should be fast enough (famous last words). This makes all the following discussion somewhat theoretical.

---

First of all, thanks for the analysis, @qbolec! I have some corrections, though:

The algorithm would simply go from right to left through the extended hierarchy in a single pass trying to match glued groups one by one, never going back.

This is probably not right. You should be able to backtrace from partial match that wasn't successful.

Contrived example:

<p>
   <div>
       <div>
           <a> 

And selector p > div a. If you match immediate parent <div> of the <a> node, you will not be able to match p > div selector, thus you need to backtrace and check on level higher in the hierarchy.

I don't yet have idea how to handle the case with siblings, but I am not even sure if the current implementation (with overwriting hierarchy[k] each time) is correct.

Yep, seems it isn't.

Also it seems that computational complexity of matcher algo should be dependent on both DOM parameters and selector parameters as not all selectors are created equal: a + b is a constant time check while a b or a ~ b requires traversing the hierarchy.

[qbolec]

I've implemented a proof of concept for my algorithm. I hope tomorrow I'll install git, clean the code up, and upload a diff. For now, here is a link to a patched mootools http://vanisoft.pl/~lopuszanski/public/slick-opt/mootools.js .
I've tested it using @markiz tests and it passes them.

The performance of Slick.match is currently a critical issue for http://nk.pl --- we recently added some functionality which depend son Mootools' new feature "click:relay", which internally uses Slick.match. The problem is that under win8 + ie10 our website is blacklisted by MS, and ie10 falls back to ie7 mode. In ie7 mode, Slick.match uses the naive algorithm, which causes around 3.5k DOM nodes to be traversed each time click:relay is used with a selector which starts without a tag name nor id. For example a selector ".links_box a" causes Slick.match to traverse all tags.

My solution has a nice property that it works in :

• O(1) for a simple selector (for example ".links_box")
• O(depth + selectorLength) for a selector which uses only " " combinator (for example ".links_box a")
• O(depth * longestChainOfArrows + selectorLength) for a selector which uses only " " and ">" (for example ".links_box div > a ")
• O(countOfNodesAboveAndToTheLeft * longestChainOfArrows + selectorLength) for a selector which uses only " ", ">" and "~"
• O(countOfNodesAboveAndToTheLeft * (longestChainOfArrows + numberOfPluses) + selectorLength) for a selector which uses only " ",">","~" and "+"
• does not work for any other selectors :PP

The idea is that I have a "head" which starts at the node to be matched, and then moves upwards (if combinator is " " or ">") or leftwards (if combinator is "+" or "~") backtracking if head points a DOM node which does not match current simple selector. The backtracking is done in a relatively smart way : I do not start from the beginning, but rather remember where the current sequence of consecutive "+" combinators started (similarly I do for sequences of ">"). This way I can prove that the same node of DOM tree can be visited only a constant number of times, which depends only on the length of the longest chain of selectors combined by "+" and the longest chain of selectors combined by ">".

I guess, my above explanation does not really explain much, so instead I'll use an analogy.

Imagine you have to write a matcher which tests if a regular expression matches a string. Moreover your regular expressions are really easy ones : they consists of words separated by "._", for example you look for "quick._brown._fox" in a text. You can do that by searching for the first occurrence of "quick" in the text. Then you can search for "brown" from the point where you have found "quick". Finally you search for "fox".
It is easy to see that searching for word "quick" which has 5 letters can be easily done in time 5_n, where n is the position at which we find first occurrence. So the total complexity is 5_n + 5_n' + 3*n'' , which is < longestWord * textLength.
Now, matching a simple selector is similar to matching a single letter (it takes O(1) time if there are O(1) attributes, id, classes etc).
Matching a selector which uses only ">" combinator is therefore like matching a single word.
Matching a selector which uses only ">" and " " combinator is like matching several words.
You can use this analogy also in horizontal way:
Matching a selector which uses only "+" combinator is therefore like matching a single word.
Matching a selector which uses only "+" and "" combinator is like matching several words.
Things get more complicated when the selectors contains both horizontal and vertical combinators.
But you can mentally split the selector into horizontal parts, for example "div+divdiv > span + span a" has tree parts :
"div+div~div"
"span + span"
"a"
now, you can treat each of these parts as a separate subproblem which as we already know can be solved in O(longestChainOfPluses * widthOfDOMTree). Once you have a subprocedure which solves this subproblem you can treat it as a single letter in our analogy, and move to a higher level of abstraction in which you build words using ">" and separate words using " ". Then, as we already know you can solve this in time O(longestChainOfArrows * depthOfDOMTree * subproblemComplexity).

I hope someone understand something from this. I'll try to reimplement it in a more functional manner as current implementation is a hacky, imperative, state-modifying, switch-reach bitch.