Bug 953296 - Introduce an EBO-performing Pair class to mfbt. r=jcranmer
authorJeff Walden <jwalden@mit.edu>
Mon, 09 Jun 2014 08:49:18 -0700
changeset 212096 f0eb37be6b5f5dbb7dd67d592b16c50f0a3c7dfa
parent 212095 e5864ea2d39ee61fd5375ab796a93a50bcb9d423
child 212097 97daabb8edbb2bfb9f68c65edffb5e8daa7a19ce
push id3857
push userraliiev@mozilla.com
push dateTue, 02 Sep 2014 16:39:23 +0000
treeherdermozilla-beta@5638b907b505 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjcranmer
bugs953296
milestone33.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 953296 - Introduce an EBO-performing Pair class to mfbt. r=jcranmer
mfbt/Pair.h
mfbt/moz.build
mfbt/tests/TestPair.cpp
mfbt/tests/moz.build
new file mode 100644
--- /dev/null
+++ b/mfbt/Pair.h
@@ -0,0 +1,182 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* 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/. */
+
+/* A class holding a pair of objects that tries to conserve storage space. */
+
+#ifndef mozilla_Pair_h
+#define mozilla_Pair_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/Move.h"
+#include "mozilla/TypeTraits.h"
+
+namespace mozilla {
+
+namespace detail {
+
+enum StorageType { AsBase, AsMember };
+
+// Optimize storage using the Empty Base Optimization -- that empty base classes
+// don't take up space -- to optimize size when one or the other class is
+// stateless and can be used as a base class.
+//
+// The extra conditions on storage for B are necessary so that PairHelper won't
+// ambiguously inherit from either A or B, such that one or the other base class
+// would be inaccessible.
+template<typename A, typename B,
+         detail::StorageType =
+           IsEmpty<A>::value ? detail::AsBase : detail::AsMember,
+         detail::StorageType =
+           IsEmpty<B>::value && !IsBaseOf<A, B>::value && !IsBaseOf<B, A>::value
+           ? detail::AsBase
+           : detail::AsMember>
+struct PairHelper;
+
+template<typename A, typename B>
+struct PairHelper<A, B, AsMember, AsMember>
+{
+  protected:
+    template<typename AArg, typename BArg>
+    PairHelper(AArg&& a, BArg&& b)
+      : firstA(Forward<AArg>(a)),
+        secondB(Forward<BArg>(b))
+    {}
+
+    A& first() { return firstA; }
+    const A& first() const { return firstA; }
+    B& second() { return secondB; }
+    const B& second() const { return secondB; }
+
+    void swap(PairHelper& other) {
+      Swap(firstA, other.firstA);
+      Swap(secondB, other.secondB);
+    }
+
+  private:
+    A firstA;
+    B secondB;
+};
+
+template<typename A, typename B>
+struct PairHelper<A, B, AsMember, AsBase> : private B
+{
+  protected:
+    template<typename AArg, typename BArg>
+    PairHelper(AArg&& a, BArg&& b)
+      : B(Forward<BArg>(b)),
+        firstA(Forward<AArg>(a))
+    {}
+
+    A& first() { return firstA; }
+    const A& first() const { return firstA; }
+    B& second() { return *this; }
+    const B& second() const { return *this; }
+
+    void swap(PairHelper& other) {
+      Swap(firstA, other.firstA);
+      Swap(static_cast<B&>(*this), static_cast<B&>(other));
+    }
+
+  private:
+    A firstA;
+};
+
+template<typename A, typename B>
+struct PairHelper<A, B, AsBase, AsMember> : private A
+{
+  protected:
+    template<typename AArg, typename BArg>
+    PairHelper(AArg&& a, BArg&& b)
+      : A(Forward<AArg>(a)),
+        secondB(Forward<BArg>(b))
+    {}
+
+    A& first() { return *this; }
+    const A& first() const { return *this; }
+    B& second() { return secondB; }
+    const B& second() const { return secondB; }
+
+    void swap(PairHelper& other) {
+      Swap(static_cast<A&>(*this), static_cast<A&>(other));
+      Swap(secondB, other.secondB);
+    }
+
+  private:
+    B secondB;
+};
+
+template<typename A, typename B>
+struct PairHelper<A, B, AsBase, AsBase> : private A, private B
+{
+  protected:
+    template<typename AArg, typename BArg>
+    PairHelper(AArg&& a, BArg&& b)
+      : A(Forward<AArg>(a)),
+        B(Forward<BArg>(b))
+    {}
+
+    A& first() { return static_cast<A&>(*this); }
+    const A& first() const { return static_cast<A&>(*this); }
+    B& second() { return static_cast<B&>(*this); }
+    const B& second() const { return static_cast<B&>(*this); }
+
+    void swap(PairHelper& other) {
+      Swap(static_cast<A&>(*this), static_cast<A&>(other));
+      Swap(static_cast<B&>(*this), static_cast<B&>(other));
+    }
+};
+
+} // namespace detail
+
+/**
+ * Pair is the logical concatenation of an instance of A with an instance B.
+ * Space is conserved when possible.  Neither A nor B may be a final class.
+ *
+ * It's typically clearer to have individual A and B member fields.  Except if
+ * you want the space-conserving qualities of Pair, you're probably better off
+ * not using this!
+ *
+ * No guarantees are provided about the memory layout of A and B, the order of
+ * initialization or destruction of A and B, and so on.  (This is approximately
+ * required to optimize space usage.)  The first/second names are merely
+ * conceptual!
+ */
+template<typename A, typename B>
+struct Pair
+  : private detail::PairHelper<A, B>
+{
+    typedef typename detail::PairHelper<A, B> Base;
+
+  public:
+    template<typename AArg, typename BArg>
+    Pair(AArg&& a, BArg&& b)
+      : Base(Forward<AArg>(a), Forward<BArg>(b))
+    {}
+
+    /** The A instance. */
+    using Base::first;
+    /** The B instance. */
+    using Base::second;
+
+    /** Swap this pair with another pair. */
+    void swap(Pair& other) {
+      Base::swap(other);
+    }
+
+  private:
+    Pair(const Pair&) MOZ_DELETE;
+};
+
+template<typename A, class B>
+void
+Swap(Pair<A, B>& x, Pair<A, B>& y)
+{
+  x.swap(y);
+}
+
+} // namespace mozilla
+
+#endif /* mozilla_Pair_h */
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -43,16 +43,17 @@ EXPORTS.mozilla = [
     'Maybe.h',
     'MaybeOneOf.h',
     'MemoryChecking.h',
     'MemoryReporting.h',
     'Move.h',
     'MSIntTypes.h',
     'NullPtr.h',
     'NumericLimits.h',
+    'Pair.h',
     'PodOperations.h',
     'Poison.h',
     'Range.h',
     'RangedPtr.h',
     'RefCountType.h',
     'ReentrancyGuard.h',
     'RefPtr.h',
     'RollingMean.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestPair.cpp
@@ -0,0 +1,61 @@
+/* -*- 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 "mozilla/Pair.h"
+
+using mozilla::Pair;
+
+// Sizes aren't part of the guaranteed Pair interface, but we want to verify our
+// attempts at compactness through EBO are moderately functional, *somewhere*.
+#define INSTANTIATE(T1, T2, name, size) \
+  Pair<T1, T2> name##_1(T1(0), T2(0)); \
+  static_assert(sizeof(name##_1.first()) > 0, \
+                "first method should work on Pair<" #T1 ", " #T2 ">"); \
+  static_assert(sizeof(name##_1.second()) > 0, \
+                "second method should work on Pair<" #T1 ", " #T2 ">"); \
+  static_assert(sizeof(name##_1) == (size), \
+                "Pair<" #T1 ", " #T2 "> has an unexpected size"); \
+  Pair<T2, T1> name##_2(T2(0), T1(0)); \
+  static_assert(sizeof(name##_2.first()) > 0, \
+                "first method should work on Pair<" #T2 ", " #T1 ">"); \
+  static_assert(sizeof(name##_2.second()) > 0, \
+                "second method should work on Pair<" #T2 ", " #T1 ">"); \
+  static_assert(sizeof(name##_2) == (size), \
+                "Pair<" #T2 ", " #T1 "> has an unexpected size");
+
+INSTANTIATE(int, int, prim1, 2 * sizeof(int));
+INSTANTIATE(int, long, prim2, 2 * sizeof(long));
+
+struct EmptyClass { EmptyClass(int) {} };
+struct NonEmpty { char c; NonEmpty(int) {} };
+
+INSTANTIATE(int, EmptyClass, both1, sizeof(int));
+INSTANTIATE(int, NonEmpty, both2, 2 * sizeof(int));
+INSTANTIATE(EmptyClass, NonEmpty, both3, 1);
+
+struct A { char dummy; A(int) {} };
+struct B : A { B(int i) : A(i) {} };
+
+INSTANTIATE(A, A, class1, 2);
+INSTANTIATE(A, B, class2, 2);
+INSTANTIATE(A, EmptyClass, class3, 1);
+
+struct OtherEmpty : EmptyClass { OtherEmpty(int i) : EmptyClass(i) {} };
+
+// C++11 requires distinct objects of the same type, within the same "most
+// derived object", to have different addresses.  Pair allocates its elements as
+// two bases, a base and a member, or two members.  If the two elements have
+// non-zero size or are unrelated, no big deal.  But if they're both empty and
+// related, something -- possibly both -- must be inflated.  Exactly which are
+// inflated depends which PairHelper specialization is used.  We could
+// potentially assert something about size for this case, but whatever we could
+// assert would be very finicky.  Plus it's two empty classes -- hardly likely.
+// So don't bother trying to assert anything about this case.
+//INSTANTIATE(EmptyClass, OtherEmpty, class4, ...something finicky...);
+
+int
+main()
+{
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -15,16 +15,17 @@ CPP_UNIT_TESTS += [
     'TestCountPopulation.cpp',
     'TestCountZeroes.cpp',
     'TestEndian.cpp',
     'TestEnumSet.cpp',
     'TestFloatingPoint.cpp',
     'TestIntegerPrintfMacros.cpp',
     'TestMacroArgs.cpp',
     'TestMacroForEach.cpp',
+    'TestPair.cpp',
     'TestRollingMean.cpp',
     'TestSHA1.cpp',
     'TestTypedEnum.cpp',
     'TestTypeTraits.cpp',
     'TestWeakPtr.cpp',
 ]
 
 if not CONFIG['MOZ_ASAN']: