[webkit-changes] [WebKit/WebKit] 106c4a: GraphicsLayer::removeAllChildren shouldn't be n^2

[Chris Dumez]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 106c4aae5f4384ffb3c573f86ae4f5aa9ad0dc07
      https://github.com/WebKit/WebKit/commit/106c4aae5f4384ffb3c573f86ae4f5aa9ad0dc07
  Author: Chris Dumez <cdumez at apple.com>
  Date:   2023-10-03 (Tue, 03 Oct 2023)

  Changed paths:
    M Source/WebCore/platform/graphics/GraphicsLayer.cpp
    M Source/WebCore/platform/graphics/GraphicsLayer.h
    M Source/WebCore/platform/graphics/ca/GraphicsLayerCA.cpp
    M Source/WebCore/platform/graphics/ca/GraphicsLayerCA.h
    M Source/WebCore/platform/graphics/texmap/coordinated/CoordinatedGraphicsLayer.cpp
    M Source/WebCore/platform/graphics/texmap/coordinated/CoordinatedGraphicsLayer.h
    M Source/WebKit/WebProcess/WebPage/wc/GraphicsLayerWC.cpp
    M Source/WebKit/WebProcess/WebPage/wc/GraphicsLayerWC.h

  Log Message:
  -----------
  GraphicsLayer::removeAllChildren shouldn't be n^2
https://bugs.webkit.org/show_bug.cgi?id=250654
rdar://104534645

Reviewed by Simon Fraser.

`GraphicsLayer::removeAllChildren()` used to select the first sublayer in the
`m_children` vector and call `removeFromParent()` on it. This would null out
`m_parent` on that sublayer and then remove the layer from m_children. This
would end up being expensive because removing items from the beginning of a
vector is expensive and involves moving following items to fill the empty
position.

To avoid the issue, I made the following changes:
1. Have GraphicsLayer::removeAllChildren() null out all parents on sub-layers
   then clear m_children all at once. No more Vector::removeFirstMatching()
   for each sub-layer.
2. GraphicsLayer::removeFromParent() used to be virtual, to notify the parent
   layer that the children changed. However, removeFromParent() is no longer
   called in removeAllChildren() after my change. To address the issue, I am
   marking GraphicsLayer::removeFromParent() as non-virtual and introducing
   a new GraphicsLayer::willModifyChildren() virtual function. This new
   virtual gets called at the beginning of removeFromParent(), before removing
   the layer from its parent, to match pre-existing behavior in child classes.
   willModifyChildren() also gets called once in GraphicsLayer::removeAllChildren()
   before removing all sub-layers, instead of one virtual function call per
   sub-layer.

This is inspired by the following Blink change but I chose a different approach
that I believe is more optimal:
- https://chromium.googlesource.com/chromium/blink/+/ea1156d6f005f978e4da707ef4e2060c2fc7151f

* Source/WebCore/platform/graphics/GraphicsLayer.cpp:
(WebCore::GraphicsLayer::removeAllChildren):
(WebCore::GraphicsLayer::removeFromParent):
* Source/WebCore/platform/graphics/GraphicsLayer.h:
(WebCore::GraphicsLayer::willModifyChildren):
* Source/WebCore/platform/graphics/ca/GraphicsLayerCA.cpp:
(WebCore::GraphicsLayerCA::willModifyChildren):
(WebCore::GraphicsLayerCA::removeFromParent): Deleted.
* Source/WebCore/platform/graphics/ca/GraphicsLayerCA.h:
* Source/WebCore/platform/graphics/texmap/coordinated/CoordinatedGraphicsLayer.cpp:
(WebCore::CoordinatedGraphicsLayer::willModifyChildren):
(WebCore::CoordinatedGraphicsLayer::removeFromParent): Deleted.
* Source/WebCore/platform/graphics/texmap/coordinated/CoordinatedGraphicsLayer.h:
* Source/WebKit/WebProcess/WebPage/wc/GraphicsLayerWC.cpp:
(WebKit::GraphicsLayerWC::willModifyChildren):
(WebKit::GraphicsLayerWC::removeFromParent): Deleted.
* Source/WebKit/WebProcess/WebPage/wc/GraphicsLayerWC.h:

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