6 ms·

How JavaScript compilers work

95 points by wx196 13y ago

deweerdt 13y ago
The 4 parts: - The JavaScript family tree: http://creativejs.com/2013/06/the-race-for-speed-part-1-the-javascript-engine-family-tree&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-1-the-...; - How compilers work: http://creativejs.com/2013/06/the-race-for-speed-part-2-how-javascript-compilers-work&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-2-how-...; - JavaScript compiler strategies: http://creativejs.com/2013/06/the-race-for-speed-part-3-javascript-compiler-strategies&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-3-java...; - The future for JavaScript: http://creativejs.com/2013/06/the-race-for-speed-part-4-the-future-for-javascript&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-4-the-...;
- imissmyjuno 13y ago
  Looks like the server is under fire, and Google didn't cache any of those links, either. Tears of desire.
WalterBright 13y ago
Source for a JavaScript compiler implemented in the D programming language: https://github.com/DigitalMars/DMDScript https://github.com/DigitalMars/DMDScript
- thejsjunky 13y ago
  Nice. Interested readers may also want to check out Higgs: https://github.com/maximecb/Higgs https://github.com/maximecb/Higgs
leetrout 13y ago
So I have question I'm sure someone here is smart enough to answer- simply put, does ASI affect compilation speed? In my head I would imagine that a compiler would expect to find semicolons as statement terminators but would have to reprocess a block if validation failed and try to figure out where the semicolons should be, and therefore ASI would slow down compilation (vs a file with all semicolons in place).
- Arelius 13y ago
  Obviously it takes some extra cycles to perform ASI. Now, having said that I doubt any additional passes on the source are done to perform ASI. I suspect that if it is of any significance, they have folded it into another pass. And the code likely runs even if not all the semicolons are already in the right place, so it'd be a sunk cost in that regard. Having said that, I'm, sure it's such a small amount of the compilation time to be pretty insignificant. This is all however based on my professional experience writing parsers, and not on any specific knowledge of the workings of Javascript however.
- WalterBright 13y ago
  No.
  - klibertp 13y ago
    You mean "no, no one here is smart enough"? If it's "no" answer to semicolon insertion affecting compilation speed your post could use some explaining.
    - WalterBright 13y ago
      > does ASI affect compilation speed? No.
- chc 13y ago
  Why would you expect that to be true in JavaScript any more than other semicolon-optional languages like Ruby and Python? You just write your parser to accept both line endings (that meet certain conditions) and semicolons as statement terminators. Going through and literally inserting semicolons shouldn't be necessary.
  - millstone 13y ago
    I don't know how this is done in JavaScript, but in Go, semicolons are emitted by the lexer, so they really are literally inserted.
rayiner 13y ago
The terminology in the article is somewhat idiomatic: "After the Directed Flow Graph (DFG) or syntax tree has been generated the compiler can use this knowledge to perform further optimisations prior to the generation of machine code. Mozilla’s IonMonkey and Google’s Crankshaft are examples of these DFG compiler." "DFG" usually refers to some sort of dependence graph. What IonMonkey and Crankshaft have is a traditional CFG (control flow graph) in SSA form. That means the code is represented as a set of straight line code paths (basic blocks) connected edges in a graph representing possible control-flow transitions. The instructions are in SSA form, which means that each variable is assigned only once and pseudo-instructions called "phi instructions" are used to merge results when a basic block is accessible from multiple predecessors blocks, both of which might assign the same variable. A "syntax tree" is different yet. It's a higher level representation that preserves the syntactic structure of the code. For example, it represents loops and "if" statements as nested elements in the tree. Translation to a CFG throws away most of that information (e.g. reducing loops to simply control flow edges in the CFG). For a (relatively) approachable set of materials on the subject, see: http://www.cs.rice.edu/~keith/512/2011/Lectures http://www.cs.rice.edu/~keith/512/2011/Lectures. I also highly recommend Cooper & Torczon's "Engineering a Compiler" (2d Ed.) In a world of CS researchers that can't write an English sentence to save their lives, Keith Cooper and Linda Torczon's work is a paragon of clear prose. (Their lab at Rice is where Cliff Click got his PhD, and if you've read his work on the JVM, you know that he too has a talent for explaining complicated concepts in plain English.)
- dman 13y ago
  I am in awe of your ability to stay informed on multiple fields - economics to compilers to lisp.
  - tptacek 13y ago
    None of which are even his day job!
    - clicks 13y ago
      He is truly HN's shiniest jewel. I especially like he doesn't give a damn about karma points and sticks to his guns argues in an intellectually honest manner no matter what.
acqq 13y ago
A very nice text with the nice code examples is: http://mrale.ph/blog/2012/06/03/explaining-js-vms-in-js-inline-caches.html http://mrale.ph/blog/2012/06/03/explaining-js-vms-in-js-inli...
- thejsjunky 13y ago
  If anyone wants to delve more into the workings of a JS VM, I've found the code of Higgs (https://github.com/maximecb/Higgs https://github.com/maximecb/Higgs) to be very straightforward and readable. The interpreter and JIT are written in D and much of the run-time is written in JS. It's a successor to the Tachyon project mentioned in that post.
frozenport 13y ago
How is the JavaScript JIT different from the Java JIT?

95 points by wx196 13y ago

The 4 parts: - The JavaScript family tree: http://creativejs.com/2013/06/the-race-for-speed-part-1-the-javascript-engine-family-tree&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-1-the-...; - How compilers work: http://creativejs.com/2013/06/the-race-for-speed-part-2-how-javascript-compilers-work&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-2-how-...; - JavaScript compiler strategies: http://creativejs.com/2013/06/the-race-for-speed-part-3-javascript-compiler-strategies&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-3-java...; - The future for JavaScript: http://creativejs.com/2013/06/the-race-for-speed-part-4-the-future-for-javascript&#x2F http://creativejs.com/2013/06/the-race-for-speed-part-4-the-...;

imissmyjuno 13y ago
Looks like the server is under fire, and Google didn't cache any of those links, either. Tears of desire.

WalterBright 13y ago

Source for a JavaScript compiler implemented in the D programming language: https://github.com/DigitalMars/DMDScript https://github.com/DigitalMars/DMDScript

thejsjunky 13y ago
Nice. Interested readers may also want to check out Higgs: https://github.com/maximecb/Higgs https://github.com/maximecb/Higgs

leetrout 13y ago

So I have question I'm sure someone here is smart enough to answer- simply put, does ASI affect compilation speed? In my head I would imagine that a compiler would expect to find semicolons as statement terminators but would have to reprocess a block if validation failed and try to figure out where the semicolons should be, and therefore ASI would slow down compilation (vs a file with all semicolons in place).

Arelius 13y ago
Obviously it takes some extra cycles to perform ASI. Now, having said that I doubt any additional passes on the source are done to perform ASI. I suspect that if it is of any significance, they have folded it into another pass. And the code likely runs even if not all the semicolons are already in the right place, so it'd be a sunk cost in that regard. Having said that, I'm, sure it's such a small amount of the compilation time to be pretty insignificant. This is all however based on my professional experience writing parsers, and not on any specific knowledge of the workings of Javascript however.
WalterBright 13y ago
No.
- klibertp 13y ago
  You mean "no, no one here is smart enough"? If it's "no" answer to semicolon insertion affecting compilation speed your post could use some explaining.
  - WalterBright 13y ago
    > does ASI affect compilation speed? No.
chc 13y ago
Why would you expect that to be true in JavaScript any more than other semicolon-optional languages like Ruby and Python? You just write your parser to accept both line endings (that meet certain conditions) and semicolons as statement terminators. Going through and literally inserting semicolons shouldn't be necessary.
- millstone 13y ago
  I don't know how this is done in JavaScript, but in Go, semicolons are emitted by the lexer, so they really are literally inserted.

rayiner 13y ago

The terminology in the article is somewhat idiomatic: "After the Directed Flow Graph (DFG) or syntax tree has been generated the compiler can use this knowledge to perform further optimisations prior to the generation of machine code. Mozilla’s IonMonkey and Google’s Crankshaft are examples of these DFG compiler." "DFG" usually refers to some sort of dependence graph. What IonMonkey and Crankshaft have is a traditional CFG (control flow graph) in SSA form. That means the code is represented as a set of straight line code paths (basic blocks) connected edges in a graph representing possible control-flow transitions. The instructions are in SSA form, which means that each variable is assigned only once and pseudo-instructions called "phi instructions" are used to merge results when a basic block is accessible from multiple predecessors blocks, both of which might assign the same variable. A "syntax tree" is different yet. It's a higher level representation that preserves the syntactic structure of the code. For example, it represents loops and "if" statements as nested elements in the tree. Translation to a CFG throws away most of that information (e.g. reducing loops to simply control flow edges in the CFG). For a (relatively) approachable set of materials on the subject, see: http://www.cs.rice.edu/~keith/512/2011/Lectures http://www.cs.rice.edu/~keith/512/2011/Lectures. I also highly recommend Cooper & Torczon's "Engineering a Compiler" (2d Ed.) In a world of CS researchers that can't write an English sentence to save their lives, Keith Cooper and Linda Torczon's work is a paragon of clear prose. (Their lab at Rice is where Cliff Click got his PhD, and if you've read his work on the JVM, you know that he too has a talent for explaining complicated concepts in plain English.)

dman 13y ago
I am in awe of your ability to stay informed on multiple fields - economics to compilers to lisp.
- tptacek 13y ago
  None of which are even his day job!
  - clicks 13y ago
    He is truly HN's shiniest jewel. I especially like he doesn't give a damn about karma points and sticks to his guns argues in an intellectually honest manner no matter what.

acqq 13y ago

A very nice text with the nice code examples is: http://mrale.ph/blog/2012/06/03/explaining-js-vms-in-js-inline-caches.html http://mrale.ph/blog/2012/06/03/explaining-js-vms-in-js-inli...

thejsjunky 13y ago
If anyone wants to delve more into the workings of a JS VM, I've found the code of Higgs (https://github.com/maximecb/Higgs https://github.com/maximecb/Higgs) to be very straightforward and readable. The interpreter and JIT are written in D and much of the run-time is written in JS. It's a successor to the Tachyon project mentioned in that post.

frozenport 13y ago

How is the JavaScript JIT different from the Java JIT?