`axe.runPartial` performance on page with 100k nodes

[straker]

We recently ran into an issue where a page had 108,000 option nodes in a single select element. Axe-core took a bit to just process that many nodes, but the real problem was processing selectors for that many nodes.

Typically our answer to that is to use resultTypes to filter out most nodes which allows us to just generate selectors for things like violations. However when using runPartial the resultTypes option is not used which means the at the end of the runPartial all 108,000 nodes will try to generate a selector even if they will be removed after running finishRun.

One thing we'll have to figure out is how to deal with rules that have after methods which may change the result of a node.

[straker]

We're going to do a few different things to address this problem.

First, there are some small improvements we can make to the getSelector code to handle generating selectors for an element with many children. We can detect that and prefer to use nth-child first rather than going through other indicators (such as id, class, etc.).

Second, a workaround for the performance problem could be to disable selectors in the run options in order to avoid generating them. This would then require having ancestors enabled in order to still get information about where an element is in the DOM when it fails. Generating ancestors is faster but still has performance problems with so many nodes. We can apply the same type of fix from getSelector in the previous point to generating ancestors as well.

Lastly, we'd like to make this switch from selectors to ancestors more dynamic to help speed up performance. We're going to allow the selectors run option to additional be a string with two options: ancestor or dynamic. Setting it to ancestor will make the target property of a node use the ancestor generation rather than the selector generation. dynamic will do this change based on the size of the page. For pages with a very large number nodes (number to be determined) axe will automatically use ancestor generation, where as for anything smaller than the very large number will use selector generation as it does today.

[dbjorge]

See also #4273

[straker]

I looked into this and I don't think just switching to use nth child selector helps.

I first created a page to run axe with a single select with n child options, where n was passed as a query parameter to the page.

<select id="foo" aria-label="foo"></select>
<script>
  const urlParams = new URLSearchParams(window.location.search);
  const nodes = urlParams.get('nodes') ?? 100;

  const fragment = document.createDocumentFragment();
  for (let i = 0; i < nodes; i++) {
    const option = document.createElement('option');
    option.textContent = 'Option #' + (i + 1);
    fragment.append(option);
  }

  foo.append(fragment);
</script>

I then created a script to open the page, run axe 5 times, and generate an average run time. I did this for 0 - 10K nodes. I also found a few real world pages (which I called "base" pages) that had similar node numbers to run axe against as well in order to compare results. I saved the results to a spread sheet in order to compare the results.

I first ran with latest axe, and the results are pretty grim. At just 2k sibling nodes, axe is slower than a base page with similar number of nodes.

Num Nodes	Time nth-child (ms)	Time base (ms)
0	38.5	141.5
1000	349.68	882.31
2000	903.18
3000	1808.91	649.31
4000	3002.76
5000	4577.82	884.89
6000	6591.77
7000	8578.02	1625.13
8000	11058.77
9000	14096.85
10000	16851.13	6551.56

I then changed the getSelector method to always use nth child selector when there are more than 2k siblings (as this is where axe started to slow down).

if (elm.parentNode?.children.length >= 2000) {
  const siblings = Array.from(elm.parentNode.children);
  const nthChild = 1 + siblings.indexOf(elm);
  features = getBaseSelector(elm) + ':nth-child(' + nthChild + ')';
}
else {
  features = getThreeLeastCommonFeatures(elm, axe._selectorData);
  features += getNthChildString(elm, features);
}

This didn't change the results at all. It seems just running querySelectorAll('option:nth-child') with more than 2.5k siblings is slow and takes ~6ms a call. With 10k nodes, that still takes ~15 seconds to generate a selector for every node.

Lastly I changed the method to always generate an ancestry path instead of a selector with >2k siblings (and thus avoiding the querySelectorAll call). The results were vastly improved with the time being less when compared to the base page.

if (elm.parentNode?.children.length >= 2000) {
  return getAncestry(elm);
}
else {
  features = getThreeLeastCommonFeatures(elm, axe._selectorData);
  features += getNthChildString(elm, features);
}

Num Nodes	Time nth-child (ms)	Time base (ms)
0	37.18	159.09
1000	352.96	867.1
2000	435.25
3000	678.86	1040.83
4000	967.03
5000	1287.81	538.14
6000	1646.05
7000	2041.38	1586.56
8000	2508.53
9000	2983.33
10000	3484.95	6842.76

Below is the script I used to generate results.

#!/usr/bin/env node
const playwright = require('playwright');
const XLSX = require('xlsx');
const { setTimeout } = require('node:timers/promises');
const axe = require('../axe.js');
const { source } = axe;
const path = require('path');

const dataAoa = [
  [
    'Num Nodes',
    'Time nth-child (ms)',
    'Time base (ms)'
  ]
];
const numRuns = 5;
const basePages = {
  0: 'https://stevenklambert.com/writing/encroaching-darkness-postmortem/',
  1_000: 'https://developer.mozilla.org/en-US/docs/Web/API/Document/createElement',
  3_000: 'https://www.amazon.com/',
  5_000: 'https://www.google.com/search?q=hello+world&oq=hello+world',
  7_000: 'https://www.youtube.com/results?search_query=code',
  10_000: 'https://stackoverflow.com/questions/11832914/how-to-round-to-at-most-2-decimal-places-if-necessary',
};

const dataNodes = {};

(async () => {
  const browser = await playwright.chromium.launch({
    headless: true
  });

  try {
    const context = await browser.newContext();
    const page = await context.newPage();

    for (let i = 0; i <= 10_000; i += 1000) {
      await perfPage(page, `http://localhost:9876/test/playground.html?nodes=${i}`, i);
    }

    for ([numNodes, url] of Object.entries(basePages)) {
      await perfPage(page, url, numNodes);
    }

    for ([numNodes, times] of Object.entries(dataNodes)) {
      dataAoa.push([numNodes, ...times]);
    }
    save();
  } finally {
    console.log(dataNodes);
    await browser.close();
  }
})();

async function perfPage(page, url, numNodes) {
  let total = 0;

  for (let num = 0; num < numRuns; num++) {
    await page.goto(url);
    await setTimeout(2000);

    const axeExist = await page.evaluate(() => !!window.axe);
    if (!axeExist) {
      await page.evaluate(source);
      await setTimeout(500);
    }

    performance.clearMarks();
    performance.clearMeasures();
    performance.mark('start');

    await page.evaluate(async () => await axe.run());

    performance.mark('end');
    performance.measure('time', 'start', 'end');
    const { duration } = performance.getEntriesByName('time')[0];
    total += duration;
  }

  const average = (total / numRuns).toFixed(2);
  dataNodes[numNodes] = dataNodes[numNodes] ?? [];
  dataNodes[numNodes].push(average);
  console.log(`average of ${numRuns} runs for ${url} and ${numNodes} nodes: ${average}ms`);
}

function save() {
  console.log(dataAoa)
  const workbook = XLSX.utils.book_new();

  const sheet = XLSX.utils.aoa_to_sheet(dataAoa);
  XLSX.utils.book_append_sheet(
    workbook,
    sheet
  );

  XLSX.writeFile(
    workbook,
    path.join(__dirname, `time.xlsx`)
  );
}