[pypy-dev] pypy for typed languages?

[Paolo Giarrusso]

On Fri, Mar 13, 2009 at 16:48, Geoffrey Irving <irving at naml.us> wrote:
> On Fri, Mar 13, 2009 at 11:19 AM, Maciej Fijalkowski <fijall at gmail.com> wrote:
>> On Fri, Mar 13, 2009 at 3:04 PM, Geoffrey Irving <irving at naml.us> wrote:
>>> On Fri, Mar 13, 2009 at 7:13 AM, Armin Rigo <arigo at tunes.org> wrote:
>>>>> In particular, what restrictions does pypy impose on storage layout?
>>>>> For example, would it be able to handle dynamically-typed homogeneous
>>>>> lists, represented as a single pointer to a type object and an array
>>>>> of structs required to be of that type?
>>>>
>>>> RPython doesn't have support for this.  If you go directly to the lltype
>>>> type system, then it's possible -- but our current JIT generator doesn't
>>>> support it.  And also, if you write an interpreter using the lltype type
>>>> system directly, you loose the abstraction level of writing an
>>>> interpreter in RPython in the first place -- e.g. it would not be
>>>> translatable any more to the ootype type system, thus to Java or CLI.
>>>>
>>>> So all in all, PyPy could probably be subverted to do what you want, but
>>>> it's not really meant to (and we are a bit unlikely to give much
>>>> support, as far as I can see).
>>>
>>> Thanks for the reply.  It seems like targeting LLVM directly is the
>>> way to go for such projects for now.
>>
>> I don't know, do you have any example?
>
> At this point I'm just in the curiosity stage, so I don't have a
> concrete example.  Roughly, I'm imagining a language based on System
> CT [1] or the like, which is somewhat like duck typing for static
> languages with homogeneous data structures.  Since all function can be
> overloaded, at runtime functions would pass around large dictionaries
> of overloads, which would need to be optimized away via JIT for
> reasonable speed.

What is your plan for optimizing those? Are you already planning to
use inline caching for that (what I describe below)?

> A JIT would have an easier job on a System CT-like language than with
> python or java, due to the guarantee of homogeneity.  For example, in
> the sum function
>
> def sum(container):
>    sum = zero
>    for elem in container:
>        sum = sum + elem
>    return sum
>
> a language with homogeneous containers knows that "+" is constant
> throughout the loop even if it is impossible to know which constant it
> is in advance.

That can be useful, but in modern JIT that's maybe not the key point,
although you can surely make also use of that.

Most JIT have a heuristic solution which optimizes late binding
anyway, without semantic restrictions, through inline caching or
aggressive inlining - around 90% percent of call sites always call the
same actual method (i.e. they are monomorphic), so code similar to:
if (dest->type == ACertainType)
  ACertainType::method(args); //Early bound call, possibly inlined.
else
  dest->method(args); //Late bound call
can be generated by the JIT. This avoids the indirect jump in most
cases. I'm omitting various details needed to make it actually go
fast, but they're described in the literature.

For that case, it'd be likely better to inline that function into the
caller to get monomorphic call sites (and by any standard that
function should be small enough for that).

Having a constant '+' doesn't help so much if it can have any value.
You save a complete method lookup over a hierarchy, in the Python case
(or in Java with inteface methods), but you still have a call through
a function pointer, which can be quite slow; applying the above
technique

Implementing the above idea in generated JVM bytecode made a
Jython-like JIT compiler for Python, written by another student at the
course, be much faster than CPython (they reported speedups of at
least 3x to 5x, with much room for improvements).

I think also PyPy does something similar for Python, but only through
a hash table. I'd love to see how much inline caching would help on
top of that, when I'll have time to start working on this.

Regards
-- 
Paolo Giarrusso