[webkit-dev] BigO correlation tests

Ryosuke Niwa rniwa at webkit.org
Wed Apr 13 12:18:06 PDT 2016

On Wed, Apr 13, 2016 at 12:17 AM, Nikos Andronikos
<Nikos.Andronikos at cisra.canon.com.au> wrote:
>> 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…
> That’s a fair comment (regarding false negatives), we can do that. But to be honest, I don’t have a lot of faith in the reliability of these tests anyway. Since they were added by Google, do you have any thoughts on whether we could remove them?

If they never pass anywhere, then removing them seems okay although
other contributors may have opposing views.  e.g. I think Darin likes
these tests.

+darin to that end.

>> 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.
> Sorry, I’m not following what you’re saying here.

I think some of these tests are added as a part of patch to fix a
performance issue.   e.g.
was added in http://trac.webkit.org/changeset/122660 when I fixed
HTMLCollection to be not O(n^2) four years ago.  You could conceivably
make HTMLCollection O(n^2), e.g. by reverting my fix, and run the
test.  The test should fail.  Since the codebase has changed quite
dramatically since I added that test so you can't probably just undo
what I did.  It might be easier to just add some loop that iterate
over nodes instead.

- R. Niwa

More information about the webkit-dev mailing list