Closed Bug 1638238 Opened 2 years ago Closed 1 year ago

TableCellAccessible::ColHeaderCells is very slow on large tables


(Core :: Disability Access APIs, enhancement, P2)




Tracking Status
firefox78 --- fixed


(Reporter: Jamie, Assigned: Jamie)


(Blocks 3 open bugs)



(1 file)

With e10s disabled, a 10000 row HTML table with no header cells takes ~32.7sec to render in NVDA browse mode. If I return at the top of TableCellAccessible::ColheaderCells, that drops to ~4.5sec.

The problem is that TableCellAccessible::ColHeaderCells walks backwards through all rows looking for headers. On row 10000, it has to check 9999 cells. On row 9999, it has to check 9998 cells. And so on.

Previously, to get the column headers for a cell when there weren't explicit headers, we walked over all previous cells in the column looking for headers.
For large tables with thousands of rows, this was very expensive, particularly when Windows screen readers rendered virtual buffers, fetching headers for all cells.

To speed this up, we now lazily cache the previous column header for each cell.
We even cache whether there is no previous header, since that is quite common and we don't want to pointlessly walk in that case.
Subsequent cells utilise the cached values (if any) for prior cells.

We don't store the cache on individual TableCellAccessibles because that would require us to walk all cells to invalidate the cache, even if few or no cells had cached values.
Instead, we store the cache as a hash table on the TableAccessible.
This way, we can just clear the cache whenever a column header is added to the tree.

We invalidate the cache whenever a column header is bound to its parent.
We don't need to invalidate the cache for removals because we instead just ignore defunct Accessibles in the cache.

Pushed by
Cache previous column header for each cell to make TableCellAccessible::ColHeaders faster. r=eeejay
Blocks: 1473310
Closed: 1 year ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla78
Blocks: 1591326
No longer regressions: 1642141
Regressions: 1688532
You need to log in before you can comment on or make changes to this bug.