Optimize the performance

[Constellation]

@inikulin 's brilliant work inikulin/esotope shows that escoregen should be cleaned up and it can get further performance gains.

To fix #209 at the same time, I'm planning to reconstruct the code base.

My plan is,

• Use methods instead of big switch

Originally it is chosen for simplicity. escodegen's first version ( it can be seen at esprima's old issue's striker.js) takes this. At that time, code is very simple, so using switch makes code readable.
But now, escodegen has a lo of options and has a lot of edge case code. So using methods based dispatch makes code simple, makes functions small, and makes it optimizable in V8.

• Introduce Dumper

Introducing dumper. And each functions add fragments unto dumper. It manages SourceMap carefully and It removes Array based code generation.

[vendethiel]

👍 I've sometimes prefered other tools to escodegen because of the bad performance when I needed fast compile-times; but my heart is here :P. This is really good news!

[stefanpenner]

Fantastic news. I know it's extra work but let me recommend a nice macro/micro performance suite. It will aid in pinpointing issues early and prevent future regressions.

Also, it promotes drive-by performance related contributions and helps build confidence that community contributions have not caused obvious regressions.

Out of curiosity why not try to unite the two projects?

[Constellation]

Out of curiosity why not try to unite the two projects?

If @inikulin is OK, I'd like to merge esotope's work into the master :)
Personally I'm now considering to create the organization for ECMAScript tools and moving escodgen into it is nice. What do you think about it?
Maybe, introducing Dumper is necessary since we need to support SourceMap.

[inikulin]

@Constellation

If @inikulin is OK, I'd like to merge esotope's work into the master

I will be happy if you do that.

I've learned some tips during this optimization which I would like to share with you. I found it surprisingly hard to optimize code generator and it was not because of the initial code quality, but because of how code generation works.

Use statement/expression generator maps instead of huge switch statements

My first intentation was to get rid of big switch statements. As you know v8's optimization unit is a function. Having two huge functions with switch statement forces it's ICs to move to polymorphic or even megamorphic states. So this functions are never optimized by Crankshaft or if they do, then they bailout quickly. So, doing this is a good starting point.

Deep call stacks

However, this optimization didn't introduced really significant performance gain. This was surprising, because this technique worked really well e.g. in parse5. I started to realize why this effect occured in code gen: parser works on plain input (string and then token stream), so parsing process doesn't involve deep call stacks. Codegen works with hierarchical input(AST), so anyway you need traverse the tree. There is no big choice here: you depth-first search or breadth-first search. My first intention was to switch to the breadth-first search. However it involved an overhead due to the increased algorithm complexity and I didn't win any performace gain with this path. So, I've tried to improve depth-first performance. Here I get rid of generateExpression and generateStatement functions because they introduced additional stack depth level for each expression/statement. To achieve this I've passed generator unit precomputated options (e.g. allowIn, directiveCtx) directly from the unit's call sites. To attach additional stuff like verbatim I just wrap raw gen units with additional functionality if specific option is enabled (https://github.com/inikulin/esotope/blob/master/esotope.js#L2163). It's still introduces additional call, but wrapper is so thin that in general v8 inlines gen unit into it, so it doesn't harm performance much. Same technique can be applied for the comments attachment (which is disabled in esotope - I was just to lazy to do that ).

Get rid of arrays

This was a tough decision and my "point of no return". escodegen uses arrays in many cases as an IR. Arrays are much slower than string then it comes to the concatenations. Unfortunately it's killed source maps support, and I don't have a good idea how to workaround it at the moment.

Reduce the amount of the strings

Strings are immutable, so each time you return string from the gen unit you end up with 2 strings internally, then it concatenated to the result you end up with 2 more additional string and so on. So I use global var to which gen unit concatenate their results directly. This gave a great performance gain, however join() func is still a nemesis for this and I don't have a good idea how to get rid of it.

Gen unit flags

The next idea was to get rid of option objects for gen units to avoid allocation of the new object for each call. So, at first I generalized all used option sets and end up having just 11 sets. Then I decided to get rid of objects and use binary flags (https://github.com/inikulin/esotope/blob/master/esotope.js#L759). Integer binary arithmetic is ultra-fast and it helped to reduce amount of code in gen units. This increased the possibility of that the gen units will be inlined, since v8 doesn't inline long functions and functions with big cummulative AST.

Microptimizations

I've also made a bunch of microoptimization. E.g. esutils isIdentifierPart checks for $ and _ codepoints first, then for the capitilized letters. Meanwhile, statistically most js vars starts with lower case letter, so reorganizing the order of the conditions (https://github.com/inikulin/esotope/blob/master/esotope.js#L759) you can end up with less comparisons and therefore achiveve perfomance gain. Also, it makes sense to have this utility functions in the main code's module. In this case they are inlined by v8. If they are into separate module they can't be inlined due to the context switch.

Please, let me know if you need any farther assistance on this.

[Constellation]

@inikulin

Awesome!!! Your assistance is really really great.
I've added you as a collaborator of escodegen. If you don't mind, please feel free to modify the code

Use statement/expression generator maps instead of huge switch statements

Yes. It seems the nice start point. I'll do this first.

Deep call stacks

It's very interesting insights. I'll investigate it more.

Get rid of arrays

Yes. This causes significant overhead I think.
To reduce this, I'm now considering introducing Dumper.
We generate code with Dumper#add and Dumper manages SourceMap and code generation.
But it still remains the idea. After low hanging fruits are done, I'll investigate it.
At this time, I'll show the design to you :)

Gen unit flags

It's very intersting. Currently, options objects are used for readability. But if it incurs significant overhead, we need to drop it and I prefer to drop it.

Microptimizations

It's very interesting.
Since it is very easy, I've reordered the comparison in esutils. estools/esutils@e40b337

If they are into separate module they can't be inlined due to the context switch.

Interesting. I need to investigate it more. It is a little problematic, but if it has very very large contribution, I'll merge esutils code into escodegen and export functions to esutils and makes esutils as stub.

[Constellation]

I've moved escodegen repository into estools organization :)
It makes contribution easier I think.

[Constellation]

Importing @inikulin 's benchmark suite into escodegen.... Good benchmark is mandatory for optimization :)

[vendethiel]

👍

[stefanpenner]

👍 collaboration makes me happy

[Constellation]

Temporary released it as 1.4.2. It ships large performance improvements.
But still there are a lot of improvements to do. I'll keep it going. (escope update is temporary done. so next, we'll update escodegen implementation)