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