benjamn/ast-types — pull request #82 by drslump (2014-12-26 21:13:53+00:00)
Title: iteration based visitor with meta-programming optimizations

> Comes from here https://github.com/benjamn/ast-types/issues/80

This is a work in progress but already seems to be a valid way to greatly improve the performance of the traversal. It's very close to the x10 @stefanpenner wished for :)

Here is the gist of it:

- Traversal (post-order) avoids recursion and allocations
- Current visiting path is kept using a stack array (`NodePath` like object to be introduced later)
- Optimized code paths by meta programming (basically just compiling a function with a switch statement)

Things yet to be implemented:

- Simplify the visitor creation pattern (it's inherited from a previous branch)
- Test pre-order traversal, it should work in theory but there seems to be a bug somewhere
- NodePath like object for transforms (I had a version but I can't remember where I saved it :flushed:)
- Improve the compilation step since right now is quite hacky analyzing the types (@benjamn please help :)
- Analyze v8 optimizer logs and see if it can be further improved (the compilation step can probably help greatly here).

The API is quite different from the current one, now the visitors receive the actual node (and an optional NodePath). If they want to control the order of the traversal they have to call `this.traverse([visitor])` but they can't provide a specific node since it would invalidate the stack, otherwise the traversal is automatic. To visit arbitrary nodes they must call `this.visit(node)`, it'll generate a new root stack and visitor state (returns the instance). Perhaps some helper like `visitChild(childName)` could be introduced in order to keep the previous stack.

Some speed figures for `visitNode`:

```
> node test/perf.js
NodePath: [102, 84, 86, 80, 82] avg 86.8 (31475)
Visitor: [17, 11, 11, 12, 11] avg 12.4 (31470)
Precompiled: [8, 4, 3, 3, 6] avg 4.8 (31470)
```

and for `visitFunctionExpression`:

```
> node test/perf.js
NodePath: [84, 64, 73, 67, 77] avg 73 (595)
Visitor: [12, 5, 5, 5, 5] avg 6.4 (595)
Precompiled: [4, 2, 1, 1, 1] avg 1.8 (595)
```

The *precompiled* is just that the visitor is created outside the benchmark, basically to show that for multiple passes (ie: a finder) the speeds are unreal :)

When no optimized code paths compilation is performed speed is degraded around a 60%, so perhaps it can be an optional feature.

So please, review the new API and let's iterate on it until it fits everyone's expectations.