Bug 1479996 - Combine nsTArray::IndexOf and element access into lambda-friendly functions - r=froydnj
authorGerald Squelart <gsquelart@mozilla.com>
Tue, 28 Aug 2018 22:04:09 +0000
changeset 488780 9fa92a1d961da1538f6af39d9401bc2793deea89
parent 488779 644e800d1d8aa4bf2a4cc560132fc290539c5bea
child 488781 33c06c93406863777cedffacc04e78caab6d1e8d
push id9734
push usershindli@mozilla.com
push dateThu, 30 Aug 2018 12:18:07 +0000
treeherdermozilla-beta@71c71ab3afae [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1479996
milestone63.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 1479996 - Combine nsTArray::IndexOf and element access into lambda-friendly functions - r=froydnj In many places, nsTArray::IndexOf is followed by accessing that element (hopefully with `Elements() + index`, which skips unnecessary bounds checks.) But this pattern introduces operations that could be avoided: - IndexOf converts the address of the found element into an index, - The caller must test for a special `NoIndex` value, - On success, accesses convert that index back into the original address. This patch introduces new 'ApplyIf...' functions that combine all these operations in a more efficient ensemble: If the sought element is found, it is passed by reference to a given callable object (usually a lambda); if not found, another callable is invoked. Depending on what they need, the first callable may take one of these parameter lists: (), (size_t), (maybe-const elem_type&), (size_t, maybe-const elem_type&). On top of removing the pointer->index->pointer operations in most cases, invoking callables directly from ApplyIf is safer, as the array is guaranteed to be untouched at this time. Also, being templates taking function objects, in most cases the compiler should be able to inline and optimize the search and its callables' code. This patch gives example uses in nsTArray::Contains, and in FrameProperties::GetInternal, SetInternal. And FrameProperties::Has now calls Contains, which is more efficient because the former code would compute an index (or NoIndex), and then convert that index to a bool; whereas the new code directly produces a bool from within the search algorithm. Differential Revision: https://phabricator.services.mozilla.com/D2758
layout/base/FrameProperties.h
xpcom/ds/nsTArray.h
xpcom/tests/gtest/TestTArray2.cpp
--- a/layout/base/FrameProperties.h
+++ b/layout/base/FrameProperties.h
@@ -209,18 +209,17 @@ public:
    * The HasSkippingBitCheck variant doesn't test NS_FRAME_HAS_PROPERTIES
    * on aFrame, so it is safe to call after aFrame has been destroyed as
    * long as, since that destruction happened, it isn't possible for a
    * new frame to have been created and the same property added.
    */
   template<typename T>
   bool Has(Descriptor<T> aProperty) const
   {
-    return mProperties.IndexOf(aProperty, 0, PropertyComparator())
-           != nsTArray<PropertyValue>::NoIndex;
+    return mProperties.Contains(aProperty, PropertyComparator());
   }
 
   /**
    * Get a property value. This requires a linear search through
    * the properties of the frame. If the frame has no such property,
    * returns zero-filled result, which means null for pointers and
    * zero for integers and floating point types.
    * @param aFoundResult if non-null, receives a value 'true' iff
@@ -405,46 +404,48 @@ private:
 
 
 inline void*
 FrameProperties::GetInternal(UntypedDescriptor aProperty,
                              bool* aFoundResult) const
 {
   MOZ_ASSERT(aProperty, "Null property?");
 
-  auto index = mProperties.IndexOf(aProperty, 0, PropertyComparator());
-  if (index == nsTArray<PropertyValue>::NoIndex) {
-    if (aFoundResult) {
-      *aFoundResult = false;
-    }
-    return nullptr;
-  }
-
-  if (aFoundResult) {
-    *aFoundResult = true;
-  }
-  return mProperties.Elements()[index].mValue;
+  return mProperties.ApplyIf(
+    aProperty, 0, PropertyComparator(),
+    [&aFoundResult](const PropertyValue& aPV) -> void* {
+      if (aFoundResult) {
+        *aFoundResult = true;
+      }
+      return aPV.mValue;
+    },
+    [&aFoundResult]() -> void* {
+      if (aFoundResult) {
+        *aFoundResult = false;
+      }
+      return nullptr;
+    });
 }
 
 inline void
 FrameProperties::SetInternal(UntypedDescriptor aProperty, void* aValue,
                              const nsIFrame* aFrame)
 {
   MOZ_ASSERT(NS_IsMainThread());
   MOZ_ASSERT(aProperty, "Null property?");
 
-  auto index = mProperties.IndexOf(aProperty, 0, PropertyComparator());
-  if (index != nsTArray<PropertyValue>::NoIndex) {
-    PropertyValue* pv = &mProperties.Elements()[index];
-    pv->DestroyValueFor(aFrame);
-    pv->mValue = aValue;
-    return;
-  }
-
-  mProperties.AppendElement(PropertyValue(aProperty, aValue));
+  mProperties.ApplyIf(
+    aProperty, 0, PropertyComparator(),
+    [&](PropertyValue& aPV) {
+      aPV.DestroyValueFor(aFrame);
+      aPV.mValue = aValue;
+    },
+    [&]() {
+      mProperties.AppendElement(PropertyValue(aProperty, aValue));
+    });
 }
 
 inline void
 FrameProperties::AddInternal(UntypedDescriptor aProperty, void* aValue)
 {
   MOZ_ASSERT(NS_IsMainThread());
   MOZ_ASSERT(aProperty, "Null property?");
 
--- a/xpcom/ds/nsTArray.h
+++ b/xpcom/ds/nsTArray.h
@@ -10,16 +10,17 @@
 #include "nsTArrayForwardDeclare.h"
 #include "mozilla/Alignment.h"
 #include "mozilla/ArrayIterator.h"
 #include "mozilla/Assertions.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/BinarySearch.h"
 #include "mozilla/CheckedInt.h"
 #include "mozilla/fallible.h"
+#include "mozilla/FunctionTypeTraits.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/mozalloc.h"
 #include "mozilla/ReverseIterator.h"
 #include "mozilla/TypeTraits.h"
 #include "mozilla/Span.h"
 
@@ -1181,17 +1182,19 @@ public:
   // This method searches for the first element in this array that is equal
   // to the given element.
   // @param aItem  The item to search for.
   // @param aComp  The Comparator used to determine element equality.
   // @return       true if the element was found.
   template<class Item, class Comparator>
   bool Contains(const Item& aItem, const Comparator& aComp) const
   {
-    return IndexOf(aItem, 0, aComp) != NoIndex;
+    return ApplyIf(aItem, 0, aComp,
+                   []() { return true; },
+                   []() { return false; });
   }
 
   // Like Contains(), but assumes a sorted array.
   template<class Item, class Comparator>
   bool ContainsSorted(const Item& aItem, const Comparator& aComp) const
   {
     return BinaryIndexOf(aItem, aComp) != NoIndex;
   }
@@ -1199,17 +1202,17 @@ public:
   // This method searches for the first element in this array that is equal
   // to the given element.  This method assumes that 'operator==' is defined
   // for elem_type.
   // @param aItem  The item to search for.
   // @return       true if the element was found.
   template<class Item>
   bool Contains(const Item& aItem) const
   {
-    return IndexOf(aItem) != NoIndex;
+    return Contains(aItem, nsDefaultComparator<elem_type, Item>());
   }
 
   // Like Contains(), but assumes a sorted array.
   template<class Item>
   bool ContainsSorted(const Item& aItem) const
   {
     return BinaryIndexOf(aItem) != NoIndex;
   }
@@ -1942,16 +1945,194 @@ public:
   // array to be swapped.
   template<class Allocator>
   typename Alloc::ResultType SwapElements(nsTArray_Impl<E, Allocator>& aOther)
   {
     return Alloc::Result(this->template SwapArrayElements<Alloc>(
       aOther, sizeof(elem_type), MOZ_ALIGNOF(elem_type)));
   }
 
+private:
+  // Used by ApplyIf functions to invoke a callable that takes either:
+  // - Nothing: F(void)
+  // - Index only: F(size_t)
+  // - Reference to element only: F(maybe-const elem_type&)
+  // - Both index and reference: F(size_t, maybe-const elem_type&)
+  // `elem_type` must be const when called from const method.
+  template<typename T, typename Param0, typename Param1>
+  struct InvokeWithIndexAndOrReferenceHelper
+  {
+    static constexpr bool valid = false;
+  };
+  template<typename T>
+  struct InvokeWithIndexAndOrReferenceHelper<T, void, void>
+  {
+    static constexpr bool valid = true;
+    template<typename F>
+    static auto Invoke(F&& f, size_t, T&) { return f(); }
+  };
+  template<typename T>
+  struct InvokeWithIndexAndOrReferenceHelper<T, size_t, void>
+  {
+    static constexpr bool valid = true;
+    template<typename F>
+    static auto Invoke(F&& f, size_t i, T&) { return f(i); }
+  };
+  template<typename T>
+  struct InvokeWithIndexAndOrReferenceHelper<T, T&, void>
+  {
+    static constexpr bool valid = true;
+    template<typename F>
+    static auto Invoke(F&& f, size_t, T& e) { return f(e); }
+  };
+  template<typename T>
+  struct InvokeWithIndexAndOrReferenceHelper<T, const T&, void>
+  {
+    static constexpr bool valid = true;
+    template<typename F>
+    static auto Invoke(F&& f, size_t, T& e) { return f(e); }
+  };
+  template<typename T>
+  struct InvokeWithIndexAndOrReferenceHelper<T, size_t, T&>
+  {
+    static constexpr bool valid = true;
+    template<typename F>
+    static auto Invoke(F&& f, size_t i, T& e) { return f(i, e); }
+  };
+  template<typename T>
+  struct InvokeWithIndexAndOrReferenceHelper<T, size_t, const T&>
+  {
+    static constexpr bool valid = true;
+    template<typename F>
+    static auto Invoke(F&& f, size_t i, T& e) { return f(i, e); }
+  };
+  template<typename T, typename F>
+  static auto InvokeWithIndexAndOrReference(F&& f, size_t i, T& e)
+  {
+    using Invoker =
+      InvokeWithIndexAndOrReferenceHelper<
+        T,
+        typename mozilla::FunctionTypeTraits<F>::template ParameterType<0>,
+        typename mozilla::FunctionTypeTraits<F>::template ParameterType<1>>;
+    static_assert(Invoker::valid,
+                  "ApplyIf's Function parameters must match either: (void), "
+                  "(size_t), (maybe-const elem_type&), or "
+                  "(size_t, maybe-const elem_type&)");
+    return Invoker::Invoke(std::forward<F>(f), i, e);
+  }
+
+public:
+  // 'Apply' family of methods.
+  //
+  // The advantages of using Apply methods with lambdas include:
+  // - Safety of accessing elements from within the call, when the array cannot
+  //   have been modified between the iteration and the subsequent access.
+  // - Avoiding moot conversions: pointer->index during a search, followed by
+  //   index->pointer after the search when accessing the element.
+  // - Embedding your code into the algorithm, giving the compiler more chances
+  //   to optimize.
+
+  // Search for the first element comparing equal to aItem with the given
+  // comparator (`==` by default).
+  // If such an element exists, return the result of evaluating either:
+  // - `aFunction()`
+  // - `aFunction(index_type)`
+  // - `aFunction(maybe-const? elem_type&)`
+  // - `aFunction(index_type, maybe-const? elem_type&)`
+  // (`aFunction` must have one of the above signatures with these exact types,
+  //  including references; implicit conversions or generic types not allowed.
+  //  If `this` array is const, the referenced `elem_type` must be const too;
+  //  otherwise it may be either const or non-const.)
+  // But if the element is not found, return the result of evaluating
+  // `aFunctionElse()`.
+  template<class Item, class Comparator, class Function, class FunctionElse>
+  auto ApplyIf(const Item& aItem, index_type aStart,
+               const Comparator& aComp,
+               Function&& aFunction, FunctionElse&& aFunctionElse) const
+  {
+    static_assert(
+      mozilla::IsSame<
+        typename mozilla::FunctionTypeTraits<Function>::ReturnType,
+        typename mozilla::FunctionTypeTraits<FunctionElse>::ReturnType>::value,
+      "ApplyIf's `Function` and `FunctionElse` must return the same type.");
+
+    ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+
+    const elem_type* const elements = Elements();
+    const elem_type* const iend = elements + Length();
+    for (const elem_type* iter = elements + aStart; iter != iend; ++iter) {
+      if (comp.Equals(*iter, aItem)) {
+        return InvokeWithIndexAndOrReference<const elem_type>(
+                 std::forward<Function>(aFunction), iter - elements, *iter);
+      }
+    }
+    return aFunctionElse();
+  }
+  template<class Item, class Comparator, class Function, class FunctionElse>
+  auto ApplyIf(const Item& aItem, index_type aStart,
+               const Comparator& aComp,
+               Function&& aFunction, FunctionElse&& aFunctionElse)
+  {
+    static_assert(
+      mozilla::IsSame<
+        typename mozilla::FunctionTypeTraits<Function>::ReturnType,
+        typename mozilla::FunctionTypeTraits<FunctionElse>::ReturnType>::value,
+      "ApplyIf's `Function` and `FunctionElse` must return the same type.");
+
+    ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+
+    elem_type* const elements = Elements();
+    elem_type* const iend = elements + Length();
+    for (elem_type* iter = elements + aStart; iter != iend; ++iter) {
+      if (comp.Equals(*iter, aItem)) {
+        return InvokeWithIndexAndOrReference<elem_type>(
+                 std::forward<Function>(aFunction), iter - elements, *iter);
+      }
+    }
+    return aFunctionElse();
+  }
+  template<class Item, class Function, class FunctionElse>
+  auto ApplyIf(const Item& aItem, index_type aStart,
+               Function&& aFunction, FunctionElse&& aFunctionElse) const
+  {
+    return ApplyIf(aItem,
+                   aStart,
+                   nsDefaultComparator<elem_type, Item>(),
+                   std::forward<Function>(aFunction),
+                   std::forward<FunctionElse>(aFunctionElse));
+  }
+  template<class Item, class Function, class FunctionElse>
+  auto ApplyIf(const Item& aItem, index_type aStart,
+               Function&& aFunction, FunctionElse&& aFunctionElse)
+  {
+    return ApplyIf(aItem,
+                   aStart,
+                   nsDefaultComparator<elem_type, Item>(),
+                   std::forward<Function>(aFunction),
+                   std::forward<FunctionElse>(aFunctionElse));
+  }
+  template<class Item, class Function, class FunctionElse>
+  auto ApplyIf(const Item& aItem,
+               Function&& aFunction, FunctionElse&& aFunctionElse) const
+  {
+    return ApplyIf(aItem,
+                   0,
+                   std::forward<Function>(aFunction),
+                   std::forward<FunctionElse>(aFunctionElse));
+  }
+  template<class Item, class Function, class FunctionElse>
+  auto ApplyIf(const Item& aItem,
+               Function&& aFunction, FunctionElse&& aFunctionElse)
+  {
+    return ApplyIf(aItem,
+                   0,
+                   std::forward<Function>(aFunction),
+                   std::forward<FunctionElse>(aFunctionElse));
+  }
+
   //
   // Allocation
   //
 
   // This method may increase the capacity of this array object to the
   // specified amount.  This method may be called in advance of several
   // AppendElement operations to minimize heap re-allocations.  This method
   // will not reduce the number of elements in this array.
--- a/xpcom/tests/gtest/TestTArray2.cpp
+++ b/xpcom/tests/gtest/TestTArray2.cpp
@@ -33,16 +33,18 @@ inline bool operator<(const nsCOMPtr<T>&
 
 //----
 
 template <class ElementType>
 static bool test_basic_array(ElementType *data,
                              size_t dataLen,
                              const ElementType& extra) {
   nsTArray<ElementType> ary;
+  const nsTArray<ElementType>& cary = ary;
+
   ary.AppendElements(data, dataLen);
   if (ary.Length() != dataLen) {
     return false;
   }
   if (!(ary == ary)) {
     return false;
   }
   size_t i;
@@ -87,32 +89,86 @@ static bool test_basic_array(ElementType
     return false;
   size_t oldLen = ary.Length();
   ary.RemoveElement(data[dataLen / 2]);
   if (ary.Length() != (oldLen - 1))
     return false;
   if (!(ary == ary))
     return false;
 
+  if (ary.ApplyIf(extra,
+                  []() { return true; },
+                  []() { return false; }))
+    return false;
+  if (ary.ApplyIf(extra,
+                  [](size_t) { return true; },
+                  []() { return false; }))
+    return false;
+  // On a non-const array, ApplyIf's first lambda may use either const or non-
+  // const element types.
+  if (ary.ApplyIf(extra,
+                  [](ElementType&) { return true; },
+                  []() { return false; }))
+    return false;
+  if (ary.ApplyIf(extra,
+                  [](const ElementType&) { return true; },
+                  []() { return false; }))
+    return false;
+  if (ary.ApplyIf(extra,
+                  [](size_t, ElementType&) { return true; },
+                  []() { return false; }))
+    return false;
+  if (ary.ApplyIf(extra,
+                  [](size_t, const ElementType&) { return true; },
+                  []() { return false; }))
+    return false;
+
+  if (cary.ApplyIf(extra,
+                   []() { return true; },
+                   []() { return false; }))
+  if (cary.ApplyIf(extra,
+                   [](size_t) { return true; },
+                   []() { return false; }))
+  // On a const array, ApplyIf's first lambda must only use const element types.
+  if (cary.ApplyIf(extra,
+                   [](const ElementType&) { return true; },
+                   []() { return false; }))
+  if (cary.ApplyIf(extra,
+                   [](size_t, const ElementType&) { return true; },
+                   []() { return false; }))
+    return false;
+
   size_t index = ary.Length() / 2;
   if (!ary.InsertElementAt(index, extra))
     return false;
   if (!(ary == ary))
     return false;
   if (ary[index] != extra)
     return false;
   if (ary.IndexOf(extra) == ary.NoIndex)
     return false;
   if (ary.LastIndexOf(extra) == ary.NoIndex)
     return false;
   // ensure proper searching
   if (ary.IndexOf(extra) > ary.LastIndexOf(extra))
     return false;
   if (ary.IndexOf(extra, index) != ary.LastIndexOf(extra, index))
     return false;
+  if (!ary.ApplyIf(extra,
+                   [&](size_t i, const ElementType& e) {
+                     return i == index && e == extra;
+                   },
+                   []() { return false; }))
+    return false;
+  if (!cary.ApplyIf(extra,
+                    [&](size_t i, const ElementType& e) {
+                      return i == index && e == extra;
+                    },
+                    []() { return false; }))
+    return false;
 
   nsTArray<ElementType> copy(ary);
   if (!(ary == copy))
     return false;
   for (i = 0; i < copy.Length(); ++i) {
     if (ary[i] != copy[i])
       return false;
   }
@@ -124,16 +180,24 @@ static bool test_basic_array(ElementType
   if (ary.Capacity() == cap)
     return false;
 
   ary.Clear();
   if (ary.IndexOf(extra) != ary.NoIndex)
     return false;
   if (ary.LastIndexOf(extra) != ary.NoIndex)
     return false;
+  if (ary.ApplyIf(extra,
+                  []() { return true; },
+                  []() { return false; }))
+    return false;
+  if (cary.ApplyIf(extra,
+                   []() { return true; },
+                   []() { return false; }))
+    return false;
 
   ary.Clear();
   if (!ary.IsEmpty() || ary.Elements() == nullptr)
     return false;
   if (!(ary == nsTArray<ElementType>()))
     return false;
   if (ary == copy)
     return false;
@@ -420,16 +484,21 @@ TEST(TArray, test_string_array) {
 
   const char kextra[] = "foo bar";
   size_t oldLen = strArray.Length();
   ASSERT_TRUE(strArray.AppendElement(kextra));
   strArray.RemoveElement(kextra);
   ASSERT_EQ(oldLen, strArray.Length());
 
   ASSERT_EQ(strArray.IndexOf("e"), size_t(1));
+  ASSERT_TRUE(strArray.ApplyIf("e",
+                               [](size_t i, nsCString& s) {
+                                 return i == 1 && s == "e";
+                               },
+                               []() { return false; }));
 
   strArray.Sort();
   const char ksorted[] = "\0 dehllloorw";
   for (i = ArrayLength(kdata); i--; ) {
     ASSERT_EQ(strArray[i].CharAt(0), ksorted[i]);
     if (i > 0 && strArray[i] == strArray[i - 1])
       strArray.RemoveElementAt(i);
   }
@@ -473,16 +542,19 @@ TEST(TArray, test_comptr_array) {
     FilePointer f;
     tmpDir->Clone(getter_AddRefs(f));
     ASSERT_TRUE(f);
     ASSERT_FALSE(NS_FAILED(f->AppendNative(nsDependentCString(kNames[i]))));
     fileArray.AppendElement(f);
   }
 
   ASSERT_EQ(fileArray.IndexOf(kNames[1], 0, nsFileNameComparator()), size_t(1));
+  ASSERT_TRUE(fileArray.ApplyIf(kNames[1], 0, nsFileNameComparator(),
+                                [](size_t i) { return i == 1; },
+                                []() { return false; }));
 
   // It's unclear what 'operator<' means for nsCOMPtr, but whatever...
   ASSERT_TRUE(test_basic_array(fileArray.Elements(), fileArray.Length(),
                                tmpDir));
 }
 
 //----
 
@@ -508,16 +580,21 @@ TEST(TArray, test_refptr_array) {
   RefcountedObject *b = new RefcountedObject(); b->AddRef();
   RefcountedObject *c = new RefcountedObject(); c->AddRef();
 
   objArray.AppendElement(a);
   objArray.AppendElement(b);
   objArray.AppendElement(c);
 
   ASSERT_EQ(objArray.IndexOf(b), size_t(1));
+  ASSERT_TRUE(objArray.ApplyIf(b,
+                               [&](size_t i, RefPtr<RefcountedObject>& r) {
+                                 return i == 1 && r == b;
+                               },
+                               []() { return false; }));
 
   a->Release();
   b->Release();
   c->Release();
 }
 
 //----
 
@@ -608,16 +685,19 @@ TEST(TArray, test_indexof) {
   nsTArray<int> array;
   array.AppendElement(0);
   // add and remove the 5
   array.AppendElement(5);
   array.RemoveElementAt(1);
   // we should not find the 5!
   auto no_index = array.NoIndex; // Fixes gtest compilation error.
   ASSERT_EQ(array.IndexOf(5, 1), no_index);
+  ASSERT_FALSE(array.ApplyIf(5, 1,
+                             []() { return true; },
+                             []() { return false; }));
 }
 
 //----
 
 template <class Array>
 static bool is_heap(const Array& ary, size_t len) {
   size_t index = 1;
   while (index < len) {