This might be getting less interesting to the general audience, so we can take it offline if you have any more questions. I'm my initials (Keith Michael Adams) @ fb.com.
The static compiler that preceded HHVM was started in a different time; it was 2008, and the JavaScript wars were just getting started. Conventional wisdom (to anybody who hadn't worked on Self in the late '90's) was that running dynamic languages fast was just kind of a lost cause. Since the static compiler was started earlier, and was inherently a more tractable system, it was done sooner. This is something that is hard for a lot of systems people to accept, but software has time value; even if HHVM ends up being faster than the static compiler, without the two years that HPHPc has been providing 2-4x improvements, Facebook would have been less able to make products. And keep in mind, the static compiler is beating our jit at most benchmarks at this writing; improving on it will take some doing.
The only optimizations we're doing are those that bottom-up type inference makes possible; so, we can generate code that knows that strings are strings, arrays are arrays, ints are ints, doubles are doubles, etc. This doesn't sound like much, but avoiding the double-dispatch on things like $a + $b is significant. We're still using the static compiler's front-end, so all of the things it can do (e.g., CSE, constant-folding, deduplicating identical data, compile-time binding of functions and methods) we hope to "inherit" when running in production mode.
PyPy is a very interesting project, with a beautiful approach. I'd be very, very curious to see what an HHVM interpreter written in RPython could do under PyPy. Unfortunately PHP is not scheme; it is a big language, with many non-orthogonal parts, so it would be a significant effort to answer this question. If I were starting over today, I'd take a much closer look at the PyPy approach, but that is just my opinion.
> This might be getting less interesting
> to the general audience, so we can take
> it offline if you have any more questions.
This is Hacker News. I, for one, would much rather read about the nitty-gritty details of this project than debate about how great Facebook's engineers are or read another opinion on whether or not PHP is a good language for X.
I think its importend to ask everything in these threads. I often find intressting questions answer in these threads (on reddit too). For JIT fans I recomend online-stalking of Mike Pall, here on Hacker News and on reddit.
Well I think if you have a task like that a team should look into what other people where doing. Self, LuaJit, parrot, some smalltalk systems, strongtalk where all allready done or on the way in 2008. In a talk about phc (https://www.youtube.com/watch?v=kKySEUrP7LA) Paul Biggar talk about why AOT might be better then JIT. His reasoning was that the suffer from bad startup times and php is a language where the comon uscase are scripts that only run a short time.
Anyway the static compiler certantly wasn't a bad way to get some speed fast.
Getting some type in there is probebly the best thing you can do :) Where can I get some more information about tracelets. I have never seen litrature about it. Did you guys invent that yourselfs?
I have been thinking about something simular. If you have a language that is dynamic but is suited for static compiling (dylan for example). On could write a compiler that does all kinds of optimization and then spits out a bytecode that is suited for the JIT. Then at runtime you let the JIT do the rest. Im not sure if this is such a good idea because the static compiler would take away some opportunities for the JIT to do an even better job. Thoughts anybody?
Thats the problem I always have. For every language I think about how good it would work with pypy. Somebody started to work on a Clojure impmentation in pypy and I want to start hacking on that. Never having done python is holding me back a little.
More Questions:
Since how long and with how many people have you been working on HHVM?
Why is the bytecode stackbased? From what I read stackbased codes arn't really suited to JIT on a register mashine. Dose the JIT compile everything to SSA first? I think thats what Hotspot does (not sure, does anybody know?).
HHVM is a follow-on effort to the static compiler. We got started long after HPHPc was in production; I started playing around in early 2010, and three of us (Jason, myself, and Drew Paroski) started earnestly putting in full-time work in summer of 2010.
I made up the term "tracelet." Do not use it when trying to sound intelligent. It roughly means "typed basic block," though the compilation units aren't quite basic blocks, and what we're doing isn't quite tracing, and ... so we thought it would be less confusing to just make up a name. Think "little tiny traces."
The bytecode is stack-based for a couple of different reasons, but it will probably remain stack-based because of compactness. Since instructions' operands are implicit, a lot of opcodes are 1, 3, or 5 bytes long. Facebook's codebase is large enough that its sheer compiled bulk can be problematic.
The translator doesn't turn the stack into SSA, instead turning it into a graph where the nodes are instructions and the edges are their inputs/outputs. You can sort of squint at this system and call it SSA where the edges are the "single assignments."
Let me give you a discription of the compiler and then you can tell me if I understand everything correct.
You have a interpreter that for every basic block starts to record a trace. If you walk in to a basic block (or codeblock) the X-time with the same type you compile it for that type and you set a typeguard. Now everytime the interpreter goes trough there again it does a typecheck then either keeps interpreting or jumps into the compiled block. So if you have basic block in a loop you have to typecheck every time you go threw the loop.
Pretty close. Once we've translated to machine code, the interpreter doesn't do type checks; it blindly enters the translation cache for anything that has a translation, and the guards live in the tracelets themselves. The tracelets directly chain to one another in machine code, so they need embedded guards.
> The static compiler that preceded HHVM was started in a different time; it was 2008, and the JavaScript wars were just getting started. Conventional wisdom (to anybody who hadn't worked on Self in the late '90's) was that running dynamic languages fast was just kind of a lost cause.
To be fair, LuaJIT has been blazing trails in running dynamic languages fast since 2005. But maybe it wasn't well-known enough to make its way into conventional wisdom.
Of course. I have kind of a difficult line to walk here; I would like to be respectful to both the authors of the HPHPc compiler, which is a really impressive achievement, and to the many many efforts past and present at running dynamic languages. LuaJIT, various SmallTalk systems, Self systems, Erlang, HPHPc, the JVM body of work, V8,hardware-level binary translators, ... are all among the shoulders we are standing on.
All that said: I get the impression reading the comments here of an emerging misconception that "everybody knows" the right way to run these languages fast. We emphatically do not know. It is still a research problem. Heck, garbage collection, a proper subset of the problem area we're talking about here, is still pretty wide open. Given the smart people who have given decades of their career to it, we should not expect there to be a single, silver-bullet technique that cleanly maps all these dynamic languages to high-performance machine code.
So we need more than one project in the air. Some of those projects should explore whole-program analysis, like HPHPc and some of Agesen's offline work on Self, and decades of Lisp compilers. Some of them should explore runtime techniques like tracing and inline-caching. Some of them should explore unifying these approaches. We need them all.
Well purly emphatically we know nothing about compilers. Since I know what a JIT is I really like them so Im bias.
I think there has been so much work put into static compiler for lisps and other dynamic languages but there is not that much to show for it. I mean sure the lisp compilers are really fast but most of the time they get there by throwing away safty and providing typehints. While the work on self was done by one researchteam. The same with LuaJit one guy writes something for a dynamic languages and without adding typehints it starts to perform like crazy.
I think the Lisp community and the rest of the world really missed out on the JIT advantsments. Self was allready fast but Sun picked Oak (Java) to be there Weblanguage (anybody know more about that?).
WRT Self: some of Agesen's work on Self work for doing type inference on conventional, ahead-of-time compilation, and they got pretty good results this way! More interestingly, the opportunities the AOT compiler found were different than the opportunities the JIT compiler found, so there is some hope that they will combine constructively. See. e.g., http://www.cs.ucla.edu/~palsberg/paper/spe95.pdf
"This might be getting less interesting to the general audience ..."
Anything that you can say about actual engineering details at FB would certainly be of interest to many of the people at HN. Large-scale social networks are like supercomputing. Few people get to see the inside of an operation which pushes the software/hardware envelope of size and performance.
The static compiler that preceded HHVM was started in a different time; it was 2008, and the JavaScript wars were just getting started. Conventional wisdom (to anybody who hadn't worked on Self in the late '90's) was that running dynamic languages fast was just kind of a lost cause. Since the static compiler was started earlier, and was inherently a more tractable system, it was done sooner. This is something that is hard for a lot of systems people to accept, but software has time value; even if HHVM ends up being faster than the static compiler, without the two years that HPHPc has been providing 2-4x improvements, Facebook would have been less able to make products. And keep in mind, the static compiler is beating our jit at most benchmarks at this writing; improving on it will take some doing.
The only optimizations we're doing are those that bottom-up type inference makes possible; so, we can generate code that knows that strings are strings, arrays are arrays, ints are ints, doubles are doubles, etc. This doesn't sound like much, but avoiding the double-dispatch on things like $a + $b is significant. We're still using the static compiler's front-end, so all of the things it can do (e.g., CSE, constant-folding, deduplicating identical data, compile-time binding of functions and methods) we hope to "inherit" when running in production mode.
PyPy is a very interesting project, with a beautiful approach. I'd be very, very curious to see what an HHVM interpreter written in RPython could do under PyPy. Unfortunately PHP is not scheme; it is a big language, with many non-orthogonal parts, so it would be a significant effort to answer this question. If I were starting over today, I'd take a much closer look at the PyPy approach, but that is just my opinion.