user_activity: Added script to select the optimal benchmark set.
It generates all possible combinations of benchmark sets of a given size
and it computes for every set a metric. Three different metrics have been
used: function count, distance variation and score.
TEST=None
BUG=None
Change-Id: I4e4af9f46a3056cfbcdc9d89b2c1333650b41ccc
Reviewed-on: https://chrome-internal-review.googlesource.com/292435
Reviewed-by: George Burgess <gbiv@google.com>
Reviewed-by: Ting-Yuan Huang <laszio@google.com>
Reviewed-by: Evelina Dumitrescu <evelinad@google.com>
Tested-by: Evelina Dumitrescu <evelinad@google.com>
Reviewed-on: https://chromium-review.googlesource.com/435914
Commit-Ready: Luis Lozano <llozano@chromium.org>
Tested-by: Luis Lozano <llozano@chromium.org>
Reviewed-by: Luis Lozano <llozano@chromium.org>
diff --git a/user_activity_benchmarks/benchmark_metrics.py b/user_activity_benchmarks/benchmark_metrics.py
index ff029a8..0b82e96 100644
--- a/user_activity_benchmarks/benchmark_metrics.py
+++ b/user_activity_benchmarks/benchmark_metrics.py
@@ -3,7 +3,7 @@
# found in the LICENSE file.
"""Computes the metrics for functions, Chrome OS components and benchmarks."""
-import collections
+from collections import defaultdict
def ComputeDistanceForFunction(child_functions_statistics_sample,
@@ -17,6 +17,7 @@
child_functions_statistics_reference: A dict that has as a key the name of
a function and as a value the inclusive count fraction. The keys are
the child functions of a reference parent function.
+
Returns:
A float value representing the sum of inclusive count fraction
differences of pairs of common child functions. If a child function is
@@ -57,6 +58,7 @@
fraction of the reference function.
sample_fraction: A float value representing the inclusive count
fraction of the sample function.
+
Returns:
A float value representing the score of the function.
"""
@@ -77,17 +79,17 @@
function_metrics: A dict having as a key the name of the function and the
name of the file where it is declared concatenated by a ',', and as a
value a tuple containing the distance and the score metrics.
+
Returns:
A dict containing as a key the name of the group and as a value a tuple
with the group file path, the number of functions matching the group,
the cumulative and average score, cumulative and average distance of all
those functions.
"""
- function_groups_metrics = \
- collections.defaultdict(lambda : (0, 0.0, 0.0, 0.0, 0.0))
+ function_groups_metrics = defaultdict(lambda: (0, 0.0, 0.0, 0.0, 0.0))
for function_key, metric in function_metrics.iteritems():
- function, function_file = function_key.split(',')
+ _, function_file = function_key.split(',')
for group, common_path in cwp_function_groups:
if common_path not in function_file:
@@ -131,8 +133,174 @@
return function_count, distance_cum, distance_avg, score_cum, score_avg
-def ComputeMetricsForBenchmarkSet(benchmark_set_function_metrics,
- cwp_function_groups):
- """TODO(evelinad): Add the computation of the metrics for a set of benchmarks.
+def ComputeFunctionCountForBenchmarkSet(set_function_metrics, cwp_functions,
+ metric_string):
+ """Computes the function count metric pair for the benchmark set.
+
+ For the function count metric, we count the unique functions covered by the
+ set of benchmarks. We compute the fraction of unique functions out
+ of the amount of CWP functions given.
+
+ We compute also the same metric pair for every group from the keys of the
+ set_function_metrics dict.
+
+ Args:
+ set_function_metrics: A list of dicts having as a key the name of a group
+ and as value a list of functions that match the given group.
+ cwp_functions: A dict having as a key the name of the groups and as a value
+ the list of CWP functions that match an individual group.
+ metric_string: A tuple of strings that will be mapped to the tuple of metric
+ values in the returned function group dict. This is done for convenience
+ for the JSON output.
+
+ Returns:
+ A tuple with the metric pair and a dict with the group names and values
+ of the metric pair. The first value of the metric pair represents the
+ function count and the second value the function count fraction.
+ The dict has as a key the name of the group and as a value a dict that
+ maps the metric_string to the values of the metric pair of the group.
"""
- raise NotImplementedError()
+ cwp_functions_count = sum(len(functions)
+ for functions in cwp_functions.itervalues())
+ set_groups_functions = defaultdict(set)
+ for benchmark_function_metrics in set_function_metrics:
+ for group_name in benchmark_function_metrics:
+ set_groups_functions[group_name] |= \
+ set(benchmark_function_metrics[group_name])
+
+ set_groups_functions_count = {}
+ set_functions_count = 0
+ for group_name, functions \
+ in set_groups_functions.iteritems():
+ set_group_functions_count = len(functions)
+ if group_name in cwp_functions:
+ set_groups_functions_count[group_name] = {
+ metric_string[0]: set_group_functions_count,
+ metric_string[1]:
+ set_group_functions_count / float(len(cwp_functions[group_name]))}
+ else:
+ set_groups_functions_count[group_name] = \
+ {metric_string[0]: set_group_functions_count, metric_string[1]: 0.0}
+ set_functions_count += set_group_functions_count
+
+ set_functions_count_fraction = \
+ set_functions_count / float(cwp_functions_count)
+ return (set_functions_count, set_functions_count_fraction), \
+ set_groups_functions_count
+
+
+def ComputeDistanceForBenchmarkSet(set_function_metrics, cwp_functions,
+ metric_string):
+ """Computes the distance variation metric pair for the benchmark set.
+
+ For the distance variation metric, we compute the sum of the distance
+ variations of the functions covered by a set of benchmarks.
+ We define the distance variation as the difference between the distance
+ value of a functions and the ideal distance value (1.0).
+ If a function appears in multiple common functions files, we consider
+ only the minimum value. We compute also the distance variation per
+ function.
+
+ In addition, we compute also the same metric pair for every group from
+ the keys of the set_function_metrics dict.
+
+ Args:
+ set_function_metrics: A list of dicts having as a key the name of a group
+ and as value a list of functions that match the given group.
+ cwp_functions: A dict having as a key the name of the groups and as a value
+ the list of CWP functions that match an individual group.
+ metric_string: A tuple of strings that will be mapped to the tuple of metric
+ values in the returned function group dict. This is done for convenience
+ for the JSON output.
+
+ Returns:
+ A tuple with the metric pair and a dict with the group names and values
+ of the metric pair. The first value of the metric pair represents the
+ distance variation per function and the second value the distance variation.
+ The dict has as a key the name of the group and as a value a dict that
+ maps the metric_string to the values of the metric pair of the group.
+ """
+ set_unique_functions = defaultdict(lambda: defaultdict(lambda: float('inf')))
+ set_function_count = 0
+ total_distance_variation = 0.0
+ for benchmark_function_metrics in set_function_metrics:
+ for group_name in benchmark_function_metrics:
+ for function_key, metrics in \
+ benchmark_function_metrics[group_name].iteritems():
+ previous_distance = \
+ set_unique_functions[group_name][function_key]
+ min_distance = min(metrics[0], previous_distance)
+ set_unique_functions[group_name][function_key] = min_distance
+ groups_distance_variations = defaultdict(lambda: (0.0, 0.0))
+ for group_name, functions_distances in set_unique_functions.iteritems():
+ group_function_count = len(functions_distances)
+ group_distance_variation = \
+ sum(functions_distances.itervalues()) - float(group_function_count)
+ total_distance_variation += group_distance_variation
+ set_function_count += group_function_count
+ groups_distance_variations[group_name] = \
+ {metric_string[0]:
+ group_distance_variation / float(group_function_count),
+ metric_string[1]: group_distance_variation}
+
+ return (total_distance_variation / set_function_count,
+ total_distance_variation), groups_distance_variations
+
+
+def ComputeScoreForBenchmarkSet(set_function_metrics, cwp_functions,
+ metric_string):
+ """Computes the function count metric pair for the benchmark set.
+
+ For the score metric, we compute the sum of the scores of the functions
+ from a set of benchmarks. If a function appears in multiple common
+ functions files, we consider only the maximum value. We compute also the
+ fraction of this sum from the sum of all the scores of the functions from
+ the CWP data covering the given groups, in the ideal case (the ideal
+ score of a function is 1.0).
+
+ In addition, we compute the same metric pair for every group from the
+ keys of the set_function_metrics dict.
+
+ Args:
+ set_function_metrics: A list of dicts having as a key the name of a group
+ and as value a list of functions that match the given group.
+ cwp_functions: A dict having as a key the name of the groups and as a value
+ the list of CWP functions that match an individual group.
+ metric_string: A tuple of strings that will be mapped to the tuple of metric
+ values in the returned function group dict. This is done for convenience
+ for the JSON output.
+
+ Returns:
+ A tuple with the metric pair and a dict with the group names and values
+ of the metric pair. The first value of the pair is the fraction of the sum
+ of the scores from the ideal case and the second value represents the
+ sum of scores of the functions. The dict has as a key the name of the group
+ and as a value a dict that maps the metric_string to the values of the
+ metric pair of the group.
+ """
+ cwp_functions_count = sum(len(functions)
+ for functions in cwp_functions.itervalues())
+ set_unique_functions = defaultdict(lambda: defaultdict(lambda: 0.0))
+ total_score = 0.0
+
+ for benchmark_function_metrics in set_function_metrics:
+ for group_name in benchmark_function_metrics:
+ for function_key, metrics in \
+ benchmark_function_metrics[group_name].iteritems():
+ previous_score = \
+ set_unique_functions[group_name][function_key]
+ max_score = max(metrics[1], previous_score)
+ set_unique_functions[group_name][function_key] = max_score
+
+ groups_scores = defaultdict(lambda: (0.0, 0.0))
+
+ for group_name, function_scores in set_unique_functions.iteritems():
+ group_function_count = len(function_scores)
+ group_score = sum(function_scores.itervalues())
+ total_score += group_score
+ groups_scores[group_name] = {
+ metric_string[0]: group_score / group_function_count,
+ metric_string[1]: group_score
+ }
+
+ return (total_score / cwp_functions_count, total_score), groups_scores
diff --git a/user_activity_benchmarks/select_optimal_benchmark_set.py b/user_activity_benchmarks/select_optimal_benchmark_set.py
new file mode 100755
index 0000000..1c8305c
--- /dev/null
+++ b/user_activity_benchmarks/select_optimal_benchmark_set.py
@@ -0,0 +1,347 @@
+#!/usr/bin/python2
+
+# Copyright 2016 The Chromium OS Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+"""Selects the optimal set of benchmarks.
+
+For each benchmark, there is a file with the common functions, as extracted by
+the process_hot_functions module.
+
+The script receives as input the CSV file with the CWP inclusive count values,
+the file with Chrome OS groups and the path containing a file with common
+functions for every benchmark.
+
+It extracts for every benchmark and for the CWP data all the functions that
+match the given Chrome OS groups.
+
+It generates all possible combinations of benchmark sets of a given size and
+it computes for every set a metric.
+It outputs the optimal sets, based on which ones have the best metric.
+
+Three different metrics have been used: function count, distance
+variation and score.
+
+For the function count metric, we count the unique functions covered by a
+set of benchmarks. Besides the number of unique functions, we compute also
+the fraction of unique functions out of the amount of CWP functions from the
+given groups. The benchmark set with the highest amount of unique functions
+that belong to all the given groups is considered better.
+
+For the distance variation metric, we compute the sum of the distance variations
+of the functions covered by a set of benchmarks. We define the distance
+variation as the difference between the distance value of a function and the
+ideal distance value (1.0). If a function appears in multiple common functions
+files, we consider only the minimum value. We compute also the distance
+variation per function. The set that has the smaller value for the
+distance variation per function is considered better.
+
+For the score metric, we compute the sum of the scores of the functions from a
+set of benchmarks. If a function appears in multiple common functions files,
+we consider only the maximum value. We compute also the fraction of this sum
+from the sum of all the scores of the functions from the CWP data covering the
+given groups, in the ideal case (the ideal score of a function is 1.0).
+
+We compute the metrics in the same manner for individual Chrome OS groups.
+"""
+
+from collections import defaultdict
+
+import argparse
+import csv
+import itertools
+import json
+import operator
+import os
+import sys
+
+import benchmark_metrics
+import utils
+
+
+class BenchmarkSet(object):
+ """Selects the optimal set of benchmarks of given size."""
+
+ # Constants that specify the metric type.
+ FUNCTION_COUNT_METRIC = 'function_count'
+ DISTANCE_METRIC = 'distance_variation'
+ SCORE_METRIC = 'score_fraction'
+
+ def __init__(self, benchmark_set_size, benchmark_set_output_file,
+ benchmark_set_common_functions_path, cwp_inclusive_count_file,
+ cwp_function_groups_file, metric):
+ """Initializes the BenchmarkSet.
+
+ Args:
+ benchmark_set_size: Constant representing the size of a benchmark set.
+ benchmark_set_output_file: The output file that will contain the set of
+ optimal benchmarks with the metric values.
+ benchmark_set_common_functions_path: The directory containing the files
+ with the common functions for the list of benchmarks.
+ cwp_inclusive_count_file: The CSV file containing the CWP functions with
+ their inclusive count values.
+ cwp_function_groups_file: The file that contains the CWP function groups.
+ metric: The type of metric used for the analysis.
+ """
+ self._benchmark_set_size = int(benchmark_set_size)
+ self._benchmark_set_output_file = benchmark_set_output_file
+ self._benchmark_set_common_functions_path = \
+ benchmark_set_common_functions_path
+ self._cwp_inclusive_count_file = cwp_inclusive_count_file
+ self._cwp_function_groups_file = cwp_function_groups_file
+ self._metric = metric
+
+ @staticmethod
+ def OrganizeCWPFunctionsInGroups(cwp_inclusive_count_statistics,
+ cwp_function_groups):
+ """Selects the CWP functions that match the given Chrome OS groups.
+
+ Args:
+ cwp_inclusive_count_statistics: A dict with the CWP functions.
+ cwp_function_groups: A list with the CWP function groups.
+
+ Returns:
+ A dict having as a key the name of the groups and as a value the list of
+ CWP functions that match an individual group.
+ """
+ cwp_functions_grouped = defaultdict(list)
+ for function_key in cwp_inclusive_count_statistics:
+ _, file_name = function_key.split(',')
+ for group_name, file_path in cwp_function_groups:
+ if file_path not in file_name:
+ continue
+ cwp_functions_grouped[group_name].append(function_key)
+ break
+ return cwp_functions_grouped
+
+ @staticmethod
+ def OrganizeBenchmarkSetFunctionsInGroups(benchmark_set_files,
+ benchmark_set_common_functions_path,
+ cwp_function_groups):
+ """Selects the benchmark functions that match the given Chrome OS groups.
+
+ Args:
+ benchmark_set_files: The list of common functions files corresponding to a
+ benchmark.
+ benchmark_set_common_functions_path: The directory containing the files
+ with the common functions for the list of benchmarks.
+ cwp_function_groups: A list with the CWP function groups.
+
+ Returns:
+ A dict having as a key the name of a common functions file. The value is
+ a dict having as a key the name of a group and as value a list of
+ functions that match the given group.
+ """
+
+ benchmark_set_functions_grouped = {}
+ for benchmark_file_name in benchmark_set_files:
+ benchmark_full_file_path = \
+ os.path.join(benchmark_set_common_functions_path,
+ benchmark_file_name)
+ with open(benchmark_full_file_path) as input_file:
+ statistics_reader = \
+ csv.DictReader(input_file, delimiter=',')
+ benchmark_functions_grouped = defaultdict(dict)
+ for statistic in statistics_reader:
+ function_name = statistic['function']
+ file_name = statistic['file']
+ for group_name, file_path in cwp_function_groups:
+ if file_path not in file_name:
+ continue
+ function_key = ','.join([function_name, file_name])
+ distance = float(statistic['distance'])
+ score = float(statistic['score'])
+ benchmark_functions_grouped[group_name][function_key] = \
+ (distance, score)
+ break
+ benchmark_set_functions_grouped[benchmark_file_name] = \
+ benchmark_functions_grouped
+ return benchmark_set_functions_grouped
+
+ @staticmethod
+ def SelectOptimalBenchmarkSetBasedOnMetric(all_benchmark_combinations_sets,
+ benchmark_set_functions_grouped,
+ cwp_functions_grouped,
+ metric_function_for_set,
+ metric_comparison_operator,
+ metric_default_value,
+ metric_string):
+ """Generic method that selects the optimal benchmark set based on a metric.
+
+ The reason of implementing a generic function is to avoid logic duplication
+ for selecting a benchmark set based on the three different metrics.
+
+ Args:
+ all_benchmark_combinations_sets: The list with all the sets of benchmark
+ combinations.
+ benchmark_set_functions_grouped: A dict with benchmark functions as
+ returned by OrganizeBenchmarkSetFunctionsInGroups.
+ cwp_functions_grouped: A dict with the CWP functions as returned by
+ OrganizeCWPFunctionsInGroups.
+ metric_function_for_set: The method used to compute the metric for a given
+ benchmark set.
+ metric_comparison_operator: A comparison operator used to compare two
+ values of the same metric (i.e: operator.lt or operator.gt).
+ metric_default_value: The default value for the metric.
+ metric_string: A tuple of strings used in the JSON output for the pair of
+ the values of the metric.
+
+ Returns:
+ A list of tuples containing for each optimal benchmark set. A tuple
+ contains the list of benchmarks from the set, the pair of metric values
+ and a dictionary with the metrics for each group.
+ """
+ optimal_sets = [([], metric_default_value, {})]
+
+ for benchmark_combination_set in all_benchmark_combinations_sets:
+ function_metrics = [benchmark_set_functions_grouped[benchmark]
+ for benchmark in benchmark_combination_set]
+ set_metrics, set_groups_metrics = \
+ metric_function_for_set(function_metrics, cwp_functions_grouped,
+ metric_string)
+ optimal_value = optimal_sets[0][1][0]
+ if metric_comparison_operator(set_metrics[0], optimal_value):
+ optimal_sets = \
+ [(benchmark_combination_set, set_metrics, set_groups_metrics)]
+ elif set_metrics[0] == optimal_sets[0][1][0]:
+ optimal_sets.append(
+ (benchmark_combination_set, set_metrics, set_groups_metrics))
+
+ return optimal_sets
+
+ def SelectOptimalBenchmarkSet(self):
+ """Selects the optimal benchmark sets and writes them in JSON format.
+
+ Parses the CWP inclusive count statistics and benchmark common functions
+ files. Organizes the functions into groups. For every optimal benchmark
+ set, the method writes in the self._benchmark_set_output_file the list of
+ benchmarks, the pair of metrics and a dictionary with the pair of
+ metrics for each group covered by the benchmark set.
+ """
+
+ benchmark_set_files = os.listdir(self._benchmark_set_common_functions_path)
+ all_benchmark_combinations_sets = \
+ itertools.combinations(benchmark_set_files, self._benchmark_set_size)
+
+ with open(self._cwp_function_groups_file) as input_file:
+ cwp_function_groups = utils.ParseFunctionGroups(input_file.readlines())
+
+ cwp_inclusive_count_statistics = \
+ utils.ParseCWPInclusiveCountFile(self._cwp_inclusive_count_file)
+ cwp_functions_grouped = self.OrganizeCWPFunctionsInGroups(
+ cwp_inclusive_count_statistics, cwp_function_groups)
+ benchmark_set_functions_grouped = \
+ self.OrganizeBenchmarkSetFunctionsInGroups(
+ benchmark_set_files, self._benchmark_set_common_functions_path,
+ cwp_function_groups)
+
+ if self._metric == self.FUNCTION_COUNT_METRIC:
+ metric_function_for_benchmark_set = \
+ benchmark_metrics.ComputeFunctionCountForBenchmarkSet
+ metric_comparison_operator = operator.gt
+ metric_default_value = (0, 0.0)
+ metric_string = ('function_count', 'function_count_fraction')
+ elif self._metric == self.DISTANCE_METRIC:
+ metric_function_for_benchmark_set = \
+ benchmark_metrics.ComputeDistanceForBenchmarkSet
+ metric_comparison_operator = operator.lt
+ metric_default_value = (float('inf'), float('inf'))
+ metric_string = \
+ ('distance_variation_per_function', 'total_distance_variation')
+ elif self._metric == self.SCORE_METRIC:
+ metric_function_for_benchmark_set = \
+ benchmark_metrics.ComputeScoreForBenchmarkSet
+ metric_comparison_operator = operator.gt
+ metric_default_value = (0.0, 0.0)
+ metric_string = ('score_fraction', 'total_score')
+ else:
+ raise ValueError("Invalid metric")
+
+ optimal_benchmark_sets = \
+ self.SelectOptimalBenchmarkSetBasedOnMetric(
+ all_benchmark_combinations_sets, benchmark_set_functions_grouped,
+ cwp_functions_grouped, metric_function_for_benchmark_set,
+ metric_comparison_operator, metric_default_value, metric_string)
+
+ json_output = []
+
+ for benchmark_set in optimal_benchmark_sets:
+ json_entry = {
+ 'benchmark_set':
+ list(benchmark_set[0]),
+ 'metrics': {
+ metric_string[0]: benchmark_set[1][0],
+ metric_string[1]: benchmark_set[1][1]
+ },
+ 'groups':
+ dict(benchmark_set[2])
+ }
+ json_output.append(json_entry)
+
+ with open(self._benchmark_set_output_file, 'w') as output_file:
+ json.dump(json_output, output_file)
+
+
+def ParseArguments(arguments):
+ parser = argparse.ArgumentParser()
+
+ parser.add_argument(
+ '--benchmark_set_common_functions_path',
+ required=True,
+ help='The directory containing the CSV files with the common functions '
+ 'of the benchmark profiles and CWP data. A file will contain all the hot '
+ 'functions from a pprof top output file that are also included in the '
+ 'file containing the cwp inclusive count values. The CSV fields are: the '
+ 'function name, the file and the object where the function is declared, '
+ 'the CWP inclusive count and inclusive count fraction values, the '
+ 'cumulative and average distance, the cumulative and average score. The '
+ 'files with the common functions will have the same names with the '
+ 'corresponding pprof output files.')
+ parser.add_argument(
+ '--cwp_inclusive_count_file',
+ required=True,
+ help='The CSV file containing the CWP hot functions with their '
+ 'inclusive_count values. The CSV fields include the name of the '
+ 'function, the file and the object with the definition, the inclusive '
+ 'count value and the inclusive count fraction out of the total amount of '
+ 'inclusive count values.')
+ parser.add_argument(
+ '--benchmark_set_size',
+ required=True,
+ help='The size of the benchmark sets.')
+ parser.add_argument(
+ '--benchmark_set_output_file',
+ required=True,
+ help='The JSON output file containing optimal benchmark sets with their '
+ 'metrics. For every optimal benchmark set, the file contains the list of '
+ 'benchmarks, the pair of metrics and a dictionary with the pair of '
+ 'metrics for each group covered by the benchmark set.')
+ parser.add_argument(
+ '--metric',
+ required=True,
+ help='The metric used to select the optimal benchmark set. The possible '
+ 'values are: distance_variation, function_count and score_fraction.')
+ parser.add_argument(
+ '--cwp_function_groups_file',
+ required=True,
+ help='The file that contains the CWP function groups. A line consists in '
+ 'the group name and a file path describing the group. A group must '
+ 'represent a Chrome OS component.')
+
+ options = parser.parse_args(arguments)
+
+ return options
+
+
+def Main(argv):
+ options = ParseArguments(argv)
+ benchmark_set = BenchmarkSet(options.benchmark_set_size,
+ options.benchmark_set_output_file,
+ options.benchmark_set_common_functions_path,
+ options.cwp_inclusive_count_file,
+ options.cwp_function_groups_file, options.metric)
+ benchmark_set.SelectOptimalBenchmarkSet()
+
+
+if __name__ == '__main__':
+ Main(sys.argv[1:])
