Performance: Reuse NodePath instances when visiting

[drslump]

Currently the traversal will create a 1:1 mapping between actual syntax Nodes and NodePaths, the paths are cached for later visits but they don't survive separate traversals, like when chaining different ES6 transformations.

I've run a very contrived benchmark that would always reuse a single NodePath just changing it's value property for each visit. The results are quite good with over a x2 increase when visiting underscode.js, so I think this route has potential.

Two options here that I see, the first one should be low hanging fruit, expose to the caller the root NodePath used in a traversal (which should have all the children already cached) and allow it to be passed along for further calls.

// First transformation returns the root nodepath
var rootPath = types.visit(ast, firstVisitor)
// Second transformation uses it instead of the AST (so the cache is used)
rootPath = types.visit(rootPath, secondVisitor)

The second option is a bit more hard to pull off but should improve the speed even on single passes. When visiting the tree we don't need to keep the whole structure, just the stack of nodes that took us to a given node. So a single NodePath can be used for the traversal, we just update its stack before passing it on to the visitor.

var path = new NodePath(ast);
assert( path.stack === [Program] === [ast] )

path.stack.push('body');  // The field name
path.stack.push(path.value.body)  // The field value
ast.body.forEach(function (item, idx) {
  path.stack.push(idx);  // field name
  path.stack.push(item);  // field value
  assert( path.stack === [Program, 'body', [Stmt, Stmt], 0, Stmt] )
  visit(path);
  path.stack.pop();
  path.stack.pop();
  assert( path.stack === [Program, 'body'] )
});

The limitation here is that a visitors cannot directly hold a reference to the passed NodePath, since it'll be mutating by the traversal. I don't see why it would want to keep it but in any case, to do so it could be documented that it needs to call first path.clone() or path.freeze() to get a copy of the path for future use. Obviously it's still possible to keep references to path.node.

The current methods in NodePath, like .each will also need to create a new NodePath instance but they are only used on transformations and even in those cases the copy can be optimized:

NodePath.value = function () {
  return this.stack[ this.stack.length - 1 ];
};

NodePath.each = function (cb) {
   var list = Array.copy(this.value);  // Freeze collection for semantics
   var iterPath = this.clone();
   list.forEach(function (item, idx) {
     iterPath.stack.push(idx);
     iterPath.stack.push(item);
     cb(iterPath);
     iterPath.stack.pop();
     iterPath.stack.pop();
   });
}

Note that to handle Scope it can either be included as a virtual item in the stack ([Statement, Scope, Function]) or act as a wrapper for a node ([Statement, Scoped(Function)]) and then handle the unwrapping on the NodePath logic.

So by having the limitation of a mutable NodePath reference, which isn't a bad thing IMHO, we can eliminate the creation of thousands of objects from the visitor logic, improving speed and memory usage.

Edit: I forgot to mention that creation of NodePath instances can probably be controlled from the traversal, so it's even possible to re-use instances like it's done for Context.

[benjamn]

The first option is similar to creating your own NodePath and passing it into types.visit, which is something you can already do, and would be an easy (and big) win for esnext:

var rootPath = new types.NodePath(ast);
types.visit(rootPath, firstVisitor);
types.visit(rootPath, secondVisitor);
// etc.

The second option is tempting too. I'm glad you noticed that we recycle Context objects in types.visit, since that's the kind of thing I have in mind.

Right now, a lot of the effort (in terms of code complexity) in Path and NodePath methods goes towards making sure any other instances that might be hanging around get updated appropriately. For example, when you insert an element at the beginning of an array, the .name (index) properties of any/all later NodePath objects need to be incremented.

If we just invalidated/recycled all NodePath objects not on the current path, then perhaps we wouldn't have to care so much about updating other NodePaths?

If you really wanted a permanent NodePath object that wouldn't be recycled, there could be an API for asking for that, like path.keep(). And maybe NodePath objects not created by the traversal would be automatically kept?

Or we could go the other way: if you explicitly call path.release() in a visitor method, then it can be recycled. A little extra effort for the consumer, but a potentially big performance win, and less of a backwards compatibility-breaking change.

[drslump]

I was just about to send a PR with the first fix, basically just retuning NodePath instead of Node, but you're right that it's already possible to do it by constructing the NodePath in advance, so it doesn't deserve to break the current API.

Testing it with 10 iterations using the benchmark visitor in the tests (visitNode) just provided a 25% performance increase, which is not bad at all! Perhaps @stefanpenner could try it with esnext on his benchmarks.

For the second option, I think that if we avoid breaking backwards compatibility it will not be worth it. It should provide a big enough performance enhancement to make current users want to adapt to the new API.

Maintaining stack based NodePath objects in sync with the transformations is doable but complex and I'm not sure if it has many benefits. I haven't seen any transformation (basically from esnext) requiring it.

Perhaps it'll be better to introduce an all new FastNodePathVisitor that uses the stack based approach, leaving the current one operating as is for those who need it. It's probably also a good idea to have a simple NodeParentVisitor that avoids any NodePath overhead and just calls visitors with visit(node, parentNode), which is enough for many use cases from what I've seen.

So are you confortable with having different visitors? Or would you prefer to have a single optimized one?

[benjamn]

I'm realizing I didn't really address your path.stack suggestion in my previous comment.

Keeping a stack of alternating name/value elements seems like the only way to avoid allocating new objects throughout the traversal. The performance benefits of that could be profound!

For what it's worth, I've experimented with maintaining a lightweight singly-linked list of nodes, but that's basically what NodePath objects are, and I wasn't able to get much speedup or memory reduction from that.

Even if we don't decide to take this route with NodePath and ast-types, the same idea could help improve the performance of recast.print.

[benjamn]

I think I'd like to do whatever encourages developers to write the most efficient code. In this case, I think that means breaking backwards compatibility and bumping the minor version so client code has to be upgraded explicitly. I bet that upgrade will be pretty trivial in most cases.

[stefanpenner]

Testing it with 10 iterations using the benchmark visitor in the tests (visitNode) just provided a 25% performance increase, which is not bad at all! Perhaps @stefanpenner could try it with esnext on his benchmarks.

I will give it a try later. 25% would be a nice win, as some people are seeing 50s initial builds o_0).. Ultimately we need to get 5x -> 10x improvement across the board to make this reasonable. I suspect it can be done, but will require energy.

[stefanpenner]

Perhaps it'll be better to introduce an all new FastNodePathVisitor

this could be used as a fast pre-run to detect which subsequent transforms may be needed. This would help short-circuit out of transforms that aren't even needed.

[stefanpenner]

I think I'd like to do whatever encourages developers to write the most efficient code. In this case, I think that means breaking backwards compatibility

if we can prove this with numbers, developers wont mind breakage for a substantial perf win.

[stefanpenner]

@benjamn was this your idea for sharing NodePath https://github.com/stefanpenner/esnext/commit/f890cb0ace3c34a77ac4cb8c8efc29a5dc989916 ?

I may have not understood you, this yielded no change.

[eventualbuddha]

FWIW, the es6-module-transpiler does actually hold onto NodePath instances for later, calling .replace() on them at some later time. Doing that is kind of a code smell, so I'm not saying I want to block this optimization on account of that. I believe I'm doing that to prevent any issues arising from the order in which replacements happen, i.e. some replacements may be dependent on information from earlier or later in the AST.

[drslump]

Closing this one since now there is an improved version on https://github.com/benjamn/ast-types/pull/82