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 513 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)
 
+        # 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)
         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 = {}
@@ skipping 542 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)))