Home | History | Annotate | Download | only in bestflags 
      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 """A variation of the hill climbing algorithm.
      5 
      6 Part of the Chrome build flags optimization.
      7 
      8 This algorithm explores all the neighbors of the current task. If at least one
      9 neighbor gives better performance than the current task, it explores the best
     10 neighbor.
     11 """
     12 
     13 __author__ = 'yuhenglong (at] google.com (Yuheng Long)'
     14 
     15 from flags import FlagSet
     16 import flags_util
     17 from generation import Generation
     18 from task import Task
     19 
     20 
     21 class HillClimbingBestBranch(Generation):
     22   """A variation of the hill climbing algorithm.
     23 
     24   Given a task, it explores all its neighbors. Pick the best neighbor for the
     25   next iteration.
     26   """
     27 
     28   def __init__(self, exe_set, parents, specs):
     29     """Set up the tasks set of this generation.
     30 
     31     Args:
     32       exe_set: A set of tasks to be run.
     33       parents: A set of tasks to be used to check whether their neighbors have
     34         improved upon them.
     35       specs: A list of specs to explore. The spec specifies the flags that can
     36         be changed to find neighbors of a task.
     37     """
     38 
     39     Generation.__init__(self, exe_set, parents)
     40     self._specs = specs
     41 
     42     # This variable will be used, by the Next method, to generate the tasks for
     43     # the next iteration. This self._next_task contains the best task in the
     44     # current iteration and it will be set by the IsImproved method. The tasks
     45     # of the next iteration are the neighbor of self._next_task.
     46     self._next_task = None
     47 
     48   def IsImproved(self):
     49     """True if this generation has improvement over its parent generation.
     50 
     51     If this generation improves upon the previous generation, this method finds
     52     out the best task in this generation and sets it to _next_task for the
     53     method Next to use.
     54 
     55     Returns:
     56       True if the best neighbor improves upon the parent task.
     57     """
     58 
     59     # Find the best neighbor.
     60     best_task = None
     61     for task in self._exe_set:
     62       if not best_task or task.IsImproved(best_task):
     63         best_task = task
     64 
     65     if not best_task:
     66       return False
     67 
     68     # The first generation may not have parent generation.
     69     parents = list(self._candidate_pool)
     70     if parents:
     71       assert len(parents) == 1
     72       self._next_task = best_task
     73       # If the best neighbor improves upon the parent task.
     74       return best_task.IsImproved(parents[0])
     75 
     76     self._next_task = best_task
     77     return True
     78 
     79   def Next(self, cache):
     80     """Calculate the next generation.
     81 
     82     The best neighbor b of the current task is the parent of the next
     83     generation. The neighbors of b will be the set of tasks to be evaluated
     84     next.
     85 
     86     Args:
     87       cache: A set of tasks that have been generated before.
     88 
     89     Returns:
     90       A set of new generations.
     91     """
     92 
     93     # The best neighbor.
     94     current_task = self._next_task
     95     flag_set = current_task.GetFlags()
     96 
     97     # The neighbors of the best neighbor.
     98     children_tasks = set([])
     99     for spec in self._specs:
    100       for next_flag in flags_util.ClimbNext(flag_set.GetFlags(), spec):
    101         new_task = Task(FlagSet(next_flag.values()))
    102 
    103         if new_task not in cache:
    104           children_tasks.add(new_task)
    105 
    106     return [HillClimbingBestBranch(children_tasks, set([current_task]),
    107                                    self._specs)]
    108