Re: Optimizing simple calls in a dynamically typed language?

Christoffer Lernv wrote:
> This obviously touches on the whole "how do you get a dynamic language
> to run as fast as C" discussion. So, does anyone have any ideas or
> pointers?


Look at "polymorphic inline caches" and trace trees:


http://research.sun.com/self/papers/pics.html (the Self papers in
general are full of really interesting stuff for implementing dynamic
languages, and they are very readable)
http://andreasgal.com/2008/06/02/trace-trees-faq/


While these techniques appears to be mainly used with VM's, they can
definitively be used without them.


Polymorphic inline caches work by generating inline code for type
checks and the methods to be called at the call site. If you allow
dynamically replacing methods at runtime (like in Ruby for example)
you'd need some mechanism for identifying and invalidating the caches.


Trace trees work by instrumenting the code and tracing the control
flow. When frequently occurring loops are identified the code is
optimized (in their case by JIT'ing, but this optimization could just
as well include creating a inlined and partially unrolled native code
sequence with inline caches.


You might also want to look into the ongoing work on the new version
of the Lua JIT which make use of some of this.


Another thing to look at is to what extend your language allows
"lifting" type checks and then statically typing subtrees. That is, if
your languages semantics allows you to show that inside f(), x will
always refer to the same type, you can consider lifting the type check
for x out of f() and optionally then compile (or inline) static
versions of f() for the most likely types.


Often you can make very good guesses - i.e. what looks like integer
addition most likely is, so lifting type checks as far up as possible
and compiling static versions that use integer additions with a fully
dynamic fallback if the type check fails may be acceptable and give
very good performance for the typical case (of course at the expense
of larger code). Of course lifting type checks out of small inner
loops wherever possible is the most obvious use case.


Vidar

Return to the comp.compilers page.
Search the comp.compilers archives again.