www.digitalmars.com         C & C++   DMDScript  

D - Why is Ackermann's function so much slower in D?

reply "DDevil" <ddevil functionalfuture.com> writes:
You know, from the shootout.  It's almost exactly twice as slow as the C
version.  I'm just curious more than anything else.  Is this due to a
tail-call optimization made by the C compilers?

As a side note, is there any way to make dmd output the assembly language
for the file you are compiling? (like the -S option in GCC)  This would
allow me see why it's slower.

--
// DDevil


The code:

import string;

int Ack(int M, int N)
{
    if (M == 0) return( N + 1 );
    if (N == 0) return( Ack(M - 1, 1) );
    return( Ack(M - 1, Ack(M, (N - 1))) );
}

int main(char[][] args)
{
   int n = args.length < 2 ? 1 : string.atoi(args[1]);
   printf("Ack(3,%d): %d\n", n, Ack(3, n));
   return(0);
}
Mar 18 2003
parent reply "Walter" <walter digitalmars.com> writes:
"DDevil" <ddevil functionalfuture.com> wrote in message
news:pan.2003.03.18.12.37.59.960375 functionalfuture.com...
 You know, from the shootout.  It's almost exactly twice as slow as the C
 version.  I'm just curious more than anything else.  Is this due to a
 tail-call optimization made by the C compilers?

Make sure you're compiling with -O -release.
 As a side note, is there any way to make dmd output the assembly language
 for the file you are compiling? (like the -S option in GCC)  This would
 allow me see why it's slower.

Sure. Compile normally, then run OBJ2ASM on the .obj file output.
Mar 18 2003
next sibling parent reply "DDevil" <ddevil functionalfuture.com> writes:
On Tue, 18 Mar 2003 08:24:00 -0800, Walter wrote:
 Make sure you're compiling with -O -release.

Yep. Without -O it's twice slower again (ie. 4 times slower than C). -release makes no difference. I'm using the 0.59 compiler by the way.
 Sure. Compile normally, then run OBJ2ASM on the .obj file output.

Where can I get OBJ2ASM? Does dmd not use an intermediate assembly stage? Thanks -- // DDevil
Mar 18 2003
parent reply Joel Lucsy <jjlucsy concentric.net> writes:
"DDevil" <ddevil functionalfuture.com> wrote in
news:pan.2003.03.18.17.16.12.727107 functionalfuture.com: 

 On Tue, 18 Mar 2003 08:24:00 -0800, Walter wrote:
 Make sure you're compiling with -O -release.

Yep. Without -O it's twice slower again (ie. 4 times slower than C). -release makes no difference. I'm using the 0.59 compiler by the way.

Huh. With -O DMD is twice as fast for me. Using the 0.57 compiler.
Mar 18 2003
parent "DDevil" <ddevil functionalfuture.com> writes:
On Tue, 18 Mar 2003 19:17:31 +0000, Joel Lucsy wrote:
 Huh. With -O DMD is twice as fast for me. Using the 0.57 compiler.

Hehe, right, that's what I said. So without -O it's 4 times slower than C and with -O it's only 2 times slower. ;) -- // DDevil
Mar 18 2003
prev sibling parent reply "DDevil" <ddevil functionalfuture.com> writes:
On Tue, 18 Mar 2003 08:24:00 -0800, Walter wrote:
 Sure. Compile normally, then run OBJ2ASM on the .obj file output.

OK, after looking at the assembly, it looks like D is not doing tail-call optimizing at all. GCC and MSVC optimize it very nicely and that's why they run so fast. They completely remove the recursive calls by using jmp. This effectively turns it into a for-loop. It's interesting because I was comparing the Fibonacci Numbers benchmark which runs about the same in C and D. After looking at the assembly, I see that GCC is not able do tail-call optimizing for that benchmark (in theory it _should_ be able to, but it might be more difficult). I can't remember when GCC does the tail-call optimizing so I don't know if using it as a back-end would help. I believe tail-call optimizing would be a great feature in D because it would allow a more functional programming style when it makes sense. Not only would you gain speed, but you don't have to worry about blowing out the stack. That's a major beef I have with C and C++. So my question is now: Does D ever do any tail-call optimizing? -- // DDevil
Mar 18 2003
next sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
DDevil wrote:

 So my question is now:  Does D ever do any tail-call optimizing?

D does! But maybe DMD doesn't....Walter? -- The Villagers are Online! villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]
Mar 18 2003
prev sibling next sibling parent reply "Walter" <walter digitalmars.com> writes:
"DDevil" <ddevil functionalfuture.com> wrote in message
news:pan.2003.03.18.21.13.04.656244 functionalfuture.com...
 I believe tail-call optimizing would be a great feature in D because it
 would allow a more functional programming style when it makes sense.  Not
 only would you gain speed, but you don't have to worry about blowing out
 the stack.  That's a major beef I have with C and C++.

 So my question is now:  Does D ever do any tail-call optimizing?

DMD currently does not do any tail recursion optimization. However, that is not a limitation of D, it is just the way the DMD compiler is implemented. There's nothing about D that would stop a D compiler from doing such optimizations.
Mar 18 2003
parent reply "DDevil" <ddevil functionalfuture.com> writes:
On Tue, 18 Mar 2003 16:01:08 -0800, Walter wrote:
 DMD currently does not do any tail recursion optimization. However, that is
 not a limitation of D, it is just the way the DMD compiler is implemented.
 There's nothing about D that would stop a D compiler from doing such
 optimizations.

OK, right, I should have phrased that as "does the DMD compiler currently do tail-call optimization". I wish more imperative language compilers supported such optimizations. Thanks -- // DDevil
Mar 18 2003
parent reply Benji Smith <Benji_member pathlink.com> writes:
So....will the DMD compiler do tail-call optimizations? It that a compiler
feature that's on the drawing board, or is it not a priority?

--Benji Smith


On Tue, 18 Mar 2003 16:01:08 -0800, Walter wrote:
 DMD currently does not do any tail recursion optimization. However, that is
 not a limitation of D, it is just the way the DMD compiler is implemented.
 There's nothing about D that would stop a D compiler from doing such
 optimizations.

OK, right, I should have phrased that as "does the DMD compiler currently do tail-call optimization". I wish more imperative language compilers supported such optimizations.

Mar 19 2003
parent "Walter" <walter digitalmars.com> writes:
"Benji Smith" <Benji_member pathlink.com> wrote in message
news:b5a1tn$2pcd$1 digitaldaemon.com...
 So....will the DMD compiler do tail-call optimizations? It that a compiler
 feature that's on the drawing board, or is it not a priority?

It can do it, it's just not a priority.
Mar 19 2003
prev sibling parent reply Ilya Minkov <midiclub 8ung.at> writes:
DDevil wrote:
 OK, after looking at the assembly, it looks like D is not doing tail-call
 optimizing at all.  GCC and MSVC optimize it very nicely and that's why
 they run so fast.  They completely remove the recursive calls by using
 jmp. This effectively turns it into a for-loop. 
 
 It's interesting because I was comparing the Fibonacci Numbers benchmark
 which runs about the same in C and D.  After looking at the assembly, I
 see that GCC is not able do tail-call optimizing for that benchmark (in
 theory it _should_ be able to, but it might be more difficult).

Show me the code for that fibonacci. If it's the most naive recursive one, it *can't* be optimised by tail recursion elimination. To understand it, you have to turn to the definition of tail recursion. Why is it called "tail"? It is in the cases, when a recursive function calls itself, but does not process a result it gets back in any way, simply returning it. This results in the interesting stack behaviour: after the stack has been built up by sucessive recursive calls, there is a computation result on top of it, of which you know it would get passed to the bottom without change. So you don't need to return n times to get to the bottom: simply decrease the stack pointer and put the result there. Furthermore, that actually means, that all those stack values were not requiered to be saved in the first place. So the tail recursion elimination kicks in and transforms the function - or a mutually recursive set of functions - into a loop. Cuts off the tail, so to say. In our first days of OCaml we were taught, that we have to change our recursion to behave like that - so that result is created unchanged in a topmost function call. This usually involves passing more arguments to the recursive function. The optimisation is very important for functional programming - where you don't want to or can't use the loops explicitly - but for a usual programmer with imperative background it does little. Like, this style doesn't even make your code terser, it just requeres you to spend time picking up names for all these tiny functions. :> Mind that when comparing C and D it's not fair to campare DMD against GCC, unless you have also compared DMC with GCC. A compiler can't be better than its underlying backend.
 I can't remember when GCC does the tail-call optimizing so I don't know if
 using it as a back-end would help.

It should in those cases "to whom it may apply". :> Besides, we would get a debugger and i could finally install D on a sparc at the university! -i.
Mar 25 2003
next sibling parent "DDevil" <ddevil functionalfuture.com> writes:
On Tue, 25 Mar 2003 19:36:07 +0100, Ilya Minkov wrote:

 DDevil wrote:
 Show me the code for that fibonacci. If it's the most naive recursive 
 one, it *can't* be optimised by tail recursion elimination.

It's listed with the rest of the D Language Shootout programs I've ported. http://www.functionalfuture.com/d And yes, it is a naive recursive version, and it must be implemented that way (or close to it) for the shootout.
 To understand it, you have to turn to the definition of tail recursion. 

Trust me, I know. I have spent many an hour in Erlang and OCaml. I probably should have worded my post differently. In theory _any_ recursive function can be optimized into a loop given a smart enough back-end or compiler. Note that I'm not only talking about tail-call elimination at this point, but recursion optimization in general.
 Mind that when comparing C and D it's not fair to campare DMD against 
 GCC, unless you have also compared DMC with GCC. A compiler can't be 
 better than its underlying backend.

True, but in the benchmark I was specifically testing Walter's default back-end against GCC and MSVC's. -- // DDevil
Mar 25 2003
prev sibling parent "Walter" <walter digitalmars.com> writes:
"Ilya Minkov" <midiclub 8ung.at> wrote in message
news:b5q744$22cp$1 digitaldaemon.com...
 Mind that when comparing C and D it's not fair to campare DMD against
 GCC, unless you have also compared DMC with GCC. A compiler can't be
 better than its underlying backend.

You're right. Any speed/size comparison of D vs C/C++ should be done with DMC/C++, since then the languages are being compared rather than the back ends.
Mar 28 2003