Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2997233002:
Update defer loading algorithm: (Closed)
|
Created:
3 years, 4 months ago by Siggi Cherem (dart-lang) Modified:
3 years, 3 months ago Reviewers:
sra1 CC:
reviews_dartlang.org, Johnni Winther Target Ref:
refs/heads/master Visibility:
Public. |
DescriptionUpdate defer loading algorithm:
On a large app this cuts the algorithm time in half.
BUG=
R=sra@google.com
Committed: https://github.com/dart-lang/sdk/commit/cf19b1e5aa3798b87b8ecdf482f83815c97e89c8
Patch Set 1 #
Total comments: 28
Patch Set 2 : cl comments, bug fixes, rebase #
Total comments: 4
Patch Set 3 : follow up comments #Patch Set 4 : follow up comments + ensure sorted output #
Messages
Total messages: 22 (15 generated)
Patchset #1 (id:1) has been deleted
Patchset #1 (id:20001) has been deleted
Patchset #1 (id:40001) has been deleted
Patchset #1 (id:60001) has been deleted
Patchset #1 (id:80001) has been deleted
Patchset #1 (id:100001) has been deleted
Patchset #1 (id:120001) has been deleted
Patchset #1 (id:140001) has been deleted
sigmund@google.com changed reviewers: + sra@google.com
https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... File pkg/compiler/lib/src/deferred_load.dart (right): https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:789: // Add `main` and their recursive dependencies to the main output unit. Explain somewhere why the main unit is completely explored before any other. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:809: while (!queue.isEmpty) { nit: queue.isNotEmpty https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1152: for (var existing in importSet._imports) { This loop inside the merge loop in union makes union O(N^2) https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1175: List<ImportElement> aImports = a._imports.toList(); Could also use iterators over the sets. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1187: if (aIndex == bIndex) { This case can be avoided with a self-edge (see below) https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1192: result = _add(result, importA); Why is this not the following? result = result._add(importA); We are merging ordered items (and removing duplicates explicitly or via a self-edge), so this should work directly. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1210: var index = _importIndex[import]; I think is is worth keeping _DeferredImport as a place to store the index. This might be advantageous if the Kernel representation is a little more tricky between multiple .dill files. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1220: class ImportSet implements OutputUnit { I'd rather ImportSet and OutputUnit be separate, with the output unit referencing the set. Not all ImportSets are OutputUnits. We will want to merge OutputUnits which breaks the 1-1 correspondence. Maybe a TODO. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1225: final Set<ImportElement> _imports = new Set(); <ImportElement> https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1229: bool get isMainOutput => _imports.isEmpty; This is called a lot. I wonder if the old way of having a final bool field would be more efficient. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1234: int get size => _imports.length; This name (or 'length') makes sense for an ImportSet but not an OutputUnit where 'size' could be the number of elements or the estimated size of all the elements. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1244: result._imports.add(import); Adding a self edge allows the 'already-a-member' case to be simplified. result._neighbors[import] = result; If you do this, rename _neighbors to _transitions https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1262: Map<Entity, WorkItem> pendingElements = {}; Types on map literals. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1262: Map<Entity, WorkItem> pendingElements = {}; final?
Patchset #3 (id:200001) has been deleted
Patchset #2 (id:180001) has been deleted
Patchset #2 (id:220001) has been deleted
Patchset #2 (id:240001) has been deleted
Thanks Stephen! I finally addressed all the comments and fixed some subtle bugs I introduced initially. PTAL https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... File pkg/compiler/lib/src/deferred_load.dart (right): https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:789: // Add `main` and their recursive dependencies to the main output unit. On 2017/08/18 23:42:28, sra1 wrote: > Explain somewhere why the main unit is completely explored before any other. Done. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:809: while (!queue.isEmpty) { On 2017/08/18 23:42:28, sra1 wrote: > nit: queue.isNotEmpty Done. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1152: for (var existing in importSet._imports) { On 2017/08/18 23:42:28, sra1 wrote: > This loop inside the merge loop in union makes union O(N^2) Doh! - and good catch! I meant to use result._add in `union`, and not this function. Funny enough even with this the implementation was faster than the old one. Now, it's way better! Large up completes in under 6s https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1175: List<ImportElement> aImports = a._imports.toList(); On 2017/08/18 23:42:28, sra1 wrote: > Could also use iterators over the sets. thanks nice idea. After splitting import-set and output unit, I realized I could simply use a List in the representation of importSets. As a result, I decided to continue with the indexing approach here. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1187: if (aIndex == bIndex) { On 2017/08/18 23:42:29, sra1 wrote: > This case can be avoided with a self-edge (see below) Done. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1192: result = _add(result, importA); On 2017/08/18 23:42:29, sra1 wrote: > Why is this not the following? > > result = result._add(importA); > > We are merging ordered items (and removing duplicates explicitly or via a > self-edge), so this should work directly. yes! indeed. good catch https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1210: var index = _importIndex[import]; On 2017/08/18 23:42:29, sra1 wrote: > I think is is worth keeping _DeferredImport as a place to store the index. > This might be advantageous if the Kernel representation is a little more tricky > between multiple .dill files. Thanks, I like how this simplified things. I changed it to wrap when we create the singleton sets. Afterwards the sets directly operate over the wrapped imports, so there is no lookup in a map anymore. Another idea I was thinking about was to just store the index in the set directly, and use a list (_allDeferredImports) to do the reverse lookup after the algorithm is done. I believe they should be similar in perf, so I went with your suggestion because I believe it makes the code easier to follow. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1220: class ImportSet implements OutputUnit { On 2017/08/18 23:42:29, sra1 wrote: > I'd rather ImportSet and OutputUnit be separate, with the output unit > referencing the set. > Not all ImportSets are OutputUnits. > We will want to merge OutputUnits which breaks the 1-1 correspondence. > > Maybe a TODO. Done. However, I don't have the edge from OutputUnit to ImportSet, but the opposite at this time. OutputUnit contains the actual set of imports, ImportSet.unit is used to indirectly map the result of the algorithm to an output unit. I did this to avoid coping again the results of the algorithm, but the alternative here would be to create a new Map<Entity, OutputUnit> (and ditch the existing Map<Entity, ImportSet>). Let me know if you prefer that we do the latter. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1225: final Set<ImportElement> _imports = new Set(); On 2017/08/18 23:42:28, sra1 wrote: > <ImportElement> Done. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1229: bool get isMainOutput => _imports.isEmpty; On 2017/08/18 23:42:28, sra1 wrote: > This is called a lot. > I wonder if the old way of having a final bool field would be more efficient. Done with the split of ImportSet and output unit https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1234: int get size => _imports.length; On 2017/08/18 23:42:28, sra1 wrote: > This name (or 'length') makes sense for an ImportSet but not an OutputUnit where > 'size' could be the number of elements or the estimated size of all the > elements. Done. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1244: result._imports.add(import); On 2017/08/18 23:42:28, sra1 wrote: > Adding a self edge allows the 'already-a-member' case to be simplified. > > result._neighbors[import] = result; > > If you do this, rename _neighbors to _transitions Done. https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1262: Map<Entity, WorkItem> pendingElements = {}; On 2017/08/18 23:42:29, sra1 wrote: > Types on map literals. Added, but note they are not needed in the short future (they'll be inferred in strong mode) https://codereview.chromium.org/2997233002/diff/160001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1262: Map<Entity, WorkItem> pendingElements = {}; On 2017/08/18 23:42:29, sra1 wrote: > final? Done.
lgtm https://codereview.chromium.org/2997233002/diff/260001/pkg/compiler/lib/src/d... File pkg/compiler/lib/src/deferred_load.dart (right): https://codereview.chromium.org/2997233002/diff/260001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:723: sortedOutputUnits.sort((a, b) => -a.compareTo(b)); Could also be b.compareTo(a) Not sure which reads easier. https://codereview.chromium.org/2997233002/diff/260001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1174: ImportSet emptySet = new ImportSet(); The use of 'emptySet' to represent an empty set in union and and a main unit in the main algorithm bothers me a bit. Perhaps add `ImportSet get mainSet => emptySet` and use mainSet wherever the main set is needed. I think after that most uses of emptySet could be private.
Patchset #3 (id:280001) has been deleted
Thanks Stephen! /cc Johnni who expressed interest in taking a look at some point. https://codereview.chromium.org/2997233002/diff/260001/pkg/compiler/lib/src/d... File pkg/compiler/lib/src/deferred_load.dart (right): https://codereview.chromium.org/2997233002/diff/260001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:723: sortedOutputUnits.sort((a, b) => -a.compareTo(b)); On 2017/08/28 22:38:08, sra1 wrote: > Could also be b.compareTo(a) > Not sure which reads easier. Done - me neither :) https://codereview.chromium.org/2997233002/diff/260001/pkg/compiler/lib/src/d... pkg/compiler/lib/src/deferred_load.dart:1174: ImportSet emptySet = new ImportSet(); On 2017/08/28 22:38:08, sra1 wrote: > The use of 'emptySet' to represent an empty set in union and and a main unit in > the main algorithm bothers me a bit. > > Perhaps add `ImportSet get mainSet => emptySet` and use mainSet wherever the > main set is needed. I think after that most uses of emptySet could be private. Nice suggestion. Done
we talked offline, but I verified now that the output has no semantic changes. I'm seeing differences with the full emitter because the output of the compiler is not stable. The output is identical when I use --fast-startup, though. I also made a small change to sort the output units with this CL to help improve the stability of the compiler output.
Description was changed from ========== Update defer loading algorithm: On a large app this cuts the algorithm time in half. BUG= ========== to ========== Update defer loading algorithm: On a large app this cuts the algorithm time in half. BUG= R=sra@google.com Committed: https://github.com/dart-lang/sdk/commit/cf19b1e5aa3798b87b8ecdf482f83815c97e89c8 ==========
Message was sent while issue was closed.
Committed patchset #4 (id:320001) manually as cf19b1e5aa3798b87b8ecdf482f83815c97e89c8 (presubmit successful). |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
