Parrot runs the ackermann benchmark faster than C. leo
Heureka - from the -Ofun department
Or - running the ackermann function (and possibly other recursive functions) really fast. $ time ./parrot -Oc -C ack.pir 11 Ack(3, 11) = 16381 real 0m0.567s user 0m0.559s sys 0m0.008s $ time ./ack 11 Ack(3,11): 16381 real 0m0.980s user 0m0.978s sys 0m0.002s Parrot is svn head (not optimized BTW), the C version is compiled -O3 with 3.3.5. Below is the C [1] and the PIR source [2]. The ack function is renamed to __pic_test - currently all the checks that would enable this optimization are missing, e.g. if only I and N registers are used and not too many, if there is no introspection and so on. The created JIT code for the ack function is also shown [3]. This is actually only the recursive part of it, there is a small stub that moves the arguments into registers and fetches the return result. ./parrot -Oc -C turns on tail-recursion optimization (recursive tail calls are converted to loops). -C is the CGP or direct-threaded runcore, which is able to recompile statically known stuff into faster versions by e.g. caching lookups and such. Have fun, leo [1] /* -*- mode: c -*- * $Id: ackermann-gcc-3.code,v 1.8 2005/12/02 08:05:56 bfulgham Exp $ * http://www.bagley.org/~doug/shootout/ * * modified by Isaac Gouy */ #include <stdio.h> #include <stdlib.h> #include <unistd.h> int Ack(int M, int N) { return(M ? (Ack(M-1,N ? Ack(M,(N-1)) : 1)) : N+1); } int main(int argc, char *argv[]) { int n = ((argc == 2) ? atoi(argv[1]) : 1); printf("Ack(3,%d): %d\n", n, Ack(3, n)); return(0); } [2] #!./parrot -C # # ackermann - ack(3, 9) is default # shootout runs ack(3, 11) # by Leopold Toetsch .sub main :main .param pmc argv .local int argc argc = elements argv .local int x, y, r x = 3 y = 9 if argc == 1 goto go $S0 = argv[1] if argc == 2 goto xdefault x = $S0 $S0 = argv[2] y = $S0 goto go xdefault: y = $S0 go: $P0 = getinterp $P0.'recursion_limit'(100000) r = __pic_test(x, y) .local pmc args args = new .ResizableIntegerArray push args, x push args, y push args, r $S0 = sprintf "Ack(%d, %d) = %d\n", args print $S0 .end .sub __pic_test .param int x .param int y if x goto a1 inc y .return (y) a1: if y goto a2 dec x .return __pic_test(x, 1) a2: dec y y = __pic_test(x, y) dec x .return __pic_test(x, y) .end [3] 0x84a80c7: test %edx,%edx 0x84a80c9: jne 0x84a80d3 0x84a80cf: inc %ecx 0x84a80d0: mov %ecx,%eax 0x84a80d2: ret 0x84a80d3: test %ecx,%ecx 0x84a80d5: jne 0x84a80e4 0x84a80db: dec %edx 0x84a80dc: mov $0x1,%ecx 0x84a80e1: jmp 0x84a80c7 0x84a80e3: nop 0x84a80e4: dec %ecx 0x84a80e5: push %edx 0x84a80e6: call 0x84a80c7 0x84a80eb: pop %edx 0x84a80ec: mov %eax,%ecx 0x84a80ee: mov %esi,%esi 0x84a80f0: dec %edx 0x84a80f1: jmp 0x84a80c7 0x84a80f3: ret
