Super-linear runtime degradation with respect to number of DOM nodes

[nwalters512]

Product

axe-core

Product Version

4.8.2

Latest Version

• I have tested the issue with the latest version of the product

Issue Description

Expectation

I would expect runtime performance to correspond at most linearly to the number of DOM nodes present.

Actual

Performance appears to degrade more than linearly with the number of DOM nodes in play. That is: if I double the number of DOM nodes, performance gets ~8x worse, whereas I would expect it to at most get 2x slower.

How to Reproduce

https://github.com/nwalters512/axe-core-performance-repro

Run yarn to install dependencies, then run node index.js. With OPTION_COUNT = 500, Axe runs in ~11 seconds. When OPTION_COUNT is doubled to 1000, runtime increases to 90 seconds

Additional context

Running this code with the Node performance profiler, I was able to identify that the vast majority of time is spent in processAggregate, and specifically in trimElementSpec inside that. I wasn't able to dig significantly deeper than that, though it appears as though getNthChildString is the slowest thing that runs as part of trimElementSpec. Here's some more detail from the profiler:

[straker]

Thanks for the issue. The code in your screenshot is our generate selector code, which is the slowest part of our entire codebase as it has to generate a unique selector for every element returned in the results object. Depending on how many DOM nodes and how unique those DOM nodes are to each other, this process can take a long time as it has to call querySelectorAll a ton to make sure the selector doesn't match anything else.

I've had it on my radar to try to come up with a faster way to generate guaranteed unique selectors, but haven't had a lot of time as of yet to work on it. You can speed up the selector generation by reducing the amount of nodes returned in the results by only the violations and incomplete (removing passes and inapplicable) by passing resultTypes: ['violations', 'incomplete'] to axe.run. This will generate a single node result for each of the non-specified result types (just so you know the rule was run) and only generate a full list of nodes for the ones specified.

await axe.run({ resultTypes: ['violations', 'incomplete'] })

[nwalters512]

That's extremely helpful advice, thank you! That simple change made our accessibility tests run about 2x faster 🎉

It's good to know the slowness is an issue you're aware of, I'm hopeful that there's a path towards improved performance!