786504 - Add a simple script to compare test runs in two revisions

Status: RESOLVED FIXED

(Testing :: Talos, defect)

Description

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: add the script

Currently there are two tools to look at talos numbers:
* compare.py in the talos repo
* the compare-talos website

compare.py seems designed to look at historical trends. It lacks the ability to show statistics on mulitple runs on the same revision.

compare-tolos is a stand alone tool and a website. It is easy for it to get out of sync and "hard" to update.

The proposed script is conceptually similar to compare talos, but:

* It is a script. If it is out of sync, the question of "where is the code that I have to change" has a a trivial answer.
* It is designed to avoid bit rot. It asserts that it understands what the graph server is saying. When checking if there is a regression in a try run, I think graceful degradation is a misfeature. If the script doesn't understand something it should abort.

Asking for a review from bjacob first to make sure the math is correct :-)

Comment 1

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: fixed sunspider

Good thing I checked with a -O1 run, sunspider was in the wrong group.

btw, an example run looks like:
./tools/performance/diff-talos.py cdffd8055b7a efb3564062d5

Comment 2

[Joel Maher ( :jmaher ) (UTC -8)]

I like the idea of stats adding to the mix.  I tried running this and couldn't get it to work.  Maybe my definition of a revision is different because the example above works just fine for me locally.

The one concern I have about this (and correct me if I am wrong), is that our numbers fluctuate greatly even running on the same changeset.  What this means is you could see what you think is a performance win from one changeset to the next, when in fact it isn't.  If we could get 5 or more data points from both changsets, then I would feel more comfortable comparing between them.

compare.py was used to look at 7 days worth of data and ensure that your current changeset was in the same range.  It doesn't consider the fact that the range you are comparing against has seen a regression or major improvement therefore making it a larger than normal range.

Comment 3

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

(In reply to Joel Maher (:jmaher) from comment #2)
> I like the idea of stats adding to the mix.  I tried running this and
> couldn't get it to work.  Maybe my definition of a revision is different
> because the example above works just fine for me locally.

I just realized that we have a different set of benchmarks for different OSs, so I had to relax the asserts a bit. I will upload a new version in a second.

> The one concern I have about this (and correct me if I am wrong), is that
> our numbers fluctuate greatly even running on the same changeset.  What this
> means is you could see what you think is a performance win from one
> changeset to the next, when in fact it isn't.  If we could get 5 or more
> data points from both changsets, then I would feel more comfortable
> comparing between them.

You can get 5 or more data points, by running the benchmarks multiple times. I can see the value of looking at multiple changes that the user "knows" have not modified a benchmark value. Something like

$ diff-talos.py rev1,rev2 rev3,rev4

would assume that rev1 and rev2 are equivalent. Same for rev3 and rev4. What makes me a bit nervous about it is that it is really hard to know what can have a performance impact. I started working on this when noticing that builds done on try were faster than builds I was doing locally. The differences I found:

* ccache producing smaller binaries by changing __FILE__ to be relative.
* a non determinism (iterating a hash of pointers) on the order clang output some functions.
* an extra symbol on the try build because the bots have a case sensitive file system.

In summary, it is really hard to know if something has a performance impact or not. On the other hand, I guess that is what the standard deviation is there for and I can implement if you want. Can we do it in version 2?

> compare.py was used to look at 7 days worth of data and ensure that your
> current changeset was in the same range.  It doesn't consider the fact that
> the range you are comparing against has seen a regression or major
> improvement therefore making it a larger than normal range.

Comment 4

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: new version

I noticed that we have a different set of benchmarks on different operating systems. This versions then just asserts that it knows a superset of the tests the graphserver sends it.

Comment 5

[Jeff Hammel]

I'm going to presume this isn't just linux

Comment 6

[Jeff Hammel]

Personally i'd much presume the script used the data in talos' test.py: http://hg.mozilla.org/build/talos/file/6d79047595a4/talos/test.py . That way it won't be out of date.

Comment 7

[Benoit Jacob [:bjacob] (mostly away)]

Comment on attachment 656434 [details] [diff] [review]
new version

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

I am only commenting on the math here. I don't know either Talos or Python.

::: tools/performance/diff-talos.py
@@ +58,5 @@
> +def c4(n):
> +    n = float(n)
> +    numerator = math.gamma(n/2)*math.sqrt(2/(n-1))
> +    denominator = math.gamma((n-1)/2)
> +    return numerator/denominator

I have no idea whether this is performance critical, but if it is, the above is rather expensive to compute and could be made cheaper either by using a known formula for Gamma(x+1/2)/Gamma(x) or even better, just replace c4 by a truncated asymptotic expansion as given in

http://en.wikipedia.org/wiki/Unbiased_estimation_of_standard_deviation#Bias_correction

c4(n) = 1 - (1/4) n^{-1} - (7/32) n^{-2} - (19/128) n^{-3} + O(n^{-4})

@@ +62,5 @@
> +    return numerator/denominator
> +
> +def unbiased_standard_deviation(values):
> +    n = len(values)
> +    if n == 1:

It probably wouldn't hurt to do this if n <= 1

@@ +65,5 @@
> +    n = len(values)
> +    if n == 1:
> +        return None
> +    acc = 0
> +    avg = average(values)

Again I have no idea whether this is performance critical, but if it is, merge this average computation into the below for loop to traverse the array only once.

@@ +67,5 @@
> +        return None
> +    acc = 0
> +    avg = average(values)
> +    for i in values:
> +        acc += pow(i - avg, 2)

It is generally much more efficient to do x*x than pow(x, 2).

@@ +68,5 @@
> +    acc = 0
> +    avg = average(values)
> +    for i in values:
> +        acc += pow(i - avg, 2)
> +    return math.sqrt(acc/n)/c4(n)

Apply "Bessel's correction" here: divide acc by n-1 instead of n. See above wiki page. This is why you had divided by n-1 in the definition of c4. These two sqrt(n-1) factors cancel out, so you might as well take them out if this is performance sensitive, but then of course the code would look more confusing as you'd depart from usual math objects.

Comment 8

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

(In reply to Jeff Hammel [:jhammel] from comment #6)
> Personally i'd much presume the script used the data in talos' test.py:
> http://hg.mozilla.org/build/talos/file/6d79047595a4/talos/test.py . That way
> it won't be out of date.

What part of it are you afraid it will go out of date? The only reason the script has a list of tests is to assert that in knows all the benchmarks where a bigger number is better, and I don't think that information is available in test.py.

Comment 9

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

> > +def c4(n):
> > +    n = float(n)
> > +    numerator = math.gamma(n/2)*math.sqrt(2/(n-1))
> > +    denominator = math.gamma((n-1)/2)
> > +    return numerator/denominator
> 
> I have no idea whether this is performance critical, but if it is, the above
> is rather expensive to compute and could be made cheaper either by using a
> known formula for Gamma(x+1/2)/Gamma(x) or even better, just replace c4 by a
> truncated asymptotic expansion as given in
> 
> http://en.wikipedia.org/wiki/
> Unbiased_estimation_of_standard_deviation#Bias_correction
> 
> c4(n) = 1 - (1/4) n^{-1} - (7/32) n^{-2} - (19/128) n^{-3} + O(n^{-4})

It is not. Even comparing two full runs with *many* reruns the scripts runs is less than 1s.

> 
> @@ +62,5 @@
> > +    return numerator/denominator
> > +
> > +def unbiased_standard_deviation(values):
> > +    n = len(values)
> > +    if n == 1:
> 
> It probably wouldn't hurt to do this if n <= 1

It gets a division by 0 in c4 :-)

> 
> It is generally much more efficient to do x*x than pow(x, 2).

done.

> @@ +68,5 @@
> > +    acc = 0
> > +    avg = average(values)
> > +    for i in values:
> > +        acc += pow(i - avg, 2)
> > +    return math.sqrt(acc/n)/c4(n)
> 
> Apply "Bessel's correction" here: divide acc by n-1 instead of n. See above
> wiki page. This is why you had divided by n-1 in the definition of c4. These
> two sqrt(n-1) factors cancel out, so you might as well take them out if this
> is performance sensitive, but then of course the code would look more
> confusing as you'd depart from usual math objects.

Thanks!

Comment 10

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: new version

Comment 11

[Jeff Hammel]

(In reply to Rafael Ávila de Espíndola (:espindola) from comment #8)
> (In reply to Jeff Hammel [:jhammel] from comment #6)
> > Personally i'd much presume the script used the data in talos' test.py:
> > http://hg.mozilla.org/build/talos/file/6d79047595a4/talos/test.py . That way
> > it won't be out of date.
> 
> What part of it are you afraid it will go out of date? The only reason the
> script has a list of tests is to assert that in knows all the benchmarks
> where a bigger number is better, and I don't think that information is
> available in test.py.

I think this is available in graphserver somewhere, though I can't find it at the moment (though perhaps :rhelmer knows better).  In the longer term, I would really like a solution which had a canonical source of tests that could be used in Talos, graphserver, scripts like this, etc, but this is some ways off

Comment 12

[Robert Helmer [:rhelmer]]

(In reply to Jeff Hammel [:jhammel] from comment #11)
> (In reply to Rafael Ávila de Espíndola (:espindola) from comment #8)
> > (In reply to Jeff Hammel [:jhammel] from comment #6)
> > > Personally i'd much presume the script used the data in talos' test.py:
> > > http://hg.mozilla.org/build/talos/file/6d79047595a4/talos/test.py . That way
> > > it won't be out of date.
> > 
> > What part of it are you afraid it will go out of date? The only reason the
> > script has a list of tests is to assert that in knows all the benchmarks
> > where a bigger number is better, and I don't think that information is
> > available in test.py.
> 
> I think this is available in graphserver somewhere, though I can't find it
> at the moment (though perhaps :rhelmer knows better).  In the longer term, I
> would really like a solution which had a canonical source of tests that
> could be used in Talos, graphserver, scripts like this, etc, but this is
> some ways off

The script catlee wrote that reports to tree-management is the only place this lives in graphserver AFAIK: http://hg.mozilla.org/graphs/file/226cc32b95c6/server/analysis/analysis.cfg.template#l44

Comment 13

[(no longer active)]

Comment on attachment 657487 [details] [diff] [review]
new version

I think someone should review this who actually knows about Talos!

Comment 14

[Jeff Hammel]

Comment on attachment 657487 [details] [diff] [review]
new version

I would tend to add more verbose error messages to the assert
statements, at least for those that are likely to be triggered in real
life.  It would also be nice to see more docstrings.

> diff --git a/tools/performance/diff-talos.py b/tools/performance/diff-talos.py
> new file mode 100644
> index 0000000..63f96d7
> --- /dev/null
> +++ b/tools/performance/diff-talos.py
> @@ -0,0 +1,167 @@
> +#!/usr/bin/python

#!/usr/bin/env python is the more usual she-bang since it doesn't depend on the exact location of python

> +# 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/.

> +# This is a simple script that does one thing only: compare talos runs from
> +# two revisions. It is intended to check which of two try runs is best or if
> +# a try improves over the m-c or m-i revision in branches from.
> +
> +# A big design goal is to avoid bit rot and to assert when bit rot is detected.
> +# The set of tests we run is a moving target. When possible this script
> +# should work with any test set, but in parts where it has to hard code
> +# information, it should try to assert that it is valid so that changes
> +# are detected and it is fixed earlier.

I would use a docstring for this instead of a comment.

> +import simplejson

I would also tend to import json first, as simplejson is deprecated in
newer python:

try:
    import json
except ImportError:
    import simplejson as json

> +import urllib2
> +import math
> +import sys

> +# FIXME: currently we assert that we know all the benchmarks just so
> +# we are sure to maintain the bigger_is_better set updated. Is there a better
> +# way to find/compute it?

I'm not sure there is a better way to find this.  I am fairly positive
we need one.

My basic idea is....it would be nice to have a package that just
covers these conventions and have graphserver us it.  Currently,
graphserver's data.sql stores what graphserver calls the tests, and
http://hg.mozilla.org/graphs/file/226cc32b95c6/server/analysis/analysis.cfg.template#l44
(supposedly) stores which tests are reverse or not.  However, the
latter seems inaccurate.

> +bigger_is_better = frozenset(('v8_7', 'dromaeo_dom', 'dromaeo_css'))
> +
> +smaller_is_better = frozenset(('tdhtmlr_paint', 'tp5n_main_rss_paint',
> +                               'ts_paint', 'tp5n_paint', 'tsvgr_opacity',
> +                               'a11yr_paint', 'kraken',
> +                               'tdhtmlr_nochrome_paint',
> +                               'tspaint_places_generated_med', 'tpaint',
> +                               'tp5n_shutdown_paint', 'tsvgr',
> +                               'tp5n_pbytes_paint', 'tscrollr_paint',
> +                               'tspaint_places_generated_max',
> +                               'tp5n_responsiveness_paint',
> +                               'sunspider', 'tp5n_xres_paint', 'num_ctors'))
> +
> +all_benchmarks = smaller_is_better | bigger_is_better
> +assert len(smaller_is_better & bigger_is_better) == 0
> +
> +def get_raw_data_for_revisions(revisions):
> +    """Loads data for the revisions, returns an array with one element for each
> +    revision."""
> +    selectors = ["revision=%s" % revision for revision in revisions]
> +    selector = '&'.join(selectors)
> +    url = "http://graphs.mozilla.org/api/test/runs/revisions?%s" % selector
> +    url_stream = urllib2.urlopen(url)
> +    data = simplejson.load(url_stream)
> +    assert frozenset(data.keys()) == frozenset(('stat', 'revisions'))
> +    assert data['stat'] == 'ok'
> +    rev_data = data['revisions']
> +    assert frozenset(rev_data.keys()) == frozenset(revisions)
> +    return [rev_data[r] for r in revisions]
> +
> +def average(values):
> +    return sum(values)/len(values)

Should this be `/float(len(values))` or float(sum(values))?
Also I would tend to call this `mean` vs `average`.

> +def c4(n):
> +    n = float(n)
> +    numerator = math.gamma(n/2)*math.sqrt(2/(n-1))
> +    denominator = math.gamma((n-1)/2)
> +    return numerator/denominator
> +
> +def unbiased_standard_deviation(values):
> +    n = len(values)
> +    if n == 1:
> +        return None
> +    acc = 0
> +    avg = average(values)
> +    for i in values:
> +        dist = i - avg
> +        acc += dist * dist
> +    return math.sqrt(acc/(n-1))/c4(n)
> +
> +class BenchmarkResult:
> +    """ Stores the summary (average and standard deviation) of a set of talus
> +    runs on the same revision and OS."""
> +    def __init__(self, avg, std):
> +        self.avg = avg
> +        self.std = std
> +    def __str__(self):
> +        t = "%s," % self.avg
> +        return "(%-13s %s)" % (t, self.std)
> +
> +#FIXME: should this support computing statistic over multilpe revisions
> +# that are assumed to be equivalent?

Not sure I understand the question. (Also, a misspelling).

> +def digest_revision_data(data):
> +    ret = {}
> +    benchmarks = frozenset(data.keys())
> +    assert all_benchmarks.issuperset(benchmarks)

So running:

python bug-786504.py 4a4c1293f2fd 8c4c2f783585

I hit this assertion error.  I would tend to print out what isn't
being found, a la:

    assert all_benchmarks.issuperset(benchmarks), "%s not found in all_benchmarks" % [i for i in benchmarks if i not in all_benchmarks]

Doing this, I see:

AssertionError: ['tp5n_modlistbytes_paint', 'trobopan', 'trace_malloc_maxheap', 'tp4m_nochrome', 'trace_malloc_leaks', 'tresize', 'tp4m_main_rss_nochrome', 'tcheckerboard', 'tcheck3', 'tcheck2', 'tp4m_shutdown_nochrome', 'tdhtml_nochrome', 'ts_shutdown', 'tp5n_%cpu_paint', 'trace_malloc_allocs', 'ts', 'codesighs', 'tsvg_nochrome', 'tp5n_content_rss_paint', 'tprovider'] not found in all_benchmarks

In fact, I'm not really sure this assert is needed at all.


> +    for benchmark in benchmarks:
> +        benchmark_data = data[benchmark]
> +        expected_keys = frozenset(("test_runs", "name", "id"))
> +        assert frozenset(benchmark_data.keys()) == expected_keys
> +        test_runs = benchmark_data["test_runs"]
> +        operating_systems = test_runs.keys()
> +        results = {}
> +        for os in operating_systems:
> +            os_runs = test_runs[os]
> +            values = []
> +            for os_run in os_runs:
> +                # there are 4 fields: test run id, build id, timestamp,
> +                # average value
> +                assert len(os_run) == 4
> +                values.append(os_run[3])
> +            avg = average(values)
> +            std = unbiased_standard_deviation(values)
> +            results[os] = BenchmarkResult(avg, std)
> +        ret[benchmark] = results
> +    return ret
> +
> +def get_data_for_revisions(revisions):
> +    raw_data = get_raw_data_for_revisions(revisions)
> +    return [digest_revision_data(x) for x in raw_data]
> +
> +def overlaps(a, b):
> +    return a[1] >= b[0] and b[1] >= a[0]
> +
> +def is_significant(old, new):
> +    # conservative hack: if we don't know, say it is significant.
> +    if old.std is None or new.std is None:
> +        return True
> +    # use a 2 standard deviation interval, which is about 95% confidence.
> +    old_interval = [old.avg - old.std, old.avg + old.std]
> +    new_interval = [new.avg - new.std, new.avg + new.std]
> +    return not overlaps(old_interval, new_interval)
> +
> +def compute_difference(benchmark, old, new):
> +    if benchmark in bigger_is_better:
> +        new, old = old, new
> +
> +    if (new.avg >= old.avg):
> +        return "%1.4fx worse" % (new.avg/old.avg)
> +    else:
> +        return "%1.4fx better" % (old.avg/new.avg)
> +
> +#FIXME: the printing could use a table class that computes the sizes of the
> +# cells instead of the current hard coded values.
> +def print_data_comparison(old_data, new_data):
> +    benchmarks = frozenset(old_data.keys())
> +    assert benchmarks == frozenset(new_data.keys())

I get an error here:

python bug-786504.py 4a4c1293f2fd 8c4c2f783585
Traceback (most recent call last):
  File "bug-786504.py", line 166, in <module>
    main()
  File "bug-786504.py", line 164, in main
    print_data_comparison(data[0], data[1])
  File "bug-786504.py", line 140, in print_data_comparison
    assert benchmarks == frozenset(new_data.keys())
AssertionError

Looking closer:

(Pdb) benchmarks.symmetric_difference(new_data.keys())
frozenset(['tcheck3', 'tprovider'])

I'm not 100% sure what to do here.  It would be nice to use the script
even if not all of the data is available.  Maybe print out a warning
with what is each set but not in the other and use the union as the
set of benchmarks?

> +    for benchmark in sorted(benchmarks):
> +        print benchmark
> +        old_benchmark_data = old_data[benchmark]
> +        new_benchmark_data = new_data[benchmark]
> +        operating_systems = frozenset(old_benchmark_data.keys())
> +        assert operating_systems == frozenset(new_benchmark_data.keys())

I also hit this.

> +        for os in operating_systems:
> +            old_os_data = old_benchmark_data[os]
> +            new_os_data = new_benchmark_data[os]
> +            if not is_significant(old_os_data, new_os_data):
> +                continue
> +
> +            diff = compute_difference(benchmark, old_os_data, new_os_data)
> +            print '%-33s | %-30s -> %-30s %s' % \
> +                (os, old_os_data, new_os_data, diff)
> +        print
> +
> +def main():
> +    old_rev = sys.argv[1]
> +    new_rev = sys.argv[2]

This is pretty error prone, as it will just err out with little
explanation if you don't give enough arguments.  Better would be to
check for this and display an error message.  Even better would be to
use optparse and display usage and have a --help swith

> +    revs=[old_rev, new_rev]
> +    data=get_data_for_revisions(revs)
> +    print_data_comparison(data[0], data[1])


> +main()

Usually, `if __name__ == '__main__': main()` in case you want to import this from something


My biggest problem is the hardest to solve:  namely, that we're
averaging a bunch of averages and that in general they're not going to
be normal distributions :( . However, all of our existing tools work
on these assumptions, so I don't think this is any worse than what we
currently have.  I would really like to have someone with a statistics
background, possibly from metrics, weigh in on this, at least for the
future.

I'm going to leave this unreviewed pending questions about what to do
about the failing asserts that I encounter.

Comment 15

[Jeff Hammel]

Attachment: what i had to do to get this working

mostly small changes in how the asserts are handled.  Not necessarily recommended as the way forward

Comment 16

[Benoit Jacob [:bjacob] (mostly away)]

Comment on attachment 657487 [details] [diff] [review]
new version

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

feedback+ on the math

Comment 17

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

Attachment: version with the review feedback

I just used the json module, is that OK?

Comment 18

[Jeff Hammel]

Comment on attachment 659797 [details] [diff] [review]
version with the review feedback

the json module will not be available in 2.5.  If you're okay with that, then I'm fine with that.

+    if (new.avg >= old.avg):
no need for ()s

+    old_rev = args[0]
+    new_rev = args[1]
+
+    revs=[old_rev, new_rev]
+    data=get_data_for_revisions(revs)
+    print_data_comparison(data[0], data[1])

This is a bit long for not really doing much.  You could do this in one line:

print_data_comparison(get_data_for_revisions(args))

If you wanted two lines, I'm inclined to do:

data = get_data_for_revisions(args)
print_data_comparison(data)

And of course you can rename `args` to `revs` if that makes more sense.

This runs for me OOTB and generates numbers.  I'm still not convinced how actually useful this is for rigorous regression detection, but we have to start somewhere.  r+

Comment 19

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

> This runs for me OOTB and generates numbers.  I'm still not convinced how
> actually useful this is for rigorous regression detection, but we have to
> start somewhere.  r+

It helps, but yes, there is still work to be done on the script to get better statistics and, probably more important, in talus to remove measurement bias.

https://hg.mozilla.org/integration/mozilla-inbound/rev/442e4532d2c7

Comment 20

[Jeff Hammel]

(In reply to Rafael Ávila de Espíndola (:espindola) from comment #19)
> > This runs for me OOTB and generates numbers.  I'm still not convinced how
> > actually useful this is for rigorous regression detection, but we have to
> > start somewhere.  r+
> 
> It helps, but yes, there is still work to be done on the script to get
> better statistics and, probably more important, in talus to remove
> measurement bias.

Do you know any of these in particular?  Could you ticket?  The only thing I am aware of, Talos-side (I think), is the filtering stuff for graphserver.  We're working on deprecating that, but this will not be quick.

Comment 21

[Rafael Ávila de Espíndola (:espindola) (not reading bugmail)]

One bias that I know does show up in sunspider is function alignment. I had a case where a new clang optimization would make the interpreter slower by reducing the size of a function past a 16 byte boundary.

See https://plus.google.com/u/0/108996039294665965197/posts/8E7zHQuTaj1 for some details. One paper that is *really* interesting is http://www-plan.cs.colorado.edu/diwan/asplos09.pdf

I will probably try to improve the statistics in this script, but I don't think I have the bandwidth (guts?) to try to modify talos.

Comment 22

[Jeff Hammel]

TBH, I think the ideas there are beyond the scope of Talos.  Talos is a python program + extension to gather statistics, but it shouldn't really do any calculation (IMHO), and its facility to setup a clean system environment is pretty limited.  Still, if you think of anything that we could do in such a system, bugs are appreciated

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/442e4532d2c7