Chromium Code Reviews
|
|
DescriptionParsing expectations is n^2 in the number of tests per line.
When merging expectations in different expectations files, we
do an n^2 operation. For each line/test combination, we merge
them. Instead, this algorithm only needs to merge a given
pair of lines once.
Add a cache of merged lines so that we reuse merged lines
when we've already seen a given pair.
This hits our current code base because we have ~25k
slimmingpaint tests that are skipped in TestExpectations.
Then running with "-i virtual" on the commandline creates
a fake expectations model to merge with that. On my z620,
this patch takes the time to merge the models from >4 minutes
to ~2 seconds.
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=197278
Patch Set 1 #
Total comments: 4
Patch Set 2 : address review comments #Patch Set 3 : improve comment #Messages
Total messages: 27 (11 generated)
ojan@chromium.org changed reviewers: + dpranke@chromium.org, joelo@chromium.org
The CQ bit was checked by ojan@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1182253003/1
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
lgtm
https://codereview.chromium.org/1182253003/diff/1/Tools/Scripts/webkitpy/layo... File Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py (right): https://codereview.chromium.org/1182253003/diff/1/Tools/Scripts/webkitpy/layo... Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py:568: # This code is n^2 in the number of tests per line. Cache the output "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. https://codereview.chromium.org/1182253003/diff/1/Tools/Scripts/webkitpy/layo... Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py:586: line = new_line 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.
https://codereview.chromium.org/1182253003/diff/1/Tools/Scripts/webkitpy/layo... File Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py (right): https://codereview.chromium.org/1182253003/diff/1/Tools/Scripts/webkitpy/layo... Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py:568: # This code is n^2 in the number of tests per line. Cache the output On 2015/06/15 at 22:50:59, Dirk Pranke wrote: > "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. Done https://codereview.chromium.org/1182253003/diff/1/Tools/Scripts/webkitpy/layo... Tools/Scripts/webkitpy/layout_tests/models/test_expectations.py:586: line = new_line On 2015/06/15 at 22:50:59, Dirk Pranke wrote: > 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. That's much better. I didn't do exactly this, but close.
The CQ bit was checked by ojan@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from joelo@chromium.org Link to the patchset: https://codereview.chromium.org/1182253003/#ps40001 (title: "improve comment")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1182253003/40001
The CQ bit was unchecked by commit-bot@chromium.org
No LGTM from a valid reviewer yet. Only full committers are accepted. Even if an LGTM may have been provided, it was from a non-committer, _not_ a full super star committer. See http://www.chromium.org/getting-involved/become-a-committer Note that this has nothing to do with OWNERS files.
Dirk, please take another look when you get a chance.
lgtm, thanks.
The CQ bit was checked by ojan@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1182253003/40001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: mac_blink_rel on tryserver.blink (JOB_FAILED, http://build.chromium.org/p/tryserver.blink/builders/mac_blink_rel/builds/59297)
The CQ bit was checked by ojan@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1182253003/40001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: mac_blink_rel on tryserver.blink (JOB_FAILED, http://build.chromium.org/p/tryserver.blink/builders/mac_blink_rel/builds/59306)
The CQ bit was checked by ojan@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1182253003/40001
Message was sent while issue was closed.
Committed patchset #3 (id:40001) as https://src.chromium.org/viewvc/blink?view=rev&revision=197278 |
