Axe-core: Performance of dom.findUp is very slow

[paulirish]

As you know, the performance of dom.findUp is really poor. However it is used very heavily across the various rules/checks.

AFAICT, you could use the DOM API of element.matches() which should be substantially faster. (browser support is good).

You basically have written the polyfill for it, so you can fall back to your current implementation if ('matches' in element) is false.

---

Good site to reproduce on: https://www.mlb.com/
Screenshot of the color-contrast rule taking 26s to complete. (All of the time is spent in the querySelectorAll within findUp)

cc @patrickhulce @kdzwinel

[dylanb]

@paulirish AFAICT element.matches cannot be used to improve color contrast speed because we actually need to retrieve the ancestor element that causes the match and element.matches simply returns true or false

I tell you what would make this check blindingly fast - give us a JavaScript function that tells me what the browser thinks the background color is for any given point on the page and a matching one for the foreground color for any given point on the page (in fact if we could get the color stack at any point above an element and the actual color of any given point, we could do the rest of the calculation blindingly fast) - know anyone who could help?

[kdzwinel]

I might be missing something here, but IMO element.closest is the native equivalent of dom.findUp. Not sure about the shadow DOM part though.

[dylanb]

@kdzwinel you are correct

@paulirish try this version of axe-core. I think I reduced the querySelectorAll time by 80% on mlb.com https://gist.github.com/dylanb/caeb6a12e2320a46925b462809924c3a

[kdzwinel]

I just tested and on https://www.mlb.com/yankees/schedule/2018-03%60 axe runtime is down from 60s+ (LH has a 60s timeout for gatherers) to 29s 🎉

[dylanb]

I am also going to use element.matches to improve the performance of the case where element.closest does not exist and see if I can optimize the shadow DOM worst case scenario too (nothing matches)

[dylanb]

what element.closest giveth, shadow DOM taketh away :-(

[dylanb]

@kdzwinel @paulirish Can you try this version? https://gist.github.com/dylanb/72387f45e38363d6bea5728809fdea8c

It is a bit slower than the previous super-fast one but actually handles all the conditions we need to handle. Y'all can look at the pull request above to see the changes if you want to make suggestions as to additional improvements

[patrickhulce]

Thanks for jumping on this @dylanb! I'm getting some pretty slow stats on that one MLB example site (https://www.mlb.com/yankees/schedule/2018-03) still :/

@kdzwinel how were you running that version, in LH? The one trace I was able to get spends about ~2 minutes. pushNode seems to be the biggest timesink here though, so maybe a separate issue?

[dylanb]

@patrickhulce the mouseover there is showing 23s with pushNode only taking 16ms of that time. I think you are seeing similar performance to what I am seeing. Its a big improvement from where we started this morning.

[patrickhulce]

Oh sorry should've been more clear, I know it's not in pushNode itself just the high-level step 😄 (a surprising amount of its time seems to be in .find actually but I digress). Since @kdzwinel was able to get a completion in ~30s before, ~140s seemed to be much slower, so I was wondering if something else changed.

[dylanb]

[EDITED]
Apologies for the confusion, I must have been tired when I looked at your screen shot.

When @kdzwinel was getting 29s, I was getting about 22 seconds - here is a screenshot

After I made the changes to correctly support shadow DOM, I am gettin around 23 seconds - a decreased of 5%. You will notice in the screenshot below this is the appearance of the axe.utils.getNodeFromTree calls.

So what this has done is remove querySelectorAll completely from the top of the performance call stack but it has shoved all of that performance into the browser. I am seeing a total improvement from about 28 seconds to about 23 seconds - so a total improvement of about 20%.

So if you had pages taking 2 minutes, they will still be taking over 1 minute

[kdzwinel]

Three LH runs on https://www.mlb.com/yankees/schedule/2018-03 with this version of axe-core: https://gist.github.com/dylanb/72387f45e38363d6bea5728809fdea8c give me 36s, 31s, 37s.

The way I test it is I just point accessability audit to a different version of axe.min.js file and call lighthouse-cli https://www.mlb.com/yankees/schedule/2018-03 --view.

[dylanb]

How does that compare to previously? Are you seeing about a 20% improvement?

[dylanb]

@patrickhulce nice find - that function was horribly inefficient. I have now reduced that page from over 200s to around 45s. Try this https://gist.github.com/dylanb/77334dd2c6d9ff510da89a09ccfa2490

[dylanb]

This is a fantastic improvement. It gets the time for the mlb.com home page down to around 14s from 28s - that is an improvement of 50% overall...thanks for the help @paulirish @patrickhulce and @kdzwinel

[benschwarz]

Would it be possible to get this in a point release @dylanb? We'd sure like to see it in Lighthouse soon

[paulirish]

@benschwarz I'm awaiting the merge of #701 and resolution of #702 before rolling. While a minor release from aXe would be awesome, I'm also happy to cherrypick these onto 2.6.1 and use that custom branch.

[WilcoFiers]

Cherry picking this fix for 2.x won't work. Much of it is build on shadow DOM code that isn't available in 2.x. We're pretty close to the 3.0 release at this point, I'd prefer all our current efforts go into 3.0 right now, instead of another 2.x release.

[paulirish]

K. that works for me.