| # Copyright (c) 2013 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. |
| """Hill climbing unitest. |
| |
| Part of the Chrome build flags optimization. |
| |
| Test the best branching hill climbing algorithms, genetic algorithm and |
| iterative elimination algorithm. |
| """ |
| |
| __author__ = 'yuhenglong@google.com (Yuheng Long)' |
| |
| import multiprocessing |
| import random |
| import sys |
| import unittest |
| |
| import flags |
| from flags import Flag |
| from flags import FlagSet |
| from genetic_algorithm import GAGeneration |
| from genetic_algorithm import GATask |
| from hill_climb_best_neighbor import HillClimbingBestBranch |
| from iterative_elimination import IterativeEliminationFirstGeneration |
| import pipeline_process |
| from steering import Steering |
| from task import BUILD_STAGE |
| from task import Task |
| from task import TEST_STAGE |
| |
| # The number of flags be tested. |
| NUM_FLAGS = 5 |
| |
| # The value range of the flags. |
| FLAG_RANGES = 10 |
| |
| # The following variables are meta data for the Genetic Algorithm. |
| STOP_THRESHOLD = 20 |
| NUM_CHROMOSOMES = 10 |
| NUM_TRIALS = 20 |
| MUTATION_RATE = 0.03 |
| |
| |
| def _GenerateRandomRasks(specs): |
| """Generate a task that has random values. |
| |
| Args: |
| specs: A list of spec from which the flag set is created. |
| |
| Returns: |
| A set containing a task that has random values. |
| """ |
| |
| flag_set = [] |
| |
| for spec in specs: |
| numeric_flag_match = flags.Search(spec) |
| if numeric_flag_match: |
| # Numeric flags. |
| start = int(numeric_flag_match.group('start')) |
| end = int(numeric_flag_match.group('end')) |
| |
| value = random.randint(start - 1, end - 1) |
| if value != start - 1: |
| # If the value falls in the range, this flag is enabled. |
| flag_set.append(Flag(spec, value)) |
| else: |
| # Boolean flags. |
| if random.randint(0, 1): |
| flag_set.append(Flag(spec)) |
| |
| return set([Task(FlagSet(flag_set))]) |
| |
| |
| def _GenerateAllFlagsTasks(specs): |
| """Generate a task that all the flags are enable. |
| |
| All the boolean flags in the specs will be enabled and all the numeric flag |
| with have the largest legal value. |
| |
| Args: |
| specs: A list of spec from which the flag set is created. |
| |
| Returns: |
| A set containing a task that has all flags enabled. |
| """ |
| |
| flag_set = [] |
| |
| for spec in specs: |
| numeric_flag_match = flags.Search(spec) |
| |
| if numeric_flag_match: |
| value = (int(numeric_flag_match.group('end')) - 1) |
| else: |
| value = -1 |
| flag_set.append(Flag(spec, value)) |
| |
| return set([Task(FlagSet(flag_set))]) |
| |
| |
| def _GenerateNoFlagTask(): |
| return set([Task(FlagSet([]))]) |
| |
| |
| def GenerateRandomGATasks(specs, num_tasks, num_trials): |
| """Generate a set of tasks for the Genetic Algorithm. |
| |
| Args: |
| specs: A list of spec from which the flag set is created. |
| num_tasks: number of tasks that should be generated. |
| num_trials: the maximum number of tries should be attempted to generate the |
| set of tasks. |
| |
| Returns: |
| A set of randomly generated tasks. |
| """ |
| |
| tasks = set([]) |
| |
| total_trials = 0 |
| while len(tasks) < num_tasks and total_trials < num_trials: |
| new_flag = FlagSet([Flag(spec) for spec in specs if random.randint(0, 1)]) |
| new_task = GATask(new_flag) |
| |
| if new_task in tasks: |
| total_trials += 1 |
| else: |
| tasks.add(new_task) |
| total_trials = 0 |
| |
| return tasks |
| |
| |
| def _GenerateInitialFlags(specs, spec): |
| """Generate the flag_set of a task in the flag elimination algorithm. |
| |
| Set the value of all the flags to the largest value, except for the flag that |
| contains spec. |
| |
| For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing] and |
| the spec is -finline-limit=[1-1000], then the result is |
| [-finline-limit=[1-1000]:-finline-limit=998, |
| -fstrict-aliasing:-fstrict-aliasing] |
| |
| Args: |
| specs: an array of specifications from which the result flag_set is created. |
| The flag_set contains one and only one flag that contain the specification |
| spec. |
| spec: The flag containing this spec should have a value that is smaller than |
| the highest value the flag can have. |
| |
| Returns: |
| An array of flags, each of which contains one spec in specs. All the values |
| of the flags are the largest values in specs, expect the one that contains |
| spec. |
| """ |
| |
| flag_set = [] |
| for other_spec in specs: |
| numeric_flag_match = flags.Search(other_spec) |
| # Found the spec in the array specs. |
| if other_spec == spec: |
| # Numeric flag will have a value that is smaller than the largest value |
| # and Boolean flag will be deleted. |
| if numeric_flag_match: |
| end = int(numeric_flag_match.group('end')) |
| flag_set.append(flags.Flag(other_spec, end - 2)) |
| |
| continue |
| |
| # other_spec != spec |
| if numeric_flag_match: |
| # numeric flag |
| end = int(numeric_flag_match.group('end')) |
| flag_set.append(flags.Flag(other_spec, end - 1)) |
| continue |
| |
| # boolean flag |
| flag_set.append(flags.Flag(other_spec)) |
| |
| return flag_set |
| |
| |
| def _GenerateAllIterativeEliminationTasks(specs): |
| """Generate the initial tasks for the negative flag elimination algorithm. |
| |
| Generate the base line task that turns on all the boolean flags and sets the |
| value to be the largest value for the numeric flag. |
| |
| For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing], |
| the base line is [-finline-limit=[1-1000]:-finline-limit=999, |
| -fstrict-aliasing:-fstrict-aliasing] |
| |
| Generate a set of task, each turns off one of the flag or sets a value that is |
| smaller than the largest value for the flag. |
| |
| Args: |
| specs: an array of specifications from which the result flag_set is created. |
| |
| Returns: |
| An array containing one generation of the initial tasks for the negative |
| flag elimination algorithm. |
| """ |
| |
| # The set of tasks to be generated. |
| results = set([]) |
| flag_set = [] |
| |
| for spec in specs: |
| numeric_flag_match = flags.Search(spec) |
| if numeric_flag_match: |
| # Numeric flag. |
| end_value = int(numeric_flag_match.group('end')) |
| flag_set.append(flags.Flag(spec, end_value - 1)) |
| continue |
| |
| # Boolean flag. |
| flag_set.append(flags.Flag(spec)) |
| |
| # The base line task that set all the flags to their largest values. |
| parent_task = Task(flags.FlagSet(flag_set)) |
| results.add(parent_task) |
| |
| for spec in specs: |
| results.add(Task(flags.FlagSet(_GenerateInitialFlags(specs, spec)))) |
| |
| return [IterativeEliminationFirstGeneration(results, parent_task)] |
| |
| |
| def _ComputeCost(cost_func, specs, flag_set): |
| """Compute the mock cost of the flag_set using the input cost function. |
| |
| All the boolean flags in the specs will be enabled and all the numeric flag |
| with have the largest legal value. |
| |
| Args: |
| cost_func: The cost function which is used to compute the mock cost of a |
| dictionary of flags. |
| specs: All the specs that are used in the algorithm. This is used to check |
| whether certain flag is disabled in the flag_set dictionary. |
| flag_set: a dictionary of the spec and flag pairs. |
| |
| Returns: |
| The mock cost of the input dictionary of the flags. |
| """ |
| |
| values = [] |
| |
| for spec in specs: |
| # If a flag is enabled, its value is added. Otherwise a padding 0 is added. |
| values.append(flag_set[spec].GetValue() if spec in flag_set else 0) |
| |
| # The cost function string can use the values array. |
| return eval(cost_func) |
| |
| |
| def _GenerateTestFlags(num_flags, upper_bound, file_name): |
| """Generate a set of mock flags and write it to a configuration file. |
| |
| Generate a set of mock flags |
| |
| Args: |
| num_flags: Number of numeric flags to be generated. |
| upper_bound: The value of the upper bound of the range. |
| file_name: The configuration file name into which the mock flags are put. |
| """ |
| |
| with open(file_name, 'w') as output_file: |
| num_flags = int(num_flags) |
| upper_bound = int(upper_bound) |
| for i in range(num_flags): |
| output_file.write('%s=[1-%d]\n' % (i, upper_bound)) |
| |
| |
| def _TestAlgorithm(cost_func, specs, generations, best_result): |
| """Test the best result the algorithm should return. |
| |
| Set up the framework, run the input algorithm and verify the result. |
| |
| Args: |
| cost_func: The cost function which is used to compute the mock cost of a |
| dictionary of flags. |
| specs: All the specs that are used in the algorithm. This is used to check |
| whether certain flag is disabled in the flag_set dictionary. |
| generations: The initial generations to be evaluated. |
| best_result: The expected best result of the algorithm. If best_result is |
| -1, the algorithm may or may not return the best value. Therefore, no |
| assertion will be inserted. |
| """ |
| |
| # Set up the utilities to test the framework. |
| manager = multiprocessing.Manager() |
| input_queue = manager.Queue() |
| output_queue = manager.Queue() |
| pp_steer = multiprocessing.Process( |
| target=Steering, |
| args=(set(), generations, output_queue, input_queue)) |
| pp_steer.start() |
| |
| # The best result of the algorithm so far. |
| result = sys.maxint |
| |
| while True: |
| task = input_queue.get() |
| |
| # POISONPILL signal the ends of the algorithm. |
| if task == pipeline_process.POISONPILL: |
| break |
| |
| task.SetResult(BUILD_STAGE, (0, 0, 0, 0, 0)) |
| |
| # Compute the mock cost for the task. |
| task_result = _ComputeCost(cost_func, specs, task.GetFlags()) |
| task.SetResult(TEST_STAGE, task_result) |
| |
| # If the mock result of the current task is the best so far, set this |
| # result to be the best result. |
| if task_result < result: |
| result = task_result |
| |
| output_queue.put(task) |
| |
| pp_steer.join() |
| |
| # Only do this test when best_result is not -1. |
| if best_result != -1: |
| assert best_result == result |
| |
| |
| class MockAlgorithmsTest(unittest.TestCase): |
| """This class mock tests different steering algorithms. |
| |
| The steering algorithms are responsible for generating the next set of tasks |
| to run in each iteration. This class does a functional testing on the |
| algorithms. It mocks out the computation of the fitness function from the |
| build and test phases by letting the user define the fitness function. |
| """ |
| |
| def _GenerateFlagSpecifications(self): |
| """Generate the testing specifications.""" |
| |
| mock_test_file = 'scale_mock_test' |
| _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file) |
| return flags.ReadConf(mock_test_file) |
| |
| def testBestHillClimb(self): |
| """Test the best hill climb algorithm. |
| |
| Test whether it finds the best results as expected. |
| """ |
| |
| # Initiate the build/test command and the log directory. |
| Task.InitLogCommand(None, None, 'output') |
| |
| # Generate the testing specs. |
| specs = self._GenerateFlagSpecifications() |
| |
| # Generate the initial generations for a test whose cost function is the |
| # summation of the values of all the flags. |
| generation_tasks = _GenerateAllFlagsTasks(specs) |
| generations = [HillClimbingBestBranch(generation_tasks, set([]), specs)] |
| |
| # Test the algorithm. The cost function is the summation of all the values |
| # of all the flags. Therefore, the best value is supposed to be 0, i.e., |
| # when all the flags are disabled. |
| _TestAlgorithm('sum(values[0:len(values)])', specs, generations, 0) |
| |
| # This test uses a cost function that is the negative of the previous cost |
| # function. Therefore, the best result should be found in task with all the |
| # flags enabled. |
| cost_function = 'sys.maxint - sum(values[0:len(values)])' |
| all_flags = list(generation_tasks)[0].GetFlags() |
| cost = _ComputeCost(cost_function, specs, all_flags) |
| |
| # Generate the initial generations. |
| generation_tasks = _GenerateNoFlagTask() |
| generations = [HillClimbingBestBranch(generation_tasks, set([]), specs)] |
| |
| # Test the algorithm. The cost function is negative of the summation of all |
| # the values of all the flags. Therefore, the best value is supposed to be |
| # 0, i.e., when all the flags are disabled. |
| _TestAlgorithm(cost_function, specs, generations, cost) |
| |
| def testGeneticAlgorithm(self): |
| """Test the Genetic Algorithm. |
| |
| Do a functional testing here and see how well it scales. |
| """ |
| |
| # Initiate the build/test command and the log directory. |
| Task.InitLogCommand(None, None, 'output') |
| |
| # Generate the testing specs. |
| specs = self._GenerateFlagSpecifications() |
| # Initiate the build/test command and the log directory. |
| GAGeneration.InitMetaData(STOP_THRESHOLD, NUM_CHROMOSOMES, NUM_TRIALS, |
| specs, MUTATION_RATE) |
| |
| # Generate the initial generations. |
| generation_tasks = GenerateRandomGATasks(specs, NUM_CHROMOSOMES, NUM_TRIALS) |
| generations = [GAGeneration(generation_tasks, set([]), 0)] |
| |
| # Test the algorithm. |
| _TestAlgorithm('sum(values[0:len(values)])', specs, generations, -1) |
| cost_func = 'sys.maxint - sum(values[0:len(values)])' |
| _TestAlgorithm(cost_func, specs, generations, -1) |
| |
| def testIterativeElimination(self): |
| """Test the iterative elimination algorithm. |
| |
| Test whether it finds the best results as expected. |
| """ |
| |
| # Initiate the build/test command and the log directory. |
| Task.InitLogCommand(None, None, 'output') |
| |
| # Generate the testing specs. |
| specs = self._GenerateFlagSpecifications() |
| |
| # Generate the initial generations. The generation contains the base line |
| # task that turns on all the flags and tasks that each turn off one of the |
| # flags. |
| generations = _GenerateAllIterativeEliminationTasks(specs) |
| |
| # Test the algorithm. The cost function is the summation of all the values |
| # of all the flags. Therefore, the best value is supposed to be 0, i.e., |
| # when all the flags are disabled. |
| _TestAlgorithm('sum(values[0:len(values)])', specs, generations, 0) |
| |
| # This test uses a cost function that is the negative of the previous cost |
| # function. Therefore, the best result should be found in task with all the |
| # flags enabled. |
| all_flags_tasks = _GenerateAllFlagsTasks(specs) |
| cost_function = 'sys.maxint - sum(values[0:len(values)])' |
| # Compute the cost of the task that turns on all the flags. |
| all_flags = list(all_flags_tasks)[0].GetFlags() |
| cost = _ComputeCost(cost_function, specs, all_flags) |
| |
| # Test the algorithm. The cost function is negative of the summation of all |
| # the values of all the flags. Therefore, the best value is supposed to be |
| # 0, i.e., when all the flags are disabled. |
| # The concrete type of the generation decides how the next generation will |
| # be generated. |
| _TestAlgorithm(cost_function, specs, generations, cost) |
| |
| |
| if __name__ == '__main__': |
| unittest.main() |
