Changeset 126374 in webkit

Timestamp:

Aug 22, 2012 6:08:25 PM (12 years ago)

Author:

dpranke@chromium.org

Message:

Baseline optimizer should try to optimize per-port if global optimization fails
​https://bugs.webkit.org/show_bug.cgi?id=94665

Reviewed by Adam Barth.

Add a fallback strategy for optimizing baselines if the default
one fails; this one simply attempts to shift baselines up in the
tree and consolidates them if a parent and child in the fallback
path have the same result. This strategy is somewhat flawed in
that we will always put something in a parent dir even if we
"shouldn't"; for example, if chromium-mac produces a different
result from chromium-win and chromium-linux, then the new
algorithm will move the mac result into platform/chromium,
leaving chromium-mac empty. This result is still correct, but
perhaps confusing.

I haven't done much testing of this algorithm yet, so it's not
clear how many cases where this does a better job than the
default algorithm and how many it'll do a worse job.

• Scripts/webkitpy/common/checkout/baselineoptimizer.py:

(BaselineOptimizer._find_optimal_result_placement):
(BaselineOptimizer._optimize_by_most_specific_common_directory):
(BaselineOptimizer):
(BaselineOptimizer._optimize_by_pushing_results_up):
(BaselineOptimizer._find_in_fallbackpath):

• Scripts/webkitpy/common/checkout/baselineoptimizer_unittest.py:

(BaselineOptimizerTest.test_platform_mac_different):

Location:

trunk/Tools

Files:

• ChangeLog (modified) (1 diff)
• Scripts/webkitpy/common/checkout/baselineoptimizer.py (modified) (3 diffs)
• Scripts/webkitpy/common/checkout/baselineoptimizer_unittest.py (modified) (1 diff)

trunk/Tools/ChangeLog

@@ +1 @@
+2012-08-22  Dirk Pranke  <dpranke@chromium.org>
+
+        Baseline optimizer should try to optimize per-port if global optimization fails
+        https://bugs.webkit.org/show_bug.cgi?id=94665
+
+        Reviewed by Adam Barth.
+
+        Add a fallback strategy for optimizing baselines if the default
+        one fails; this one simply attempts to shift baselines up in the
+        tree and consolidates them if a parent and child in the fallback
+        path have the same result. This strategy is somewhat flawed in
+        that we will always put something in a parent dir even if we
+        "shouldn't"; for example, if chromium-mac produces a different
+        result from chromium-win and chromium-linux, then the new
+        algorithm will move the mac result into platform/chromium,
+        leaving chromium-mac empty. This result is still correct, but
+        perhaps confusing.
+
+        I haven't done much testing of this algorithm yet, so it's not
+        clear how many cases where this does a better job than the
+        default algorithm and how many it'll do a worse job.
+
+        * Scripts/webkitpy/common/checkout/baselineoptimizer.py:
+        (BaselineOptimizer._find_optimal_result_placement):
+        (BaselineOptimizer._optimize_by_most_specific_common_directory):
+        (BaselineOptimizer):
+        (BaselineOptimizer._optimize_by_pushing_results_up):
+        (BaselineOptimizer._find_in_fallbackpath):
+        * Scripts/webkitpy/common/checkout/baselineoptimizer_unittest.py:
+        (BaselineOptimizerTest.test_platform_mac_different):
+
 2012-08-22  Dirk Pranke  <dpranke@chromium.org>
 

trunk/Tools/Scripts/webkitpy/common/checkout/baselineoptimizer.py

@@ -27 +27 @@
 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
+import copy
 import logging
 
@@ -126 +127 @@
         port_names_by_result = _invert_dictionary(results_by_port_name)
 
-        results_by_directory, new_results_by_directory = self._optimize_by_most_specific_common_directory(results_by_directory, results_by_port_name, port_names_by_result)
+        new_results_by_directory = self._optimize_by_most_specific_common_directory(results_by_directory, results_by_port_name, port_names_by_result)
         if not new_results_by_directory:
-            pass  # FIXME: Try something else.
+            new_results_by_directory = self._optimize_by_pushing_results_up(results_by_directory, results_by_port_name, port_names_by_result)
 
         return results_by_directory, new_results_by_directory
@@ -145 +146 @@
 
             if len(new_unsatisfied_port_names_by_result.values()) >= len(unsatisfied_port_names_by_result.values()):
-                break  # Frowns. We do not appear to be converging.
+                return {}  # Frowns. We do not appear to be converging.
             unsatisfied_port_names_by_result = new_unsatisfied_port_names_by_result
 
-        return results_by_directory, new_results_by_directory
+        return new_results_by_directory
+
+    def _optimize_by_pushing_results_up(self, results_by_directory, results_by_port_name, port_names_by_result):
+        results_by_directory = results_by_directory
+        best_so_far = results_by_directory
+        while True:
+            new_results_by_directory = copy.copy(best_so_far)
+            for port_name in self._hypergraph.keys():
+                fallback_path = self._hypergraph[port_name]
+                current_index, current_directory = self._find_in_fallbackpath(fallback_path, results_by_port_name[port_name], results_by_directory)
+                current_result = results_by_port_name[port_name]
+                for index in range(current_index + 1, len(fallback_path)):
+                    new_directory = fallback_path[index]
+                    if not new_directory in new_results_by_directory:
+                        new_results_by_directory[new_directory] = current_result
+                        if current_directory in new_results_by_directory:
+                            del new_results_by_directory[current_directory]
+                    elif new_results_by_directory[new_directory] == current_result:
+                        if current_directory in new_results_by_directory:
+                            del new_results_by_directory[current_directory]
+                    else:
+                        # The new_directory contains a different result, so stop trying to push results up.
+                        break
+
+            if len(new_results_by_directory) >= len(best_so_far):
+                # We've failed to improve, so give up.
+                break
+            best_so_far = new_results_by_directory
+
+        return best_so_far
+
+    def _find_in_fallbackpath(self, fallback_path, current_result, results_by_directory):
+        for index, directory in enumerate(fallback_path):
+            if directory in results_by_directory and (results_by_directory[directory] == current_result):
+                return index, directory
+        assert False, "result %s not found in fallback_path %s, %s" % (current_result, fallback_path, results_by_directory)
 
     def _filtered_results_by_port_name(self, results_by_directory):

trunk/Tools/Scripts/webkitpy/common/checkout/baselineoptimizer_unittest.py

@@ -75 +75 @@
         self.assertEqual(host.filesystem.read_binary_file('/mock-checkout/LayoutTests/platform/chromium/another/test-expected.txt'), 'result A')
 
-    def disabled_test_platform_mac_different(self):
+    def test_platform_mac_different(self):
         self._assertOptimization({
             'LayoutTests': '462d03b9c025db1b0392d7453310dbee5f9a9e74',