pypy for typed languages?
Hello, I've come to the conclusion that JIT compilation is essential to avoid abstract penalties even for typed languages. The one sentence summary is that the C++ inline keyword is exactly the opposite of what you want: in a JIT language you can have a "flatten" function that recursively inlines everything that a function calls (including closures). Thus, I'm curious about whether pypy could be practically applied to a typed front end language, say with the following basic set of features: 1. Packed storage such as C structs and arrays. 2. A Hindley Milner polymorphic type system with type classes. 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? Also, if pypy can target LLVM, how do you imagine the two JIT systems cooperating (if at all)? Thanks! Geoffrey
(sorry Geoffrey for the missend) 2009/3/13 Geoffrey Irving <irving@naml.us>:
Hello, Hi! and welcome.
2. A Hindley Milner polymorphic type system with type classes.
I'll leave it to someone with a better knowledge of how the JIT takes advantage of types to answer this. William Leslie
Hi Geoffrey, On Thu, Mar 12, 2009 at 08:57:21PM -0400, Geoffrey Irving wrote:
I've come to the conclusion that JIT compilation is essential to avoid abstract penalties even for typed languages.
Indeed: our approach to JIT compilation was first tried with machine code (see Dynamo/DynamoRio) and then with Java.
I suppose you can try. For a direct application you need a language for which it makes sense to write an interpreter in RPython.
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).
Also, if pypy can target LLVM, how do you imagine the two JIT systems cooperating (if at all)?
That's a longer-term goal, but I can easily imagine that the code produced by our JIT could be sent to LLVM at runtime for further optimizations. A bientot, Armin.
On Fri, Mar 13, 2009 at 11:19 AM, Maciej Fijalkowski <fijall@gmail.com> wrote:
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. 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. Geoffrey [1] http://homepages.dcc.ufmg.br/~camarao/CT
On Fri, Mar 13, 2009 at 16:48, Geoffrey Irving <irving@naml.us> wrote:
What is your plan for optimizing those? Are you already planning to use inline caching for that (what I describe below)?
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
Hi Armin, On Sat, Mar 14, 2009 at 18:52, Armin Rigo <arigo@tunes.org> wrote:
Hi Paolo,
I was thinking about the method cache in the interpreter; I'm not yet familiar with the approaches you used for JIT compilation (neither the one of PyPy 1.0 nor the one being prototyped right now), but I know the general purpose "get a JIT from an interpreter", and I thought that having a matching behaviour implied using the same lookup algorithm in JITted code. I understand that's no more true, with the ideas of trace-based JITs. Greetings, -- Paolo Giarrusso
Hi Paolo, On Mon, Mar 23, 2009 at 11:46:29AM +0100, Paolo Giarrusso wrote:
Ah, sorry. I may have misread your original post. The fact is that both the PyPy 1.0 JIT and the current prototype JIT (and all other prototypes inbetween) are similar, in that they are derived automatically from the interpreter. If this interpreter happens to contain a hash table lookup, as the Python interpreter of PyPy optionally does, then the JIT will contain it too. So we are left with experimenting with which interpreter features are useful for the JIT too, and which ones give bad results. This experimentation is both easy and not quite doable right now because we are still developping the JIT generation basics. A bientot, Armin.
(sorry Geoffrey for the missend) 2009/3/13 Geoffrey Irving <irving@naml.us>:
Hello, Hi! and welcome.
2. A Hindley Milner polymorphic type system with type classes.
I'll leave it to someone with a better knowledge of how the JIT takes advantage of types to answer this. William Leslie
Hi Geoffrey, On Thu, Mar 12, 2009 at 08:57:21PM -0400, Geoffrey Irving wrote:
I've come to the conclusion that JIT compilation is essential to avoid abstract penalties even for typed languages.
Indeed: our approach to JIT compilation was first tried with machine code (see Dynamo/DynamoRio) and then with Java.
I suppose you can try. For a direct application you need a language for which it makes sense to write an interpreter in RPython.
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).
Also, if pypy can target LLVM, how do you imagine the two JIT systems cooperating (if at all)?
That's a longer-term goal, but I can easily imagine that the code produced by our JIT could be sent to LLVM at runtime for further optimizations. A bientot, Armin.
On Fri, Mar 13, 2009 at 11:19 AM, Maciej Fijalkowski <fijall@gmail.com> wrote:
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. 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. Geoffrey [1] http://homepages.dcc.ufmg.br/~camarao/CT
On Fri, Mar 13, 2009 at 16:48, Geoffrey Irving <irving@naml.us> wrote:
What is your plan for optimizing those? Are you already planning to use inline caching for that (what I describe below)?
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
Hi Armin, On Sat, Mar 14, 2009 at 18:52, Armin Rigo <arigo@tunes.org> wrote:
Hi Paolo,
I was thinking about the method cache in the interpreter; I'm not yet familiar with the approaches you used for JIT compilation (neither the one of PyPy 1.0 nor the one being prototyped right now), but I know the general purpose "get a JIT from an interpreter", and I thought that having a matching behaviour implied using the same lookup algorithm in JITted code. I understand that's no more true, with the ideas of trace-based JITs. Greetings, -- Paolo Giarrusso
Hi Paolo, On Mon, Mar 23, 2009 at 11:46:29AM +0100, Paolo Giarrusso wrote:
Ah, sorry. I may have misread your original post. The fact is that both the PyPy 1.0 JIT and the current prototype JIT (and all other prototypes inbetween) are similar, in that they are derived automatically from the interpreter. If this interpreter happens to contain a hash table lookup, as the Python interpreter of PyPy optionally does, then the JIT will contain it too. So we are left with experimenting with which interpreter features are useful for the JIT too, and which ones give bad results. This experimentation is both easy and not quite doable right now because we are still developping the JIT generation basics. A bientot, Armin.
participants (5)
-
Armin Rigo -
Geoffrey Irving -
Maciej Fijalkowski -
Paolo Giarrusso -
William Leslie