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

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

Index: Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py
diff --git a/Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py b/Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py
index afb63367b06e64a5ed4c0eeb7018aba8ee0c62c7..7a0ab9dc876b79fff234c694d662c9868474b45b 100644
--- a/Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py
+++ b/Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py
@@ -30,6 +30,8 @@
 for layout tests.
 """
 
+from collections import defaultdict
+
 import logging
 import re
 
@@ -562,10 +564,26 @@ class TestExpectationsModel(object):
     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)