I agree - same reason Rubinius will probably be the future of Ruby.
Smalltalk has been around forever and one of Smalltalk's strengths is that most of the implementation is in Smalltalk itself.
When I first got into Ruby I kept the implementation handy and a Textmate project set up for all installed Ruby gems to make it easy to read through the code. Rubinius makes it easier to read the implementation code. I installed Rubinius using an OS X installer, but then went back and installed the source code.
>Smalltalk has been around forever and one of Smalltalk's strengths is that most of the implementation is in Smalltalk itself.
I think LISP is a good thing to look at as well. Even though it's not that efficient to write the implementation of LISP in LISP, it's practically possible with 37 operators. There has to be something with these languages where you can write the language in itself.
To be completely honest, I'm somewhat astonished that speed is one of the reasons to write the core in itself: Usually you would think it would be a reason to write it in a low level language.
> To be completely honest, I'm somewhat astonished that speed is one of the reasons to write the core in itself: Usually you would think it would be a reason to write it in a low level language.
Clever beats just fast? I think the idea behind PyPy is that the high-level language is more flexible, and allows trying many different approaches, rather than heavily optimizing one or two possibly sub-optimal approaches in a low-level language.
Also, if you write the core in the language itself, when you improve your optimizations, you speed the core up too.
A good optimizing compiler almost always beats hand coded assembly language. It is difficult for a programmer to keep track of what is going on in his code: instruction timing, register allocation and locking, pipelined multiple instruction execution, instruction optimization, global optimization, on and on. JIT can do even better.
I've done hand optimization of RISC assembly. It's fun, but nowhere near as productive as productive as coding in Python, or C for that matter.
Modern processors may be to blame for that. Out of order execution, register renaming and speculative execution are very hard to wrap your head around.
That's what I liked about the 6502 - very simple, very direct and somewhat RISC-ish. Not many ways to do something. It is said the ARM was very 6502 influenced, but I never worked with it on a low level.
The other thing I liked about the 6502 was that I was flying under the OS all the time on those machines. Dealing with the OS at the machine-language-level is usually painful.
I think you are overestimating the current capabilities of JIT's.
Also, unfortunately, current compilers are notoriously bad at generating code with special instructions (vectorized code).
So in the end applications that need to be really fast end up being written in assembly, or carefully written fortran and C code to generate a particular assembly.
Last I heard, there were some quirks in matching the memory model between C and Python which caused excessive paging (?) that PyPy can avoid. Can't find the reference, but maybe it's a clue to help you look.
It seems like eventually it should be the JIT that will make it faster. Not only that, the JIT compiler is itself automatically generated. That is black magic indeed!
When PyPy is translated into an executable like pypy-c, the executable contains a full virtual machine that can optionally include a Just-In-Time compiler. This JIT compiler is generated automatically from the interpreter that we wrote in RPython.
This JIT Compiler Generator can be applied on interpreters for any language, as long as the interpreter itself is written in RPython and contains a few hints to guide the JIT Compiler Generator.
the JIT compiler is itself automatically generated
Indeed it is. Compiling took 9000s on a 2GHz Dual Core Athlon with 2GB RAM. Don't even try to compile it on a machine with 1GB RAM, your system will start trashing heavily and finish sometimes between next week and never. </rant>
But after downloading the binaries, I have to say: Wow! One of my naive project euler solution is about 3-4 times faster than it was using Psyco. Absolutely impressive. (Numbers: ~66s Python 2.6, ~8.6s Psyco, ~2.8s PyPy)
I just tried it. On first start up (when the 13MB pypy executable has to be loaded into memory), it's slightly slower. About 0.5 to 1.0 seconds, I'd guess.
My highly scientific benchmarks (time python -c "pass") give no noticeable difference, with pypy starting in between 0.015s and 0.020s and Python 2.6 starting in 0.022s to 0.028s.
All of this is on a 1.6GHz C2D, 1GB RAM, Arch Linux 32 bit.
13MB? Seems like a lot. I think the full IDE, plus version control and all base libraries fits into a 14MB VisualWorks Smalltalk image. (Plus, if you disabled the splash screen and herald WAV, it would start faster than Perl 5.) Executable used to be way smaller than 1MB.
Basically, RPython fills the role of a concrete semantics of Python, and then they write functions that can convert that concrete semantics to other forms - for example, a JIT compiler that when run generates x86 machine code with the same semantics as the interpreter.
It's a very powerful technique that can generate all sorts of information about the program, much of which can then feed back into the compiler to direct further optimization. For example, you can model typechecking as an abstract interpretation that maps values to their types. You can model type inference as typechecking plus a substitution that maps type variables to concrete (or generalized) types. You can model Haskell-style typeclasses as type inference plus a list of predicates on every expression labeling the possible typeclasses that the type may belong to.
When you don't have to babysit C, you get to spend your time improving the actual application you are trying to write. This makes for a better application.
What does it mean for Unladen Swallow? Can they both be used together? If Unladen Swallow merged into Python 3, then when using PyPy will one get a performance boost from both?
I'm kind of not so surprised there are 19 olds in PyPy team. This is a project that requires idealism and enthousiasm: "let's build python in python, compile to everything possible, and make it faster than cpython". Contrast this to the more pragmatic approach of unladen swallow. I envy this guy even now!
He's definitely working on cooler projects than I was when I was 19, but I dunno if he's more productive. When I was 19, we took a dot-com from conception to launch in 1.5 months, lost our funding and shut it down 2 months later, then I got folded into the parent company (a VC-funded startup) for the remainder of the year and went through about 4 different business plans.
It's the 10 years since then (and particularly what I did - or rather didn't do - in college) that makes me depressed. :-/
I like this little bit about how the first self-hosting lisp compiler was created:
"The first self-hosting compiler (excluding assemblers) was written for Lisp by Hart and Levin at MIT in 1962. They wrote a Lisp compiler in Lisp, testing it inside an existing Lisp interpreter. Once they had improved the compiler to the point where it could compile its own source code, it was self-hosting.[4]
The compiler as it exists on the standard compiler tape is a machine language program that was obtained by having the S-expression definition of the compiler work on itself through the interpreter. (AI Memo 39)" -- http://en.wikipedia.org/wiki/Bootstrapping_%28compilers%29#H...
Another way to show that LISP was neater than Turing machines was to write a universal LISP function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function eval[e,a], which computes the value of a LISP expression e - the second argument a being a list of assignments of values to variables. (a is needed to make the recursion work). Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice. Logical completeness required that the notation used to express functions used as functional arguments be extended to provide for recursive functions, and the LABEL notation was invented by Nathaniel Rochester for that purpose. D.M.R. Park pointed out that LABEL was logically unnecessary since the result could be achieved using only LAMBDA - by a construction analogous to Church's Y-operator, albeit in a more complicated way.
S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.
The unexpected appearance of an interpreter tended to freeze the form of the language, and some of the decisions made rather lightheartedly for the ``Recursive functions ...'' paper later proved unfortunate. These included the COND notation for conditional expressions which leads to an unnecessary depth of parentheses, and the use of the number zero to denote the empty list NIL and the truth value false. Besides encouraging pornographic programming, giving a special interpretation to the address 0 has caused difficulties in all subsequent implementations.
- takes source code in one language as an input, and
- turns the input into an assembly language output.
Now, ignoring the specifics of the input language and whether the assembly output is in fact bytecode for some interpreter or JIT compiler, or machine code for a CPU, this is a quite well-specified procedure.
Such a feat can surely be accomplished in any language. Source code in, binary instructions out—how hard is that?
If the input happens to be the compiler source code itself, that doesn't really matter. The same translation occurs.
If the language used to write the compiler is the same as the compiler itself takes as input, that doesn't really matter.
42 comments
[ 2.1 ms ] story [ 97.4 ms ] threadSmalltalk has been around forever and one of Smalltalk's strengths is that most of the implementation is in Smalltalk itself.
When I first got into Ruby I kept the implementation handy and a Textmate project set up for all installed Ruby gems to make it easy to read through the code. Rubinius makes it easier to read the implementation code. I installed Rubinius using an OS X installer, but then went back and installed the source code.
I think LISP is a good thing to look at as well. Even though it's not that efficient to write the implementation of LISP in LISP, it's practically possible with 37 operators. There has to be something with these languages where you can write the language in itself.
To be completely honest, I'm somewhat astonished that speed is one of the reasons to write the core in itself: Usually you would think it would be a reason to write it in a low level language.
Can anyone elaborate on this?
Also, if you write the core in the language itself, when you improve your optimizations, you speed the core up too.
speed.pypy.org gives a timeout for me
I've done hand optimization of RISC assembly. It's fun, but nowhere near as productive as productive as coding in Python, or C for that matter.
That's what I liked about the 6502 - very simple, very direct and somewhat RISC-ish. Not many ways to do something. It is said the ARM was very 6502 influenced, but I never worked with it on a low level.
The other thing I liked about the 6502 was that I was flying under the OS all the time on those machines. Dealing with the OS at the machine-language-level is usually painful.
Also, unfortunately, current compilers are notoriously bad at generating code with special instructions (vectorized code).
So in the end applications that need to be really fast end up being written in assembly, or carefully written fortran and C code to generate a particular assembly.
Sounds like the downfall of the Itanium. They promised that the compilers would make it all usable, but the compilers never showed up.
Here is the summary in their own words: (http://codespeak.net/pypy/dist/pypy/doc/jit/index.html)
---
When PyPy is translated into an executable like pypy-c, the executable contains a full virtual machine that can optionally include a Just-In-Time compiler. This JIT compiler is generated automatically from the interpreter that we wrote in RPython.
This JIT Compiler Generator can be applied on interpreters for any language, as long as the interpreter itself is written in RPython and contains a few hints to guide the JIT Compiler Generator.
---
Indeed it is. Compiling took 9000s on a 2GHz Dual Core Athlon with 2GB RAM. Don't even try to compile it on a machine with 1GB RAM, your system will start trashing heavily and finish sometimes between next week and never. </rant>
But after downloading the binaries, I have to say: Wow! One of my naive project euler solution is about 3-4 times faster than it was using Psyco. Absolutely impressive. (Numbers: ~66s Python 2.6, ~8.6s Psyco, ~2.8s PyPy)
My highly scientific benchmarks (time python -c "pass") give no noticeable difference, with pypy starting in between 0.015s and 0.020s and Python 2.6 starting in 0.022s to 0.028s.
All of this is on a 1.6GHz C2D, 1GB RAM, Arch Linux 32 bit.
http://en.wikipedia.org/wiki/Abstract_interpretation
Basically, RPython fills the role of a concrete semantics of Python, and then they write functions that can convert that concrete semantics to other forms - for example, a JIT compiler that when run generates x86 machine code with the same semantics as the interpreter.
It's a very powerful technique that can generate all sorts of information about the program, much of which can then feed back into the compiler to direct further optimization. For example, you can model typechecking as an abstract interpretation that maps values to their types. You can model type inference as typechecking plus a substitution that maps type variables to concrete (or generalized) types. You can model Haskell-style typeclasses as type inference plus a list of predicates on every expression labeling the possible typeclasses that the type may belong to.
When you don't have to babysit C, you get to spend your time improving the actual application you are trying to write. This makes for a better application.
"let's build python in python, compile to everything possible, and make it faster than cpython" are all examples of that.
I wish I spend my childhood learning programming and all sort of cool stuff.
It's the 10 years since then (and particularly what I did - or rather didn't do - in college) that makes me depressed. :-/
"The first self-hosting compiler (excluding assemblers) was written for Lisp by Hart and Levin at MIT in 1962. They wrote a Lisp compiler in Lisp, testing it inside an existing Lisp interpreter. Once they had improved the compiler to the point where it could compile its own source code, it was self-hosting.[4]
The compiler as it exists on the standard compiler tape is a machine language program that was obtained by having the S-expression definition of the compiler work on itself through the interpreter. (AI Memo 39)" -- http://en.wikipedia.org/wiki/Bootstrapping_%28compilers%29#H...
Near the end of http://www-formal.stanford.edu/jmc/history/lisp/node3.html#S... we find:
Another way to show that LISP was neater than Turing machines was to write a universal LISP function and show that it is briefer and more comprehensible than the description of a universal Turing machine. This was the LISP function eval[e,a], which computes the value of a LISP expression e - the second argument a being a list of assignments of values to variables. (a is needed to make the recursion work). Writing eval required inventing a notation representing LISP functions as LISP data, and such a notation was devised for the purposes of the paper with no thought that it would be used to express LISP programs in practice. Logical completeness required that the notation used to express functions used as functional arguments be extended to provide for recursive functions, and the LABEL notation was invented by Nathaniel Rochester for that purpose. D.M.R. Park pointed out that LABEL was logically unnecessary since the result could be achieved using only LAMBDA - by a construction analogous to Church's Y-operator, albeit in a more complicated way.
S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.
The unexpected appearance of an interpreter tended to freeze the form of the language, and some of the decisions made rather lightheartedly for the ``Recursive functions ...'' paper later proved unfortunate. These included the COND notation for conditional expressions which leads to an unnecessary depth of parentheses, and the use of the number zero to denote the empty list NIL and the truth value false. Besides encouraging pornographic programming, giving a special interpretation to the address 0 has caused difficulties in all subsequent implementations.
- takes source code in one language as an input, and - turns the input into an assembly language output.
Now, ignoring the specifics of the input language and whether the assembly output is in fact bytecode for some interpreter or JIT compiler, or machine code for a CPU, this is a quite well-specified procedure.
Such a feat can surely be accomplished in any language. Source code in, binary instructions out—how hard is that?
If the input happens to be the compiler source code itself, that doesn't really matter. The same translation occurs.
If the language used to write the compiler is the same as the compiler itself takes as input, that doesn't really matter.
I remember in the early 2000's when MS were first making .net, being self-hosted was actually a huge deal and celebrated by the dev team.