D - Why is Ackermann's function so much slower in D?
- DDevil (22/22) Mar 18 2003 You know, from the shootout. It's almost exactly twice as slow as the C
- Walter (4/10) Mar 18 2003 Make sure you're compiling with -O -release.
- DDevil (7/9) Mar 18 2003 Yep. Without -O it's twice slower again (ie. 4 times slower than C).
- Joel Lucsy (3/8) Mar 18 2003 Huh. With -O DMD is twice as fast for me. Using the 0.57 compiler.
- DDevil (6/7) Mar 18 2003 Hehe, right, that's what I said.
- DDevil (18/19) Mar 18 2003 OK, after looking at the assembly, it looks like D is not doing tail-cal...
- Russ Lewis (7/8) Mar 18 2003 D does! But maybe DMD doesn't....Walter?
- Walter (6/11) Mar 18 2003 DMD currently does not do any tail recursion optimization. However, that...
- DDevil (7/11) Mar 18 2003 OK, right, I should have phrased that as "does the DMD compiler currentl...
- Benji Smith (3/11) Mar 19 2003 So....will the DMD compiler do tail-call optimizations? It that a compil...
- Walter (3/5) Mar 19 2003 It can do it, it's just not a priority.
- Ilya Minkov (31/42) Mar 25 2003 Show me the code for that fibonacci. If it's the most naive recursive
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
"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
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
"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:Huh. With -O DMD is twice as fast for me. Using the 0.57 compiler.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.
Mar 18 2003
"DDevil" <ddevil functionalfuture.com> 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
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
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
"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
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
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 SmithOn 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
"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
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
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
"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