[webkit-dev] BigO correlation tests

[Ryosuke Niwa]

I don’t think order of magnitudes tests ever quite worked JSC (it was added by Google so it obviously worked on V8).  If adjusting the threshold was all that was needed to make the tests pass, I see no reason how to change it.

However, what you proposed will only reduce the likelihood of type I errors (false positives).  You should also examine how it affects the likelihood of type II errors (false negative).  You might want to make some API artificially O(n^2) and make sure the test starts failing, etc…  You can probably look at the svn/git blame the change which added relevant tests in LayoutTests/perf/ and apply a reverse change locally to test that.

- R. Niwa
On April 12, 2016 at 10:05:25 PM, Nikos Andronikos (nikos.andronikos at cisra.canon.com.au) wrote:

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.  
_______________________________________________
webkit-dev mailing list
webkit-dev at lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-dev/attachments/20160412/b4c228d8/attachment.html>