[webkit-changes] [WebKit/WebKit] c432de: REGRESSION(282266 at main): Accessibility tree update...

[Tyler Wilcock]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: c432de0695706f7cb574bcce51c04d8291966b93
      https://github.com/WebKit/WebKit/commit/c432de0695706f7cb574bcce51c04d8291966b93
  Author: Tyler Wilcock <tyler_w at apple.com>
  Date:   2024-09-20 (Fri, 20 Sep 2024)

  Changed paths:
    M Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
    M Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h

  Log Message:
  -----------
  REGRESSION(282266 at main): Accessibility tree updates on large webpages are slow due to repeated m_pendingProtectedFromDeletionIDs.formUnion() calls
https://bugs.webkit.org/show_bug.cgi?id=280031
rdar://136329962

Reviewed by Andres Gonzalez and Chris Fleizach.

In https://commits.webkit.org/282266@main, we changed this code in `queueRemovalsLocked` from:

m_pendingProtectedFromDeletionIDs.formUnion(std::exchange(m_protectedFromDeletionIDs, { }));

to:

if (m_protectedFromDeletionIDsIsDirty)
    m_pendingProtectedFromDeletionIDs.formUnion(m_protectedFromDeletionIDs);

The thought was that m_protectedFromDeletionIDsIsDirty would rarely become dirty and then get flushed, so the O(n)
behavior introduced would be fine. However, some webpages behave in ways that constantly dirty this list, and
m_protectedFromDeletionIDs can get extremely large, making the constant formUnion calls expensive.

The only reason formUnion(std::exchange(m_protectedFromDeletionIDs, { })) was problematic in the first place was because some
AXIsolatedTree::updateChildren iterations would queueRemovals separately from queueing appends, meaning we could delete
objects we shouldn't have been deleting. With this commit, we move back to std::exchange(m_protectedFromDeletionIDs, { }),
and solve the problem in a more logical way — force AXIsolatedTree::updateChildren to queue its appends and removals
at the same time by removing the else branch at the bottom of updateChildren:

if (resolveNodeChanges == ResolveNodeChanges::Yes)
    queueRemovalsAndUnresolvedChanges(WTFMove(oldChildrenIDs));
else // removed
    queueRemovals(WTFMove(oldChildrenIDs));

We now accumulate removals in a new list, AXIsolatedTree::m_subtreesToRemove, and flush them to m_pendingSubtreeRemovals
at the same time we flush our appends.

This is better in every way: simpler, avoids the expensive formUnion calls, results in fewer lock acquisitions,
and removes the Vector<AXID> parameter to queueRemovalsAndUnresolvedChanges that only one code path actually passed in.

https://commits.webkit.org/282266@main introduced two new layout tests — both still pass after this change with 100 iterations.
I have also manually tested the webpages those testcases came from, and have confirmed the missing content bugs are not
reintroduced with this change.

* Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:
(WebCore::AXIsolatedTree::generateSubtree):
(WebCore::AXIsolatedTree::queueRemovalsLocked):
(WebCore::AXIsolatedTree::queueRemovalsAndUnresolvedChanges):
(WebCore::AXIsolatedTree::queueAppendsAndRemovals):
(WebCore::AXIsolatedTree::collectNodeChangesForSubtree):
(WebCore::AXIsolatedTree::updateChildren):
(WebCore::AXIsolatedTree::updateChildrenForObjects):
(WebCore::AXIsolatedTree::processQueuedNodeUpdates):
(WebCore::AXIsolatedTree::protectFromDeletion): Deleted.
* Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h:

Canonical link: https://commits.webkit.org/283983@main



To unsubscribe from these emails, change your notification settings at https://github.com/WebKit/WebKit/settings/notifications