[Shootout-list] Major flaw in Ackermann Ada implementation

[Vasiliy Fofanov]

Hello,

I am pleased to see that suggestions to improve optimization level of GNAT
programs were quickly integrated.

However, there remains a major difference between Ackermann algorithms as
proposed for GCC C and for GNAT. In the first case, the function is global.
In the second, it is local. This might not seem like a great deal but in
fact this has staggering repercussions for GCC backends prior to 4.0. To
see this, just try to time the following two C variants.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int Ack(int M, int N) { return(M ? (Ack(M-1,N ? Ack(M,(N-1)) : 1)) : N+1); }

int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 10);

    printf("Ack(3,%d): %d\n", n, Ack(3, n));
    /* sleep long enough so we can measure memory usage */
    sleep(1);
    return(0);
}

--------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
    int Ack(int M, int N) { return(M ? (Ack(M-1,N ? Ack(M,(N-1)) : 1)) : N+1); }

    int n = ((argc == 2) ? atoi(argv[1]) : 10);

    printf("Ack(3,%d): %d\n", n, Ack(3, n));
    /* sleep long enough so we can measure memory usage */
    sleep(1);
    return(0);
}

You will see that the first is 2-3 times faster than the second. It's
related to tail recursion optimizations.

Therefore, this is a problem of GCC backend and not at all the problem of
GNAT as your shoot-out stats appear to suggest because of algorithms
difference. Should you rewrite the Ada implementation of the test to
eliminate the local function, the Ada performance will at least double, as
expected. Note that GNAT on GCC 4.0 backend doesn't exhibit this
peculiarity, again as expected.

Generally speaking whenever there is more than ~20% difference between GNAT
and GCC C performance on a given algorithm, it should be immediately
investigated whether the algorithms are, indeed, equivalent. And when
certain that they are, it makes sense to alert AdaCore at
report at adacore.com. I am serious... we at AdaCore are committed to making
our compiler comparable to GCC C in efficiency and will look at any case
where the performance difference is so large.

Please find attached a proposed Ada test. To be sure it will have abysmal
lines-of-code score. But frankly... don't you think that this measurement
is more than a little silly?! I mean, is there any doubt that I can write an
entire Ada program on a single line? Or that Ada writing style would
mandate that this abomination -

    int Ack(int M, int N) { return(M ? (Ack(M-1,N ? Ack(M,(N-1)) : 1)) : N+1); }

- were actually written on at least 10 lines?

If I were you I'd have dropped this irrelevant measurement completely, or
at least expressed it in terms of number of lexems or number of control
constructs, but certainly not number of lines!

Best regards to all,
 Vasiliy Fofanov.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ack.adb
Type: application/octet-stream
Size: 357 bytes
Desc: not available
Url : http://lists.alioth.debian.org/pipermail/shootout-list/attachments/20060423/26dae1de/ack.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ack_f.adb
Type: application/octet-stream
Size: 260 bytes
Desc: not available
Url : http://lists.alioth.debian.org/pipermail/shootout-list/attachments/20060423/26dae1de/ack_f.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ack_f.ads
Type: application/octet-stream
Size: 49 bytes
Desc: not available
Url : http://lists.alioth.debian.org/pipermail/shootout-list/attachments/20060423/26dae1de/ack_f-0001.obj