[pypy-dev] befunge

[Terrence Cole]

I have built an RPython implementation of befunge98 on top of pypy.  It
took about a week at 30%, and about half of that was spent writing a
befunge implementation of pidigits[1].  I honestly expected to have more
trouble getting this working, which is one of the reasons I chose
something as simple as befunge.  There were some hiccups, certainly, but
compared to working with parrot and llvm, pypy was startlingly easy to
get up and running.

On to benchmarks.

Time taken to compute the first 1,000 digits of pi:
befunge.py: 3:03.18
befunge-c: 0:02.76

As advertised, I was able to write and test in python and run it through
the translator to get... the wrong test output.  This was, naturally, my
own fault.  As it turns out, pidigits requires arbitrary precision
integer support.  A quick skim of rarithmatic and rbignum and a bit of
hacking later, and I got the awesomely cool results you see above.

It was my plan at this point to lay down some benchmarks against other
language implementations of pidigits showing how awesome pypy is.
Unfortunately, the pidigits test is basically entirely limited by the
performance of the bignum library in use.  This effectively means that
every language that can use gmp does, and gets a result of 3-7 seconds,
which makes the pidigits test basically useless for meaningful
interpreter benchmarking.  That said, it is still a good benchmark for
bignum libraries, so here goes: 

Time taken to compute the first 10,000 digits of pi:
befunge-c: 5:22.13
pypy-c [2]: 5:35.26
python-2.5 [2]: 1:31.56
python-2.5(gmp) [3]: 0:10.22

>From what I see on the pyjitpl5 branch, jit support seems to be wildly
in flux at the moment.  I'm thinking I probably want to put jit support
on hold until things settle down, although it's definitely on my todo
list.  Supporting jit on top of befunge will, I think, be an interesting
edge case because the language was specifically designed to be hard to
compile.

Does pypy want a befunge interpreter?  It is a rather easier to read
interpreter than malbolge or javascript, although I did write it myself,
so I may be biased. Some of the more esoteric instructions and edge
cases are still missing, and there are several improvements that I would
still like to try, but it basically works now, so I figured I would
throw it out there.  Pypy isn't using a DVCS, so I'm not sure what the
best way is for me to share this code.  For now  I've just attached it
inline -- it's only 12KiB, packed up.  Untar it into the lang directory
and it will create a befunge subdirectory.  Let me know if there is a
better way to share code.

-Terrence Cole

[1] -
http://shootout.alioth.debian.org/u32q/benchmark.php?test=pidigits&lang=all#about
[2] -
http://shootout.alioth.debian.org/u32q/benchmark.php?test=pidigits&lang=python&id=1
[3] -
http://shootout.alioth.debian.org/u32q/benchmark.php?test=pidigits&lang=python&id=3

-------------- next part --------------
A non-text attachment was scrubbed...
Name: befunge98-20090808.tar.bz2
Type: application/x-bzip-compressed-tar
Size: 11696 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/pypy-dev/attachments/20090808/ab33f8e5/attachment.bin>