Psyco Specializing Compiler

[Armin Rigo]

Hello Terry,

On Thu, 11 Oct 2001, Terry Reedy wrote:
> An interesting project.  If I understand properly, you are dynamically
> compiling small chunks of PyCode to machine code according to the
> actual run-time type of the values involved in the chunk.

That's only part of the story. The specialization can actually occur on
anything, not only on the type of the Python objects --- althought it will
probably be the most common case. An example of specialization over
something else would be when using constants; e.g. in code like 'x=1;
x+=2' the addition is performed at compile-time, because 'x+=2' can be
specialized for the only case that might occur, that is, when 'x' is
currently equal to '1'.

> You say that your system saves the compiled machine code for a
> function, after the function exits, for later reuse.   Are the saved
> chunks tagged with the specific types used in the compilation, so the
> the system will recompile a function if/when entered with different
> types?

Yes, that's how we can think about it, althought more general than just on
types. For example in a function call, say 'f(x)', Psyco can use the
current specializations of 'x' to recompile 'f'. If we know that 'x', say,
is an int, look for a version of 'f' specialized for ints. If we know that
'x' is zero, 'f(x)' can be recompiled by knowing that the argument will be
exactly '0'. This means one of the big benefits of inlining in C --
constant folding -- is also available. Interestingly enough, we have this
benefit without the drawback of code explosion, because several calls to
'f(0)' can still call the same code. Removing the overhead of the 'call'
instruction itself could be done later, e.g. by tagging which blocks of
code are small and self-contained enough for inlining by copy.

> While aiming for completeness is good, speeding up just arithmetic
> functions would be an important contribution.  You might consider
> making explicit assumptions that programmers using your system do not
> pathologically rebind variables.  For instance, tail recursion
> elimination requires that the name of the recursing function not be
> rebound to anything else during the recursion.

I will certainly make such assumptions at first; for completeness,
pathological rebinds could be detected e.g. by enhancing dictionaries to
signal when they are modified, letting Psyco know that the compiled code
has become invalid. Such solutions would not slow down at all the
generated code in the common case.  It would also let the value of global
constants be inlined; if a global variable's value changes later, we
invalidate the produced code and mark the variable as run-time instead of
compile-time-known.


Armin