Track deep literal reassignments and improve performance by lukastaegert · Pull Request #2254 · rollup/rollup

lukastaegert · 2018-06-10T07:09:08Z

This resolves #2237.

The issue was that when tracking reassignments of variables, only the top most keys were considered while in fact reassignments of nested keys needed to be considered as well.

As first thought this increased amount of reassignments would have a heavy performance impact, I first refactored the way infinite recursions are prevented when tracking reassignments to use a mutable shared map structure. This had a noticeably positive effect on the performance of the node binding phase.

I also played around with replacing immutableJS for literal recursion tracking with a custom solution (here, immutability was important as otherwise, many literals would be treated as unknown needlessly) but it turns out the internal optimizations of immutableJS are not to be underestimated.

The actual fix turned out to be rather small and focused, solely happening in ObjectExpression and LocalVariable.

guybedford · 2018-06-10T14:51:57Z

Amazing work. Just starting to play around with this and get an idea of what's going on, so please bear with me.

As far as I can gather, what is being done is to track all reassignments so that the set of all possible assignments per subpath of an object is known?

I will being with my extremely naive questions:

What are the use cases for having both EntityPathTracker and ImmutableEntityPathTracker? At a glance it seems like ImmutableEntityPathTracker is used to track values, while entity path tracker handles the reassignments of objects themselves?
Once we have an unknown value in a given path assignment, surely an optimization would be to stop tracking further assignments to that path at that point given that the whole path is deopted then? Is this being done?
If we are tracking subpath reassignments comprehensively now, how come the following case isn't supported for treeshaking:

const x = {
  a: false,
  b: false
};

function p (y) {
  y.a = true;
}

p(x);

if (x.b)
  console.log('bad');
else
  console.log('good');

lukastaegert · 2018-06-10T16:09:13Z

Thanks for taking a look already!

As far as I can gather, what is being done is to track all reassignments so that the set of all possible assignments per subpath of an object is known?

Yes and no. This tracking is primarily used to prevent infinite recursions and is only used by LocalVariables for normal reassignments and CallExpressions for return value reassignments. As such, the intention is to track which reassignment requests happen a these two places.

This, however, is not the complete reassignment information. The core of the bug at hand was that when for instance foo is exported, all keys of foo as well as all keys of all members of foo etc. need to be treated as reassigned. The reassignment tracker, however, will only track that an "unknown key" of foo was reassigned. All other reassignments are tracked directly at the definition of foo (at least if foo is an object literal).

Once we have an unknown value in a given path assignment, surely an optimization would be to stop tracking further assignments to that path at that point given that the whole path is deopted then? Is this being done?

Yes, this is exactly why there is now a reassignment tracker on module level so that this information is shared. Now if a reassignment request reaches a LocalVariable, the tracker is checked and if it has already tracked such a request, we abort the request. Due to this optimization, the "analyze dependency graph" phase is now about 25% faster in my experiments bundling (mainly) the TypeScript compiler.

What are the use cases for having both EntityPathTracker and ImmutableEntityPathTracker? At a glance it seems like ImmutableEntityPathTracker is used to track values, while entity path tracker handles the reassignments of objects themselves?

The EntityPathTracker is much faster and/but will deoptimize much more easily in situations where results matter (as is the case for getLiteralValue). I first tried to use the EntityPathTracker for literal values as well but then it would deoptimize e.g. these situations:

const a = 'key';
const obj = {[a]: false};

// this would be retained as the value of `a` needs to be looked up twice to get
// the value of `obj[a]`
if (obj[a]) console.log('not happening');

const b = false;

// again this would be retained as `b` is looked up twice to get the value of `b || b`
if (b || b) console.log('not happening');

However for future optimizations, the faster EntityPathTracker could be used e.g. to check if we have already called a function when checking if a function call has a side effect.

If we are tracking subpath reassignments comprehensively now, how come the following case isn't supported for treeshaking

Reassignment tracking is not capable of tracking through function calls yet (mostly due to performance reasons). Thus if you pass an object to a function (any function really), a deoptimization will kick in that marks all keys as reassigned because "something bad might happen inside the function" (as it does in fact for x.a)

guybedford

I've added a few more notes for now, slowly getting my head around it!

The EntityPathTracker is much faster and/but will deoptimize much more easily in situations where results matter (as is the case for getLiteralValue)

So this is because EntityPathTracker is a single path tracker, while ImmutableEntityPathTracker tracks each and every unique path? I understand it may well be a convenient distinction, but it would help to see why EntityPathTracker is being provided at the Module level and not the Graph level, given that modules share bindings and execution context. What optimizations does this make possible?

Reassignment tracking is not capable of tracking through function calls yet (mostly due to performance reasons). Thus if you pass an object to a function (any function really), a deoptimization will kick in that marks all keys as reassigned because "something bad might happen inside the function" (as it does in fact for x.a)

ExecutionPathOptions seemed to have concepts of depth etc associated with it, where one might be able to say "this execution path can go through x number of function checks before deoptimization". Would some kind of extension still be possible here in the new approach? As usual, just ensuring doors are not closing on possible optimizations :)

guybedford · 2018-06-11T21:58:12Z

 			nodeConstructors,
 			propertyReadSideEffects:
 				!this.graph.treeshake || this.graph.treeshakingOptions.propertyReadSideEffects,
+			reassignmentTracker: new EntityPathTracker(),


If EntityPathTracker is for managing "seen" paths over the whole execution graph, why is it module-specific and not graph-specific?

Good point, some wrong conceptions I had in my head while designing this.

guybedford · 2018-06-11T22:12:42Z

+const RESULT_KEY: RESULT_KEY = {};
+type KeyTypes = OptionTypes | Entity | RESULT_KEY;

 export class ExecutionPathOptions {


Can NEW_EXECUTION_PATH be removed from this file with all these refactorings of it?

Even though it is only used once in code, using the same variable would still provide some benefit. But I will move it to the proper location.

guybedford · 2018-06-11T22:26:17Z

+
 	createScope(parentScope: Scope) {
-		this.scope = new ReturnValueScope({ parent: parentScope });
+		this.scope = new ReturnValueScope(parentScope);


Much nicer.

guybedford · 2018-06-11T22:28:40Z

-	getLiteralValueAtPath(path: ObjectPath, options: ExecutionPathOptions): LiteralValueOrUnknown {
+	getLiteralValueAtPath(
+		path: ObjectPath,
+		getValueTracker: ImmutableEntityPathTracker


getValue makes it sound like this will be a function. How about just calling this tracker or even recursionTracker? As someone not familiar with the approach, I only finally got the "recursion" part properly when you explained it in the last comment, as otherwise there was nothing in the code to indicate this is what it's for.

Yes, recursionTracker is probably much clearer to outsiders. Thanks for looking into this that deeply, this really helps to make the code a lot easier to understand!

guybedford · 2018-06-11T22:29:50Z

 		callOptions: CallOptions,
 		callback: ForEachReturnExpressionCallback,
-		options: ExecutionPathOptions
+		calledPathTracker: EntityPathTracker


Again, it is probably obvious that the tracker is for this "called path", so perhaps just tracker or recursionTracker?

lukastaegert · 2018-06-12T07:26:34Z

ExecutionPathOptions seemed to have concepts of depth etc associated with it, where one might be able to say "this execution path can go through x number of function checks before deoptimization". Would some kind of extension still be possible here in the new approach?

Actually a very interesting idea. Such an approach would not be possible everywhere (e.g. for reassignments, you definitely want to reach all variables that need to be reassigned) but it could definitely be used to replace the expensive "immutable" path tracker. For instance for getLiteralValue, we might just use a simple counter instead of the tracker and just abort after a given number of getLiteralValue calls (no matter on what entity).

cons: will deoptimize a little later on recursions and might deoptimize in some situations where this is not strictly necessary
pro: this will be much easier to understand and much faster in the vast majority of cases

I have run out of time for today unfortunately but I might set this up tomorrow.

I would not refactor the rest of the execution path options in this PR as this is clearly starting to break the scope of this bug fix but I think this could be tackled soon (and we can finally get rid of ImmutableJS).

lukastaegert · 2018-06-13T05:43:43Z

Ok, I have tried tracking literal value recursions via a counter and the result was rather disappointing: With my test code base (which contained the notoriously demanding TypeScript compiler itself as a worthy bundling target), there was hardly any measurable performance change, no matter how often I tried.

In this light, I would stick with the immutable tracker for now as it promises to provide optimal results. Optimal means that we only deoptimize if, while determining a literal value, we need to know this very literal value.

That doesn't mean there isn't a lot of potential for the ExecutionPathOptions left as in many cases here, a mutable tracker might provide better results. But I would leave this for another PR as this could also mean changing the way, other information about the execution path is forwarded. So this is again ready for another review.

guybedford

Nice to hear you tried the other approach even if it didn't work out (does that mean three separate different approaches tried then for this one PR!?) - experimenting with variations of this stuff is super important to long-term architecture.

guybedford · 2018-06-13T13:04:42Z

 			propertyReadSideEffects:
 				!this.graph.treeshake || this.graph.treeshakingOptions.propertyReadSideEffects,
-			reassignmentTracker: new EntityPathTracker(),
+			reassignmentTracker,


We already read things off graph here, so I would suggest just setting this as reassignmentTracker: graph.reassignmentTracker instead of a new argument, unless we switch all to being provided as arguments.

guybedford · 2018-06-13T13:26:17Z

-	reassignPath(path: ObjectPath, options: ExecutionPathOptions) {
-		!options.hasReturnExpressionBeenAssignedAtPath(path, this) &&
+	reassignPath(path: ObjectPath) {
+		if (path.length > 0 && !this.context.reassignmentTracker.track(this, path)) {


So reassignment is basically a deoptimization, and the reassignment tracker allows us to track this globally? Or is it again about managing recursion here?

Yes, reassignments are a global deoptimization but basically, it is still only about recursion tracking. The reason I had to add this here is in addition to the usages in LocalVariable is this situation:

const foo = () => foo(); foo().bar = 'baz';

The second assigment will trigger a "forEachReturnExpression" with a reassignment for foo. This again will try to reassign the return expression foo() where we loose the recursion tracker of "forEachReturnExpression" and then another cycle starts. To break this cycle, one way was to extend the active tracking to call expressions.

loops when reassigning * Use special immutable tracker to prevent infinite loops when retrieving values

apparently much better optimized than out custom solution.

This Pull Request updates dependency [rollup](https://github.com/rollup/rollup) from `v0.60.4` to `v0.60.6` <details> <summary>Release Notes</summary> ### [`v0.60.6`](https://github.com/rollup/rollup/blob/master/CHANGELOG.md#0606) [Compare Source](rollup/rollup@v0.60.5...v0.60.6) *2018-06-14* * Track mutations of included virtual arrays ([#2263](`https://github.com/rollup/rollup/pull/2263`)) * Update readme ([#2266](`https://github.com/rollup/rollup/pull/2266`)) --- ### [`v0.60.5`](https://github.com/rollup/rollup/blob/master/CHANGELOG.md#0605) [Compare Source](rollup/rollup@v0.60.4...v0.60.5) *2018-06-14* * Track deep reassignments of global and exported variables and improve performance ([#2254](`https://github.com/rollup/rollup/pull/2254`)) --- </details> --- This PR has been generated by [Renovate Bot](https://renovatebot.com).

lukastaegert requested a review from guybedford June 10, 2018 07:09

guybedford reviewed Jun 11, 2018

View reviewed changes

guybedford approved these changes Jun 13, 2018

View reviewed changes

lukastaegert added 7 commits June 14, 2018 06:03

Fix TypeScript errors

f4b37ca

* Use module shared, mutable reassignment tracker to prevent infinite

857ce8d

loops when reassigning * Use special immutable tracker to prevent infinite loops when retrieving values

Prevent infinite recursions when reassigning return values

d2596a0

Resolve #2237

e6bc4e3

Switch back to using immutable JS for immutable path tracking as it is

8d3d298

apparently much better optimized than out custom solution.

Review comments

7f98bd3

Get reassignment tracker directly from graph.

e3f8bb3

lukastaegert force-pushed the object-literal-reassignments branch from d080293 to e3f8bb3 Compare June 14, 2018 04:39

lukastaegert added this to the 0.60.5 milestone Jun 14, 2018

lukastaegert merged commit e3f8bb3 into master Jun 14, 2018

lukastaegert deleted the object-literal-reassignments branch June 14, 2018 04:47

Uh oh!

Uh oh!

Conversation

lukastaegert commented Jun 10, 2018

Uh oh!

guybedford commented Jun 10, 2018

Uh oh!

lukastaegert commented Jun 10, 2018

Uh oh!

guybedford left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lukastaegert commented Jun 12, 2018

Uh oh!

lukastaegert commented Jun 13, 2018

Uh oh!

guybedford left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants