Parsing expectations is n^2 in the number of tests per line.

Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py

 # Copyright (C) 2010 Google Inc. All rights reserved.
 #
 # Redistribution and use in source and binary forms, with or without
 # modification, are permitted provided that the following conditions are
 # met:
 #
 #     * Redistributions of source code must retain the above copyright
 # notice, this list of conditions and the following disclaimer.
 #     * Redistributions in binary form must reproduce the above
 # copyright notice, this list of conditions and the following disclaimer
@@ skipping 12 matching lines @@
 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 """A helper class for reading in and dealing with tests expectations
 for layout tests.
 """
 
+from collections import defaultdict
+
 import logging
 import re
 
 from webkitpy.layout_tests.models.test_configuration import TestConfigurationConverter
 
 _log = logging.getLogger(__name__)
 
 
 # Test expectation and specifier constants.
 #
@@ skipping 512 matching lines @@
                 new_expectations |= set(self_map[test])
             self_map[test] = list(new_expectations) if isinstance(other_map[test], list) else new_expectations
 
     def _merge_dict_of_sets(self, self_dict, other_dict):
         for key in other_dict:
             self_dict[key] |= other_dict[key]
 
     def merge_model(self, other):
         self._merge_test_map(self._test_to_expectations, other._test_to_expectations)
 
-        for test, line in other._test_to_expectation_line.items():
+        # merge_expectation_lines is O(tests per line). Therefore, this loop
+        # is O((tests per line)^2) which is really expensive when a line
+        # contains a lot of tests. Cache the output of merge_expectation_lines
+        # so that we only call that n^2 in the number of *lines*.
+        merge_lines_cache = defaultdict(dict)
+
+        for test, other_line in other._test_to_expectation_line.items():
+            merged_line = None
             if test in self._test_to_expectation_line:
-                line = TestExpectationLine.merge_expectation_lines(self._test_to_expectation_line[test], line, model_all_expectations=False)
-            self._test_to_expectation_line[test] = line
+                self_line = self._test_to_expectation_line[test]
+
+                if other_line not in merge_lines_cache[self_line]:
+                    merge_lines_cache[self_line][other_line] = TestExpectationLine.merge_expectation_lines(
+                        self_line, other_line, model_all_expectations=False)
+
+                merged_line = merge_lines_cache[self_line][other_line]
+            else:
+                merged_line = other_line
+
+            self._test_to_expectation_line[test] = merged_line
 
         self._merge_dict_of_sets(self._expectation_to_tests, other._expectation_to_tests)
         self._merge_dict_of_sets(self._timeline_to_tests, other._timeline_to_tests)
         self._merge_dict_of_sets(self._result_type_to_tests, other._result_type_to_tests)
 
     def _dict_of_sets(self, strings_to_constants):
         """Takes a dict of strings->constants and returns a dict mapping
         each constant to an empty set."""
         d = {}
         for c in strings_to_constants.values():
@@ skipping 541 matching lines @@
             # If reconstitute_only_these is an empty list, we want to return original_string.
             # So we need to compare reconstitute_only_these to None, not just check if it's falsey.
             if reconstitute_only_these is None or expectation_line in reconstitute_only_these:
                 return expectation_line.to_string(test_configuration_converter)
             return expectation_line.original_string
 
         def nones_out(expectation_line):
             return expectation_line is not None
 
         return "\n".join(filter(nones_out, map(serialize, expectation_lines)))