ackermann test

ackermann test

[skaller]

Entirely for amusement, current timings for 
ackermanns function, ack(3,y):

     Felix Ocaml bytecode  Felix/opt     C -O3  Ocaml native code
---------------------------------------------------------
y=10 113        12             7          1.8          0.4
y=11  ?         50            55         16            2
y=12  ?        220           290        113            9

Times in seconds on 700MHz PIII. 

For y=12, my disk light went on occasionally 
(i.e the process was hitting VM), looks like the size of 
stack frames begins to dominate as y increases?

Be interesting to see comparison with ocaml bytecode/JIT.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] ackermann test

[Michael Walter]

Where can I find the C code you are using?

Michael


On Tue, 08 Feb 2005 20:02:28 -0800 (PST), skaller
<skaller@users.sourceforge.net> wrote:
> Entirely for amusement, current timings for
> ackermanns function, ack(3,y):
> 
>      Felix Ocaml bytecode  Felix/opt     C -O3  Ocaml native code
> ---------------------------------------------------------
> y=10 113        12             7          1.8          0.4
> y=11  ?         50            55         16            2
> y=12  ?        220           290        113            9
> 
> Times in seconds on 700MHz PIII.
> 
> For y=12, my disk light went on occasionally
> (i.e the process was hitting VM), looks like the size of
> stack frames begins to dominate as y increases?
> 
> Be interesting to see comparison with ocaml bytecode/JIT.
> 
> --
> John Skaller, mailto:skaller@users.sf.net
> voice: 061-2-9660-0850,
> snail: PO BOX 401 Glebe NSW 2037 Australia
> Checkout the Felix programming language http://felix.sf.net
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] ackermann test

[skaller]

On Wed, 2005-02-09 at 15:09, Michael Walter wrote:
> Where can I find the C code you are using?

int ack(int x, int y) {
  return x==0? y+1: (y==0? ack(x-1,1):ack(x-1,ack(x,y-1)));
}

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] ackermann test

[Marcin 'Qrczak' Kowalczyk]

skaller <skaller@users.sourceforge.net> writes:

>> Where can I find the C code you are using?
>
> int ack(int x, int y) {
>   return x==0? y+1: (y==0? ack(x-1,1):ack(x-1,ack(x,y-1)));
> }

If you write it like this:

int ack(int x, int y) {
   if (x==0) return y+1;
   if (y==0) return ack(x-1,1);
   return ack(x-1,ack(x,y-1));
}

then gcc-3.4.3 generates better code (optimizes tail calls).
-fomit-frame-pointer further speeds it up.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: [Caml-list] ackermann test

[Oliver Bandel]

On Wed, Feb 09, 2005 at 10:26:39AM +0100, Marcin 'Qrczak' Kowalczyk wrote:
> skaller <skaller@users.sourceforge.net> writes:
> 
> >> Where can I find the C code you are using?
> >
> > int ack(int x, int y) {
> >   return x==0? y+1: (y==0? ack(x-1,1):ack(x-1,ack(x,y-1)));
> > }
> 
> If you write it like this:
> 
> int ack(int x, int y) {
>    if (x==0) return y+1;
>    if (y==0) return ack(x-1,1);
>    return ack(x-1,ack(x,y-1));
> }
> 
> then gcc-3.4.3 generates better code (optimizes tail calls).
> -fomit-frame-pointer further speeds it up.


Would be nice to have the comlete benchmark again - now with this
code (or with an added row for this C-Code).

So we can compare, what reults will yielded by that different code
on the same platform for which we saw the other benchmark values.

Ciao,
   Oliver

Re: [Caml-list] ackermann test

[skaller]

On Wed, 2005-02-09 at 22:17, Oliver Bandel wrote:

> > int ack(int x, int y) {
> >    if (x==0) return y+1;
> >    if (y==0) return ack(x-1,1);
> >    return ack(x-1,ack(x,y-1));
> > }
> > 
> > then gcc-3.4.3 generates better code (optimizes tail calls).
> > -fomit-frame-pointer further speeds it up.

> 
> Would be nice to have the comlete benchmark again - now with this
> code (or with an added row for this C-Code).

I only have gcc 3.2.2.  With -fomit-frame-pointer and -O3 and -static
for the new C:

       new C  w/o old C  new Felix  old Felix  HACKED  Ocamlopt Ocamlb
y=10    0.5   0.8    1.8       2.9          7     10      0.4     12 
y=11    7.4   12.5  16        28           55     75      2       50
y=12   64     98   113       180          290    370      9      220

w/o -- new C code without -fomit-frame-pointer

'old Felix' + 2 ints on stack frame
'HACKED'    + 4 ints on stack frame

Felix puts at least 2 extra words on the stack,
probably 3, plus possibly g++ is saving the 
'this' pointer which is a 4 word overhead
compared to the C code.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] ackermann test

[Marcin 'Qrczak' Kowalczyk]

skaller <skaller@users.sourceforge.net> writes:

> I only have gcc 3.2.2.  With -fomit-frame-pointer and -O3 and -static
> for the new C:
>
>        new C  w/o old C  new Felix  old Felix  HACKED  Ocamlopt Ocamlb
> y=10    0.5   0.8    1.8       2.9          7     10      0.4     12 
> y=11    7.4   12.5  16        28           55     75      2       50
> y=12   64     98   113       180          290    370      9      220

A further speedup in C:

__attribute__((regparm(2)))
int ack(int x, int y) {
   ...
}

BTW, gcc -O2 and -O3 give the same code here.

gcc generates some redundant register moves (I guess regparm is not
optimized as well as it could because it's not common), so ocamlopt
is still marginally faster.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: [Caml-list] ackermann test

[skaller]

On Thu, 2005-02-10 at 01:00, Marcin 'Qrczak' Kowalczyk wrote:
> skaller <skaller@users.sourceforge.net> writes:

> >        new C  w/o old C  new Felix  old Felix  HACKED  Ocamlopt Ocamlb
> > y=10    0.5   0.8    1.8       2.9          7     10      0.4     12 
> > y=11    7.4   12.5  16        28           55     75      2       50
> > y=12   64     98   113       180          290    370      9      220
> 
> A further speedup in C:
> 
> __attribute__((regparm(2)))
> int ack(int x, int y) {
>    ...
> }

You are certainly not kidding! With that change:

         C         Felix   Ocamlopt
Y=10   0.5         0.8        0.4
Y=11   2.1         9.3        2
Y=12  21.5        87          9


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] ackermann test

[Jon Harrop]

On Tuesday 08 February 2005 10:43, Xavier Leroy wrote:
> Ah, another micro-benchmark.  Great pasttime!

No way, that nbody benchmark was _huge_! ;-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.