1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.android.regression.tests;
17 
18 import com.android.ddmlib.Log;
19 import com.android.regression.tests.MetricsXmlParser.ParseException;
20 import com.android.tradefed.config.Option;
21 import com.android.tradefed.config.OptionClass;
22 import com.android.tradefed.log.LogUtil.CLog;
23 import com.android.tradefed.result.ITestInvocationListener;
24 import com.android.tradefed.result.TestDescription;
25 import com.android.tradefed.testtype.IRemoteTest;
26 import com.android.tradefed.testtype.suite.ModuleDefinition;
27 import com.android.tradefed.util.FileUtil;
28 import com.android.tradefed.util.MultiMap;
29 import com.android.tradefed.util.Pair;
30 import com.android.tradefed.util.TableBuilder;
31 
32 import com.google.common.annotations.VisibleForTesting;
33 import com.google.common.collect.ImmutableSet;
34 import com.google.common.collect.Sets;
35 import com.google.common.primitives.Doubles;
36 
37 import java.io.File;
38 import java.io.IOException;
39 import java.util.ArrayList;
40 import java.util.HashSet;
41 import java.util.List;
42 import java.util.Random;
43 import java.util.Set;
44 import java.util.stream.Collectors;
45 
46 /** An algorithm to detect local metrics regression. */
47 @OptionClass(alias = "regression")
48 public class DetectRegression implements IRemoteTest {
49 
50     @Option(
51         name = "pre-patch-metrics",
52         description = "Path to pre-patch metrics folder.",
53         mandatory = true
54     )
55     private File mPrePatchFolder;
56 
57     @Option(
58         name = "post-patch-metrics",
59         description = "Path to post-patch metrics folder.",
60         mandatory = true
61     )
62     private File mPostPatchFolder;
63 
64     @Option(
65         name = "strict-mode",
66         description = "When before/after metrics mismatch, true=throw exception, false=log error"
67     )
68     private boolean mStrict = false;
69 
70     @Option(name = "blacklist-metrics", description = "Ignore metrics that match these names")
71     private Set<String> mBlacklistMetrics = new HashSet<>();
72 
73     private static final String TITLE = "Metric Regressions";
74     private static final String PROLOG =
75             "\n====================Metrics Comparison Results====================\nTest Summary\n";
76     private static final String EPILOG =
77             "==================End Metrics Comparison Results==================\n";
78     private static final String[] TABLE_HEADER = {
79         "Metric Name", "Pre Avg", "Post Avg", "False Positive Probability"
80     };
81     /** Matches metrics xml filenames. */
82     private static final String METRICS_PATTERN = "metrics-.*\\.xml";
83 
84     private static final int SAMPLES = 100000;
85     private static final double STD_DEV_THRESHOLD = 2.0;
86 
87     private static final Set<String> DEFAULT_IGNORE =
88             ImmutableSet.of(
89                     ModuleDefinition.PREPARATION_TIME,
90                     ModuleDefinition.TEST_TIME,
91                     ModuleDefinition.TEAR_DOWN_TIME);
92 
93     @VisibleForTesting
94     public static class TableRow {
95         String name;
96         double preAvg;
97         double postAvg;
98         double probability;
99 
toStringArray()100         public String[] toStringArray() {
101             return new String[] {
102                 name,
103                 String.format("%.2f", preAvg),
104                 String.format("%.2f", postAvg),
105                 String.format("%.3f", probability)
106             };
107         }
108     }
109 
DetectRegression()110     public DetectRegression() {
111         mBlacklistMetrics.addAll(DEFAULT_IGNORE);
112     }
113 
114     @Override
run(ITestInvocationListener listener)115     public void run(ITestInvocationListener listener) {
116         try {
117             // Load metrics from files, and validate them.
118             Metrics before =
119                     MetricsXmlParser.parse(
120                             mBlacklistMetrics, mStrict, getMetricsFiles(mPrePatchFolder));
121             Metrics after =
122                     MetricsXmlParser.parse(
123                             mBlacklistMetrics, mStrict, getMetricsFiles(mPostPatchFolder));
124             before.crossValidate(after);
125             runRegressionDetection(before, after);
126         } catch (IOException | ParseException e) {
127             throw new RuntimeException(e);
128         }
129     }
130 
131     /**
132      * Computes metrics regression between pre-patch and post-patch.
133      *
134      * @param before pre-patch metrics
135      * @param after post-patch metrics
136      */
137     @VisibleForTesting
runRegressionDetection(Metrics before, Metrics after)138     void runRegressionDetection(Metrics before, Metrics after) {
139         Set<String> runMetricsToCompare =
140                 Sets.intersection(before.getRunMetrics().keySet(), after.getRunMetrics().keySet());
141         List<TableRow> runMetricsResult = new ArrayList<>();
142         for (String name : runMetricsToCompare) {
143             List<Double> beforeMetrics = before.getRunMetrics().get(name);
144             List<Double> afterMetrics = after.getRunMetrics().get(name);
145             if (computeRegression(beforeMetrics, afterMetrics)) {
146                 runMetricsResult.add(getTableRow(name, beforeMetrics, afterMetrics));
147             }
148         }
149 
150         Set<Pair<TestDescription, String>> testMetricsToCompare =
151                 Sets.intersection(
152                         before.getTestMetrics().keySet(), after.getTestMetrics().keySet());
153         MultiMap<String, TableRow> testMetricsResult = new MultiMap<>();
154         for (Pair<TestDescription, String> id : testMetricsToCompare) {
155             List<Double> beforeMetrics = before.getTestMetrics().get(id);
156             List<Double> afterMetrics = after.getTestMetrics().get(id);
157             if (computeRegression(beforeMetrics, afterMetrics)) {
158                 testMetricsResult.put(
159                         id.first.toString(), getTableRow(id.second, beforeMetrics, afterMetrics));
160             }
161         }
162         logResult(before, after, runMetricsResult, testMetricsResult);
163     }
164 
165     /** Prints results to the console. */
166     @VisibleForTesting
logResult( Metrics before, Metrics after, List<TableRow> runMetricsResult, MultiMap<String, TableRow> testMetricsResult)167     void logResult(
168             Metrics before,
169             Metrics after,
170             List<TableRow> runMetricsResult,
171             MultiMap<String, TableRow> testMetricsResult) {
172         TableBuilder table = new TableBuilder(TABLE_HEADER.length);
173         table.addTitle(TITLE).addLine(TABLE_HEADER).addDoubleLineSeparator();
174 
175         int totalRunMetrics =
176                 Sets.intersection(before.getRunMetrics().keySet(), after.getRunMetrics().keySet())
177                         .size();
178         String runResult =
179                 String.format(
180                         "Run Metrics (%d compared, %d changed)",
181                         totalRunMetrics, runMetricsResult.size());
182         table.addLine(runResult).addSingleLineSeparator();
183         runMetricsResult.stream().map(TableRow::toStringArray).forEach(table::addLine);
184         if (!runMetricsResult.isEmpty()) {
185             table.addSingleLineSeparator();
186         }
187 
188         int totalTestMetrics =
189                 Sets.intersection(before.getTestMetrics().keySet(), after.getTestMetrics().keySet())
190                         .size();
191         int changedTestMetrics =
192                 testMetricsResult
193                         .keySet()
194                         .stream()
195                         .mapToInt(k -> testMetricsResult.get(k).size())
196                         .sum();
197         String testResult =
198                 String.format(
199                         "Test Metrics (%d compared, %d changed)",
200                         totalTestMetrics, changedTestMetrics);
201         table.addLine(testResult).addSingleLineSeparator();
202         for (String test : testMetricsResult.keySet()) {
203             table.addLine("> " + test);
204             testMetricsResult
205                     .get(test)
206                     .stream()
207                     .map(TableRow::toStringArray)
208                     .forEach(table::addLine);
209             table.addBlankLineSeparator();
210         }
211         table.addDoubleLineSeparator();
212 
213         StringBuilder sb = new StringBuilder(PROLOG);
214         sb.append(
215                 String.format(
216                         "%d tests. %d sets of pre-patch metrics. %d sets of post-patch metrics.\n\n",
217                         before.getNumTests(), before.getNumRuns(), after.getNumRuns()));
218         sb.append(table.build()).append('\n').append(EPILOG);
219 
220         CLog.logAndDisplay(Log.LogLevel.INFO, sb.toString());
221     }
222 
getMetricsFiles(File folder)223     private List<File> getMetricsFiles(File folder) throws IOException {
224         CLog.i("Loading metrics from: %s", mPrePatchFolder.getAbsolutePath());
225         return FileUtil.findFiles(folder, METRICS_PATTERN)
226                 .stream()
227                 .map(File::new)
228                 .collect(Collectors.toList());
229     }
230 
getTableRow(String name, List<Double> before, List<Double> after)231     private static TableRow getTableRow(String name, List<Double> before, List<Double> after) {
232         TableRow row = new TableRow();
233         row.name = name;
234         row.preAvg = calcMean(before);
235         row.postAvg = calcMean(after);
236         row.probability = probFalsePositive(before.size(), after.size());
237         return row;
238     }
239 
240     /** @return true if there is regression from before to after, false otherwise */
241     @VisibleForTesting
computeRegression(List<Double> before, List<Double> after)242     static boolean computeRegression(List<Double> before, List<Double> after) {
243         final double mean = calcMean(before);
244         final double stdDev = calcStdDev(before);
245         int regCount = 0;
246         for (double value : after) {
247             if (Math.abs(value - mean) > stdDev * STD_DEV_THRESHOLD) {
248                 regCount++;
249             }
250         }
251         return regCount > after.size() / 2;
252     }
253 
254     @VisibleForTesting
calcMean(List<Double> list)255     static double calcMean(List<Double> list) {
256         return list.stream().collect(Collectors.averagingDouble(x -> x));
257     }
258 
259     @VisibleForTesting
calcStdDev(List<Double> list)260     static double calcStdDev(List<Double> list) {
261         final double mean = calcMean(list);
262         return Math.sqrt(
263                 list.stream().collect(Collectors.averagingDouble(x -> Math.pow(x - mean, 2))));
264     }
265 
probFalsePositive(int priorRuns, int postRuns)266     private static double probFalsePositive(int priorRuns, int postRuns) {
267         int failures = 0;
268         Random rand = new Random();
269         for (int run = 0; run < SAMPLES; run++) {
270             double[] prior = new double[priorRuns];
271             for (int x = 0; x < priorRuns; x++) {
272                 prior[x] = rand.nextGaussian();
273             }
274             double estMu = calcMean(Doubles.asList(prior));
275             double estStd = calcStdDev(Doubles.asList(prior));
276             int count = 0;
277             for (int y = 0; y < postRuns; y++) {
278                 if (Math.abs(rand.nextGaussian() - estMu) > estStd * STD_DEV_THRESHOLD) {
279                     count++;
280                 }
281             }
282             failures += count > postRuns / 2 ? 1 : 0;
283         }
284         return (double) failures / SAMPLES;
285     }
286 }
287