Slow recursive functions
Christian Mayrhuber
christian.mayrhuber@gmx.net
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
More information about the Java
mailing list