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