1# Copyright (c) 2013 The Chromium OS 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"""Hill climbing unitest.
5
6Part of the Chrome build flags optimization.
7
8Test the best branching hill climbing algorithms, genetic algorithm and
9iterative elimination algorithm.
10"""
11
12__author__ = 'yuhenglong@google.com (Yuheng Long)'
13
14import multiprocessing
15import random
16import sys
17import unittest
18
19import flags
20from flags import Flag
21from flags import FlagSet
22from genetic_algorithm import GAGeneration
23from genetic_algorithm import GATask
24from hill_climb_best_neighbor import HillClimbingBestBranch
25from iterative_elimination import IterativeEliminationFirstGeneration
26import pipeline_process
27from steering import Steering
28from task import BUILD_STAGE
29from task import Task
30from task import TEST_STAGE
31
32# The number of flags be tested.
33NUM_FLAGS = 5
34
35# The value range of the flags.
36FLAG_RANGES = 10
37
38# The following variables are meta data for the Genetic Algorithm.
39STOP_THRESHOLD = 20
40NUM_CHROMOSOMES = 10
41NUM_TRIALS = 20
42MUTATION_RATE = 0.03
43
44
45def _GenerateRandomRasks(specs):
46  """Generate a task that has random values.
47
48  Args:
49    specs: A list of spec from which the flag set is created.
50
51  Returns:
52    A set containing a task that has random values.
53  """
54
55  flag_set = []
56
57  for spec in specs:
58    numeric_flag_match = flags.Search(spec)
59    if numeric_flag_match:
60      # Numeric flags.
61      start = int(numeric_flag_match.group('start'))
62      end = int(numeric_flag_match.group('end'))
63
64      value = random.randint(start - 1, end - 1)
65      if value != start - 1:
66        # If the value falls in the range, this flag is enabled.
67        flag_set.append(Flag(spec, value))
68    else:
69      # Boolean flags.
70      if random.randint(0, 1):
71        flag_set.append(Flag(spec))
72
73  return set([Task(FlagSet(flag_set))])
74
75
76def _GenerateAllFlagsTasks(specs):
77  """Generate a task that all the flags are enable.
78
79  All the boolean flags in the specs will be enabled and all the numeric flag
80  with have the largest legal value.
81
82  Args:
83    specs: A list of spec from which the flag set is created.
84
85  Returns:
86    A set containing a task that has all flags enabled.
87  """
88
89  flag_set = []
90
91  for spec in specs:
92    numeric_flag_match = flags.Search(spec)
93
94    if numeric_flag_match:
95      value = (int(numeric_flag_match.group('end')) - 1)
96    else:
97      value = -1
98    flag_set.append(Flag(spec, value))
99
100  return set([Task(FlagSet(flag_set))])
101
102
103def _GenerateNoFlagTask():
104  return set([Task(FlagSet([]))])
105
106
107def GenerateRandomGATasks(specs, num_tasks, num_trials):
108  """Generate a set of tasks for the Genetic Algorithm.
109
110  Args:
111    specs: A list of spec from which the flag set is created.
112    num_tasks: number of tasks that should be generated.
113    num_trials: the maximum number of tries should be attempted to generate the
114      set of tasks.
115
116  Returns:
117    A set of randomly generated tasks.
118  """
119
120  tasks = set([])
121
122  total_trials = 0
123  while len(tasks) < num_tasks and total_trials < num_trials:
124    new_flag = FlagSet([Flag(spec) for spec in specs if random.randint(0, 1)])
125    new_task = GATask(new_flag)
126
127    if new_task in tasks:
128      total_trials += 1
129    else:
130      tasks.add(new_task)
131      total_trials = 0
132
133  return tasks
134
135
136def _GenerateInitialFlags(specs, spec):
137  """Generate the flag_set of a task in the flag elimination algorithm.
138
139  Set the value of all the flags to the largest value, except for the flag that
140  contains spec.
141
142  For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing] and
143  the spec is -finline-limit=[1-1000], then the result is
144  [-finline-limit=[1-1000]:-finline-limit=998,
145   -fstrict-aliasing:-fstrict-aliasing]
146
147  Args:
148    specs: an array of specifications from which the result flag_set is created.
149      The flag_set contains one and only one flag that contain the specification
150      spec.
151    spec: The flag containing this spec should have a value that is smaller than
152      the highest value the flag can have.
153
154  Returns:
155    An array of flags, each of which contains one spec in specs. All the values
156    of the flags are the largest values in specs, expect the one that contains
157    spec.
158  """
159
160  flag_set = []
161  for other_spec in specs:
162    numeric_flag_match = flags.Search(other_spec)
163    # Found the spec in the array specs.
164    if other_spec == spec:
165      # Numeric flag will have a value that is smaller than the largest value
166      # and Boolean flag will be deleted.
167      if numeric_flag_match:
168        end = int(numeric_flag_match.group('end'))
169        flag_set.append(flags.Flag(other_spec, end - 2))
170
171      continue
172
173    # other_spec != spec
174    if numeric_flag_match:
175      # numeric flag
176      end = int(numeric_flag_match.group('end'))
177      flag_set.append(flags.Flag(other_spec, end - 1))
178      continue
179
180    # boolean flag
181    flag_set.append(flags.Flag(other_spec))
182
183  return flag_set
184
185
186def _GenerateAllIterativeEliminationTasks(specs):
187  """Generate the initial tasks for the negative flag elimination algorithm.
188
189  Generate the base line task that turns on all the boolean flags and sets the
190  value to be the largest value for the numeric flag.
191
192  For example, if the specs are [-finline-limit=[1-1000], -fstrict-aliasing],
193  the base line is [-finline-limit=[1-1000]:-finline-limit=999,
194  -fstrict-aliasing:-fstrict-aliasing]
195
196  Generate a set of task, each turns off one of the flag or sets a value that is
197  smaller than the largest value for the flag.
198
199  Args:
200    specs: an array of specifications from which the result flag_set is created.
201
202  Returns:
203    An array containing one generation of the initial tasks for the negative
204    flag elimination algorithm.
205  """
206
207  # The set of tasks to be generated.
208  results = set([])
209  flag_set = []
210
211  for spec in specs:
212    numeric_flag_match = flags.Search(spec)
213    if numeric_flag_match:
214      # Numeric flag.
215      end_value = int(numeric_flag_match.group('end'))
216      flag_set.append(flags.Flag(spec, end_value - 1))
217      continue
218
219    # Boolean flag.
220    flag_set.append(flags.Flag(spec))
221
222  # The base line task that set all the flags to their largest values.
223  parent_task = Task(flags.FlagSet(flag_set))
224  results.add(parent_task)
225
226  for spec in specs:
227    results.add(Task(flags.FlagSet(_GenerateInitialFlags(specs, spec))))
228
229  return [IterativeEliminationFirstGeneration(results, parent_task)]
230
231
232def _ComputeCost(cost_func, specs, flag_set):
233  """Compute the mock cost of the flag_set using the input cost function.
234
235  All the boolean flags in the specs will be enabled and all the numeric flag
236  with have the largest legal value.
237
238  Args:
239    cost_func: The cost function which is used to compute the mock cost of a
240      dictionary of flags.
241    specs: All the specs that are used in the algorithm. This is used to check
242      whether certain flag is disabled in the flag_set dictionary.
243    flag_set: a dictionary of the spec and flag pairs.
244
245  Returns:
246    The mock cost of the input dictionary of the flags.
247  """
248
249  values = []
250
251  for spec in specs:
252    # If a flag is enabled, its value is added. Otherwise a padding 0 is added.
253    values.append(flag_set[spec].GetValue() if spec in flag_set else 0)
254
255  # The cost function string can use the values array.
256  return eval(cost_func)
257
258
259def _GenerateTestFlags(num_flags, upper_bound, file_name):
260  """Generate a set of mock flags and write it to a configuration file.
261
262  Generate a set of mock flags
263
264  Args:
265    num_flags: Number of numeric flags to be generated.
266    upper_bound: The value of the upper bound of the range.
267    file_name: The configuration file name into which the mock flags are put.
268  """
269
270  with open(file_name, 'w') as output_file:
271    num_flags = int(num_flags)
272    upper_bound = int(upper_bound)
273    for i in range(num_flags):
274      output_file.write('%s=[1-%d]\n' % (i, upper_bound))
275
276
277def _TestAlgorithm(cost_func, specs, generations, best_result):
278  """Test the best result the algorithm should return.
279
280  Set up the framework, run the input algorithm and verify the result.
281
282  Args:
283    cost_func: The cost function which is used to compute the mock cost of a
284      dictionary of flags.
285    specs: All the specs that are used in the algorithm. This is used to check
286      whether certain flag is disabled in the flag_set dictionary.
287    generations: The initial generations to be evaluated.
288    best_result: The expected best result of the algorithm. If best_result is
289      -1, the algorithm may or may not return the best value. Therefore, no
290      assertion will be inserted.
291  """
292
293  # Set up the utilities to test the framework.
294  manager = multiprocessing.Manager()
295  input_queue = manager.Queue()
296  output_queue = manager.Queue()
297  pp_steer = multiprocessing.Process(
298      target=Steering,
299      args=(set(), generations, output_queue, input_queue))
300  pp_steer.start()
301
302  # The best result of the algorithm so far.
303  result = sys.maxint
304
305  while True:
306    task = input_queue.get()
307
308    # POISONPILL signal the ends of the algorithm.
309    if task == pipeline_process.POISONPILL:
310      break
311
312    task.SetResult(BUILD_STAGE, (0, 0, 0, 0, 0))
313
314    # Compute the mock cost for the task.
315    task_result = _ComputeCost(cost_func, specs, task.GetFlags())
316    task.SetResult(TEST_STAGE, task_result)
317
318    # If the mock result of the current task is the best so far, set this
319    # result to be the best result.
320    if task_result < result:
321      result = task_result
322
323    output_queue.put(task)
324
325  pp_steer.join()
326
327  # Only do this test when best_result is not -1.
328  if best_result != -1:
329    assert best_result == result
330
331
332class MockAlgorithmsTest(unittest.TestCase):
333  """This class mock tests different steering algorithms.
334
335  The steering algorithms are responsible for generating the next set of tasks
336  to run in each iteration. This class does a functional testing on the
337  algorithms. It mocks out the computation of the fitness function from the
338  build and test phases by letting the user define the fitness function.
339  """
340
341  def _GenerateFlagSpecifications(self):
342    """Generate the testing specifications."""
343
344    mock_test_file = 'scale_mock_test'
345    _GenerateTestFlags(NUM_FLAGS, FLAG_RANGES, mock_test_file)
346    return flags.ReadConf(mock_test_file)
347
348  def testBestHillClimb(self):
349    """Test the best hill climb algorithm.
350
351    Test whether it finds the best results as expected.
352    """
353
354    # Initiate the build/test command and the log directory.
355    Task.InitLogCommand(None, None, 'output')
356
357    # Generate the testing specs.
358    specs = self._GenerateFlagSpecifications()
359
360    # Generate the initial generations for a test whose cost function is the
361    # summation of the values of all the flags.
362    generation_tasks = _GenerateAllFlagsTasks(specs)
363    generations = [HillClimbingBestBranch(generation_tasks, set([]), specs)]
364
365    # Test the algorithm. The cost function is the summation of all the values
366    # of all the flags. Therefore, the best value is supposed to be 0, i.e.,
367    # when all the flags are disabled.
368    _TestAlgorithm('sum(values[0:len(values)])', specs, generations, 0)
369
370    # This test uses a cost function that is the negative of the previous cost
371    # function. Therefore, the best result should be found in task with all the
372    # flags enabled.
373    cost_function = 'sys.maxint - sum(values[0:len(values)])'
374    all_flags = list(generation_tasks)[0].GetFlags()
375    cost = _ComputeCost(cost_function, specs, all_flags)
376
377    # Generate the initial generations.
378    generation_tasks = _GenerateNoFlagTask()
379    generations = [HillClimbingBestBranch(generation_tasks, set([]), specs)]
380
381    # Test the algorithm. The cost function is negative of the summation of all
382    # the values of all the flags. Therefore, the best value is supposed to be
383    # 0, i.e., when all the flags are disabled.
384    _TestAlgorithm(cost_function, specs, generations, cost)
385
386  def testGeneticAlgorithm(self):
387    """Test the Genetic Algorithm.
388
389    Do a functional testing here and see how well it scales.
390    """
391
392    # Initiate the build/test command and the log directory.
393    Task.InitLogCommand(None, None, 'output')
394
395    # Generate the testing specs.
396    specs = self._GenerateFlagSpecifications()
397    # Initiate the build/test command and the log directory.
398    GAGeneration.InitMetaData(STOP_THRESHOLD, NUM_CHROMOSOMES, NUM_TRIALS,
399                              specs, MUTATION_RATE)
400
401    # Generate the initial generations.
402    generation_tasks = GenerateRandomGATasks(specs, NUM_CHROMOSOMES, NUM_TRIALS)
403    generations = [GAGeneration(generation_tasks, set([]), 0)]
404
405    # Test the algorithm.
406    _TestAlgorithm('sum(values[0:len(values)])', specs, generations, -1)
407    cost_func = 'sys.maxint - sum(values[0:len(values)])'
408    _TestAlgorithm(cost_func, specs, generations, -1)
409
410  def testIterativeElimination(self):
411    """Test the iterative elimination algorithm.
412
413    Test whether it finds the best results as expected.
414    """
415
416    # Initiate the build/test command and the log directory.
417    Task.InitLogCommand(None, None, 'output')
418
419    # Generate the testing specs.
420    specs = self._GenerateFlagSpecifications()
421
422    # Generate the initial generations. The generation contains the base line
423    # task that turns on all the flags and tasks that each turn off one of the
424    # flags.
425    generations = _GenerateAllIterativeEliminationTasks(specs)
426
427    # Test the algorithm. The cost function is the summation of all the values
428    # of all the flags. Therefore, the best value is supposed to be 0, i.e.,
429    # when all the flags are disabled.
430    _TestAlgorithm('sum(values[0:len(values)])', specs, generations, 0)
431
432    # This test uses a cost function that is the negative of the previous cost
433    # function. Therefore, the best result should be found in task with all the
434    # flags enabled.
435    all_flags_tasks = _GenerateAllFlagsTasks(specs)
436    cost_function = 'sys.maxint - sum(values[0:len(values)])'
437    # Compute the cost of the task that turns on all the flags.
438    all_flags = list(all_flags_tasks)[0].GetFlags()
439    cost = _ComputeCost(cost_function, specs, all_flags)
440
441    # Test the algorithm. The cost function is negative of the summation of all
442    # the values of all the flags. Therefore, the best value is supposed to be
443    # 0, i.e., when all the flags are disabled.
444    # The concrete type of the generation decides how the next generation will
445    # be generated.
446    _TestAlgorithm(cost_function, specs, generations, cost)
447
448
449if __name__ == '__main__':
450  unittest.main()
451