Anthony Jones (:ajones, :kentuckyfriedtakahe, :k17e) Assignee
	Description • 11 years ago

      No description provided.

	Jeff Walden [:Waldo]
	Comment 4 • 11 years ago

At a skim things look mostly fine here, except for use of std::vector, which won't play well with JS's potential use of this.  I'm working now at moving js::Vector over into mfbt so that you can use that instead -- might have patches later this week if I'm lucky.  Just an FYI.

	Anthony Jones (:ajones, :kentuckyfriedtakahe, :k17e) Assignee
	Comment 5 • 11 years ago

Can you add that bug as a blocker for this one then?

	Jeff Walden [:Waldo]
	Comment 6 • 11 years ago

Vector stuff landing is progressing nicely -- one yak-shavy bug to land, and I think that should be good to land.  Once that happens I'll finish up the review here.

	Jeff Walden [:Waldo]
	Comment 7 • 11 years ago

Comment on attachment 770019 [details] [diff] [review]
Rolling mean for MFBT;

Review of attachment 770019 [details] [diff] [review]:
-----------------------------------------------------------------

Whee, Vector is in so I can finally deal with this!  Sorry for the delay on that.

::: mfbt/RollingMean.h
@@ +2,5 @@
> +/* 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. */

Needs updating.

@@ +5,5 @@
> +
> +/* A set abstraction for enumeration values. */
> +
> +#ifndef mozilla_RollingMean_h
> +#define mozilla_RollingMean_h

mfbt/STYLE currently says this should have a trailing _.

@@ +10,5 @@
> +
> +#include "mozilla/Assertions.h"
> +
> +#include <stdint.h>
> +#include <vector>

Don't use <vector>, please use the new "mozilla/Vector.h" in m-i as of late last night.  Nice to see us able to use <stdint.h> directly, finally, tho.  :-)

@@ +20,5 @@
> + * accumulates the total as values are added and removed.
> + *
> + * WARNING: Float types are not supported due to rounding errors.
> + */
> +template<typename T, T (ZeroValue)()>

Hmm.  So you want this ZeroValue() thing to support stuff like TimeDuration that's a class with arithmetic operators on it.  But, really, we could just require that T(0) evaluate to the type's zero value.  That works for all the integral types, and it works for TimeDuration.  So let's use T(0) as the zero value, rather than have every user pass along a function pointer here.

@@ +22,5 @@
> + * WARNING: Float types are not supported due to rounding errors.
> + */
> +template<typename T, T (ZeroValue)()>
> +class RollingMeanBase
> +{

If float types aren't supported, add a

  #include "mozilla/TypeTraits.h"

  MOZ_STATIC_ASSERT(!IsFloatingPoint<T>::value,
                    "floating-point types are unsupported due to rounding errors");

There are patches in my request queue to mostly replace MOZ_STATIC_ASSERT with C++11 static_assert(), so watch out in case that changes between review here and landing.

@@ +38,5 @@
> +      MOZ_ASSERT(mValues.size() <= mMaxValues);
> +
> +      if (!mMaxValues) {
> +        return;
> +      }

mfbt doesn't brace single-line bodies, unless the associated control flow statements are multi-line.  The |if| condition is single-line here, so this shouldn't be braced.

@@ +45,5 @@
> +        mTotal -= mValues[mInsertIndex];
> +        mValues[mInsertIndex] = aValue;
> +      } else {
> +        mValues.insert(mValues.begin() + mInsertIndex, aValue);
> +      }

(In contrast the if-consequence is multiple lines, so bracing the else here is correct.)

@@ +50,5 @@
> +
> +      mTotal += aValue;
> +
> +      if (++mInsertIndex == mMaxValues) {
> +        mInsertIndex = 0;

|mInsertIndex = (mInsertIndex + 1) % mMaxValues| makes the modular-increment behavior clearer, I think.

@@ +60,5 @@
> +     */
> +    T getMean() {
> +      if (!mValues.size()) {
> +        return ZeroValue();
> +      }

No bracing.

@@ +61,5 @@
> +    T getMean() {
> +      if (!mValues.size()) {
> +        return ZeroValue();
> +      }
> +      return mTotal / mValues.size();

I don't see anything that handles mTotal overflow -- thus something like this:

  RollingMean<uint32_t> r;
  r.setMaxValues(4);
  for (int i = 0; i < 4; i++)
    r.insert(1 << 30);
  MOZ_ASSERT(r.getMean() == (1 << 30));

will fail.  I think you can handle this by tracking the mean value as you go, updating the incremental mean value in accordance with the current number of values tracked.  To avoid losing precision you'll need to keep around the sum of all the values modulo mMaxValues, and getMean() will have to take the incremental mean and add one if the modular sum is >= mMaxValues / 2.  A little messy -- particular for the signed types where overflow has undefined behavior -- but if we're going to do this, we need to get it right.

We also need tests for this behavior, and the API must document what mean value is chosen when there's not an exact mean value -- whether round-up, round-down, round-to-nearest-even, etc. gets chosen.

@@ +67,5 @@
> +
> +    /**
> +     * Set the maximum number of values in the rolling mean.
> +     */
> +    void setMaxValues(size_t aMaxValues)

I remember looking at the patch using this, and it wanting this.  But is it necessarily, absolutely the case that this should be settable after initialization, rather than being a parameter passed to the constructor?  Just asking that be considered, not asking for a change -- if there's good reason for it to be this way, that's fine.

@@ +73,5 @@
> +      mMaxValues = aMaxValues;
> +      if (mValues.size() > mMaxValues) {
> +        size_t toRemove = mValues.size() - mMaxValues;
> +        size_t toRemoveFromEnd = std::min(toRemove,
> +                                          mValues.size() - mInsertIndex);

If you're going to use std::min, #include <algorithm>.

@@ +85,5 @@
> +        }
> +
> +        MOZ_ASSERT(mValues.size() == mMaxValues);
> +      }
> +      mValues.reserve(mMaxValues);

When this method uses mozilla::Vector, this will need to propagate errors.

@@ +94,5 @@
> +     */
> +    void clear()
> +    {
> +      mValues.clear();
> +      mTotal = ZeroValue();

Should you be able to get a mean value when there are no values tracked?  Suppose you were using this structure to track the average speeds of vehicles on an expressway, it wouldn't make sense to say that the average speed before you'd tracked any cars' speeds was 0mph.  I think it probably makes more sense, in this case, to assert, such that you can't get an average until you've added at least one value.  (Which I guess means we need to add an API to indicate how many values are being used to calculate the mean value, so users can avoid this if they don't know values have yet been tracked.)

@@ +107,5 @@
> +                    mValues.begin() + aLastIndex);
> +    }
> +
> +    size_t mInsertIndex;
> +    size_t mMaxValues;

#include <stddef.h> for size_t.

@@ +112,5 @@
> +    std::vector<T> mValues;
> +    T mTotal;
> +};
> +
> +class RollingMeanHelpers {

We can get rid of all this helper/base/specialization gunk if we just use T(0) as the zero value.

::: mfbt/tests/TestRollingMean.cpp
@@ +3,5 @@
> + * 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/RollingMean.h"
> +#include "mozilla/Assertions.h"

Alphabetize.

@@ +5,5 @@
> +
> +#include "mozilla/RollingMean.h"
> +#include "mozilla/Assertions.h"
> +
> +using namespace mozilla;

We don't open up the entire namespace, rather we pick out the bits and pieces from it we need, individually.

using mozilla::RollingMean;

@@ +7,5 @@
> +#include "mozilla/Assertions.h"
> +
> +using namespace mozilla;
> +
> +class MyClass {

{ on new line.

@@ +99,5 @@
> +
> +      mean.insert(60);
> +      mean.insert(70);
> +      mean.insert(80);
> +      // The array shoud look like 60,70,80,40,50

s/shoud/should/g

	Jeff Walden [:Waldo]
	Comment 10 • 11 years ago

Comment on attachment 808988 [details] [diff] [review]
Rolling mean for MFBT;

Review of attachment 808988 [details] [diff] [review]:
-----------------------------------------------------------------

The Vector.h changes are independent of everything else -- r=me on landing that bit as its own change, independent of any other comments I have on the rest of this.  Comments on the rest to follow.

::: mfbt/Vector.h
@@ +531,5 @@
>      /**
>       * Removes the element |t|, which must fall in the bounds [begin, end),
>       * shifting existing elements from |t + 1| onward one position lower.
>       */
> +    void erase(T* t) { erase(t, t + 1); }

Let's add to this comment to note that this has performance linear in the number of elements past the specified element.

I think this may need to be inline void erase, with the implementation shifted below the OOL erase(T*, T*) implementation, to avoid used-but-not-defined warnings.

@@ +536,5 @@
> +
> +    /**
> +     * Removes the element |first| to |last - 1|, which must fall in the
> +     * bounds [begin, end), shifting existing elements from |last| onward
> +     * lower in the vector.

Also note linear in the number of elements past the removed range.

@@ +959,5 @@
>  }
>  
>  template<typename T, size_t N, class AP, class TV>
>  inline void
> +VectorBase<T, N, AP, TV>::erase(T* it, T* last)

s/it/first/ definitely.  And maybe s/last/lastExclusive/ as well?

@@ +964,3 @@
>  {
>    MOZ_ASSERT(begin() <= it);
>    MOZ_ASSERT(it < end());

Remove this assertion -- it's not a problem to erase no elements at the end of the vector, and in generic algorithms it may well require special code to work around, for no reason.

@@ +965,5 @@
>    MOZ_ASSERT(begin() <= it);
>    MOZ_ASSERT(it < end());
> +  MOZ_ASSERT(begin() <= last);
> +  MOZ_ASSERT(last <= end());
> +  size_t count = last - it;

PointerRangeSize(it, last);

	Jeff Walden [:Waldo]
	Comment 11 • 11 years ago

Second round of review nearly done, but I'm out for the day.  Tomorrow, promise!

	Jeff Walden [:Waldo]
	Comment 12 • 11 years ago

Actually, maybe not.  :-\  I have some questions that probably motivate enough back-and-forth that it's worth talking directly.  You're in Auckland right now, right?  I'm in London til Saturday (then fly back to SF), and the exact 12h difference makes this totally great right now.  But I could stick in the office later someday, or arrive earlier within vaguely normal limits, if that'd help.  What does your schedule look like the rest of the week, as far as IRC hours availability or so?

	Anthony Jones (:ajones, :kentuckyfriedtakahe, :k17e) Assignee
	Comment 13 • 11 years ago

It can wait until next week.

	Jeff Walden [:Waldo]
	Comment 14 • 11 years ago

Comment on attachment 808988 [details] [diff] [review]
Rolling mean for MFBT;

Review of attachment 808988 [details] [diff] [review]:
-----------------------------------------------------------------

Having setMaxValues as a mutating method makes for weird semantics, versus having it set in the constructor.  We both agreed on this in IRC, so we're going to just do that in the constructor, instead.  (I guess a subsequent init() method will have to be fallible, to allocate the relevant memory.  Oh well.  Better than having insert() be fallible, seems to me.)

These comments were written before I got to quite that point, when reviewing.  Some may still apply, many probably don't, but it seems worth getting them out there just in case any remain relevant.  :-)

::: mfbt/RollingMean.h
@@ +44,5 @@
> +
> +    /**
> +     * Insert a value into the rolling mean.
> +     */
> +    void insert(T aValue) {

bool insert(T value) {

@@ +48,5 @@
> +    void insert(T aValue) {
> +      MOZ_ASSERT(mValues.length() <= mMaxValues);
> +
> +      if (!mMaxValues)
> +        return;

Remove this bit, it's only hit if the assertion already happened, and that shouldn't happen.

@@ +55,5 @@
> +        mTotal = mTotal - mValues[mInsertIndex] + aValue;
> +        mValues[mInsertIndex] = aValue;
> +      } else {
> +        mTotal = mValues.empty() ? aValue : mTotal + aValue;
> +        mValues.insert(mValues.begin() + mInsertIndex, aValue);

This is fallible -- check for failure, return false if it fails.

@@ +58,5 @@
> +        mTotal = mValues.empty() ? aValue : mTotal + aValue;
> +        mValues.insert(mValues.begin() + mInsertIndex, aValue);
> +      }
> +
> +      mInsertIndex = (mInsertIndex + 1) % mMaxValues;

And return true here, then.

@@ +76,5 @@
> +    }
> +
> +    /**
> +     * Set the maximum number of values in the rolling mean. Returns false if
> +     * it fails to allocate the memory.

, which must be greater than zero

This has some really weird effects on the sequence of stored/observed values.  For example, suppose you have mMaxValues 4, mInsertIndex 2, with this sequence of observed values:

  [1, 1, 1, 1]

Then you change max-values to 8:

  [1, 1, 1, 1, U, U, U, U]

For the next insertion of value 3, length != mMaxValues, so |v| will be inserted at mInsertIndex and everything above it will shift up:

  [1, 1, 3, 1, 1, U, U, U]

And for an insertion of 4 after that:

  [1, 1, 3, 4, 1, 1, U, U]

Thus every insertion after a setMaxValues until the internal vector is filled again will be O(n), which is neither documented nor promised in the API, nor is it something I expect people will particularly expect.

I think we need to think harder about the API we're exposing here before we offer/expose it.  Under what conditions is the user here going to be calling setMaxValues?  Is it something that'll only happen once for the RollingMean, such that it'd be specifiable as an init() method (and we could just require that people not call it twice)?  Is it okay if we specify that calling setMaxValues throws away all cached values?  And what does it do to RollingMean::mean()?  The current method doesn't even touch mTotal at all when the max number of values is being decreased, so it kind of is nonsense right now.

@@ +80,5 @@
> +     * it fails to allocate the memory.
> +     */
> +    bool setMaxValues(size_t aMaxValues)
> +    {
> +      mMaxValues = aMaxValues;

MOZ_ASSERT(aMaxValues > 0);

@@ +95,5 @@
> +          mInsertIndex = 0;
> +
> +        MOZ_ASSERT(mValues.length() == mMaxValues);
> +      }
> +      return mValues.reserve(mMaxValues);

If this fails, we're in kind of sort of almost an inconsistent state.

@@ +118,5 @@
> +
> +    size_t mInsertIndex;
> +    size_t mMaxValues;
> +    Vector<T> mValues;
> +    S mTotal;

Fields go at the start of a class, so they're all in one consistent place and are easily scanned before seeing the exposed API or implementation of the class.

	Jeff Walden [:Waldo]
	Comment 17 • 11 years ago

Comment on attachment 829049 [details] [diff] [review]
Rolling mean for MFBT;

Review of attachment 829049 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry for the further delay here.  :-(

A part of me still thinks that, rather than having two types T/S to track values and total, we should just reuse T twice, one tracking the current average, one tracking the modulus of the current sum  divided by elements.  With careful arithmetic you could get an accurate mean without ever having to worry about overflows, etc.  But it probably doesn't matter *that* much in practice, and it can be a followup at some point, I guess.

::: mfbt/RollingMean.h
@@ +42,5 @@
> +                  "errors");
> +
> +    RollingMean(size_t aMaxValues)
> +      : mInsertIndex(0)
> +      , mMaxValues(aMaxValues)

, at end of previous line.

@@ +44,5 @@
> +    RollingMean(size_t aMaxValues)
> +      : mInsertIndex(0)
> +      , mMaxValues(aMaxValues)
> +    {
> +      // mTotal is left uninitialised/undefined until we insert a value

MOZ_ASSERT(aMaxValues > 0);

@@ +47,5 @@
> +    {
> +      // mTotal is left uninitialised/undefined until we insert a value
> +    }
> +
> +    bool operator=(const RollingMean<T, S>& aOther) {

You could equivalently omit <T, S> to make this more readable and slightly less error-prone.

This being fallible is messy -- particularly as your use shows, because people are probably just going to not check for errors.  :-\  But I think we can work around that here.  Just make this a move-assignment operator (for more info read the comments in mfbt/Move.h):

#include "mozilla/Move.h"

  RollingMean& operator=(RollingMean&& other) {
    MOZ_ASSERT(this != &other, "self-assignment is forbidden");
    this->~RollingMean();
    mInsertIndex = other.mInsertIndex;
    mMaxValues = other.mMaxValues;
    mTotal = other.mTotal;
    mValues.swap(other);
    return *this;
  }

The use in the other patch will be fine, because it's being assigned a temporary.

@@ +67,5 @@
> +      if (mValues.length() == mMaxValues) {
> +        mTotal = mTotal - mValues[mInsertIndex] + aValue;
> +        mValues[mInsertIndex] = aValue;
> +      } else {
> +        if (!mValues.insert(mValues.begin() + mInsertIndex, aValue))

This is the only way mValues ever increases in length, right?  And if clear() resets to zero, as it must (see below), that means mInsertIndex for non-full vector is always the length of the vector.  So can't we make this an append(aValue)?

@@ +69,5 @@
> +        mValues[mInsertIndex] = aValue;
> +      } else {
> +        if (!mValues.insert(mValues.begin() + mInsertIndex, aValue))
> +          return false;
> +        mTotal = mValues.length() == 1 ? aValue : mTotal + aValue;

Any reason we can't make this mTotal += aValue and just initialize mTotal to 0 to remove this special case?

@@ +92,5 @@
> +    /**
> +     * Remove all values from the rolling mean.
> +     */
> +    void clear() {
> +      mValues.clear();

Doesn't this need to reset mInsertIndex?  Please add a test that exercises this.

::: mfbt/Vector.h
@@ +530,5 @@
>  
>      /**
>       * Removes the element |t|, which must fall in the bounds [begin, end),
>       * shifting existing elements from |t + 1| onward one position lower.
>       */

Separate paragraph:

This operation requires time proportional to the number of elements after the element removed.

@@ +536,5 @@
> +
> +    /**
> +     * Removes the element |first| to |last - 1|, which must fall in the
> +     * bounds [begin, end), shifting existing elements from |last| onward
> +     * lower in the vector.

This operation requires time proportional to the number of elements after the elements removed.

@@ +966,5 @@
>    MOZ_ASSERT(begin() <= it);
>    MOZ_ASSERT(it < end());
> +  MOZ_ASSERT(begin() <= last);
> +  MOZ_ASSERT(last <= end());
> +  size_t count = last - it;

mozilla::PointerRangeSize here, please.

::: mfbt/tests/TestRollingMean.cpp
@@ +29,5 @@
> +    MyClass operator/(uint32_t div) const {
> +      return MyClass(value / div);
> +    }
> +
> +    uint32_t value;

Put this at the top of the class for readability.

@@ +59,5 @@
> +      mean.insert(4);
> +      MOZ_ASSERT(mean.mean() == 4);
> +
> +      mean.clear();
> +      MOZ_ASSERT(mean.empty());

Adding a |mean.insert(3)| after this test should, I'm pretty sure, either generate an assert *or* generate a memory access error with valgrind -- unless clear() resets the insert index.

@@ +99,5 @@
> +
> +      mean.insert(10);
> +      MOZ_ASSERT(mean.mean() == 10);
> +
> +      RollingMean<uint32_t, uint64_t> copy(0);

There's no use case for aMaxValues == 0, so this should change to 1 or something.

@@ +100,5 @@
> +      mean.insert(10);
> +      MOZ_ASSERT(mean.mean() == 10);
> +
> +      RollingMean<uint32_t, uint64_t> copy(0);
> +      copy = mean;

This will need Move(mean) to work with the infallible move-assignment operator.

@@ +102,5 @@
> +
> +      RollingMean<uint32_t, uint64_t> copy(0);
> +      copy = mean;
> +      MOZ_ASSERT(mean.mean() == 10);
> +      MOZ_ASSERT(copy.mean() == 10);

And at this point -- only because we know the implementation of RollingMean -- we can MOZ_ASSERT(mean.clear()).  (We can no longer assert |mean.mean() == 10|, because the move constructor cleared out |mean|.)

@@ +108,5 @@
> +      copy.insert(30);
> +      copy.insert(30);
> +      copy.insert(30);
> +      copy.insert(30);
> +      MOZ_ASSERT(copy.mean() == 30);

Change these to all different values, then check for the appropriate mean, in the interests of more robustness.

	Anthony Jones (:ajones, :kentuckyfriedtakahe, :k17e) Assignee
	Comment 18 • 11 years ago

https://tbpl.mozilla.org/?tree=Try&rev=be0300df3586

	Anthony Jones (:ajones, :kentuckyfriedtakahe, :k17e) Assignee
	Comment 19 • 11 years ago

https://hg.mozilla.org/integration/mozilla-inbound/rev/468598d17533
https://hg.mozilla.org/integration/mozilla-inbound/rev/ec023921268d

	Carsten Book [:Tomcat]
	Comment 20 • 11 years ago

https://hg.mozilla.org/mozilla-central/rev/468598d17533
https://hg.mozilla.org/mozilla-central/rev/ec023921268d