Bug 1258460: create microbenchmarks for TreeTraversal.h algorithms r=botond draft
authorKevin Wern <kevin.m.wern@gmail.com>
Tue, 07 Jun 2016 19:43:35 -0700
changeset 376551 2b7efb5370674bc3b9060af8bc0d328a2a7be265
parent 372484 2c7440e46d8786b2c82a1d2004e2b6d9d13f4046
child 523184 9f40811e5f55d3a85bd22e56911de2a8ba39f59f
push id20611
push userkevin.m.wern@gmail.com
push dateWed, 08 Jun 2016 08:21:21 +0000
reviewersbotond
bugs1258460
milestone49.0a1
Bug 1258460: create microbenchmarks for TreeTraversal.h algorithms r=botond MozReview-Commit-ID: 1idDaLOqSd1
gfx/tests/gtest/TestTreeTraversal.cpp
--- a/gfx/tests/gtest/TestTreeTraversal.cpp
+++ b/gfx/tests/gtest/TestTreeTraversal.cpp
@@ -1,56 +1,73 @@
 #include <vector>
 #include "mozilla/RefPtr.h"
 #include "gtest/gtest.h"
+#include "gtest/MozGTestBench.h"
+#include "nsRegion.h"
+#include "nsRect.h"
 #include "TreeTraversal.h"
+#include <stack>
+#include <queue>
+
+#define PERFORMANCE_TREE_DEPTH 20
+#define PERFORMANCE_TREE_CHILD_COUNT 2
+#define PERFORMANCE_TREE_LEAF_COUNT 1048576 // 2 ** 20
+#define PERFORMANCE_REGION_XWRAP 100000
 
 using namespace mozilla::layers;
 using namespace mozilla;
 
 enum class SearchNodeType {Needle, Hay};
 enum class ForEachNodeType {Continue, Skip};
 
 template <class T>
 class TestNodeBase {
   public:
     explicit TestNodeBase(T aType, int aExpectedTraversalRank = -1);
+    explicit TestNodeBase();
     void SetActualTraversalRank(int aRank);
+    void SetType(T aType);
+    void SetRegion(nsRegion* aRegion);
     int GetExpectedTraversalRank();
     int GetActualTraversalRank();
     T GetType();
+    nsRegion* GetRegion();
   private:
     int mExpectedTraversalRank;
     int mActualTraversalRank;
+    nsRegion* mRegion;
     T mType;
   protected:
     ~TestNodeBase<T>() {};
 };
 
 template <class T>
 class TestNodeReverse : public TestNodeBase<T> {
   public:
     NS_INLINE_DECL_REFCOUNTING(TestNodeReverse<T>);
     explicit TestNodeReverse(T aType, int aExpectedTraversalRank = -1);
+    explicit TestNodeReverse();
     void AddChild(RefPtr<TestNodeReverse<T>> aNode);
     TestNodeReverse<T>* GetLastChild();
     TestNodeReverse<T>* GetPrevSibling();
   private:
     void SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode);
     void SetLastChild(RefPtr<TestNodeReverse<T>> aNode);
     RefPtr<TestNodeReverse<T>> mSiblingNode;
     RefPtr<TestNodeReverse<T>> mLastChildNode;
     ~TestNodeReverse<T>() {};
 };
 
 template <class T>
 class TestNodeForward : public TestNodeBase<T> {
   public:
     NS_INLINE_DECL_REFCOUNTING(TestNodeForward<T>);
     explicit TestNodeForward(T aType, int aExpectedTraversalRank = -1);
+    explicit TestNodeForward();
     void AddChild(RefPtr<TestNodeForward<T>> aNode);
     TestNodeForward<T>* GetFirstChild();
     TestNodeForward<T>* GetNextSibling();
   private:
     void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
     void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
     void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
     RefPtr<TestNodeForward<T>> mSiblingNode = nullptr;
@@ -63,16 +80,23 @@ class TestNodeForward : public TestNodeB
 template <class T>
 TestNodeReverse<T>::TestNodeReverse(T aType, int aExpectedTraversalRank) :
   TestNodeBase<T>(aType, aExpectedTraversalRank)
 {
 
 }
 
 template <class T>
+TestNodeReverse<T>::TestNodeReverse() :
+  TestNodeBase<T>()
+{
+
+}
+
+template <class T>
 void TestNodeReverse<T>::SetLastChild(RefPtr<TestNodeReverse<T>> aNode)
 {
   mLastChildNode = aNode;
 }
 
 template <class T>
 void TestNodeReverse<T>::AddChild(RefPtr<TestNodeReverse<T>> aNode)
 {
@@ -101,16 +125,23 @@ TestNodeReverse<T>* TestNodeReverse<T>::
 template <class T>
 TestNodeForward<T>::TestNodeForward(T aType, int aExpectedTraversalRank) :
   TestNodeBase<T>(aType, aExpectedTraversalRank)
 {
 
 }
 
 template <class T>
+TestNodeForward<T>::TestNodeForward() :
+  TestNodeBase<T>()
+{
+
+}
+
+template <class T>
 void TestNodeForward<T>::AddChild(RefPtr<TestNodeForward<T>> aNode)
 {
   if (mFirstChildNode == nullptr) {
     SetFirstChild(aNode);
     SetLastChild(aNode);
   }
   else {
     mLastChildNode->SetNextSibling(aNode);
@@ -152,16 +183,21 @@ template <class T>
 TestNodeBase<T>::TestNodeBase(T aType, int aExpectedTraversalRank):
     mExpectedTraversalRank(aExpectedTraversalRank),
     mActualTraversalRank(-1),
     mType(aType)
 {
 }
 
 template <class T>
+TestNodeBase<T>::TestNodeBase()
+{
+}
+
+template <class T>
 int TestNodeBase<T>::GetActualTraversalRank()
 {
   return mActualTraversalRank;
 }
 
 template <class T>
 void TestNodeBase<T>::SetActualTraversalRank(int aRank)
 {
@@ -175,21 +211,61 @@ int TestNodeBase<T>::GetExpectedTraversa
 }
 
 template <class T>
 T TestNodeBase<T>::GetType()
 {
   return mType;
 }
 
+template <class T>
+void TestNodeBase<T>::SetType(T aType)
+{
+  mType = aType;
+}
+
+template <class T>
+nsRegion* TestNodeBase<T>::GetRegion()
+{
+  return mRegion;
+}
+
+template <class T>
+void TestNodeBase<T>::SetRegion(nsRegion* aRegion)
+{
+  mRegion = aRegion;
+}
+
 typedef TestNodeReverse<SearchNodeType> SearchTestNodeReverse;
 typedef TestNodeReverse<ForEachNodeType> ForEachTestNodeReverse;
 typedef TestNodeForward<SearchNodeType> SearchTestNodeForward;
 typedef TestNodeForward<ForEachNodeType> ForEachTestNodeForward;
 
+template <typename Node, typename Action>
+void CreateBenchmarkTreeRecursive(RefPtr<Node> aNode, int aDepth, int aChildrenCount, Action aAction)
+{
+  if (aDepth > 0) {
+    for (int i = 0; i < aChildrenCount; i++) {
+      RefPtr<Node> newNode = new Node();
+      aNode->AddChild(newNode);
+      CreateBenchmarkTreeRecursive(newNode, aDepth-1, aChildrenCount, aAction);
+    }
+  }
+  aAction(aNode);
+}
+
+template <typename Node, typename Action>
+RefPtr<Node> CreateBenchmarkTree(int aDepth, int aChildrenCount, Action aAction)
+{
+  RefPtr<Node> rootNode = new Node();
+  CreateBenchmarkTreeRecursive(rootNode, aDepth, aChildrenCount, aAction);
+  return rootNode;
+}
+
+
 TEST(TreeTraversal, DepthFirstSearchNull)
 {
   RefPtr<SearchTestNodeReverse> nullNode;
   RefPtr<SearchTestNodeReverse> result = DepthFirstSearch<layers::ReverseIterator>(nullNode.get(),
       [](SearchTestNodeReverse* aNode)
       {
         return aNode->GetType() == SearchNodeType::Needle;
       });
@@ -1145,8 +1221,966 @@ TEST(TreeTraversal, ForEachNodeLambdaRet
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
     ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
         nodeList[i]->GetActualTraversalRank())
         << "Node at index " << i << " was hit out of order.";
   }
 }
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchForwardRecursive(RefPtr<Node> aNode)
+{
+  if (aNode->GetType() == SearchNodeType::Needle) {
+    return aNode;
+  }
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    if (RefPtr<Node> foundNode = DepthFirstSearchForwardRecursive(node)) {
+      return foundNode;
+    }
+  }
+  return nullptr;
+}
+
+static void Plain_ForwardDepthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> needleNode;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [&needleNode](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetFirstChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode =
+    DepthFirstSearchForwardRecursive<SearchTestNodeForward>(root.get());
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardDepthFirstSearchPerformance, &Plain_ForwardDepthFirstSearchPerformance);
+
+static void TreeTraversal_ForwardDepthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> needleNode;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [&needleNode](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetFirstChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearch<layers::ForwardIterator>(root.get(),
+      [](SearchTestNodeForward* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardDepthFirstSearchPerformance, &TreeTraversal_ForwardDepthFirstSearchPerformance);
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchCaptureVariablesForwardRecursive(RefPtr<Node> aNode,
+    int a, int b, int c, int d, int e, int f,
+    int g, int h, int i, int j, int k, int l,
+    int m, int& n, int& o, int& p, int& q, int& r,
+    int& s, int& t, int& u, int& v, int& w, int& x,
+    int& y, int& z)
+{
+  if (aNode->GetType() == SearchNodeType::Needle) {
+    return aNode;
+  }
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    if (RefPtr<Node> foundNode = DepthFirstSearchCaptureVariablesForwardRecursive(node,
+          a, b, c, d, e, f, g, h, i, j, k, l, m,
+          n, o, p, q, r, s, t, u, v, w, x, y, z)) {
+      return foundNode;
+    }
+  }
+  return nullptr;
+}
+
+static void Plain_ForwardDepthFirstSearchCaptureVariablesPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int a = 1; int b = 1; int c = 1; int d = 1; int e = 1; int f = 1;
+  int g = 1; int h = 1; int i = 1; int j = 1; int k = 1; int l = 1;
+  int m = 1; int n = 1; int o = 1; int p = 1; int q = 1; int r = 1;
+  int s = 1; int t = 1; int u = 1; int v = 1; int w = 1; int x = 1;
+  int y = 1; int z = 1;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> needleNode;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [&needleNode](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetFirstChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode =
+      DepthFirstSearchCaptureVariablesForwardRecursive<SearchTestNodeForward>(root.get(),
+          a, b, c, d, e, f, g, h, i, j, k, l, m,
+          n, o, p, q, r, s, t, u, v, w, x, y, z);
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardDepthFirstSearchCaptureVariablesPerformance, &Plain_ForwardDepthFirstSearchCaptureVariablesPerformance);
+
+static void TreeTraversal_ForwardDepthFirstSearchCaptureVariablesPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int a = 1; int b = 1; int c = 1; int d = 1; int e = 1; int f = 1;
+  int g = 1; int h = 1; int i = 1; int j = 1; int k = 1; int l = 1;
+  int m = 1; int n = 1; int o = 1; int p = 1; int q = 1; int r = 1;
+  int s = 1; int t = 1; int u = 1; int v = 1; int w = 1; int x = 1;
+  int y = 1; int z = 1;
+  RefPtr<SearchTestNodeForward> needleNode;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [&needleNode](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetFirstChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearch<layers::ForwardIterator>(root.get(),
+      [a, b, c, d, e, f, g, h, i, j, k, l, m,
+      &n, &o, &p, &q, &r, &s, &t, &u, &v, &w, &x, &y, &z]
+      (SearchTestNodeForward* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardDepthFirstSearchCaptureVariablesPerformance, &TreeTraversal_ForwardDepthFirstSearchCaptureVariablesPerformance);
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchPostOrderForwardRecursive(RefPtr<Node> aNode)
+{
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    if (RefPtr<Node> foundNode = DepthFirstSearchPostOrderForwardRecursive(node)) {
+      return foundNode;
+    }
+  }
+  if (aNode->GetType() == SearchNodeType::Needle) {
+    return aNode;
+  }
+  return nullptr;
+}
+
+static void Plain_ForwardDepthFirstSearchPostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+      });
+  root->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode =
+    DepthFirstSearchPostOrderForwardRecursive<SearchTestNodeForward>(root.get());
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(root, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardDepthFirstSearchPostOrderPerformance, &Plain_ForwardDepthFirstSearchPostOrderPerformance);
+
+static void TreeTraversal_ForwardDepthFirstSearchPostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+      });
+  root->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearchPostOrder<layers::ForwardIterator>(root.get(),
+      [](SearchTestNodeForward* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(root, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardDepthFirstSearchPostOrderPerformance, &TreeTraversal_ForwardDepthFirstSearchPostOrderPerformance);
+
+template <typename Node>
+static RefPtr<Node> BreadthFirstSearchForwardQueue(RefPtr<Node> aNode)
+{
+  RefPtr<Node> returnNode = nullptr;
+  queue<RefPtr<Node>> nodes;
+  nodes.push(aNode);
+  while(!nodes.empty()) {
+    RefPtr<Node> node = nodes.front();
+    nodes.pop();
+    if (node->GetType() == SearchNodeType::Needle){
+      return node;
+    }
+    for (RefPtr<Node> childNode = node->GetFirstChild();
+        childNode != nullptr;
+        childNode = childNode->GetNextSibling()) {
+      nodes.push(childNode);
+    }
+  }
+  return nullptr;
+}
+
+static void Plain_ForwardBreadthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> needleNode;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [&needleNode](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetFirstChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode =
+      BreadthFirstSearchForwardQueue<SearchTestNodeForward>(root.get());
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardBreadthFirstSearchPerformance, &Plain_ForwardBreadthFirstSearchPerformance);
+
+static void TreeTraversal_ForwardBreadthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeForward> needleNode;
+  RefPtr<SearchTestNodeForward> root = CreateBenchmarkTree<SearchTestNodeForward>(depth, childrenCount,
+      [&needleNode](SearchTestNodeForward* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetFirstChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeForward> foundNode = BreadthFirstSearch<layers::ForwardIterator>(root.get(),
+      [](SearchTestNodeForward* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardBreadthFirstSearchPerformance, &TreeTraversal_ForwardBreadthFirstSearchPerformance);
+
+// This test ((Plain|TreeTraversal)_ForwardForEachNodePostOrderPerformance)
+// uses the following benchmark:
+//
+// Starting with a tree whose leaves only are augmented with region data
+// (arranged as a series of 1x1 blocks stacked in rows of 100000), calculate
+// each ancestor's region as the union of its child regions.
+template <typename Node>
+static void ForEachNodePostOrderForwardRecursive(RefPtr<Node> aNode)
+{
+  aNode->SetRegion(new nsRegion());
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    ForEachNodePostOrderForwardRecursive(node);
+    nsRegion* currentRegion = aNode->GetRegion();
+    nsRegion* childRegion = node->GetRegion();
+    nsRegion* newRegion = new nsRegion(currentRegion->OrWith(*childRegion));
+    aNode->SetRegion(newRegion);
+  }
+}
+
+static void Plain_ForwardForEachNodePostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int squareCount = 0;
+  int xWrap = PERFORMANCE_REGION_XWRAP;
+  RefPtr<ForEachTestNodeForward> root = CreateBenchmarkTree<ForEachTestNodeForward>(depth, childrenCount,
+      [&squareCount, xWrap](ForEachTestNodeForward* aNode) {
+        if (aNode->GetFirstChild() == nullptr) {
+          int x = squareCount % xWrap;
+          int y = squareCount / xWrap;
+          aNode->SetRegion(new nsRegion(nsRect(x, y, 1, 1)));
+        }
+      });
+  ForEachNodePostOrderForwardRecursive(root);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardForEachNodePostOrderPerformance, &Plain_ForwardForEachNodePostOrderPerformance);
+
+static void TreeTraversal_ForwardForEachNodePostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int squareCount = 0;
+  int xWrap = PERFORMANCE_REGION_XWRAP;
+  RefPtr<ForEachTestNodeForward> root = CreateBenchmarkTree<ForEachTestNodeForward>(depth, childrenCount,
+      [&squareCount, xWrap](ForEachTestNodeForward* aNode) {
+        if (aNode->GetFirstChild() == nullptr) {
+          int x = squareCount % xWrap;
+          int y = squareCount / xWrap;
+          aNode->SetRegion(new nsRegion(nsRect(x, y, 1, 1)));
+        }
+      });
+  ForEachNodePostOrder<layers::ForwardIterator>(root.get(),
+      [](ForEachTestNodeForward* aNode) {
+        if (aNode->GetFirstChild()) {
+          aNode->SetRegion(new nsRegion());
+          for (RefPtr<ForEachTestNodeForward> node = aNode->GetFirstChild();
+              node != nullptr;
+              node = node->GetNextSibling()) {
+            nsRegion* currentRegion = aNode->GetRegion();
+            nsRegion* childRegion = node->GetRegion();
+            nsRegion* newRegion = new nsRegion(currentRegion->OrWith(*childRegion));
+            aNode->SetRegion(newRegion);
+          }
+        }
+      });
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardForEachNodePostOrderPerformance, &TreeTraversal_ForwardForEachNodePostOrderPerformance);
+
+// This test ((Plain|TreeTraversal)_ForwardForEachNodePerformance) uses the
+// following benchmark:
+//
+// Starting with a tree whose root has a rectangular region of size
+// PERFORMANCE_TREE_LEAF_COUNT x 1, for each node, split the region into
+// PERFORMANCE_TREE_CHILD_COUNT separate regions of equal width and assign to
+// each child left-to-right. In the end, every node's region should equal the
+// sum of its childrens' regions, and each level of depth's regions should sum
+// to the root's region.
+template <typename Node>
+static void ForEachNodeForwardRecursive(RefPtr<Node> aNode)
+{
+  int nChildren = 0;
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    nChildren++;
+  }
+  nsRect bounds = aNode->GetRegion()->GetBounds();
+  int childWidth = bounds.width;
+  int x = bounds.x;
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    node->SetRegion(new nsRegion(nsRect(x, 0, childWidth, 1)));
+    ForEachNodeForwardRecursive(node);
+    x += childWidth;
+  }
+}
+
+static void Plain_ForwardForEachNodePerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  RefPtr<ForEachTestNodeForward> root = CreateBenchmarkTree<ForEachTestNodeForward>(depth, childrenCount,
+      [](ForEachTestNodeForward* aNode) {
+      });
+  root->SetRegion(new nsRegion(nsRect(0, 0, rectangleWidth, 1)));
+  ForEachNodeForwardRecursive(root);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardForEachNodePerformance, &Plain_ForwardForEachNodePerformance);
+
+static void TreeTraversal_ForwardForEachNodePerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  RefPtr<ForEachTestNodeForward> root = CreateBenchmarkTree<ForEachTestNodeForward>(depth, childrenCount,
+      [](ForEachTestNodeForward* aNode) {
+      });
+  root->SetRegion(new nsRegion(nsRect(0, 0, rectangleWidth, 1)));
+  ForEachNode<layers::ForwardIterator>(root.get(),
+      [](ForEachTestNodeForward* aNode) {
+        int nChildren = 0;
+        for (RefPtr<ForEachTestNodeForward> node = aNode->GetFirstChild();
+            node != nullptr;
+            node = node->GetNextSibling()) {
+          nChildren++;
+        }
+        nsRect bounds = aNode->GetRegion()->GetBounds();
+        int childWidth = bounds.width;
+        int x = bounds.x;
+        for (RefPtr<ForEachTestNodeForward> node = aNode->GetFirstChild();
+            node != nullptr;
+            node = node->GetNextSibling()) {
+          node->SetRegion(new nsRegion(nsRect(x, 0, childWidth, 1)));
+          x += childWidth;
+        }
+      });
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardForEachNodePerformance, &TreeTraversal_ForwardForEachNodePerformance);
+
+// This test ((Plain|TreeTraversal)_ForwardForEachNodeStackPerformance) uses
+// the following benchmark:
+//
+// Starting with an unattached region equal to PERFORMANCE_TREE_LEAF_COUNT x 1,
+// a starting width of PERFORMANCE_TREE_LEAF_COUNT, and an empty tree, create a
+// tree with the same conditions as
+// ((Plain|TreeTraversal)_ForwardForEachNodePerformance) by assigning regions
+// of the current width, starting from the min x and min y coordinates. For
+// each level of depth, the current width decreases by a factor of
+// PERFORMANCE_TREE_CHILD_COUNT, and a stack of ancestor regions is maintained.
+// The stack is used to track the poriton of each region that is still
+// available to assign to children, which determines the aformentioned min x
+// and min y coordinates. Compare this to using the program stack.
+template <typename Node>
+static void ForEachNodeForwardStackRecursive(RefPtr<Node> aNode, int aRectangleWidth, nsRegion aRegion, int childrenCount)
+{
+  nsRect parentRect = aRegion.GetBounds();
+  nsRect newRectangle(parentRect.x, parentRect.y, aRectangleWidth, 1);
+  nsRegion newRegion(newRectangle);
+  aNode->SetRegion(new nsRegion(newRegion));
+
+  int newRectangleWidth = aRectangleWidth / childrenCount;
+
+  for (RefPtr<Node> node = aNode->GetFirstChild();
+      node != nullptr;
+      node = node->GetNextSibling()) {
+    ForEachNodeForwardStackRecursive(node, newRectangleWidth, newRegion, childrenCount);
+    newRegion = newRegion.SubOut(node->GetRegion()->GetBounds());
+  }
+}
+
+static void Plain_ForwardForEachNodeStackPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  RefPtr<ForEachTestNodeForward> root = CreateBenchmarkTree<ForEachTestNodeForward>(depth, childrenCount,
+      [](ForEachTestNodeForward* aNode) {
+      });
+  nsRegion startRegion(nsRect(0, 0, rectangleWidth, 1));
+  ForEachNodeForwardStackRecursive(root, rectangleWidth, startRegion, childrenCount);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ForwardForEachNodeStackPerformance, &Plain_ForwardForEachNodeStackPerformance);
+
+static void TreeTraversal_ForwardForEachNodeStackPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  stack<nsRegion*> regionStack;
+  RefPtr<ForEachTestNodeForward> root = CreateBenchmarkTree<ForEachTestNodeForward>(depth, childrenCount,
+      [](ForEachTestNodeForward* aNode) {
+      });
+  regionStack.push(new nsRegion(nsRect(0, 0, rectangleWidth, 1)));
+  ForEachNode<layers::ForwardIterator>(root.get(),
+      [&regionStack, &rectangleWidth, childrenCount](ForEachTestNodeForward* aNode) {
+        nsRegion* parentRegion = regionStack.top();
+        nsRect parentRect = parentRegion->GetBounds();
+        nsRect newRect(parentRect.x, parentRect.y, rectangleWidth, 1);
+        nsRegion newRegion(newRect);
+        aNode->SetRegion(new nsRegion(newRegion));
+        regionStack.top() = new nsRegion(regionStack.top()->SubOut(newRegion));
+        regionStack.push(new nsRegion(newRegion));
+        rectangleWidth /= childrenCount;
+      },
+      [&regionStack, &rectangleWidth, childrenCount](ForEachTestNodeForward* aNode) {
+        regionStack.pop();
+        rectangleWidth *= childrenCount;
+      });
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ForwardForEachNodeStackPerformance, &TreeTraversal_ForwardForEachNodeStackPerformance);
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchReverseRecursive(RefPtr<Node> aNode)
+{
+  if (aNode->GetType() == SearchNodeType::Needle) {
+    return aNode;
+  }
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    if (RefPtr<Node> foundNode = DepthFirstSearchReverseRecursive(node)) {
+      return foundNode;
+    }
+  }
+  return nullptr;
+}
+
+static void Plain_ReverseDepthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [&needleNode](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetLastChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode =
+    DepthFirstSearchReverseRecursive<SearchTestNodeReverse>(root.get());
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseDepthFirstSearchPerformance, &Plain_ReverseDepthFirstSearchPerformance);
+
+static void TreeTraversal_ReverseDepthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [&needleNode](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (!needleNode) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearch<layers::ReverseIterator>(root.get(),
+      [](SearchTestNodeReverse* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseDepthFirstSearchPerformance, &TreeTraversal_ReverseDepthFirstSearchPerformance);
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchCaptureVariablesReverseRecursive(RefPtr<Node> aNode,
+    int a, int b, int c, int d, int e, int f,
+    int g, int h, int i, int j, int k, int l,
+    int m, int& n, int& o, int& p, int& q, int& r,
+    int& s, int& t, int& u, int& v, int& w, int& x,
+    int& y, int& z)
+{
+  if (aNode->GetType() == SearchNodeType::Needle) {
+    return aNode;
+  }
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    if (RefPtr<Node> foundNode = DepthFirstSearchCaptureVariablesReverseRecursive(node,
+            a, b, c, d, e, f, g, h, i, j, k, l, m,
+            n, o, p, q, r, s, t, u, v, w, x, y, z)) {
+      return foundNode;
+    }
+  }
+  return nullptr;
+}
+
+static void Plain_ReverseDepthFirstSearchCaptureVariablesPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int a = 1; int b = 1; int c = 1; int d = 1; int e = 1; int f = 1;
+  int g = 1; int h = 1; int i = 1; int j = 1; int k = 1; int l = 1;
+  int m = 1; int n = 1; int o = 1; int p = 1; int q = 1; int r = 1;
+  int s = 1; int t = 1; int u = 1; int v = 1; int w = 1; int x = 1;
+  int y = 1; int z = 1;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [&needleNode](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetLastChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode =
+      DepthFirstSearchCaptureVariablesReverseRecursive<SearchTestNodeReverse>(root.get(),
+          a, b, c, d, e, f, g, h, i, j, k, l, m,
+          n, o, p, q, r, s, t, u, v, w, x, y, z);
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseDepthFirstSearchCaptureVariablesPerformance, &Plain_ReverseDepthFirstSearchCaptureVariablesPerformance);
+
+static void TreeTraversal_ReverseDepthFirstSearchCaptureVariablesPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int a = 1; int b = 1; int c = 1; int d = 1; int e = 1; int f = 1;
+  int g = 1; int h = 1; int i = 1; int j = 1; int k = 1; int l = 1;
+  int m = 1; int n = 1; int o = 1; int p = 1; int q = 1; int r = 1;
+  int s = 1; int t = 1; int u = 1; int v = 1; int w = 1; int x = 1;
+  int y = 1; int z = 1;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [&needleNode](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (!needleNode) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearch<layers::ReverseIterator>(root.get(),
+      [a, b, c, d, e, f, g, h, i, j, k, l, m,
+      &n, &o, &p, &q, &r, &s, &t, &u, &v, &w, &x, &y, &z]
+      (SearchTestNodeReverse* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseDepthFirstSearchCaptureVariablesPerformance, &TreeTraversal_ReverseDepthFirstSearchCaptureVariablesPerformance);
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchPostOrderReverseRecursive(RefPtr<Node> aNode)
+{
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    if (RefPtr<Node> foundNode = DepthFirstSearchPostOrderReverseRecursive(node)) {
+      return foundNode;
+    }
+  }
+  if (aNode->GetType() == SearchNodeType::Needle) {
+    return aNode;
+  }
+  return nullptr;
+}
+
+static void Plain_ReverseDepthFirstSearchPostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+      });
+  root->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode =
+    DepthFirstSearchPostOrderReverseRecursive<SearchTestNodeReverse>(root.get());
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(root, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseDepthFirstSearchPostOrderPerformance, &Plain_ReverseDepthFirstSearchPostOrderPerformance);
+
+static void TreeTraversal_ReverseDepthFirstSearchPostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+      });
+  root->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
+      [](SearchTestNodeReverse* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(root, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseDepthFirstSearchPostOrderPerformance, &TreeTraversal_ReverseDepthFirstSearchPostOrderPerformance);
+
+template <typename Node>
+static RefPtr<Node> BreadthFirstSearchReverseQueue(RefPtr<Node> aNode)
+{
+  RefPtr<Node> returnNode = nullptr;
+  queue<RefPtr<Node>> nodes;
+  nodes.push(aNode);
+  while(!nodes.empty()) {
+    RefPtr<Node> node = nodes.front();
+    nodes.pop();
+    if (node->GetType() == SearchNodeType::Needle){
+      return node;
+    }
+    for (RefPtr<Node> childNode = node->GetLastChild();
+        childNode != nullptr;
+        childNode = childNode->GetPrevSibling()) {
+      nodes.push(childNode);
+    }
+  }
+  return nullptr;
+}
+
+static void Plain_ReverseBreadthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [&needleNode](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (aNode->GetLastChild() == nullptr) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode =
+    BreadthFirstSearchReverseQueue<SearchTestNodeReverse>(root.get());
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseBreadthFirstSearchPerformance, &Plain_ReverseBreadthFirstSearchPerformance);
+
+static void TreeTraversal_ReverseBreadthFirstSearchPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  RefPtr<SearchTestNodeReverse> root = CreateBenchmarkTree<SearchTestNodeReverse>(depth, childrenCount,
+      [&needleNode](SearchTestNodeReverse* aNode) {
+        aNode->SetType(SearchNodeType::Hay);
+        if (!needleNode) {
+          needleNode = aNode;
+        }
+      });
+  needleNode->SetType(SearchNodeType::Needle);
+  RefPtr<SearchTestNodeReverse> foundNode = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
+      [](SearchTestNodeReverse* aNode) {
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle);
+  ASSERT_EQ(needleNode, foundNode);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseBreadthFirstSearchPerformance, &TreeTraversal_ReverseBreadthFirstSearchPerformance);
+
+// This test ((Plain|TreeTraversal)_ForwardForEachNodePostOrderPerformance)
+// uses the following benchmark:
+//
+// Starting with a tree whose leaves only are augmented with region data
+// (arranged as a series of 1x1 blocks stacked in rows of 100000), calculate
+// each ancestor's region as the union of its child regions.
+template <typename Node>
+static void ForEachNodePostOrderReverseRecursive(RefPtr<Node> aNode)
+{
+  aNode->SetRegion(new nsRegion());
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    ForEachNodePostOrderReverseRecursive(node);
+    nsRegion* currentRegion = aNode->GetRegion();
+    nsRegion* childRegion = node->GetRegion();
+    nsRegion* newRegion = new nsRegion(currentRegion->OrWith(*childRegion));
+    aNode->SetRegion(newRegion);
+  }
+}
+
+static void Plain_ReverseForEachNodePostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int squareCount = 0;
+  int xWrap = PERFORMANCE_REGION_XWRAP;
+  RefPtr<ForEachTestNodeReverse> root = CreateBenchmarkTree<ForEachTestNodeReverse>(depth, childrenCount,
+      [&squareCount, xWrap](ForEachTestNodeReverse* aNode) {
+        if (aNode->GetLastChild() == nullptr) {
+          int x = squareCount % xWrap;
+          int y = squareCount / xWrap;
+          aNode->SetRegion(new nsRegion(nsRect(x, y, 1, 1)));
+        }
+      });
+  ForEachNodePostOrderReverseRecursive(root);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseForEachNodePostOrderPerformance, &Plain_ReverseForEachNodePostOrderPerformance);
+
+static void TreeTraversal_ReverseForEachNodePostOrderPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int squareCount = 0;
+  int xWrap = PERFORMANCE_REGION_XWRAP;
+  RefPtr<ForEachTestNodeReverse> root = CreateBenchmarkTree<ForEachTestNodeReverse>(depth, childrenCount,
+      [&squareCount, xWrap](ForEachTestNodeReverse* aNode) {
+        if (aNode->GetLastChild() == nullptr) {
+          int x = squareCount % xWrap;
+          int y = squareCount / xWrap;
+          aNode->SetRegion(new nsRegion(nsRect(x, y, 1, 1)));
+        }
+      });
+  ForEachNodePostOrder<layers::ReverseIterator>(root.get(),
+      [](ForEachTestNodeReverse* aNode) {
+        if (aNode->GetLastChild()) {
+          aNode->SetRegion(new nsRegion());
+          for (RefPtr<ForEachTestNodeReverse> node = aNode->GetLastChild();
+              node != nullptr;
+              node = node->GetPrevSibling()) {
+            nsRegion* currentRegion = aNode->GetRegion();
+            nsRegion* childRegion = node->GetRegion();
+            nsRegion* newRegion = new nsRegion(currentRegion->OrWith(*childRegion));
+            aNode->SetRegion(newRegion);
+          }
+        }
+      });
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseForEachNodePostOrderPerformance, &TreeTraversal_ReverseForEachNodePostOrderPerformance);
+
+// This test ((Plain|TreeTraversal)_ReverseForEachNodePerformance) uses the
+// following benchmark:
+//
+// Starting with a tree whose root has a rectangular region of size
+// PERFORMANCE_TREE_LEAF_COUNT x 1, for each node, split the region into
+// PERFORMANCE_TREE_CHILD_COUNT separate regions of equal width and assign to
+// each child left-to-right. In the end, every node's region should equal the
+// sum of its childrens' regions, and each level of depth's regions should sum
+// to the root's region.
+template <typename Node>
+static void ForEachNodeReverseRecursive(RefPtr<Node> aNode)
+{
+  int nChildren = 0;
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    nChildren++;
+  }
+  nsRect bounds = aNode->GetRegion()->GetBounds();
+  int childWidth = bounds.width;
+  int x = bounds.x;
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    node->SetRegion(new nsRegion(nsRect(x, 0, childWidth, 1)));
+    ForEachNodeReverseRecursive(node);
+    x += childWidth;
+  }
+}
+
+static void Plain_ReverseForEachNodePerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  RefPtr<ForEachTestNodeReverse> root = CreateBenchmarkTree<ForEachTestNodeReverse>(depth, childrenCount,
+      [](ForEachTestNodeReverse* aNode) {
+      });
+  root->SetRegion(new nsRegion(nsRect(0, 0, rectangleWidth, 1)));
+  ForEachNodeReverseRecursive(root);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseForEachNodePerformance, &Plain_ReverseForEachNodePerformance);
+
+static void TreeTraversal_ReverseForEachNodePerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  RefPtr<ForEachTestNodeReverse> root = CreateBenchmarkTree<ForEachTestNodeReverse>(depth, childrenCount,
+      [](ForEachTestNodeReverse* aNode) {
+      });
+  root->SetRegion(new nsRegion(nsRect(0, 0, rectangleWidth, 1)));
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [](ForEachTestNodeReverse* aNode) {
+        int nChildren = 0;
+        for (RefPtr<ForEachTestNodeReverse> node = aNode->GetLastChild();
+            node != nullptr;
+            node = node->GetPrevSibling()) {
+          nChildren++;
+        }
+        nsRect bounds = aNode->GetRegion()->GetBounds();
+        int childWidth = bounds.width;
+        int x = bounds.x;
+        for (RefPtr<ForEachTestNodeReverse> node = aNode->GetLastChild();
+            node != nullptr;
+            node = node->GetPrevSibling()) {
+          node->SetRegion(new nsRegion(nsRect(x, 0, childWidth, 1)));
+          x += childWidth;
+        }
+      });
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseForEachNodePerformance, &TreeTraversal_ReverseForEachNodePerformance);
+
+// This test ((Plain|TreeTraversal)_ReverseForEachNodeStackPerformance) uses
+// the following benchmark:
+//
+// Starting with an unattached region equal to PERFORMANCE_TREE_LEAF_COUNT x 1,
+// a starting width of PERFORMANCE_TREE_LEAF_COUNT, and an empty tree, create a
+// tree with the same conditions as
+// ((Plain|TreeTraversal)_ReverseForEachNodePerformance) by assigning regions
+// of the current width, starting from the min x and min y coordinates. For
+// each level of depth, the current width decreases by a factor of
+// PERFORMANCE_TREE_CHILD_COUNT, and a stack of ancestor regions is maintained.
+// The stack is used to track the poriton of each region that is still
+// available to assign to children, which determines the aformentioned min x
+// and min y coordinates. Compare this to using the program stack.
+template <typename Node>
+static void ForEachNodeReverseStackRecursive(RefPtr<Node> aNode, int aRectangleWidth, nsRegion aRegion, int childrenCount)
+{
+  nsRect parentRect = aRegion.GetBounds();
+  nsRect newRectangle(parentRect.x, parentRect.y, aRectangleWidth, 1);
+  nsRegion newRegion(newRectangle);
+  aNode->SetRegion(new nsRegion(newRegion));
+
+  int newRectangleWidth = aRectangleWidth / childrenCount;
+
+  for (RefPtr<Node> node = aNode->GetLastChild();
+      node != nullptr;
+      node = node->GetPrevSibling()) {
+    ForEachNodeReverseStackRecursive(node, newRectangleWidth, newRegion, childrenCount);
+    newRegion = newRegion.SubOut(node->GetRegion()->GetBounds());
+  }
+}
+
+static void Plain_ReverseForEachNodeStackPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  RefPtr<ForEachTestNodeReverse> root = CreateBenchmarkTree<ForEachTestNodeReverse>(depth, childrenCount,
+      [](ForEachTestNodeReverse* aNode) {
+      });
+  nsRegion startRegion(nsRect(0, 0, rectangleWidth, 1));
+  ForEachNodeReverseStackRecursive(root, rectangleWidth, startRegion, childrenCount);
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, Plain_ReverseForEachNodeStackPerformance, &Plain_ReverseForEachNodeStackPerformance);
+
+static void TreeTraversal_ReverseForEachNodeStackPerformance()
+{
+  int depth = PERFORMANCE_TREE_DEPTH;
+  int childrenCount = PERFORMANCE_TREE_CHILD_COUNT;
+  int rectangleWidth = PERFORMANCE_TREE_LEAF_COUNT;
+  stack<nsRegion*> regionStack;
+  RefPtr<ForEachTestNodeReverse> root = CreateBenchmarkTree<ForEachTestNodeReverse>(depth, childrenCount,
+      [](ForEachTestNodeReverse* aNode) {
+      });
+  regionStack.push(new nsRegion(nsRect(0, 0, rectangleWidth, 1)));
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [&regionStack, &rectangleWidth, childrenCount](ForEachTestNodeReverse* aNode) {
+        nsRegion* parentRegion = regionStack.top();
+        nsRect parentRect = parentRegion->GetBounds();
+        nsRect newRect(parentRect.x, parentRect.y, rectangleWidth, 1);
+        nsRegion newRegion(newRect);
+        aNode->SetRegion(new nsRegion(newRegion));
+        regionStack.top() = new nsRegion(regionStack.top()->SubOut(newRegion));
+        regionStack.push(new nsRegion(newRegion));
+        rectangleWidth /= childrenCount;
+      },
+      [&regionStack, &rectangleWidth, childrenCount](ForEachTestNodeReverse* aNode) {
+        regionStack.pop();
+        rectangleWidth *= childrenCount;
+      });
+}
+
+MOZ_GTEST_BENCH(TreeTraversal, TreeTraversal_ReverseForEachNodeStackPerformance, &TreeTraversal_ReverseForEachNodeStackPerformance);