Bug 1287243 - Optimize the type used to store Variant's tag. r=fitzgen
authorJeff Walden <jwalden@mit.edu>
Sat, 16 Jul 2016 02:31:45 -0700
changeset 330793 2475145b53b60a5294a5a624982004bf02132f90
parent 330792 d7f56af6ddd22743c7cce4c9fdb2a72df3a16dea
child 330794 bd4fd5d4436f1d5e0d2f6f3b2a7707c33621c028
push id9858
push userjlund@mozilla.com
push dateMon, 01 Aug 2016 14:37:10 +0000
treeherdermozilla-aurora@203106ef6cb6 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfitzgen
bugs1287243
milestone50.0a1
Bug 1287243 - Optimize the type used to store Variant's tag. r=fitzgen
mfbt/Variant.h
--- a/mfbt/Variant.h
+++ b/mfbt/Variant.h
@@ -2,20 +2,22 @@
 /* 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 template class for tagged unions. */
 
 #include <new>
+#include <stdint.h>
 
 #include "mozilla/Alignment.h"
 #include "mozilla/Assertions.h"
 #include "mozilla/Move.h"
+#include "mozilla/TypeTraits.h"
 
 #ifndef mozilla_Variant_h
 #define mozilla_Variant_h
 
 namespace mozilla {
 
 template<typename... Ts>
 class Variant;
@@ -104,53 +106,74 @@ struct SelectVariantTypeHelper<T, Head, 
  * or a reference to type T. If no such type was found, Type is not defined.
  */
 template <typename T, typename... Variants>
 struct SelectVariantType
   : public SelectVariantTypeHelper<typename RemoveConst<typename RemoveReference<T>::Type>::Type,
                                    Variants...>
 { };
 
+// Compute a fast, compact type that can be used to hold integral values that
+// distinctly map to every type in Ts.
+template<typename... Ts>
+struct VariantTag
+{
+private:
+  static const size_t TypeCount = sizeof...(Ts);
+
+public:
+  using Type =
+    typename Conditional<TypeCount < 3,
+                         bool,
+                         typename Conditional<TypeCount < (1 << 8),
+                                              uint_fast8_t,
+                                              size_t // stop caring past a certain point :-)
+                                              >::Type
+                         >::Type;
+};
+
 // TagHelper gets the given sentinel tag value for the given type T. This has to
-// be split out from VariantImplementation because you can't nest a partial template
-// specialization within a template class.
+// be split out from VariantImplementation because you can't nest a partial
+// template specialization within a template class.
 
-template<size_t N, typename T, typename U, typename Next, bool isMatch>
+template<typename Tag, size_t N, typename T, typename U, typename Next, bool isMatch>
 struct TagHelper;
 
 // In the case where T != U, we continue recursion.
-template<size_t N, typename T, typename U, typename Next>
-struct TagHelper<N, T, U, Next, false>
+template<typename Tag, size_t N, typename T, typename U, typename Next>
+struct TagHelper<Tag, N, T, U, Next, false>
 {
-  static size_t tag() { return Next::template tag<U>(); }
+  static Tag tag() { return Next::template tag<U>(); }
 };
 
 // In the case where T == U, return the tag number.
-template<size_t N, typename T, typename U, typename Next>
-struct TagHelper<N, T, U, Next, true>
+template<typename Tag, size_t N, typename T, typename U, typename Next>
+struct TagHelper<Tag, N, T, U, Next, true>
 {
-  static size_t tag() { return N; }
+  static Tag tag() { return Tag(N); }
 };
 
-// The VariantImplementation template provides the guts of mozilla::Variant. We create
-// an VariantImplementation for each T in Ts... which handles construction,
-// destruction, etc for when the Variant's type is T. If the Variant's type is
-// not T, it punts the request on to the next VariantImplementation.
+// The VariantImplementation template provides the guts of mozilla::Variant.  We
+// create a VariantImplementation for each T in Ts... which handles
+// construction, destruction, etc for when the Variant's type is T.  If the
+// Variant's type isn't T, it punts the request on to the next
+// VariantImplementation.
 
-template<size_t N, typename... Ts>
+template<typename Tag, size_t N, typename... Ts>
 struct VariantImplementation;
 
 // The singly typed Variant / recursion base case.
-template<size_t N, typename T>
-struct VariantImplementation<N, T> {
+template<typename Tag, size_t N, typename T>
+struct VariantImplementation<Tag, N, T>
+{
   template<typename U>
-  static size_t tag() {
+  static Tag tag() {
     static_assert(mozilla::IsSame<T, U>::value,
                   "mozilla::Variant: tag: bad type!");
-    return N;
+    return Tag(N);
   }
 
   template<typename Variant>
   static void copyConstruct(void* aLhs, const Variant& aRhs) {
     new (aLhs) T(aRhs.template as<T>());
   }
 
   template<typename Variant>
@@ -174,25 +197,25 @@ struct VariantImplementation<N, T> {
   match(Matcher&& aMatcher, ConcreteVariant& aV)
     -> decltype(aMatcher.match(aV.template as<T>()))
   {
     return aMatcher.match(aV.template as<T>());
   }
 };
 
 // VariantImplementation for some variant type T.
-template<size_t N, typename T, typename... Ts>
-struct VariantImplementation<N, T, Ts...>
+template<typename Tag, size_t N, typename T, typename... Ts>
+struct VariantImplementation<Tag, N, T, Ts...>
 {
   // The next recursive VariantImplementation.
-  using Next = VariantImplementation<N + 1, Ts...>;
+  using Next = VariantImplementation<Tag, N + 1, Ts...>;
 
   template<typename U>
-  static size_t tag() {
-    return TagHelper<N, T, U, Next, IsSame<T, U>::value>::tag();
+  static Tag tag() {
+    return TagHelper<Tag, N, T, U, Next, IsSame<T, U>::value>::tag();
   }
 
   template<typename Variant>
   static void copyConstruct(void* aLhs, const Variant& aRhs) {
     if (aRhs.template is<T>()) {
       new (aLhs) T(aRhs.template as<T>());
     } else {
       Next::copyConstruct(aLhs, aRhs);
@@ -406,26 +429,27 @@ struct AsVariantTemporary
  *       Variant<const char*, UniquePtr<char[]>> string;
  *
  *       ...
  *     };
  */
 template<typename... Ts>
 class MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS Variant
 {
-  using Impl = detail::VariantImplementation<0, Ts...>;
+  using Tag = typename detail::VariantTag<Ts...>::Type;
+  using Impl = detail::VariantImplementation<Tag, 0, Ts...>;
   using RawData = AlignedStorage<detail::MaxSizeOf<Ts...>::size>;
 
-  // Each type is given a unique size_t sentinel. This tag lets us keep track of
-  // the contained variant value's type.
-  size_t tag;
-
   // Raw storage for the contained variant value.
   RawData raw;
 
+  // Each type is given a unique tag value that lets us keep track of the
+  // contained variant value's type.
+  Tag tag;
+
   void* ptr() {
     return reinterpret_cast<void*>(&raw);
   }
 
 public:
   /** Perfect forwarding construction for some variant type T. */
   template<typename RefT,
            // RefT captures both const& as well as && (as intended, to support