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