[webkit-dev] BigO correlation tests

[Nikos Andronikos]

Hey all,

We’ve noticed what we think is some flakiness with tests that attempt to
determine the BigO characteristics (using magnitude-perf.js) of
performance tests and would like some feedback from the community.

In our particular case, we are seeing a failure on the iOS simulator of
the following test:
LayoutTests/perf/nested-combined-selectors.html

See: https://webkit-queues.webkit.org/results/1107504
From bug: https://bugs.webkit.org/show_bug.cgi?id=156096

The result on the iOS sim is falling just short of being correlated to
linear due to the tolerances chosen.

The numbers for an example run are:
rSquared 0.8817542004431037
rSquaredXLog 0.44260332869587665
rSquaredXYLog 0.8678643749155268
rSquaredMax 0.8817542004431037


And the relevant bit of code in magnitude-perf.js that determines
correlation is:

  var bigO = Magnitude.INDETERMINATE;

  // FIXME: These numbers were chosen arbitrarily.
  // Are there a better value to check against? Do we need to check
rSquaredMax?
  if (rSquared < 0.8 && rSquaredMax < 0.9)
      bigO = Magnitude.CONSTANT;
  else if (rSquaredMax > 0.9) {
      if (rSquared == rSquaredMax)
          bigO = Magnitude.LINEAR;
      else if (rSquaredXLog == rSquaredMax)
          bigO = Magnitude.LOGARITHMIC;
      else if (rSquaredXYLog == rSquaredMax)
          bigO = Magnitude.POLYNOMIAL;
  }


So you can see we don’t quite pass the ‘else if (rSquaredMax 0.9)’ test
and so the result is given as indeterminate.

My feeling is that the numbers we are getting are correlated closely
enough to Magnitude.LINEAR, and we should consider changing the values in
magnitude-perf.js.

So I’d like to propose that we lower the thresholds and change the following lines to check the slope of the linear correlation
and the correlation coefficient:

From:
  if (rSquared < 0.8 && rSquaredMax < 0.9)
      bigO = Magnitude.CONSTANT;
  else if (rSquaredMax 0.9) {
To:
  if (rSquared > 0.7) {
      bigO = Magnitude.LINEAR;
  }
  else if (Math.abs(slope) < 1.0E-04)
      bigO = Magnitude.CONSTANT;
  else {
      // calculate and check correlation coefficient for rSquaredXLog and rSquaredXYLog
  }

This check first tests the correlation coefficient (i.e. if linear order) – note the threshold is lowered to 0.7.
Then it checks whether the performance is independent of the number of iterations/objects (i.e. a shallow slope).
Then we calculate and check the other cases (i.e. polynomial or logarithmic).
Failing all other checks, the order defaults to indeterminate.

We are considering submitting a patch to make this change, but would like
input from anyone who has experience with this test framework.

Thanks,
Nikos
The information contained in this email message and any attachments may be confidential and may also be the subject to legal professional privilege. If you are not the intended recipient, any use, interference with, disclosure or copying of this material is unauthorised and prohibited. If you have received this email in error, please immediately advise the sender by return email and delete the information from your system.