It seems like DMD doesn't optimize tail recursion very well
Akhropov
andkhropov at nospam_mtu-net.ru
Fri Jun 9 06:56:30 PDT 2006
Looking through tests on http://shootout.alioth.debian.org/ website I noticed
that the only tests where DMD is inferior to GCC are where recursion is
seriously involved (binary trees and recursive). My own experiments with
ackermann function confirmed that:
C++:
---------------------------------------------------------------
#include <iostream>
#include <windows.h> // for GetTickCount
int Ack(int a, int b)
{
if (a == 0)
return b + 1;
else if (b == 0)
return Ack(a - 1, 1);
else
return Ack(a - 1, Ack(a, b - 1));
}
int main()
{
DWORD start = GetTickCount();
std::cout << Ack(3, 11) << std::endl;
DWORD stop = GetTickCount();
std::cout << stop-start << " ms elapsed.\n";
return 0;
}
-------------------------------------------------------------
D:
-------------------------------------------------------------
private import std.perf, std.stdio;
int Ack(int a, int b)
{
if (a == 0)
return b + 1;
else if (b == 0)
return Ack(a - 1, 1);
else
return Ack(a - 1, Ack(a, b - 1));
}
void main()
{
HighPerformanceCounter t = new HighPerformanceCounter();
t.start();
Ack(3, 11);
t.stop();
writefln("%d ms elapsed.", t.milliseconds());
}
---------------------------------------------------------------
I tried MSVC++ 8, MinGW GCC 3.4.2 and DMD 0.157
cl ack.cpp /Ox /Feack-cpp.exe
g++ ack.cpp -O99 -oack-gpp.exe
dmd ack.d -O -release -inline -ofack-d.exe
Here are the results (averaged over 10 times):
1) MS C++ : 830.5 ms
3) GCC : 990.4 ms
5) DMD : 2247.3 ms
Am I right? What could be done with this?
--
AKhropov
More information about the Digitalmars-d
mailing list