Slow recursive functions

[Andrew Haley]

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.
 
With -O2 -fomit-frame-pointer and ackermann.Ack declared private I get
this:

ackermann.Ack(int, int):
.LFB3:
        pushl   %ebx
.LCFI0:
        subl    $8, %esp
.LCFI1:
        movl    16(%esp), %edx
        movl    20(%esp), %eax
        testl   %edx, %edx
        jne     .L10
.L3:
        addl    $8, %esp
        incl    %eax
        popl    %ebx
        ret
        .p2align 4,,7
.L12:
        leal    -1(%edx), %ebx
        movl    $1, %eax
.L5:
        testl   %ebx, %ebx
        je      .L3
        movl    %ebx, %edx
.L10:
        testl   %eax, %eax
        je      .L12
        decl    %eax
        leal    -1(%edx), %ebx
        movl    %eax, 4(%esp)
        movl    %edx, (%esp)
        call    ackermann.Ack(int, int)
        jmp     .L5

I can't duplicate your jit results because I get a stack overflow.

Andrew.