Slow recursive functions

Thu Apr 14 20:58:00 GMT 2005

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.
================== ackermann.java ===================
// $Id: ackermann.java,v 1.1 2004年05月22日 07:00:56 bfulgham Exp $
// http://www.bagley.org/~doug/shootout/
public class ackermann {
 public static void main(String[] args) {
 int num = Integer.parseInt(args[0]);
 System.out.println("Ack(3," + num + "): " + Ack(3, num));
 }
 public static int Ack(int m, int n) {
 return (m == 0) ? (n + 1) : ((n == 0) ? Ack(m-1, 1) :
 Ack(m-1, Ack(m, n - 1)));
 }
}
=====================================================
================== ackermann.s ======================
 .file "ackermann.java"
 .section .rodata.jutf8.10,"aM",@progbits,10
 .section .rodata.jutf8.28,"aM",@progbits,28
 .section .rodata.jutf8.8,"aM",@progbits,8
 .section .rodata.jutf8.10
 .section .rodata.jutf8.12,"aM",@progbits,12
 .section .rodata.jutf8.8
 .section .rodata.jutf8.12
 .section .rodata.jutf8.14,"aM",@progbits,14
 .section .jcr,"aw",@progbits
 .align 4
 .long _ZN9ackermann6class$E
.globl _ZN9ackermann6class$E
 .data
 .align 32
 .type _ZN9ackermann6class$E, @object
 .size _ZN9ackermann6class$E, 140
_ZN9ackermann6class$E:
 .long _ZTVN4java4lang5ClassE+8
 .long 40000
 .long _Utf9
 .value 1
 .zero 2
 .long _ZN4java4lang6Object6class$E
 .long 3
 .long _CT_ackermann
 .long _CD_ackermann
 .long _MT_ackermann
 .value 3
 .value 5
 .long 0
 .long 4
 .value 0
 .value 0
 .long _ZTVN9ackermannE+8
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .long _catch_classes_ackermann
 .long 0
 .long 0
 .value 0
 .byte 6
 .zero 1
 .long 0
 .value 0
 .zero 2
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .long 0
 .align 4
 .type _catch_classes_ackermann, @object
 .size _catch_classes_ackermann, 24
_catch_classes_ackermann:
 .zero 24
 .align 32
 .type _MT_ackermann, @object
 .size _MT_ackermann, 60
_MT_ackermann:
 .long _Utf1
 .long _Utf2
 .value 16393
 .value -1
 .long .L_ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE0
 .long 0
 .long _Utf3
 .long _Utf4
 .value 16393
 .value -1
 .long .L_ZN9ackermann3AckEii1
 .long 0
 .long _Utf5
 .long _Utf6
 .value 16385
 .value -1
 .long .L_ZN9ackermannC1Ev2
 .long 0
 .section .rodata.jutf8.8
 .align 2
 .type _Utf6, @object
 .size _Utf6, 4
_Utf6:
 .value 39797
 .value 3
 .ascii "()V"
 .zero 1
 .section .rodata.jutf8.12
 .align 2
 .type _Utf5, @object
 .size _Utf5, 4
_Utf5:
 .value 626
 .value 6
 .ascii "<init>"
 .zero 1
 .section .rodata.jutf8.10
 .align 2
 .type _Utf4, @object
 .size _Utf4, 4
_Utf4:
 .value 62088
 .value 5
 .ascii "(II)I"
 .zero 1
 .section .rodata.jutf8.8
 .align 2
 .type _Utf3, @object
 .size _Utf3, 4
_Utf3:
 .value 105
 .value 3
 .ascii "Ack"
 .zero 1
 .section .rodata.jutf8.28
 .align 2
 .type _Utf2, @object
 .size _Utf2, 4
_Utf2:
 .value 59434
 .value 22
 .ascii "([Ljava.lang.String;)V"
 .zero 1
 .section .rodata.jutf8.10
 .align 2
 .type _Utf1, @object
 .size _Utf1, 4
_Utf1:
 .value 1465
 .value 4
 .ascii "main"
 .zero 1
 .data
 .align 4
 .type _CD_ackermann, @object
 .size _CD_ackermann, 12
_CD_ackermann:
 .long 0
 .long _Utf8
 .long _Utf7
 .section .rodata.jutf8.8
 .align 2
 .type _Utf7, @object
 .size _Utf7, 4
_Utf7:
 .value 41231
 .value 3
 .ascii "): "
 .zero 1
 .section .rodata.jutf8.12
 .align 2
 .type _Utf8, @object
 .size _Utf8, 4
_Utf8:
 .value 22392
 .value 6
 .ascii "Ack(3,"
 .zero 1
 .data
 .type _CT_ackermann, @object
 .size _CT_ackermann, 3
_CT_ackermann:
 .byte 0
 .byte 8
 .byte 8
 .section .rodata.jutf8.14
 .align 2
 .type _Utf9, @object
 .size _Utf9, 4
_Utf9:
 .value 8778
 .value 9
 .ascii "ackermann"
 .zero 1
.globl _ZTVN9ackermannE
 .data
 .align 32
 .type _ZTVN9ackermannE, @object
 .size _ZTVN9ackermannE, 36
_ZTVN9ackermannE:
 .long 0
 .long 0
 .long _ZN9ackermann6class$E
 .long 4
 .long _ZN4java4lang6Object8finalizeEv
 .long _ZN4java4lang6Object8hashCodeEv
 .long _ZN4java4lang6Object6equalsEPS1_
 .long _ZN4java4lang6Object8toStringEv
 .long _ZN4java4lang6Object5cloneEv
 .text
 .align 2
.globl _ZN9ackermann3AckEii
 .type _ZN9ackermann3AckEii, @function
_ZN9ackermann3AckEii:
.LFB3:
 pushl %ebp
.LCFI0:
 movl %esp, %ebp
.LCFI1:
 pushl %edi
.LCFI2:
 pushl %esi
.LCFI3:
 pushl %ebx
.LCFI4:
 movl 8(%ebp), %ebx
 movl 12(%ebp), %esi
 jmp .L3
.L4:
 movl %edi, %ebx
.L3:
 pushl $_ZN9ackermann6class$E
.LCFI5:
 call _Jv_InitClass
 popl %ecx
.LCFI6:
 testl %ebx, %ebx
 je .L10
 testl %esi, %esi
 leal -1(%ebx), %edi
 jne .L7
 movw 1,ドル %si
 jmp .L4
.L7:
 leal -1(%esi), %eax
 pushl %eax
.LCFI7:
 pushl %ebx
.LCFI8:
 call _ZN9ackermann3AckEii
 movl %eax, %esi
 popl %eax
.LCFI9:
 popl %edx
.LCFI10:
 jmp .L4
.L10:
 leal 1(%esi), %eax
 leal -12(%ebp), %esp
 popl %ebx
 popl %esi
 popl %edi
 popl %ebp
 ret
.LFE3:
 .size _ZN9ackermann3AckEii, .-_ZN9ackermann3AckEii
 .align 2
.globl _ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE
 .type _ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE, 
@function
_ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE:
.LFB2:
 pushl %ebp
.LCFI11:
 movl %esp, %ebp
.LCFI12:
 pushl %edi
.LCFI13:
 pushl %esi
.LCFI14:
 pushl %ebx
.LCFI15:
 movl 8(%ebp), %ebx
 pushl $_ZN9ackermann6class$E
.LCFI16:
 call _Jv_InitClass
 popl %esi
.LCFI17:
 cmpl 0,ドル 4(%ebx)
 jne .L12
 pushl 0ドル
.LCFI18:
 call _Jv_ThrowBadArrayIndex
.LCFI19:
.L12:
 pushl 8(%ebx)
.LCFI20:
 call _ZN4java4lang7Integer8parseIntEPNS0_6StringE
 movl %eax, %esi
 pushl $_ZN4java4lang6System6class$E
.LCFI21:
 call _Jv_InitClass
 movl _ZN4java4lang6System3outE, %edi
 pushl $_ZN3gnu3gcj7runtime12StringBuffer6class$E
.LCFI22:
 call _Jv_AllocObjectNoFinalizer
 movl %eax, %ebx
 pushl _CD_ackermann+4
.LCFI23:
 pushl %eax
.LCFI24:
 call _ZN3gnu3gcj7runtime12StringBufferC1EPN4java4lang6StringE
 addl 20,ドル %esp
.LCFI25:
 testl %ebx, %ebx
 je .L24
 pushl %esi
.LCFI26:
 pushl %ebx
.LCFI27:
 call _ZN3gnu3gcj7runtime12StringBuffer6appendEi
 popl %ecx
.LCFI28:
 popl %ebx
.LCFI29:
 testl %eax, %eax
 je .L24
 pushl _CD_ackermann+8
.LCFI30:
 pushl %eax
.LCFI31:
 call 
_ZN3gnu3gcj7runtime12StringBuffer6appendEPN4java4lang6StringE
 movl %eax, %ebx
 popl %eax
.LCFI32:
 popl %edx
.LCFI33:
 testl %ebx, %ebx
 je .L24
 pushl %esi
.LCFI34:
 pushl 3ドル
.LCFI35:
 call _ZN9ackermann3AckEii
 pushl %eax
.LCFI36:
 pushl %ebx
.LCFI37:
 call _ZN3gnu3gcj7runtime12StringBuffer6appendEi
 addl 16,ドル %esp
.LCFI38:
 testl %eax, %eax
 jne .L20
.L24:
 call _Jv_ThrowNullPointerException
.L20:
 pushl %eax
.LCFI39:
 call _ZN3gnu3gcj7runtime12StringBuffer8toStringEv
 movl (%edi), %edx
 pushl %eax
.LCFI40:
 pushl %edi
.LCFI41:
 call *120(%edx)
 addl 12,ドル %esp
.LCFI42:
 leal -12(%ebp), %esp
 popl %ebx
 popl %esi
 popl %edi
 popl %ebp
 ret
.LFE2:
 .size _ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE, 
.-_ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE
 .align 2
.globl _ZN9ackermannC1Ev
 .type _ZN9ackermannC1Ev, @function
_ZN9ackermannC1Ev:
.LFB4:
 pushl %ebp
.LCFI43:
 movl %esp, %ebp
.LCFI44:
 pushl 8(%ebp)
.LCFI45:
 call _ZN4java4lang6ObjectC1Ev
 popl %eax
.LCFI46:
 leave
 ret
.LFE4:
 .size _ZN9ackermannC1Ev, .-_ZN9ackermannC1Ev
 .set 
.L_ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE0,_ZN9ackermann4mainEP6JArrayIPN4java4lang6StringEE
 .set .L_ZN9ackermann3AckEii1,_ZN9ackermann3AckEii
 .set .L_ZN9ackermannC1Ev2,_ZN9ackermannC1Ev
 .section .eh_frame,"a",@progbits
.Lframe1:
 .long .LECIE1-.LSCIE1
.LSCIE1:
 .long 0x0
 .byte 0x1
 .string "zP"
 .uleb128 0x1
 .sleb128 -4
 .byte 0x8
 .uleb128 0x5
 .byte 0x0
 .long __gcj_personality_v0
 .byte 0xc
 .uleb128 0x4
 .uleb128 0x4
 .byte 0x88
 .uleb128 0x1
 .align 4
.LECIE1:
.LSFDE1:
 .long .LEFDE1-.LASFDE1
.LASFDE1:
 .long .LASFDE1-.Lframe1
 .long .LFB3
 .long .LFE3-.LFB3
 .uleb128 0x0
 .byte 0x4
 .long .LCFI0-.LFB3
 .byte 0xe
 .uleb128 0x8
 .byte 0x85
 .uleb128 0x2
 .byte 0x4
 .long .LCFI1-.LCFI0
 .byte 0xd
 .uleb128 0x5
 .byte 0x4
 .long .LCFI4-.LCFI1
 .byte 0x83
 .uleb128 0x5
 .byte 0x86
 .uleb128 0x4
 .byte 0x87
 .uleb128 0x3
 .byte 0x4
 .long .LCFI5-.LCFI4
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI6-.LCFI5
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI7-.LCFI6
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI8-.LCFI7
 .byte 0x2e
 .uleb128 0x8
 .byte 0x4
 .long .LCFI9-.LCFI8
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI10-.LCFI9
 .byte 0x2e
 .uleb128 0x0
 .align 4
.LEFDE1:
.LSFDE3:
 .long .LEFDE3-.LASFDE3
.LASFDE3:
 .long .LASFDE3-.Lframe1
 .long .LFB2
 .long .LFE2-.LFB2
 .uleb128 0x0
 .byte 0x4
 .long .LCFI11-.LFB2
 .byte 0xe
 .uleb128 0x8
 .byte 0x85
 .uleb128 0x2
 .byte 0x4
 .long .LCFI12-.LCFI11
 .byte 0xd
 .uleb128 0x5
 .byte 0x4
 .long .LCFI15-.LCFI12
 .byte 0x83
 .uleb128 0x5
 .byte 0x86
 .uleb128 0x4
 .byte 0x87
 .uleb128 0x3
 .byte 0x4
 .long .LCFI16-.LCFI15
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI17-.LCFI16
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI18-.LCFI17
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI19-.LCFI18
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI20-.LCFI19
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI21-.LCFI20
 .byte 0x2e
 .uleb128 0x8
 .byte 0x4
 .long .LCFI22-.LCFI21
 .byte 0x2e
 .uleb128 0xc
 .byte 0x4
 .long .LCFI23-.LCFI22
 .byte 0x2e
 .uleb128 0x10
 .byte 0x4
 .long .LCFI24-.LCFI23
 .byte 0x2e
 .uleb128 0x14
 .byte 0x4
 .long .LCFI25-.LCFI24
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI26-.LCFI25
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI27-.LCFI26
 .byte 0x2e
 .uleb128 0x8
 .byte 0x4
 .long .LCFI28-.LCFI27
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI29-.LCFI28
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI30-.LCFI29
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI31-.LCFI30
 .byte 0x2e
 .uleb128 0x8
 .byte 0x4
 .long .LCFI32-.LCFI31
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI33-.LCFI32
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI34-.LCFI33
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI35-.LCFI34
 .byte 0x2e
 .uleb128 0x8
 .byte 0x4
 .long .LCFI36-.LCFI35
 .byte 0x2e
 .uleb128 0xc
 .byte 0x4
 .long .LCFI37-.LCFI36
 .byte 0x2e
 .uleb128 0x10
 .byte 0x4
 .long .LCFI38-.LCFI37
 .byte 0x2e
 .uleb128 0x0
 .byte 0x4
 .long .LCFI39-.LCFI38
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI40-.LCFI39
 .byte 0x2e
 .uleb128 0x8
 .byte 0x4
 .long .LCFI41-.LCFI40
 .byte 0x2e
 .uleb128 0xc
 .byte 0x4
 .long .LCFI42-.LCFI41
 .byte 0x2e
 .uleb128 0x0
 .align 4
.LEFDE3:
.LSFDE5:
 .long .LEFDE5-.LASFDE5
.LASFDE5:
 .long .LASFDE5-.Lframe1
 .long .LFB4
 .long .LFE4-.LFB4
 .uleb128 0x0
 .byte 0x4
 .long .LCFI43-.LFB4
 .byte 0xe
 .uleb128 0x8
 .byte 0x85
 .uleb128 0x2
 .byte 0x4
 .long .LCFI44-.LCFI43
 .byte 0xd
 .uleb128 0x5
 .byte 0x4
 .long .LCFI45-.LCFI44
 .byte 0x2e
 .uleb128 0x4
 .byte 0x4
 .long .LCFI46-.LCFI45
 .byte 0x2e
 .uleb128 0x0
 .align 4
.LEFDE5:
 .ident "GCC: (GNU) 4.0.0 20050326 (prerelease) (Debian 4.0-0pre9)"
 .section .note.GNU-stack,"",@progbits
=====================================================
-- 
lg, Chris