Slow recursive functions

Fri Apr 15 19:41:00 GMT 2005

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