xref: /aosp_15_r20/external/toolchain-utils/bestflags/hill_climb_best_neighbor.py (revision 760c253c1ed00ce9abd48f8546f08516e57485fe) 
1# Copyright 2013 The ChromiumOS Authors
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
6Part of the Chrome build flags optimization.
7
8This algorithm explores all the neighbors of the current task. If at least one
9neighbor gives better performance than the current task, it explores the best
10neighbor.
11"""
12
13__author__ = "[email protected] (Yuheng Long)"
14
15from flags import FlagSet
16import flags_util
17from generation import Generation
18from task import Task
19
20
21class 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 [
107            HillClimbingBestBranch(
108                children_tasks, set([current_task]), self._specs
109            )
110        ]
111