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 641572f60c66de9f476288a77e651dcbadbbcdaa..ae3b853793c066aa13bf5eb83439b152abe8d3ea 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
 
@@ -563,9 +565,26 @@ class TestExpectationsModel(object):
     def merge_model(self, other):
         self._merge_test_map(self._test_to_expectations, other._test_to_expectations)
 
+        # This code is n^2 in the number of tests per line. Cache the output

[Dirk Pranke, 2015/06/15 22:50:59]

"This code" is a bit ambiguous. 

It's merge_expectation_lines() that is O((tests per line)^2) and hence really
expensive when a line contains a lot of tests (like it would with -i virtual). 

I would probably rework the comment to make that a bit clearer.

[ojan, 2015/06/17 17:16:53]

Done

+        # of merge_expectation_lines so that we only call that n^2 in the number
+        # of *lines*.
+        merge_lines_cache = defaultdict(dict)
+
         for test, line in other._test_to_expectation_line.items():
             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_line = self._test_to_expectation_line[test]
+
+                cached_line = None
+                if self_line in merge_lines_cache:
+                    cached_line = merge_lines_cache[self_line].get(line)
+
+                if cached_line:
+                    line = cached_line
+                else:
+                    new_line = TestExpectationLine.merge_expectation_lines(self_line, line, model_all_expectations=False)
+                    merge_lines_cache[self_line][line] = new_line
+                    line = new_line

[Dirk Pranke, 2015/06/15 22:50:59]

Can you rewrite lines 577-586 as:

if line not in merge_lines_cache[self_line]:
    merge_lines_cache[self_line][line] =
TestExpectationLine.merge_expectations_lines(
        self_line, line, model_all_expectations=False)
    
self._test_to_expectation_line[test] = merge_lines_cache[self_line][line]

? 

I would probably also rename 'line' to 'other_line'. The mix of 'self_line',
'line', 'new_line', 'cached_line' is fairly confusing; if we can reduce the
number of variables and make them all be single-assignment, that would probably
be helpful.

[ojan, 2015/06/17 17:16:53]

That's much better. I didn't do exactly this, but close.

+
             self._test_to_expectation_line[test] = line
 
         self._merge_dict_of_sets(self._expectation_to_tests, other._expectation_to_tests)