118764 2013-07-16 20:05:35 -0700 Optimize RenderLayerCompositor's OverlapMap 2013-07-17 15:07:51 -0700 1 1 1 Unclassified WebKit Layout and Rendering 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 simon.fraser simon.fraser commit-queue esprehn+autocc glenn simon.fraser oldest_to_newest 909116 0 simon.fraser 2013-07-16 20:05:35 -0700 OverlapMap::overlapsLayers() can end up doing hundreds of rect intersections on some content. This can be optimized if we keep a bounding rect of the list of rects. 909118 1 simon.fraser 2013-07-16 20:06:04 -0700 Kinda patch: diff --git a/Source/WebCore/rendering/RenderLayerCompositor.cpp b/Source/WebCore/rendering/RenderLayerCompositor.cpp index 26bcdfd087d333112f630ebc93387b1c8f19a6ed..05da81d52cda0b3812c0a4c3cbc0603974b465c4 100644 --- a/Source/WebCore/rendering/RenderLayerCompositor.cpp +++ b/Source/WebCore/rendering/RenderLayerCompositor.cpp @@ -99,6 +99,9 @@ static const double throttledLayerFlushDelay = .5; using namespace HTMLNames; +static size_t totalRectCompares = 0; +static size_t totalTries = 0; + class RenderLayerCompositor::OverlapMap { WTF_MAKE_NONCOPYABLE(OverlapMap); public: @@ -128,12 +131,7 @@ public: bool overlapsLayers(const IntRect& bounds) const { - const RectList& layerRects = m_overlapStack.last(); - for (unsigned i = 0; i < layerRects.size(); i++) { - if (layerRects[i].intersects(bounds)) - return true; - } - return false; + return m_overlapStack.last().intersects(bounds); } bool isEmpty() @@ -148,14 +146,50 @@ public: void popCompositingContainer() { - m_overlapStack[m_overlapStack.size() - 2].appendVector(m_overlapStack.last()); + m_overlapStack[m_overlapStack.size() - 2].append(m_overlapStack.last()); m_overlapStack.removeLast(); } RenderGeometryMap& geometryMap() { return m_geometryMap; } private: - typedef Vector<IntRect> RectList; + struct RectList { + Vector<IntRect> rects; + IntRect boundingRect; + + void append(const IntRect& rect) + { + rects.append(rect); + boundingRect.unite(rect); + } + + void append(const RectList& rectList) + { + rects.appendVector(rectList.rects); + boundingRect.unite(rectList.boundingRect); + } + + bool intersects(const IntRect& rect) const + { + if (!rects.size()) + return false; + ++totalTries; + if (!boundingRect.intersects(rect)) { + WTFLogAlways("bounding rect early return\n"); + return false; + } + + for (unsigned i = 0; i < rects.size(); i++) { + if (rects[i].intersects(rect)) { + totalRectCompares += i; + return true; + } + } + totalRectCompares += rects.size(); + return false; + } + }; + Vector<RectList> m_overlapStack; HashSet<const RenderLayer*> m_layers; RenderGeometryMap m_geometryMap; @@ -652,6 +686,10 @@ void RenderLayerCompositor::updateCompositingLayers(CompositingUpdateType update // most of the time, geometry is updated via RenderLayer::styleChanged(). updateLayerTreeGeometry(updateRoot, 0); } + + + WTFLogAlways("Mean rect compares %.2f (%zu tries)\n", (double)totalRectCompares / totalTries, totalTries); + #if !LOG_DISABLED if (compositingLogEnabled() && isFullUpdate && (needHierarchyUpdate || needGeometryUpdate)) { @@ -1501,7 +1539,7 @@ void RenderLayerCompositor::updateLayerTreeGeometry(RenderLayer* layer, int dept if (RenderLayerBacking* layerBacking = layer->backing()) { // The compositing state of all our children has been updated already, so now // we can compute and cache the composited bounds for this layer. - layerBacking->updateCompositedBounds(); +// layerBacking->updateCompositedBounds(); if (RenderLayer* reflection = layer->reflectionLayer()) { if (reflection->backing()) 909344 2 206891 simon.fraser 2013-07-17 09:24:58 -0700 Created attachment 206891 Patch 909475 3 simon.fraser 2013-07-17 15:07:51 -0700 http://trac.webkit.org/changeset/152806 206891 2013-07-17 09:24:58 -0700 2013-07-17 09:27:30 -0700 Patch bug-118764-20130717092457.patch text/plain 3384 simon.fraser U3VidmVyc2lvbiBSZXZpc2lvbjogMTUyNzAxCmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggYzJjMWFiYTc5ZGY0ZDMy MGVlYzBkMTA3YWExNWJiZmEwMDk4YzBkOS4uYjMyNTZiNzE5YzRjOGVhN2UzMzI4ZTIwMTFiZWVm MDIyYjRmZTIyNSAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDIzIEBACisyMDEzLTA3LTE3ICBTaW1v biBGcmFzZXIgIDxzaW1vbi5mcmFzZXJAYXBwbGUuY29tPgorCisgICAgICAgIE9wdGltaXplIFJl bmRlckxheWVyQ29tcG9zaXRvcidzIE92ZXJsYXBNYXAKKyAgICAgICAgaHR0cHM6Ly9idWdzLndl YmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTExODc2NAorCisgICAgICAgIFJldmlld2VkIGJ5IE5P Qk9EWSAoT09QUyEpLgorCisgICAgICAgIE92ZXJsYXAgc3RhY2sgaXRlbXMgY2FuIGhhdmUgUmVj dExpc3RzIHdpdGggaHVuZHJlZHMgb2YgcmVjdGFuZ2xlcy4KKyAgICAgICAgVGhpcyBtYWtlcyB0 aGUgbGluZWFyIHNlYXJjaCBpbiBPdmVybGFwTWFwOjpvdmVybGFwc0xheWVycygpIHZlcnkgc2xv dy4KKyAgICAgICAgCisgICAgICAgIE9wdGltaXplIGJ5IHN0b3JpbmcgdGhlIGJvdW5kaW5nIHJl Y3Qgb2YgdGhlIGxpc3Qgb2YgcmVjdHMsIGFuZCBkb2luZyBhbiBlYXJseQorICAgICAgICBjaGVj ayBvbiB0aGF0LiBUaGlzIHJlZHVjZXMgdGltZSBzcGVudCBpbiBSZW5kZXJMYXllcjo6c2Nyb2xs VG8oKSBieSAxMyUgaW4gc29tZQorICAgICAgICBjb250ZW50IHdpdGggbG90cyBvZiBsYXllcnMg aW5zaWRlIGFuIG92ZXJmbG93OnNjcm9sbC4KKworICAgICAgICAqIHJlbmRlcmluZy9SZW5kZXJM YXllckNvbXBvc2l0b3IuY3BwOgorICAgICAgICAoV2ViQ29yZTo6UmVuZGVyTGF5ZXJDb21wb3Np dG9yOjpPdmVybGFwTWFwOjpvdmVybGFwc0xheWVycyk6CisgICAgICAgIChXZWJDb3JlOjpSZW5k ZXJMYXllckNvbXBvc2l0b3I6Ok92ZXJsYXBNYXA6OnBvcENvbXBvc2l0aW5nQ29udGFpbmVyKToK KyAgICAgICAgKFdlYkNvcmU6OlJlbmRlckxheWVyQ29tcG9zaXRvcjo6T3ZlcmxhcE1hcDo6UmVj dExpc3Q6OmFwcGVuZCk6CisgICAgICAgIChXZWJDb3JlOjpSZW5kZXJMYXllckNvbXBvc2l0b3I6 Ok92ZXJsYXBNYXA6OlJlY3RMaXN0OjppbnRlcnNlY3RzKToKKwogMjAxMy0wNy0xNSAgVGltIEhv cnRvbiAgPHRpbW90aHlfaG9ydG9uQGFwcGxlLmNvbT4KIAogICAgICAgICBVcGRhdGUgYmxvY2tl ZC9taXNzaW5nIHBsdWctaW4gVUkKZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3JlL3JlbmRlcmlu Zy9SZW5kZXJMYXllckNvbXBvc2l0b3IuY3BwIGIvU291cmNlL1dlYkNvcmUvcmVuZGVyaW5nL1Jl bmRlckxheWVyQ29tcG9zaXRvci5jcHAKaW5kZXggZWEzNWI0OWNkYjZmYTliYTkwYWVmMTY4Nzc1 MjMyNzA2NTZhMzI4Mi4uNjJhOTg2ZjhlYTAwMGYzMWRkMmQ2MThkYjlmMzI3MDY1YTg3MWMwYiAx MDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvcmVuZGVyaW5nL1JlbmRlckxheWVyQ29tcG9zaXRv ci5jcHAKKysrIGIvU291cmNlL1dlYkNvcmUvcmVuZGVyaW5nL1JlbmRlckxheWVyQ29tcG9zaXRv ci5jcHAKQEAgLTExOSwxMiArMTE5LDcgQEAgcHVibGljOgogCiAgICAgYm9vbCBvdmVybGFwc0xh eWVycyhjb25zdCBJbnRSZWN0JiBib3VuZHMpIGNvbnN0CiAgICAgewotICAgICAgICBjb25zdCBS ZWN0TGlzdCYgbGF5ZXJSZWN0cyA9IG1fb3ZlcmxhcFN0YWNrLmxhc3QoKTsKLSAgICAgICAgZm9y ICh1bnNpZ25lZCBpID0gMDsgaSA8IGxheWVyUmVjdHMuc2l6ZSgpOyBpKyspIHsKLSAgICAgICAg ICAgIGlmIChsYXllclJlY3RzW2ldLmludGVyc2VjdHMoYm91bmRzKSkKLSAgICAgICAgICAgICAg ICByZXR1cm4gdHJ1ZTsKLSAgICAgICAgfQotICAgICAgICByZXR1cm4gZmFsc2U7CisgICAgICAg IHJldHVybiBtX292ZXJsYXBTdGFjay5sYXN0KCkuaW50ZXJzZWN0cyhib3VuZHMpOwogICAgIH0K IAogICAgIGJvb2wgaXNFbXB0eSgpCkBAIC0xMzksMTQgKzEzNCw0MiBAQCBwdWJsaWM6CiAKICAg ICB2b2lkIHBvcENvbXBvc2l0aW5nQ29udGFpbmVyKCkKICAgICB7Ci0gICAgICAgIG1fb3Zlcmxh cFN0YWNrW21fb3ZlcmxhcFN0YWNrLnNpemUoKSAtIDJdLmFwcGVuZFZlY3RvcihtX292ZXJsYXBT dGFjay5sYXN0KCkpOworICAgICAgICBtX292ZXJsYXBTdGFja1ttX292ZXJsYXBTdGFjay5zaXpl KCkgLSAyXS5hcHBlbmQobV9vdmVybGFwU3RhY2subGFzdCgpKTsKICAgICAgICAgbV9vdmVybGFw U3RhY2sucmVtb3ZlTGFzdCgpOwogICAgIH0KIAogICAgIFJlbmRlckdlb21ldHJ5TWFwJiBnZW9t ZXRyeU1hcCgpIHsgcmV0dXJuIG1fZ2VvbWV0cnlNYXA7IH0KIAogcHJpdmF0ZToKLSAgICB0eXBl ZGVmIFZlY3RvcjxJbnRSZWN0PiBSZWN0TGlzdDsKKyAgICBzdHJ1Y3QgUmVjdExpc3QgeworICAg ICAgICBWZWN0b3I8SW50UmVjdD4gcmVjdHM7CisgICAgICAgIEludFJlY3QgYm91bmRpbmdSZWN0 OworICAgICAgICAKKyAgICAgICAgdm9pZCBhcHBlbmQoY29uc3QgSW50UmVjdCYgcmVjdCkKKyAg ICAgICAgeworICAgICAgICAgICAgcmVjdHMuYXBwZW5kKHJlY3QpOworICAgICAgICAgICAgYm91 bmRpbmdSZWN0LnVuaXRlKHJlY3QpOworICAgICAgICB9CisKKyAgICAgICAgdm9pZCBhcHBlbmQo Y29uc3QgUmVjdExpc3QmIHJlY3RMaXN0KQorICAgICAgICB7CisgICAgICAgICAgICByZWN0cy5h cHBlbmRWZWN0b3IocmVjdExpc3QucmVjdHMpOworICAgICAgICAgICAgYm91bmRpbmdSZWN0LnVu aXRlKHJlY3RMaXN0LmJvdW5kaW5nUmVjdCk7CisgICAgICAgIH0KKyAgICAgICAgCisgICAgICAg IGJvb2wgaW50ZXJzZWN0cyhjb25zdCBJbnRSZWN0JiByZWN0KSBjb25zdAorICAgICAgICB7Cisg ICAgICAgICAgICBpZiAoIXJlY3RzLnNpemUoKSB8fCAhYm91bmRpbmdSZWN0LmludGVyc2VjdHMo cmVjdCkpCisgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOworCisgICAgICAgICAgICBmb3Ig KHVuc2lnbmVkIGkgPSAwOyBpIDwgcmVjdHMuc2l6ZSgpOyBpKyspIHsKKyAgICAgICAgICAgICAg ICBpZiAocmVjdHNbaV0uaW50ZXJzZWN0cyhyZWN0KSkKKyAgICAgICAgICAgICAgICAgICAgcmV0 dXJuIHRydWU7CisgICAgICAgICAgICB9CisgICAgICAgICAgICByZXR1cm4gZmFsc2U7CisgICAg ICAgIH0KKyAgICB9OworCiAgICAgVmVjdG9yPFJlY3RMaXN0PiBtX292ZXJsYXBTdGFjazsKICAg ICBIYXNoU2V0PGNvbnN0IFJlbmRlckxheWVyKj4gbV9sYXllcnM7CiAgICAgUmVuZGVyR2VvbWV0 cnlNYXAgbV9nZW9tZXRyeU1hcDsK