[L] Change in dart/sdk[main]: [record_use] Const instances loading units
Daco Harkes (Gerrit)
New activity on the change![]( "Open in Gerrit")
Related details
- Nate Biggs
Code-Owners
Code-Review
Commit-Message-Has-TEST
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Sigmund Cherem (Gerrit)
Sigmund Cherem added 4 comments![]( "Open in Gerrit")
// We deduplicate them here.should this comment be in the block below instead?
result.addAll(_recordConstantUses(dependency, sourceInformation));this has a potential of using a lot of heap space (e.g. potentially quadratic in the size of the constant-graph).
A few considerations:
- consider only creating a list lazily if there are any recorded uses of a given constant, otherwise leave the constant mapping empty (or use `const []` as a placeholder)
- consider extending this recursive method to expect a list parameter if it's being used in the context of a parent constant
- consider, alternatively, not recording dependencies's record uses in our own constant, but leaving that recorded only at the level of that other constant.
// dart2js and VM assign loading units differently. Work around thisnits:
- 80 col
- bummer: we often use the term "output unit" rather than "loading unit" in dart2js. Seems that TFA uses the latter? It would be nice to align, but the dart2js naming convention is as old as time.
// in the format.Alternatively, we could use the output unit canonical naming scheme. I'm not sure if TFA does the same, though.
Dart2js file names are not canonical, but dart2js does give you the metadata you need if you pass the `--deferred-map` flag, to properly identify each output unit.
The metadata is a simple .json file where each output unit (loading unit) is identified as a **set of keys**, each key is a deferred-import (not the target library of the deferred import). We identify deferred-imports uniquely by using the URI of the source where they appear and the prefix they used (which is guaranteed to be unique within the file by the spec).
As an example. The current unit test has two deferred imports in `loading_units_nested_shared_constant.dart`:
```
import 'loading_units_nested_shared_constant_helper_a.dart' deferred as a;
import 'loading_units_nested_shared_constant_helper_b.dart' deferred as b;
```
These are identified as:
- `loading_units_nested_shared_constant.dart#a` (note how the target library is not part of the identifier)
- `loading_units_nested_shared_constant.dart#b`
Let me use relabel these as `constants.dart#a` and `constants.dart#b`, for short.
This program defines at most 4 output units, one per subset of deferred-imports in the program: ```
- main = out = {}
- out_1 = {constants.dart#a}
- out_3 = {constants.dart#b}
- out_2 = {constants.dart#a, constants.dart#b}
- ```
If you call `b.loadLibrary` (on `constants.dart#b`), this implies you will need to actually load out_3 and out_2. The deferred reachability graph is implicitly represented by the partial order defined by the subset relation of these sets 😊.
Related details
- Daco Harkes
Code-Owners
Code-Review
Commit-Message-Has-TEST
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Daco Harkes (Gerrit)
Daco Harkes voted and added 4 comments![]( "Open in Gerrit")
Votes added by Daco Harkes
| Commit-Queue | +1 |
4 comments
should this comment be in the block below instead?
Oh, I moved the logic into a new CL because it changes a bunch of other tests. But I forgot to remove the comment.
result.addAll(_recordConstantUses(dependency, sourceInformation));this has a potential of using a lot of heap space (e.g. potentially quadratic in the size of the constant-graph).
A few considerations:
- consider only creating a list lazily if there are any recorded uses of a given constant, otherwise leave the constant mapping empty (or use `const []` as a placeholder)
- consider extending this recursive method to expect a list parameter if it's being used in the context of a parent constant
- consider, alternatively, not recording dependencies's record uses in our own constant, but leaving that recorded only at the level of that other constant.
Right, we should use an O(1) concat method instead of flatting the lists.
I've added a new data structure to get the desired algorithmic complexity.
And incorporated a special const object for the empty case to avoid allocating tons of objects.
// dart2js and VM assign loading units differently. Work around thisnits:
- 80 col
- bummer: we often use the term "output unit" rather than "loading unit" in dart2js. Seems that TFA uses the latter? It would be nice to align, but the dart2js naming convention is as old as time.
Done.
VM and wasm use loading unit. So lets stick with that for now.
Alternatively, we could use the output unit canonical naming scheme. I'm not sure if TFA does the same, though.
Dart2js file names are not canonical, but dart2js does give you the metadata you need if you pass the `--deferred-map` flag, to properly identify each output unit.
The metadata is a simple .json file where each output unit (loading unit) is identified as a **set of keys**, each key is a deferred-import (not the target library of the deferred import). We identify deferred-imports uniquely by using the URI of the source where they appear and the prefix they used (which is guaranteed to be unique within the file by the spec).
As an example. The current unit test has two deferred imports in `loading_units_nested_shared_constant.dart`:
```
import 'loading_units_nested_shared_constant_helper_a.dart' deferred as a;
import 'loading_units_nested_shared_constant_helper_b.dart' deferred as b;
```These are identified as:
- `loading_units_nested_shared_constant.dart#a` (note how the target library is not part of the identifier)
- `loading_units_nested_shared_constant.dart#b`
Let me use relabel these as `constants.dart#a` and `constants.dart#b`, for short.
This program defines at most 4 output units, one per subset of deferred-imports in the program: ```
- main = out = {}
- out_1 = {constants.dart#a}
- out_3 = {constants.dart#b}
- out_2 = {constants.dart#a, constants.dart#b}
- ```
If you call `b.loadLibrary` (on `constants.dart#b`), this implies you will need to actually load out_3 and out_2. The deferred reachability graph is implicitly represented by the partial order defined by the subset relation of these sets 😊.
Oh, this is very interesting! Using the current "output names" for loading units makes them unstable and useless for understanding. So canonical names sounds lovely!
I want to explore this, and also look at the VM and dart2wasm to see if we have something similar there.
I've filed https://github.com/dart-lang/native/issues/3210 to track this.
Related details
- Sigmund Cherem
Code-Owners
Code-Review
Commit-Message-Has-TEST
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Sigmund Cherem (Gerrit)
Sigmund Cherem added 1 comment![]( "Open in Gerrit")
result.addAll(_recordConstantUses(dependency, sourceInformation));Daco Harkesthis has a potential of using a lot of heap space (e.g. potentially quadratic in the size of the constant-graph).
A few considerations:
- consider only creating a list lazily if there are any recorded uses of a given constant, otherwise leave the constant mapping empty (or use `const []` as a placeholder)
- consider extending this recursive method to expect a list parameter if it's being used in the context of a parent constant
- consider, alternatively, not recording dependencies's record uses in our own constant, but leaving that recorded only at the level of that other constant.
Right, we should use an O(1) concat method instead of flatting the lists.
I've added a new data structure to get the desired algorithmic complexity.
And incorporated a special const object for the empty case to avoid allocating tons of objects.
I don't believe we need to add a new data-structure in this case. There is an intrinsic cost to adding a new datastructure that I worry it may add more tech-debt than we are willing to take in there. Whenever we add new abstractions like these, it takes time and effort to tune them and make them work right. Just as an example, this implementation doesn't properly handle the const empty case because `fromList` calls `cast`, and `cast` creates new objects to wrap the original list, effectively creating a new object for every empty list.
Taking a step back, what is the invariant we need during codegen? Is it that each emitted constant has all its transitive record-use, or is it sufficient if it just lists its direct record-uses?
I'm thinking that the third suggestion I proposed above may be a good fit either way, but much simpler if you only need direct record-uses. This means:
- The map only stores direct uses: constant -> immediate record-uses
- If you ever need to find all recursive record-uses of a constaat, you can walk the constant dependencies (e.g. using a visitor) and look up each sub-constant in the map to accumulate the results on demand. We never store the flattened version permanently, so the quadratic storage problem goes away.
The reason I think only immediate record-uses may be sufficient is because dart2js emits constants using subexpressions per sub-constant, so we'll have an opportunity to include the record-use at each level in separate parts of the output.
Related details
- Daco Harkes
Code-Owners
Code-Review
Commit-Message-Has-TEST
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Daco Harkes (Gerrit)
Daco Harkes added 1 comment![]( "Open in Gerrit")
result.addAll(_recordConstantUses(dependency, sourceInformation));Daco Harkesthis has a potential of using a lot of heap space (e.g. potentially quadratic in the size of the constant-graph).
A few considerations:
- consider only creating a list lazily if there are any recorded uses of a given constant, otherwise leave the constant mapping empty (or use `const []` as a placeholder)
- consider extending this recursive method to expect a list parameter if it's being used in the context of a parent constant
- consider, alternatively, not recording dependencies's record uses in our own constant, but leaving that recorded only at the level of that other constant.
Sigmund CheremRight, we should use an O(1) concat method instead of flatting the lists.
I've added a new data structure to get the desired algorithmic complexity.
And incorporated a special const object for the empty case to avoid allocating tons of objects.
I don't believe we need to add a new data-structure in this case. There is an intrinsic cost to adding a new datastructure that I worry it may add more tech-debt than we are willing to take in there. Whenever we add new abstractions like these, it takes time and effort to tune them and make them work right. Just as an example, this implementation doesn't properly handle the const empty case because `fromList` calls `cast`, and `cast` creates new objects to wrap the original list, effectively creating a new object for every empty list.
Taking a step back, what is the invariant we need during codegen? Is it that each emitted constant has all its transitive record-use, or is it sufficient if it just lists its direct record-uses?
I'm thinking that the third suggestion I proposed above may be a good fit either way, but much simpler if you only need direct record-uses. This means:
- The map only stores direct uses: constant -> immediate record-uses
- If you ever need to find all recursive record-uses of a constaat, you can walk the constant dependencies (e.g. using a visitor) and look up each sub-constant in the map to accumulate the results on demand. We never store the flattened version permanently, so the quadratic storage problem goes away.
The reason I think only immediate record-uses may be sufficient is because dart2js emits constants using subexpressions per sub-constant, so we'll have an opportunity to include the record-use at each level in separate parts of the output.
That will be quadratic in another way: consider a very big constant that is used in many places. And somewhere burried deep in that constant, we
That is not sufficient. You might refer to a big constant that somewhere nested within it has a constant that is recorded.
For example: A large fully const widget tree in Flutter, with some const `IconData`.
The reason I think only immediate record-uses may be sufficient is because dart2js emits constants using subexpressions per sub-constant
Can you elaborate on this? That sounds like quadratic behavior. If you need a load for each sub-expression.
If you have 100 identical const Flutter widget trees, your program size effectively becomes `O(number-of-references-to-big-const * size-of-big-const)`.
Is this how it works?
Related details
- Sigmund Cherem
Code-Owners
Code-Review
Commit-Message-Has-TEST
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Sigmund Cherem (Gerrit)
Sigmund Cherem added 1 comment![]( "Open in Gerrit")
just to document our offline chat:
- dart2js constant initialization ensures each constant is only evaluated once
- however, we noted that here we are trying to record details on the constant-expression, rather than the constant-value (which may have tradeoffs in the future with deferred loading, if assets are to be loaded at the use-site or the declaration site).
- we decided to move forward with something like the new data structure, but moving it here and making it more specialized and not general purpose (e.g. remove generics, make it specific about record use), as an opportunity to simplify it.
Related details
- Daco Harkes
Code-Owners
Code-Review
Commit-Message-Has-TEST
Review-Enforcement
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |