Bug 888084 - Rolling mean for MFBT; r=waldo
authorAnthony Jones <ajones@mozilla.com>
Tue, 24 Sep 2013 15:56:55 +1200
changeset 172478 468598d17533a1d1a401aea5479da63f4ee74f5f
parent 172477 a98e26325e28103e1e2395ada0f09cd634eed54c
child 172479 ec023921268dfde904904d6693ffd9665a1b5b82
push id3224
push userlsblakk@mozilla.com
push dateTue, 04 Feb 2014 01:06:49 +0000
treeherdermozilla-beta@60c04d0987f1 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs888084
milestone28.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 888084 - Rolling mean for MFBT; r=waldo
mfbt/RollingMean.h
mfbt/Vector.h
mfbt/common.mozbuild
mfbt/tests/TestRollingMean.cpp
mfbt/tests/moz.build
new file mode 100644
--- /dev/null
+++ b/mfbt/RollingMean.h
@@ -0,0 +1,109 @@
+/* -*- Mode: C++; tab-w idth: 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/. */
+
+/* A set abstraction for enumeration values. */
+
+#ifndef mozilla_RollingMean_h_
+#define mozilla_RollingMean_h_
+
+#include "mozilla/Assertions.h"
+#include "mozilla/TypeTraits.h"
+#include "mozilla/Vector.h"
+
+#include <algorithm>
+#include <stddef.h>
+#include <stdint.h>
+
+namespace mozilla {
+
+/**
+ * RollingMean<T> calculates a rolling mean of the values it is given. It
+ * accumulates the total as values are added and removed. The second type
+ * argument S specifies the type of the total. This may need to be a bigger
+ * type in order to maintain that the sum of all values in the average doesn't
+ * exceed the maximum input value.
+ *
+ * WARNING: Float types are not supported due to rounding errors.
+ */
+template<typename T, typename S>
+class RollingMean
+{
+  private:
+    size_t mInsertIndex;
+    size_t mMaxValues;
+    Vector<T> mValues;
+    S mTotal;
+
+  public:
+    static_assert(!IsFloatingPoint<T>::value,
+                  "floating-point types are unsupported due to rounding "
+                  "errors");
+
+    RollingMean(size_t aMaxValues)
+      : mInsertIndex(0),
+        mMaxValues(aMaxValues),
+        mTotal(0)
+    {
+      MOZ_ASSERT(aMaxValues > 0);
+    }
+
+    RollingMean& operator=(RollingMean&& aOther) {
+      MOZ_ASSERT(this != &aOther, "self-assignment is forbidden");
+      this->~RollingMean();
+      new(this) RollingMean(aOther.mMaxValues);
+      mInsertIndex = aOther.mInsertIndex;
+      mTotal = aOther.mTotal;
+      mValues.swap(aOther.mValues);
+      return *this;
+    }
+
+    /**
+     * Insert a value into the rolling mean.
+     */
+    bool insert(T aValue) {
+      MOZ_ASSERT(mValues.length() <= mMaxValues);
+
+      if (mValues.length() == mMaxValues) {
+        mTotal = mTotal - mValues[mInsertIndex] + aValue;
+        mValues[mInsertIndex] = aValue;
+      } else {
+        if (!mValues.append(aValue))
+          return false;
+        mTotal = mTotal + aValue;
+      }
+
+      mInsertIndex = (mInsertIndex + 1) % mMaxValues;
+      return true;
+    }
+
+    /**
+     * Calculate the rolling mean.
+     */
+    T mean() {
+      MOZ_ASSERT(!empty());
+      return T(mTotal / mValues.length());
+    }
+
+    bool empty() {
+      return mValues.empty();
+    }
+
+    /**
+     * Remove all values from the rolling mean.
+     */
+    void clear() {
+      mValues.clear();
+      mInsertIndex = 0;
+      mTotal = T(0);
+    }
+
+    size_t maxValues() {
+      return mMaxValues;
+    }
+};
+
+} // namespace mozilla
+
+#endif // mozilla_RollingMean_h_
--- a/mfbt/Vector.h
+++ b/mfbt/Vector.h
@@ -964,17 +964,17 @@ inline void
 VectorBase<T, N, AP, TV>::erase(T* it)
 {
   MOZ_ASSERT(begin() <= it);
   MOZ_ASSERT(it < end());
   while (it + 1 < end()) {
     *it = *(it + 1);
     ++it;
   }
-  popBack();
+    popBack();
 }
 
 template<typename T, size_t N, class AP, class TV>
 template<typename U>
 MOZ_ALWAYS_INLINE bool
 VectorBase<T, N, AP, TV>::append(const U* insBegin, const U* insEnd)
 {
   MOZ_REENTRANCY_GUARD_ET_AL;
--- a/mfbt/common.mozbuild
+++ b/mfbt/common.mozbuild
@@ -43,16 +43,17 @@ mfbt_headers = [
     'NullPtr.h',
     'NumericLimits.h',
     'PodOperations.h',
     'Poison.h',
     'Range.h',
     'RangedPtr.h',
     'ReentrancyGuard.h',
     'RefPtr.h',
+    'RollingMean.h',
     'Scoped.h',
     'SHA1.h',
     'SplayTree.h',
     'TemplateLib.h',
     'ThreadLocal.h',
     'TypedEnum.h',
     'Types.h',
     'TypeTraits.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestRollingMean.cpp
@@ -0,0 +1,121 @@
+/* -*- 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/Assertions.h"
+#include "mozilla/RollingMean.h"
+
+using mozilla::RollingMean;
+
+class MyClass
+{
+  public:
+    uint32_t value;
+
+    MyClass(uint32_t val = 0) : value(val) {
+    }
+
+    bool operator==(const MyClass& other) const {
+      return value == other.value;
+    }
+
+    MyClass operator+(const MyClass& other) const {
+      return MyClass(value + other.value);
+    }
+
+    MyClass operator-(const MyClass& other) const {
+      return MyClass(value - other.value);
+    }
+
+    MyClass operator/(uint32_t div) const {
+      return MyClass(value / div);
+    }
+};
+
+class RollingMeanSuite
+{
+  public:
+    RollingMeanSuite()
+    { }
+
+    void runTests() {
+      testZero();
+      testClear();
+      testRolling();
+      testClass();
+      testMove();
+    }
+
+  private:
+    void testZero() {
+      RollingMean<uint32_t, uint64_t> mean(3);
+      MOZ_ASSERT(mean.empty());
+    }
+
+    void testClear() {
+      RollingMean<uint32_t, uint64_t> mean(3);
+
+      mean.insert(4);
+      MOZ_ASSERT(mean.mean() == 4);
+
+      mean.clear();
+      MOZ_ASSERT(mean.empty());
+
+      mean.insert(3);
+      MOZ_ASSERT(mean.mean() == 3);
+    }
+
+    void testRolling() {
+      RollingMean<uint32_t, uint64_t> mean(3);
+
+      mean.insert(10);
+      MOZ_ASSERT(mean.mean() == 10);
+
+      mean.insert(20);
+      MOZ_ASSERT(mean.mean() == 15);
+
+      mean.insert(35);
+      MOZ_ASSERT(mean.mean() == 21);
+
+      mean.insert(5);
+      MOZ_ASSERT(mean.mean() == 20);
+
+      mean.insert(10);
+      MOZ_ASSERT(mean.mean() == 16);
+    }
+
+    void testClass() {
+      RollingMean<MyClass, MyClass> mean(3);
+
+      mean.insert(MyClass(4));
+      MOZ_ASSERT(mean.mean() == MyClass(4));
+
+      mean.clear();
+      MOZ_ASSERT(mean.empty());
+    }
+
+    void testMove() {
+      RollingMean<uint32_t, uint64_t> mean(3);
+      mean = RollingMean<uint32_t, uint64_t>(4);
+      MOZ_ASSERT(mean.maxValues() == 4);
+
+      mean.insert(10);
+      MOZ_ASSERT(mean.mean() == 10);
+
+      mean = RollingMean<uint32_t, uint64_t>(3);
+      mean.insert(30);
+      mean.insert(40);
+      mean.insert(50);
+      mean.insert(60);
+      MOZ_ASSERT(mean.mean() == 50);
+    }
+
+};
+
+int main()
+{
+  RollingMeanSuite suite;
+  suite.runTests();
+  return 0;
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -10,16 +10,17 @@ CPP_UNIT_TESTS += [
     'TestCasting.cpp',
     'TestCeilingFloor.cpp',
     'TestCheckedInt.cpp',
     'TestCountZeroes.cpp',
     'TestEndian.cpp',
     'TestEnumSet.cpp',
     'TestFloatingPoint.cpp',
     'TestIntegerPrintfMacros.cpp',
+    'TestRollingMean.cpp',
     'TestSHA1.cpp',
     'TestTypedEnum.cpp',
     'TestTypeTraits.cpp',
     'TestWeakPtr.cpp',
 ]
 
 if not CONFIG['MOZ_ASAN']:
     CPP_UNIT_TESTS += [