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 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 111 public DetectRegression() { 112 mBlacklistMetrics.addAll(DEFAULT_IGNORE); 113 } 114 115 @Override 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 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 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 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 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 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 256 static double calcMean(List<Double> list) { 257 return list.stream().collect(Collectors.averagingDouble(x -> x)); 258 } 259 260 @VisibleForTesting 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 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
