Bug 1351426 - Part 3: Refactor BSPTree to use list instead of deque r=kip
☠☠ backed out by 3cc843a5c109 ☠ ☠
authorMiko Mynttinen <mikokm@gmail.com>
Wed, 05 Apr 2017 20:12:35 +0200
changeset 560192 a6c0e4789330b9a37956bcb123449db35e27e6f0
parent 560191 8e36dfa4061ed197cc373dc2a3f8e0da1ce06f9b
child 560193 aeca2ef150b857167731ced9b3a8da68227b88a0
push id53365
push userjichen@mozilla.com
push dateTue, 11 Apr 2017 08:35:12 +0000
reviewerskip
bugs1351426
milestone55.0a1
Bug 1351426 - Part 3: Refactor BSPTree to use list instead of deque r=kip MozReview-Commit-ID: F4ezRzbGihI
gfx/layers/BSPTree.cpp
gfx/layers/BSPTree.h
gfx/layers/Layers.cpp
gfx/tests/gtest/TestBSPTree.cpp
--- a/gfx/layers/BSPTree.cpp
+++ b/gfx/layers/BSPTree.cpp
@@ -4,68 +4,66 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "BSPTree.h"
 #include "mozilla/gfx/Polygon.h"
 
 namespace mozilla {
 namespace layers {
 
-LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers)
-{
-  LayerPolygon layer = Move(aLayers.front());
-  aLayers.pop_front();
-  return layer;
-}
-
 void
-BSPTree::BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
+BSPTree::BuildDrawOrder(BSPTreeNode* aNode,
                         nsTArray<LayerPolygon>& aLayers) const
 {
   const gfx::Point4D& normal = aNode->First().GetNormal();
 
-  UniquePtr<BSPTreeNode> *front = &aNode->front;
-  UniquePtr<BSPTreeNode> *back = &aNode->back;
+  BSPTreeNode* front = aNode->front;
+  BSPTreeNode* back = aNode->back;
 
   // Since the goal is to return the draw order from back to front, we reverse
   // the traversal order if the current polygon is facing towards the camera.
   const bool reverseOrder = normal.z > 0.0f;
 
   if (reverseOrder) {
     std::swap(front, back);
   }
 
-  if (*front) {
-    BuildDrawOrder(*front, aLayers);
+  if (front) {
+    BuildDrawOrder(front, aLayers);
   }
 
   for (LayerPolygon& layer : aNode->layers) {
     MOZ_ASSERT(layer.geometry);
 
     if (layer.geometry->GetPoints().Length() >= 3) {
       aLayers.AppendElement(Move(layer));
     }
   }
 
-  if (*back) {
-    BuildDrawOrder(*back, aLayers);
+  if (back) {
+    BuildDrawOrder(back, aLayers);
   }
 }
 
 void
-BSPTree::BuildTree(UniquePtr<BSPTreeNode>& aRoot,
-                   std::deque<LayerPolygon>& aLayers)
+BSPTree::BuildTree(BSPTreeNode* aRoot,
+                   std::list<LayerPolygon>& aLayers)
 {
+  MOZ_ASSERT(!aLayers.empty());
+
+  aRoot->layers.push_back(Move(aLayers.front()));
+  aLayers.pop_front();
+
   if (aLayers.empty()) {
     return;
   }
 
   const gfx::Polygon& plane = aRoot->First();
-  std::deque<LayerPolygon> backLayers, frontLayers;
 
+  std::list<LayerPolygon> backLayers, frontLayers;
   for (LayerPolygon& layerPolygon : aLayers) {
     const Maybe<gfx::Polygon>& geometry = layerPolygon.geometry;
 
     size_t pos = 0, neg = 0;
     nsTArray<float> dots = geometry->CalculateDotProducts(plane, pos, neg);
 
     // Back polygon
     if (pos == 0 && neg > 0) {
@@ -83,30 +81,30 @@ BSPTree::BuildTree(UniquePtr<BSPTreeNode
     else if (pos > 0 && neg > 0) {
       nsTArray<gfx::Point4D> backPoints, frontPoints;
       geometry->SplitPolygon(plane.GetNormal(), dots, backPoints, frontPoints);
 
       const gfx::Point4D& normal = geometry->GetNormal();
       Layer *layer = layerPolygon.layer;
 
       if (backPoints.Length() >= 3) {
-        backLayers.push_back(LayerPolygon(layer, Move(backPoints), normal));
+        backLayers.emplace_back(layer, Move(backPoints), normal);
       }
 
       if (frontPoints.Length() >= 3) {
-        frontLayers.push_back(LayerPolygon(layer, Move(frontPoints), normal));
+        frontLayers.emplace_back(layer, Move(frontPoints), normal);
       }
     }
   }
 
   if (!backLayers.empty()) {
-    aRoot->back.reset(new BSPTreeNode(PopFront(backLayers)));
+    aRoot->back = new (mPool) BSPTreeNode();
     BuildTree(aRoot->back, backLayers);
   }
 
   if (!frontLayers.empty()) {
-    aRoot->front.reset(new BSPTreeNode(PopFront(frontLayers)));
+    aRoot->front = new (mPool) BSPTreeNode();
     BuildTree(aRoot->front, frontLayers);
   }
 }
 
 } // namespace layers
 } // namespace mozilla
--- a/gfx/layers/BSPTree.h
+++ b/gfx/layers/BSPTree.h
@@ -1,107 +1,119 @@
 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef MOZILLA_LAYERS_BSPTREE_H
 #define MOZILLA_LAYERS_BSPTREE_H
 
+#include "mozilla/ArenaAllocator.h"
 #include "mozilla/gfx/Polygon.h"
 #include "mozilla/Move.h"
 #include "mozilla/UniquePtr.h"
 #include "nsTArray.h"
 
-#include <deque>
+#include <list>
 
 namespace mozilla {
 namespace layers {
 
 class Layer;
 
 // Represents a layer that might have a non-rectangular geometry.
 struct LayerPolygon {
   explicit LayerPolygon(Layer *aLayer)
     : layer(aLayer) {}
 
   LayerPolygon(Layer *aLayer,
                gfx::Polygon&& aGeometry)
-    : layer(aLayer), geometry(Some(aGeometry)) {}
+    : layer(aLayer), geometry(Some(Move(aGeometry))) {}
 
   LayerPolygon(Layer *aLayer,
                nsTArray<gfx::Point4D>&& aPoints,
                const gfx::Point4D& aNormal)
-    : layer(aLayer), geometry(Some(gfx::Polygon(Move(aPoints), aNormal))) {}
+    : layer(aLayer)
+  {
+    geometry.emplace(Move(aPoints), aNormal);
+  }
 
   Layer *layer;
   Maybe<gfx::Polygon> geometry;
 };
 
-LayerPolygon PopFront(std::deque<LayerPolygon>& aLayers);
+/**
+ * Allocate BSPTreeNodes from a memory arena to improve performance with
+ * complex scenes.
+ * The arena size of 4096 bytes was selected as an arbitrary power of two.
+ * Depending on the platform, this size accommodates roughly 100 BSPTreeNodes.
+ */
+typedef mozilla::ArenaAllocator<4096, 8> BSPTreeArena;
 
 // Represents a node in a BSP tree. The node contains at least one layer with
 // associated geometry that is used as a splitting plane, and at most two child
 // nodes that represent the splitting planes that further subdivide the space.
 struct BSPTreeNode {
-  explicit BSPTreeNode(LayerPolygon&& layer)
-  {
-    layers.push_back(Move(layer));
-  }
+  BSPTreeNode()
+    : front(nullptr), back(nullptr) {}
 
   const gfx::Polygon& First() const
   {
-    MOZ_ASSERT(layers[0].geometry);
-    return *layers[0].geometry;
+    MOZ_ASSERT(!layers.empty());
+    MOZ_ASSERT(layers.front().geometry);
+    return *layers.front().geometry;
   }
 
-  UniquePtr<BSPTreeNode> front;
-  UniquePtr<BSPTreeNode> back;
-  std::deque<LayerPolygon> layers;
+  static void* operator new(size_t aSize, BSPTreeArena& mPool)
+  {
+    return mPool.Allocate(aSize);
+  }
+
+  BSPTreeNode* front;
+  BSPTreeNode* back;
+  std::list<LayerPolygon> layers;
 };
 
 // BSPTree class takes a list of layers as an input and uses binary space
 // partitioning algorithm to create a tree structure that can be used for
 // depth sorting.
 //
 // Sources for more information:
 // https://en.wikipedia.org/wiki/Binary_space_partitioning
 // ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html
 class BSPTree {
 public:
-  // This constructor takes the ownership of layers in the given list.
-  explicit BSPTree(std::deque<LayerPolygon>& aLayers)
+  /**
+   * The constructor modifies layers in the given list.
+   */
+  explicit BSPTree(std::list<LayerPolygon>& aLayers)
   {
     MOZ_ASSERT(!aLayers.empty());
-    mRoot.reset(new BSPTreeNode(PopFront(aLayers)));
 
+    mRoot = new (mPool) BSPTreeNode();
     BuildTree(mRoot, aLayers);
   }
 
-  // Returns the root node of the BSP tree.
-  const UniquePtr<BSPTreeNode>& GetRoot() const
-  {
-    return mRoot;
-  }
-
   // Builds and returns the back-to-front draw order for the created BSP tree.
   nsTArray<LayerPolygon> GetDrawOrder() const
   {
     nsTArray<LayerPolygon> layers;
     BuildDrawOrder(mRoot, layers);
     return layers;
   }
 
 private:
-  UniquePtr<BSPTreeNode> mRoot;
+  BSPTreeArena mPool;
+  BSPTreeNode* mRoot;
 
   // BuildDrawOrder and BuildTree are called recursively. The depth of the
   // recursion depends on the amount of polygons and their intersections.
-  void BuildDrawOrder(const UniquePtr<BSPTreeNode>& aNode,
+  void BuildDrawOrder(BSPTreeNode* aNode,
                       nsTArray<LayerPolygon>& aLayers) const;
-  void BuildTree(UniquePtr<BSPTreeNode>& aRoot,
-                 std::deque<LayerPolygon>& aLayers);
+
+  void BuildTree(BSPTreeNode* aRoot,
+                 std::list<LayerPolygon>& aLayers);
 };
 
 } // namespace layers
 } // namespace mozilla
 
 #endif /* MOZILLA_LAYERS_BSPTREE_H */
--- a/gfx/layers/Layers.cpp
+++ b/gfx/layers/Layers.cpp
@@ -45,17 +45,17 @@
 #include "nsCSSValue.h"                 // for nsCSSValue::Array, etc
 #include "nsDisplayList.h"              // for nsDisplayItem
 #include "nsPrintfCString.h"            // for nsPrintfCString
 #include "nsStyleStruct.h"              // for nsTimingFunction, etc
 #include "protobuf/LayerScopePacket.pb.h"
 #include "mozilla/Compression.h"
 #include "TreeTraversal.h"              // for ForEachNode
 
-#include <deque>
+#include <list>
 #include <set>
 
 uint8_t gLayerManagerLayerBuilder;
 
 namespace mozilla {
 namespace layers {
 
 FILE*
@@ -1153,18 +1153,17 @@ ContainerLayer::Collect3DContextLeaves(n
         return TraversalFlag::Skip;
       }
   );
 }
 
 static nsTArray<LayerPolygon>
 SortLayersWithBSPTree(nsTArray<Layer*>& aArray)
 {
-  std::deque<LayerPolygon> inputLayers;
-  nsTArray<LayerPolygon> orderedLayers;
+  std::list<LayerPolygon> inputLayers;
 
   // Build a list of polygons to be sorted.
   for (Layer* layer : aArray) {
     // Ignore invisible layers.
     if (!layer->IsVisible()) {
       continue;
     }
 
@@ -1184,22 +1183,23 @@ SortLayersWithBSPTree(nsTArray<Layer*>& 
     polygon.TransformToScreenSpace(transform);
 
     if (polygon.GetPoints().Length() >= 3) {
       inputLayers.push_back(LayerPolygon(layer, Move(polygon)));
     }
   }
 
   if (inputLayers.empty()) {
-    return orderedLayers;
+    return nsTArray<LayerPolygon>();
   }
 
   // Build a BSP tree from the list of polygons.
   BSPTree tree(inputLayers);
-  orderedLayers = Move(tree.GetDrawOrder());
+
+  nsTArray<LayerPolygon> orderedLayers(tree.GetDrawOrder());
 
   // Transform the polygons back to layer space.
   for (LayerPolygon& layerPolygon : orderedLayers) {
     gfx::Matrix4x4 inverse =
       layerPolygon.layer->GetEffectiveTransform().Inverse();
 
     MOZ_ASSERT(layerPolygon.geometry);
     layerPolygon.geometry->TransformToLayerSpace(inverse);
--- a/gfx/tests/gtest/TestBSPTree.cpp
+++ b/gfx/tests/gtest/TestBSPTree.cpp
@@ -16,17 +16,17 @@ using namespace mozilla::gfx;
 using namespace mozilla::layers;
 typedef mozilla::gfx::Polygon MozPolygon;
 
 namespace {
 
 static void RunTest(std::deque<MozPolygon> aPolygons,
                     std::deque<MozPolygon> aExpected)
 {
-  std::deque<LayerPolygon> layers;
+  std::list<LayerPolygon> layers;
   for (MozPolygon& polygon : aPolygons) {
     layers.push_back(LayerPolygon(nullptr, Move(polygon)));
   }
 
   const BSPTree tree(layers);
   const nsTArray<LayerPolygon> order = tree.GetDrawOrder();
 
   EXPECT_EQ(aExpected.size(), order.Length());