Slow recursive functions

[Christian Mayrhuber]

Andrew Haley schrieb:
> Christian Mayrhuber writes:
>  > Hi,
>  > 
>  > I compiled the ackermann source from the computer language shootout with
>  > j2se 1.5 and gcj and ran a simple benchmark:
>  > 
>  > ackermann$ time java -server ackermann 12
>  > Ack(3,12): 32765
>  > 
>  > real    0m4.312s
>  > user    0m4.104s
>  > sys     0m0.029s
>  > 
>  > ackermann$ time ./ackermann.java.elf 12
>  > Ack(3,12): 32765
>  > 
>  > real    0m32.301s
>  > user    0m30.667s
>  > sys     0m0.039s
>  > 
>  > This result surprised me. The native compiled program was 8x slower than
>  > the version run by the sun jvm.
>  > 
>  > I've included the java source file and the -Os optimized
>  > assembler output.
>  > 
>  > My suspect are the calls of _Jv_InitClass in
>  > _ZN9ackermann3AckEii function.
> 
> That, and the calling convention.  We use the x86 system calling
> convention throughout gcj, and this is slower than passing args in
> registers.  There's also the possibility that some JITs might be
> optimized for this kind of benchmark.
> 
> Make Ack private and the _Jv_InitClass calls should go away.
>  

Indeed. With Ack made private the executeable produced by gcj
lines up on par with "java -server" and even with the C version
of ackermann.

Very impressive.
I didn't expect gcj to produce an executeable which can compete
with it's relative in C.

I read Mark Wielaard's Article on LWN (http://lwn.net/Articles/130796/)
which is pretty informative. With some gcj specific optimizations
in gcc 4.1 it will (hopefully) finally be possible to produce good
performing native java applications with the GNU toolchain.

Thanks!

Runs with the Ack method made private:
--------------------------------------
j2se1.5.0_01, gcj 4.0.0 20050326 (prerelease) (Debian 4.0-0pre9)
Athlon XP 2000+

ackermann$ time java -server ackermann 12
Ack(3,12): 32765
real    0m4.590s, user    0m4.124s, sys     0m0.041s

ackermann$ time java ackermann 12
Ack(3,12): 32765
real    0m21.990s, user    0m21.010s, sys     0m0.025s

ackermann$ gcj-4.0 -O3 -march=athlon \
-o ackermann.java.elf --main=ackermann ackermann.java
ackermann$ time ./ackermann.java.elf 12
Ack(3,12): 32765
real    0m4.569s, user    0m4.543s, sys     0m0.013s

ackermann$ gcc-4.0 -O3 -march=athlon \
-o ackermann.c.elf ackermann.c
time ./ackermann.c.elf 12
Ack(3,12): 32765
real    0m4.669s, user    0m4.644s, sys     0m0.003s

=============== ackermann.c ==================
/* -*- mode: c -*-
  * $Id: ackermann.gcc,v 1.1.1.1 2004/05/19 18:09:09 bfulgham Exp $
  * http://www.bagley.org/~doug/shootout/
  */

#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));
     /* sleep long enough so we can measure memory usage */
     /* sleep(1); */
     return(0);
}
==============================================

-- 
lg, Chris