1// Copyright 2014 The Flutter Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5import 'dart:math' as math;
6
7import 'task_result.dart';
8
9const String kBenchmarkTypeKeyName = 'benchmark_type';
10const String kBenchmarkVersionKeyName = 'version';
11const String kLocalEngineKeyName = 'local_engine';
12const String kLocalEngineHostKeyName = 'local_engine_host';
13const String kTaskNameKeyName = 'task_name';
14const String kRunStartKeyName = 'run_start';
15const String kRunEndKeyName = 'run_end';
16const String kAResultsKeyName = 'default_results';
17const String kBResultsKeyName = 'local_engine_results';
18
19const String kBenchmarkResultsType = 'A/B summaries';
20const String kBenchmarkABVersion = '1.0';
21
22enum FieldJustification { LEFT, RIGHT, CENTER }
23
24/// Collects data from an A/B test and produces a summary for human evaluation.
25///
26/// See [printSummary] for more.
27class ABTest {
28 ABTest({required this.localEngine, required this.localEngineHost, required this.taskName})
29 : runStart = DateTime.now(),
30 _aResults = <String, List<double>>{},
31 _bResults = <String, List<double>>{};
32
33 ABTest.fromJsonMap(Map<String, dynamic> jsonResults)
34 : localEngine = jsonResults[kLocalEngineKeyName] as String,
35 localEngineHost = jsonResults[kLocalEngineHostKeyName] as String?,
36 taskName = jsonResults[kTaskNameKeyName] as String,
37 runStart = DateTime.parse(jsonResults[kRunStartKeyName] as String),
38 _runEnd = DateTime.parse(jsonResults[kRunEndKeyName] as String),
39 _aResults = _convertFrom(jsonResults[kAResultsKeyName] as Map<String, dynamic>),
40 _bResults = _convertFrom(jsonResults[kBResultsKeyName] as Map<String, dynamic>);
41
42 final String localEngine;
43 final String? localEngineHost;
44 final String taskName;
45 final DateTime runStart;
46 DateTime? _runEnd;
47 DateTime? get runEnd => _runEnd;
48
49 final Map<String, List<double>> _aResults;
50 final Map<String, List<double>> _bResults;
51
52 static Map<String, List<double>> _convertFrom(dynamic results) {
53 final Map<String, dynamic> resultMap = results as Map<String, dynamic>;
54 return <String, List<double>>{
55 for (final String key in resultMap.keys)
56 key: (resultMap[key] as List<dynamic>).cast<double>(),
57 };
58 }
59
60 /// Adds the result of a single A run of the benchmark.
61 ///
62 /// The result may contain multiple score keys.
63 ///
64 /// [result] is expected to be a serialization of [TaskResult].
65 void addAResult(TaskResult result) {
66 if (_runEnd != null) {
67 throw StateError('Cannot add results to ABTest after it is finalized');
68 }
69 _addResult(result, _aResults);
70 }
71
72 /// Adds the result of a single B run of the benchmark.
73 ///
74 /// The result may contain multiple score keys.
75 ///
76 /// [result] is expected to be a serialization of [TaskResult].
77 void addBResult(TaskResult result) {
78 if (_runEnd != null) {
79 throw StateError('Cannot add results to ABTest after it is finalized');
80 }
81 _addResult(result, _bResults);
82 }
83
84 void finalize() {
85 _runEnd = DateTime.now();
86 }
87
88 Map<String, dynamic> get jsonMap => <String, dynamic>{
89 kBenchmarkTypeKeyName: kBenchmarkResultsType,
90 kBenchmarkVersionKeyName: kBenchmarkABVersion,
91 kLocalEngineKeyName: localEngine,
92 if (localEngineHost != null) kLocalEngineHostKeyName: localEngineHost,
93 kTaskNameKeyName: taskName,
94 kRunStartKeyName: runStart.toIso8601String(),
95 kRunEndKeyName: runEnd!.toIso8601String(),
96 kAResultsKeyName: _aResults,
97 kBResultsKeyName: _bResults,
98 };
99
100 static void updateColumnLengths(List<int> lengths, List<String?> results) {
101 for (int column = 0; column < lengths.length; column++) {
102 if (results[column] != null) {
103 lengths[column] = math.max(lengths[column], results[column]?.length ?? 0);
104 }
105 }
106 }
107
108 static void formatResult(
109 StringBuffer buffer,
110 List<int> lengths,
111 List<FieldJustification> aligns,
112 List<String?> values,
113 ) {
114 for (int column = 0; column < lengths.length; column++) {
115 final int len = lengths[column];
116 String? value = values[column];
117 if (value == null) {
118 value = ''.padRight(len);
119 } else {
120 value = switch (aligns[column]) {
121 FieldJustification.LEFT => value.padRight(len),
122 FieldJustification.RIGHT => value.padLeft(len),
123 FieldJustification.CENTER => value.padLeft((len + value.length) ~/ 2).padRight(len),
124 };
125 }
126 if (column > 0) {
127 value = value.padLeft(len + 1);
128 }
129 buffer.write(value);
130 }
131 buffer.writeln();
132 }
133
134 /// Returns the summary as a tab-separated spreadsheet.
135 ///
136 /// This value can be copied straight to a Google Spreadsheet for further analysis.
137 String asciiSummary() {
138 final Map<String, _ScoreSummary> summariesA = _summarize(_aResults);
139 final Map<String, _ScoreSummary> summariesB = _summarize(_bResults);
140
141 final List<List<String?>> tableRows = <List<String?>>[
142 for (final String scoreKey in <String>{...summariesA.keys, ...summariesB.keys})
143 <String?>[
144 scoreKey,
145 summariesA[scoreKey]?.averageString,
146 summariesA[scoreKey]?.noiseString,
147 summariesB[scoreKey]?.averageString,
148 summariesB[scoreKey]?.noiseString,
149 summariesA[scoreKey]?.improvementOver(summariesB[scoreKey]),
150 ],
151 ];
152
153 final List<String> titles = <String>[
154 'Score',
155 'Average A',
156 '(noise)',
157 'Average B',
158 '(noise)',
159 'Speed-up',
160 ];
161 final List<FieldJustification> alignments = <FieldJustification>[
162 FieldJustification.LEFT,
163 FieldJustification.RIGHT,
164 FieldJustification.LEFT,
165 FieldJustification.RIGHT,
166 FieldJustification.LEFT,
167 FieldJustification.CENTER,
168 ];
169
170 final List<int> lengths = List<int>.filled(6, 0);
171 updateColumnLengths(lengths, titles);
172 for (final List<String?> row in tableRows) {
173 updateColumnLengths(lengths, row);
174 }
175
176 final StringBuffer buffer = StringBuffer();
177 formatResult(buffer, lengths, <FieldJustification>[
178 FieldJustification.CENTER,
179 ...alignments.skip(1),
180 ], titles);
181 for (final List<String?> row in tableRows) {
182 formatResult(buffer, lengths, alignments, row);
183 }
184
185 return buffer.toString();
186 }
187
188 /// Returns unprocessed data collected by the A/B test formatted as
189 /// a tab-separated spreadsheet.
190 String rawResults() {
191 final StringBuffer buffer = StringBuffer();
192 for (final String scoreKey in _allScoreKeys) {
193 buffer.writeln('$scoreKey:');
194 buffer.write(' A:\t');
195 if (_aResults.containsKey(scoreKey)) {
196 for (final double score in _aResults[scoreKey]!) {
197 buffer.write('${score.toStringAsFixed(2)}\t');
198 }
199 } else {
200 buffer.write('N/A');
201 }
202 buffer.writeln();
203
204 buffer.write(' B:\t');
205 if (_bResults.containsKey(scoreKey)) {
206 for (final double score in _bResults[scoreKey]!) {
207 buffer.write('${score.toStringAsFixed(2)}\t');
208 }
209 } else {
210 buffer.write('N/A');
211 }
212 buffer.writeln();
213 }
214 return buffer.toString();
215 }
216
217 Set<String> get _allScoreKeys => <String>{..._aResults.keys, ..._bResults.keys};
218
219 /// Returns the summary as a tab-separated spreadsheet.
220 ///
221 /// This value can be copied straight to a Google Spreadsheet for further analysis.
222 String printSummary() {
223 final Map<String, _ScoreSummary> summariesA = _summarize(_aResults);
224 final Map<String, _ScoreSummary> summariesB = _summarize(_bResults);
225
226 final StringBuffer buffer = StringBuffer(
227 'Score\tAverage A (noise)\tAverage B (noise)\tSpeed-up\n',
228 );
229
230 for (final String scoreKey in _allScoreKeys) {
231 final _ScoreSummary? summaryA = summariesA[scoreKey];
232 final _ScoreSummary? summaryB = summariesB[scoreKey];
233 buffer.write('$scoreKey\t');
234
235 if (summaryA != null) {
236 buffer.write('${summaryA.averageString} ${summaryA.noiseString}\t');
237 } else {
238 buffer.write('\t');
239 }
240
241 if (summaryB != null) {
242 buffer.write('${summaryB.averageString} ${summaryB.noiseString}\t');
243 } else {
244 buffer.write('\t');
245 }
246
247 if (summaryA != null && summaryB != null) {
248 buffer.write('${summaryA.improvementOver(summaryB)}\t');
249 }
250
251 buffer.writeln();
252 }
253
254 return buffer.toString();
255 }
256}
257
258class _ScoreSummary {
259 _ScoreSummary({required this.average, required this.noise});
260
261 /// Average (arithmetic mean) of a series of values collected by a benchmark.
262 final double average;
263
264 /// The noise (standard deviation divided by [average]) in the collected
265 /// values.
266 final double noise;
267
268 String get averageString => average.toStringAsFixed(2);
269 String get noiseString => '(${_ratioToPercent(noise)})';
270
271 String improvementOver(_ScoreSummary? other) {
272 return other == null ? '' : '${(average / other.average).toStringAsFixed(2)}x';
273 }
274}
275
276void _addResult(TaskResult result, Map<String, List<double>> results) {
277 for (final String scoreKey in result.benchmarkScoreKeys ?? <String>[]) {
278 final double score = (result.data![scoreKey] as num).toDouble();
279 results.putIfAbsent(scoreKey, () => <double>[]).add(score);
280 }
281}
282
283Map<String, _ScoreSummary> _summarize(Map<String, List<double>> results) {
284 return results.map<String, _ScoreSummary>((String scoreKey, List<double> values) {
285 final double average = _computeAverage(values);
286 return MapEntry<String, _ScoreSummary>(
287 scoreKey,
288 _ScoreSummary(
289 average: average,
290 // If the average is zero, the benchmark got the perfect score with no noise.
291 noise: average > 0 ? _computeStandardDeviationForPopulation(values) / average : 0.0,
292 ),
293 );
294 });
295}
296
297/// Computes the arithmetic mean (or average) of given [values].
298double _computeAverage(Iterable<double> values) {
299 final double sum = values.reduce((double a, double b) => a + b);
300 return sum / values.length;
301}
302
303/// Computes population standard deviation.
304///
305/// Unlike sample standard deviation, which divides by N - 1, this divides by N.
306///
307/// See also:
308///
309/// * https://en.wikipedia.org/wiki/Standard_deviation
310double _computeStandardDeviationForPopulation(Iterable<double> population) {
311 final double mean = _computeAverage(population);
312 final double sumOfSquaredDeltas = population.fold<double>(
313 0.0,
314 (double previous, num value) => previous += math.pow(value - mean, 2),
315 );
316 return math.sqrt(sumOfSquaredDeltas / population.length);
317}
318
319String _ratioToPercent(double value) {
320 return '${(value * 100).toStringAsFixed(2)}%';
321}
322