Meeting notes: Monday, December 8th, 7pm, CubeSpace
Igal Koshevoy
together on short notice!
We had a great meeting, excellent speaker, and many first-time
attendees. There were many good questions asked too because the audience
included folks working on VMs or JIT compilers for Perl, Ruby, Smalltalk
and so on. While the presentation was not strictly on FP, it touched
upon many challenges shared by FP language implementors.
I've asked Chromatic (lead developer of Parrot) to take another set of
notes, so please defer to those in case of divergence because his
knowledge of this field is superior to mine. My notes are not direct
quotes, but are interpretations. Feel free to post corrections or additions.
PRESENTATION
Jim Blandy of Mozilla presented "Trace-Based Just-In-Time Compilation
For Highly-Dynamic Languages". The techniques presented have made major
improvements in the performance of the Mozilla SpiderMonkey JavaScript
interpreter. These techniques can be applied to many other languages.
Some techniques rely on specialized hardware and exploit its extra
memory, cores, caches and processor cycles.
Slides, bibliography, project and additional links
- Jim's homepage: http://www.red-bean.com/jimb/
- Presentation slides: http://www.red-bean.com/jimb/pdxfunc-tjit/
- TraceMonkey home: https://wiki.mozilla.org/JavaScript:TraceMonkey
- Compiling notes:
https://developer.mozilla.org/en/Building_only_SpiderMonkey
- Related article: http://andreasgal.com/2008/08/22/tracing-the-web/
Biography
Jim has spent his whole career contributing to the Free Software
movement, including GNU Emacs, Guile, GDB, EGLIBC, Mozilla, Subversion,
and others.
Caveats
Techniques discussed are relatively new and their possibilities
aren't thoroughly explored. Thus some may have edge cases that are
counterproductive and these need to be guarded against.
Performance
- "For programming languages, good performance effectively improves
expressiveness."
- Algorithms are vital. In the past, we often heard people say, "My
Perl program is faster than the C program it replaced!". This shouldn't
have been possible because Perl is written in C and thus should be
slower. However, because of Perl's built-in optimized features and
ability to easily express better algorithms, programmers were able to
easily write faster code.
- Expressiveness is vital. Programs like `grep` make it easy to
perform useful operations in seemingly inefficient ways. Thus optimizing
the way real people use programming languages is necessary.
- Humans seem to counteract each step forward in technology by
adding slow, new features, gimmicks, and sloppiness. Thus net gains in
performance are both necessary yet often short-lived.
Compiling Scheme
- Lessons have been learned from trying to write compilers for Scheme.
- Flow analysis is challenging to do with dynamic code.
- High-level type inference is needed to optimize down to underlying
types.
- Correctness may lead to inefficient implementation (e.g., using
`bignums` in loop which never needs more than an `int`).
JavaScript
- JWZ declared "WE MUST SHIP NAVIGATOR 2.0 IN TWO WEEKS!" and
Brendan Eich threw something together based on "Self" to provide scripting.
- JavaScript is standardized in the form of ECMAScript (ECMA-262).
- Competition to build a fast JavaScript interpreter is active
between Mozilla's SpiderMonkey, Apple's SquirrelFish Extreme, and
Google's V8.
- Performance is significant to users, with Apple emphasizing
"blindingly fast" as marketing message.
- SpiderMonkey is Mozilla's JavaScript library, and can be embedded
easily into other programs.
SpiderMonkey bytecode
- Jim showed JavaScript code, its resulting bytecode, and talked us
through each line.
- There are basic optimizations done to the bytecode, such as
sequencing instructions in such a way as to minimize the need for jumps.
TraceMonkey
- "Trace" + "SpiderMonkey" = "TraceMonkey", the tracing JIT stuff.
- Instruments the JavaScript interpreter to provide the tracing JIT
compiler.
- Uses Adobe's "Nanojit", from their open sourced "Tamarin" (libre)
library.
- The internals of SpiderMonkey are highly-optimized and rather
opaque. This isn't a criticism, but rather an inevitability.
Unfortunately, this also makes it hard to add optimizations into the
SpiderMonkey code directly.
- Rather than inspecting source code, the trace-based JIT compiler
observes the behavior of a program as it is executing to identify
potential optimizations.
- Not everything is JIT'ed. This minimizes the number of potential
optimizations that must be checked, focuses on the most noticeable
optimizations, and avoids tricky counterproductive traps where
"optimized" code runs more slowly than the original.
TraceMonkey generated code
- The tracer records progress through code as it's executed...
- ...and when it sees the same code about to be run the second time,
often due to a jump, it classifies the enclosed area as a loop...
- ...and compiles the bytecode collected by the tracer for this loop...
- ...and executes it the third and subsequent times.
- Larger loops are more efficient for JIT compiling, and these
larger sections of code are collected thanks to the tracer watching the
generated bytecode to locate the loops, rather than naively stopping at
function boundaries.
- Code is generated for the types that are seen, making it
inexpensive to generate code for both an `int` and `bignum`, and bail
out from `int` to a `bignum` mid-execution if there's an overflow, thus
using the more-efficient-yet-possibly-incorrect type first, and then
falling back to the less-efficient-but-always-correct type when needed.
- Loop unrolling becomes trivial with trace-based JIT compilation
because you simply keep tracing until you see a jump back to code you've
already seen, and then JIT compile it. True loop unrolling seems
unnecessary on modern hardware.
- Jim showed the assembly code produced from the bytecode from the
JavaScript, talked us through the lines, and the sections which can be
JIT compiled.
Static single assignment (SSA) form
- SSA form describes a program where every variable is assigned to
only once.
- Useful because it's possible to create a functionally-equivalent
intermediate representation of code using SSA form where a larger
section of code is identical and can be JIT compiled.
- E.g., assume that if a variable can be assigned by both the `if`
and `then` sides of a conditional, then we could create an intermediate
representation that features two versions of this variable that can be
compiled together more efficiently.
- Implementors of Java Mobile Edition used this technique to create
a fast, efficient JIT that could operate in a fraction of memory
available on a cellphone by reducing the amount of code that needed to
be compiled and stored separately.
- Generating SSA form code takes computation, but thanks to
ingenious algorithms and some extra processor cycles, it's possible to
create significantly faster code as a result.
- Further details on SSA:
http://en.wikipedia.org/wiki/Static_single_assignment_form
Tracing function calls
In-lining functions becomes easy by tracing across boundaries and
thus identifying common blocks.
Tracing virtual function calls
- JavaScript heavily relies on virtual function calls through its
prototype-based delegation. Each object is really just an associative
array (AKA dict, hash). Each method call is really just looking up an
element in the associative array and calling a function assigned to that
named element. If a method isn't found in the object, it asks the
object's prototype for the item.
- As objects are dynamically altered, their "shape" changes in terms
of their internal representation.
- The shape versions are stored in a tree to provide a way to
efficiently add properties to pre-existing shapes.
- Checking the object's shape is vital to identifying the appropriate
compiled code.
Trace trees
- Keep multiple trace paths in a common tree with branches for each
variation...
- ...and JIT compile and store optimized code in the branches...
- ...and run native code as loops are identified.
- Folding common branch tails within the tree makes it possible to
graft them back together to reduce total native code generated, vital in
situations where there can be many tails.
- Nested trees provide a way to split out code into separate trees
that can then be joined as needed to efficiently bounce execution
between a series of compiled sections.
Partial evaluation?!?
- Fancy constant propagation.
- If an object can be detected as immutable, it'd be possible to
eliminate many checks that'd be wasted checking its type.
- E.g., if you know that a variable will remain an `int` for the
duration of a loop, you don't need to have code called within the loop
checking if it's still an `int`.
Blacklisting
Some seemingly obvious optimizations turn out to be
counterproductive. Therefore, it's useful to build rules that recognize
problematic cases using blacklists to prevent any attempt to optimize them.
Garbage collection
GC throws away all JIT compiled code because the addresses and such
change. Thus knowing how the GC works and working with it is vital.
JIT in Haskell
- Value type reduction, replaces types with optimized versions
because it knows variables can't change types???
- Haskell typically replaces entire functions.
- New hot-spot optimizer can deal with smaller sections.
JIT and multiple cores
- New hardware will have more cores and using them efficiently is a
challenge.
- Linear piece of code in SSA form could easily be parallelized
efficiently if the sections are large enough.
- Demo of Squeak application on a Tilera TILE64 board with 64
processors was able to run quickly by populating core caches and
bouncing execution between them rapidly.
- Major challenges include limited bus bandwidth between cores,
dissimilar performance from various caches, varying performance between
how far hardware/software can look ahead and optimize.
- Future changes include GPGPU (General-purpose computing on
graphics processing units), where hardware like nVidia's CUDA & Tesla
(marketing slogan: "960 cores for under $9,999"), AMD's FireStream, and
Intel's Larrabee provide APIs for accessing fast, multi-core,
multi-pipeline, multi-threaded video cards that can provide superior
computing performance by offloading work from the machine's main CPU cores
- Links
- Dave Ungar presenting Squeak running on the TILE64:
http://goran.krampe.se/blog/OOPSLA/OOPSLA08-more.rdoc
- Tilera TILE64: http://www.tilera.com/products/TILE64.php
- Discussion on TILE64:
http://cuu.it-director.com/enterprise/manufacturing/content.php?cid=9766
- Larrabee: http://en.wikipedia.org/wiki/Larrabee_(GPU)
JIT in Java
- Has proven value of JIT to many by making Java way faster than it
was originally.
- ARM's Jazelle processors provide hardware-optimized execution of
some, but not all, Java bytecodes. The system can bounce a program
between an incomplete hardware implementation of the JVM to provide fast
operations, and fallback to a complete software implementation as
needed. The software gives an address to the memory address with the
bytecode to the hardware and lets it take over execution until it bails
out back to the software JVM. This caused a spontaneous outburst from an
audience member, "That's horrific on so many levels!!"
JavaScript within Firefox
More and more code is being moved into JavaScript, thus making all
this optimization more valuable, and more easily accessible.
Biggest headache
So many optimizations are being added to the code that it's tricky
to adapt TraceMonkey to these changes.
Extreme
"Stalin" was an aggressive whole-program optimizing Scheme
implementation. By analyzing the entire program during compilation, as
opposed to just bits of it during runtime, it could produce
highly-optimized executables that were often significantly faster than
those produced from hand-written C code. Unfortunately, it could take
days to create these executables.
http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation)
POST-PRESENTATION
We retired to Produce Row, discussion topics included:
- Discussion of "State of Portland Tech":
http://siliconflorist.com/2008/12/04/portland-web-innovators-portland-tech-2008-in-a-word-community/
- Discussion on OurPDX "Historical Perspective" post:
http://ourpdx.net/2008/12/a-little-historical-perspective-on-portland-tech/
- Scientific management of Type 1 Diabetes.
- Tests for determining right/left brain preference, e.g.,:
http://www.news.com.au/heraldsun/story/0,21985,22556281-661,00.html
- Psycho-olfactory quantum perfume analysis, e.g.,:
http://neurophilosophy.wordpress.com/2006/12/12/the-quantum-mechanics-of-smell/
http://neurophilosophy.wordpress.com/2006/12/12/the-quantum-mechanics-of-smell/
- What we'd see when traveling faster than speed of light.
- Sci-fi book club discussion on stories by Issac Asimov, Larry
Niven, etc.
- Much more.
Jim Blandy
> A huge thanks to Jim for the excellent presentation that he pulled
> together on short notice!
Thanks --- I had a great time!
The notes look great in general, but there was one part where I didn't
get across what I'd intended:
> Static single assignment (SSA) form
> - SSA form describes a program where every variable is assigned to
> only once.
> - Useful because it's possible to create a functionally-equivalent
> intermediate representation of code using SSA form where a larger
> section of code is identical and can be JIT compiled.
> - E.g., assume that if a variable can be assigned by both the `if`
> and `then` sides of a conditional, then we could create an intermediate
> representation that features two versions of this variable that can be
> compiled together more efficiently.
> - Implementors of Java Mobile Edition used this technique to create
> a fast, efficient JIT that could operate in a fraction of memory
> available on a cellphone by reducing the amount of code that needed to
> be compiled and stored separately.
> - Generating SSA form code takes computation, but thanks to
> ingenious algorithms and some extra processor cycles, it's possible to
> create significantly faster code as a result.
> - Further details on SSA:
> http://en.wikipedia.org/wiki/Static_single_assignment_form
Here's what I was trying to say:
Once a program has been put in Static Single Assignment form, many
optimizations become much easier. There are many papers describing
optimizations that begin, "First, put the code in SSA form. Then..."
It's been known for quite a while that, if you could get a program
into SSA form, then you'd be in a good position, but SSA still wasn't
widely used even in highly optimizing, traditional ahead-of-time
compilers because there was no good algorithm for getting code into
SSA in the first place. In 1991, Ron Cytron et al found a good
algorithm (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8240),
and SSA has since become widely used. However, even Cytron's
algorithm is a bit heavy for embedded devices, and I don't believe
it's widely used there.
The reason I brought up SSA at the talk is that, by their nature,
tracing JITs only compile either single loop traces, or trace trees
--- not arbitrary control flow graphs. This restriction happens to
mean that it is always trivial to put code traces in SSA --- the cases
that make Cytron's algorithm necessary simply don't arise. Thus, we
can apply SSA-based optimizations without incurring the cost of
converting to SSA. If, in the future, our trace collection techniques
became more sophisticated and we began to collect traces that were
more general in shape (not just trees whose leaves jump back to the
root), then it might become expensive to put the tree in SSA, and we'd
be in the same position as everyone else. We're just protected at the
moment by our naivete.
So: SSA is a technique that (since 1991, anyway) is very practical for
use in ahead-of-time compilers with lots of room (memory, time). It
is not, in its general form, practical on mobile devices, as far as I
know. However, because we compile traces, not source programs, it
happens to be trivial for us to put code in SSA form, so we can take
advantage of its properties.
Igal Koshevoy
Thanks for the clarification!
-igal