Performance of axe.utils.select('*') is slow with lots of nodes

[paulirish]

Example trace: https://chromedevtools.github.io/timeline-viewer/?loadTimelineFromURL=drive://1qJeP82OwoRZ0g4PS-bvJuf_FKI0UfIEm

The above trace is of the mlb homepage with a dev build of axe (including both #699 and #701)

You can see these pretty big chunks of array sorting:

Looking into it, it appears to be when axe.utils.select is called with a selector of * and then does the sort() to get document order. Do we need these results in an order other than what qSA returns?

[dylanb]

This code returns the nodes in the document order, ordered by selector. So for example if a rule looks for 'button, [role=button]', QSA returns the button matches first, followed by the [role=button] matches and some rules (e.g. heading order) rely on things being in the correct order.

We would have to expose a property in all rules to indicate whether they require sorted nodes and then make this sort conditional

@WilcoFiers @marcysutton thoughts?

[paulirish]

some rules (e.g. heading order) rely on things being in the correct order.
We would have to expose a property in all rules to indicate whether they require sorted nodes

Hmmm.. If that's a little hairy, how about memoizing axe.utils.select? That'd at least nuke 3 of the 4 expensive calls, which seems like a pretty decent win.

[WilcoFiers]

Agreed. Memoization seems like a sensible approach, although we'd have to make sure it's cleaned reset after every run.

[dylanb]

@paulirish @WilcoFiers memoizing select will reduce the number of sorts from 56 to 40 (if you run all the rules). This is based on some code I wrote quickly to parse all the selectors in all the rules and then compare the parsed selectors stringified. I could write a more accurate comparitor but I don't think the difference is going to be huge. So we are talking about eliminating ~30% of this time.

In order for a check to be able to take advantage of the order of elements returned, it has to do one of two things:

1. It has to use an after function that looks at the data that is aggregated, and/or
2. It has to use select directly and rely on the sorting

I have reviewed all the checks that have an after function and only heading order relies on the order

I have reviewed all the checks and can find no use of it within the builtin checks

This means we can eliminate 98.3% of the time by adding an attribute to the rules object and only sorting when we see that. Given that we are talking about a major release, I would prefer to make this change now - thoughts?

[WilcoFiers]

I don't think we should return nodes out of order in the DOM. I've seen what that looks like in the extension, and it's quite confusing. I don't like having this as an option, even if it's on by default, it exposes a design flaw, which I think isn't very clean.

I think maybe a smarter way to do this is to build QSA in such a way that it can't return elements out of order. If instead of going through each expression in the selector one at a time, we consider all of them as we're walking this composed DOM, we can keep them in order. QSA is a little more complicated because of it, but we would never have to sort the results.

[paulirish]

One alternative idea...
The sort is for a selector string containing multiple selectors, because it's this scenario that gets returned out of document order. Right?

What if you only do this sort when there's a , in the selector string? That solves my major issue which is that '*' selector which returns a ton of nodes goes through the .sort().

[WilcoFiers]

That could work. We'd have to sort and deduplicate the context object to make that work I think. We might as well move node sorting into QSA. Easier to do it there, and it should probably always have its results sorted.

I still think we should memoize axe.utils.select. That 30% performance improvement is worth picking up IMO. There's really no reason to do all that DOM walking if we can avoid it.

[dylanb]

ok, I think memoizing the results and changing QSA to return guaranteed sorted results would be the best outcome. Assuming no new performance issues, that would get us 100% elimination of the sort plus 30% elimination of the QSA work.

[WilcoFiers]

Awesome. @paulirish are you interested to work on a PR for this?

[dylanb]

@paulirish @WilcoFiers if neither of you has done anything on this by Saturday, I will take a shot at it myself at the weekend

[dylanb]

@paulirish Implemented the first half of this, you can download the axe.js file https://gist.github.com/dylanb/37509ec425d0b00331caa25963b093d4

I am seeing about a 7% improvement in performance by eliminating the sort (mlb.com goes down to 13s from 14s) - not as much as I was expecting. I would appreciate a gander at the changes for suggestions as to whether there are parts of the code that might not be optimizable or alternative approaches that might exhibit better performance.

I estimate that memoization of select will give us another 4% at most

[dylanb]

Ok, I memoized axe.utils.select and it does not really help on the mlb.com home page but it brings the time for the Yankees calendar page down to 32s from a previous time of approximately 45s

Here is the gist https://gist.github.com/dylanb/fc6e4d6af4c68566218f65562328f37e

[paulirish]

@dylanb if you're still around, drop by https://gitter.im/dequelabs/axe-core if not, i'll be around on a weekday.