Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel
authorBenoit Girard <b56girard@gmail.com>
Thu, 27 Aug 2015 16:06:38 -0400
changeset 290129 394c9900b838a9ae3bd40ecc27aafbb6d76b4dc3
parent 290128 1cc3d0a27d30363a6e3e3727d67fc05ef758b826
child 290130 85ff16d9d6f3dffaaf07d22b82d85bde8629253c
push id30114
push usercbook@mozilla.com
push dateThu, 24 Mar 2016 15:15:54 +0000
treeherdermozilla-central@24c5fbde4488 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjrmuizel
bugs1248044
milestone48.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1248044 - Add PingPongRegion for faster region operations for 2x memory usage. r=jrmuizel MozReview-Commit-ID: KiIGiQYN33u
gfx/src/PingPongRegion.h
gfx/src/moz.build
gfx/tests/gtest/TestRegion.cpp
new file mode 100644
--- /dev/null
+++ b/gfx/src/PingPongRegion.h
@@ -0,0 +1,63 @@
+/* -*- 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 PingPongRegion_h__
+#define PingPongRegion_h__
+
+/* This class uses a pair of regions and swaps between them while
+ * accumulating to avoid the heap allocations associated with
+ * modifying a region in place.
+ *
+ * It is sizeof(T)*2 + sizeof(T*) and can use end up using
+ * approximately double the amount of memory as using single
+ * region so use it sparingly.
+ */
+
+template <typename T>
+class PingPongRegion
+{
+  typedef typename T::RectType RectType;
+public:
+  PingPongRegion()
+  {
+    rgn = &rgn1;
+  }
+
+  void SubOut(const RectType& aOther)
+  {
+    T* nextRgn = nextRegion();
+    nextRgn->Sub(*rgn, aOther);
+    rgn = nextRgn;
+  }
+
+  void OrWith(const RectType& aOther)
+  {
+    T* nextRgn = nextRegion();
+    nextRgn->Or(*rgn, aOther);
+    rgn = nextRgn;
+  }
+
+  T& Region()
+  {
+    return *rgn;
+  }
+
+private:
+
+  T* nextRegion()
+  {
+    if (rgn == &rgn1) {
+      return &rgn2;
+    } else {
+      return &rgn1;
+    }
+  }
+
+  T* rgn;
+  T rgn1;
+  T rgn2;
+};
+
+#endif
--- a/gfx/src/moz.build
+++ b/gfx/src/moz.build
@@ -32,16 +32,17 @@ EXPORTS += [
     'nsPoint.h',
     'nsRect.h',
     'nsRegion.h',
     'nsRegionFwd.h',
     'nsRenderingContext.h',
     'nsSize.h',
     'nsThemeConstants.h',
     'nsTransform2D.h',
+    'PingPongRegion.h',
     'RegionBuilder.h',
 ]
 
 EXPORTS.mozilla += [
     'AppUnits.h',
 ]
 
 if CONFIG['MOZ_X11']:
--- a/gfx/tests/gtest/TestRegion.cpp
+++ b/gfx/tests/gtest/TestRegion.cpp
@@ -1,15 +1,16 @@
 /* -*- 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/. */
 
 #include <algorithm>
 
+#include "PingPongRegion.h"
 #include "gtest/gtest.h"
 #include "gtest/MozGTestBench.h"
 #include "nsRect.h"
 #include "nsRegion.h"
 #include "RegionBuilder.h"
 
 using namespace std;
 
@@ -558,49 +559,105 @@ TEST(Gfx, RegionVisitEdges) {
     r.Or(r, nsRect(115, 49, 99, 1));
     r.Or(r, nsRect(12, 50, 11, 5));
     r.Or(r, nsRect(25, 50, 28, 5));
     r.Or(r, nsRect(115, 50, 99, 5));
     r.Or(r, nsRect(115, 55, 99, 12));
 
     TestVisit(r);
   }
+}
 
+TEST(Gfx, PingPongRegion) {
+  nsRect rects[] = {
+    nsRect(4, 1, 61, 49),
+    nsRect(115, 1, 99, 49),
+    nsRect(115, 49, 99, 1),
+    nsRect(12, 50, 11, 5),
+    nsRect(25, 50, 28, 5),
+    nsRect(115, 50, 99, 5),
+    nsRect(115, 55, 99, 12),
+  };
+
+  // Test accumulations of various sizes to make sure
+  // the ping-pong behavior of PingPongRegion is working.
+  for (size_t size = 0; size < mozilla::ArrayLength(rects); size++) {
+    // bug 1130978.
+    nsRegion r;
+    PingPongRegion<nsRegion> ar;
+    for (size_t i = 0; i < size; i++) {
+      r.Or(r, rects[i]);
+      ar.OrWith(rects[i]);
+      EXPECT_TRUE(ar.Region().IsEqual(r));
+    }
+
+    for (size_t i = 0; i < size; i++) {
+      ar.SubOut(rects[i]);
+      r.SubOut(rects[i]);
+      EXPECT_TRUE(ar.Region().IsEqual(r));
+    }
+  }
 }
 
 MOZ_GTEST_BENCH(GfxBench, RegionOr, []{
   const int size = 5000;
+
   nsRegion r;
   for (int i = 0; i < size; i++) {
     r = r.Or(r, nsRect(i, i, i + 10, i + 10));
   }
+
+  nsIntRegion rInt;
+  for (int i = 0; i < size; i++) {
+    rInt = rInt.Or(rInt, nsIntRect(i, i, i + 10, i + 10));
+  }
 });
 
 MOZ_GTEST_BENCH(GfxBench, RegionAnd, []{
   const int size = 5000;
   nsRegion r(nsRect(0, 0, size, size));
   for (int i = 0; i < size; i++) {
     nsRegion rMissingPixel(nsRect(0, 0, size, size));
     rMissingPixel = rMissingPixel.Sub(rMissingPixel, nsRect(i, i, 1, 1));
     r = r.And(r, rMissingPixel);
   }
 });
 
-void TestExec() {
+void BenchRegionBuilderOr() {
   const int size = 5000;
 
   RegionBuilder<nsRegion> r;
   for (int i = 0; i < size; i++) {
     r.Or(nsRect(i, i, i + 10, i + 10));
   }
   r.ToRegion();
 
   RegionBuilder<nsIntRegion> rInt;
   for (int i = 0; i < size; i++) {
     rInt.Or(nsIntRect(i, i, i + 10, i + 10));
   }
   rInt.ToRegion();
 }
 
 MOZ_GTEST_BENCH(GfxBench, RegionBuilderOr, []{
-  TestExec();
+  BenchRegionBuilderOr();
 });
 
+void BenchPingPongRegionOr() {
+  const int size = 5000;
+
+  PingPongRegion<nsRegion> r;
+  for (int i = 0; i < size; i++) {
+    r.OrWith(nsRect(i, i, i + 10, i + 10));
+  }
+  r.Region();
+
+  PingPongRegion<nsIntRegion> rInt;
+  for (int i = 0; i < size; i++) {
+    rInt.OrWith(nsIntRect(i, i, i + 10, i + 10));
+  }
+  rInt.Region();
+}
+
+MOZ_GTEST_BENCH(GfxBench, PingPongRegionOr, []{
+  BenchPingPongRegionOr();
+});
+