[Ecls-list] Bug report (?) and two questions

[Dr. Edmund Weitz]

Juan Jose Garcia-Ripoll <Juan.Ripoll at mpq.mpg.de> writes:

> This is now fixed in CVS. What worries me now is that the
> calculation of factorials is not very fast. I lack a lisp to compare
> with, but could anybody compare CLISP, a new copy of ECL and CMUCL
> on the same platform?

My bad. I somehow managed to use the old ecls binary instead of the
new ecl. Sorry for the confusion caused by my last mail.

Here are some test results. All Lisp results were achieved by
compiling the file, then loading it. Note that I couldn't run the
10,000 test cases with Allegro and LispWorks due to stack limitations
in the trial versions.

Test machine is a laptop with 850 MHz P3 and 250 MB RAM, Linux
2.4.10.

I think ECL performs remarkably well! (This is mostly due to the GMP
library, though.)

Cheers,
Edi.

PS: Looks like there are problems with the ~F format statement.


C

fac(0) to fac(999), recursion: 0.890
fac(0) to fac(999), fake recursion: 0.322
fac(0) to fac(999), iteration: 0.309
fac(10000), 10 repetitions, recursion: 1.607
fac(10000), 10 repetitions, fake recursion: 1.187
fac(10000), 10 repetitions, iteration: 1.160

CLISP

fac(0) to fac(999), iteration: 1.892
fac(0) to fac(999), tail-recursion with opt args: 2.185
fac(0) to fac(999), tail-recursion with helper: 2.170
fac(0) to fac(999), recursion: 2.079
fac(3000), 10 repetitions, iteration: 0.562
fac(3000), 10 repetitions, tail-recursion with opt args: 0.596
fac(3000), 10 repetitions, tail-recursion with helper: 0.593
fac(3000), 10 repetitions, recursion: 0.562
fac(10000), 10 repetitions, iteration: 7.695
fac(10000), 10 repetitions, tail-recursion with opt args: 7.403
fac(10000), 10 repetitions, tail-recursion with helper: 7.408
fac(10000), 10 repetitions, recursion: 7.703

ECL

fac(0) to fac(999), iteration: 4.000
fac(0) to fac(999), tail-recursion with opt args: 4.000
fac(0) to fac(999), tail-recursion with helper: 4.000
fac(0) to fac(999), recursion: 3.000
fac(3000), 10 repetitions, iteration: 2.000
fac(3000), 10 repetitions, tail-recursion with opt args: 0.000
fac(3000), 10 repetitions, tail-recursion with helper: 1.000
fac(3000), 10 repetitions, recursion: 0.000
fac(10000), 10 repetitions, iteration: 9.000
fac(10000), 10 repetitions, tail-recursion with opt args: 7.000
fac(10000), 10 repetitions, tail-recursion with helper: 5.000
fac(10000), 10 repetitions, recursion: 5.000

CMUCL

fac(0) to fac(999), iteration: 3.430
fac(0) to fac(999), tail-recursion with opt args: 4.160
fac(0) to fac(999), tail-recursion with helper: 3.980
fac(0) to fac(999), recursion: 3.550
fac(3000), 10 repetitions, iteration: 1.150
fac(3000), 10 repetitions, tail-recursion with opt args: 1.320
fac(3000), 10 repetitions, tail-recursion with helper: 1.390
fac(3000), 10 repetitions, recursion: 1.180
fac(10000), 10 repetitions, iteration: 15.300
fac(10000), 10 repetitions, tail-recursion with opt args: 16.640
fac(10000), 10 repetitions, tail-recursion with helper: 16.600
fac(10000), 10 repetitions, recursion: 15.280

SBCL

fac(0) to fac(999), iteration: 4.430
fac(0) to fac(999), tail-recursion with opt args: 5.160
fac(0) to fac(999), tail-recursion with helper: 5.160
fac(0) to fac(999), recursion: 4.450
fac(3000), 10 repetitions, iteration: 1.470
fac(3000), 10 repetitions, tail-recursion with opt args: 1.670
fac(3000), 10 repetitions, tail-recursion with helper: 1.640
fac(3000), 10 repetitions, recursion: 1.520
fac(10000), 10 repetitions, iteration: 19.260
fac(10000), 10 repetitions, tail-recursion with opt args: 21.140
fac(10000), 10 repetitions, tail-recursion with helper: 21.100
fac(10000), 10 repetitions, recursion: 19.410

Allegro

fac(0) to fac(999), iteration: 2.927
fac(0) to fac(999), tail-recursion with opt args: 6.563
fac(0) to fac(999), tail-recursion with helper: 5.307
fac(0) to fac(999), recursion: 4.889
fac(3000), 10 repetitions, iteration: 1.689
fac(3000), 10 repetitions, tail-recursion with opt args: 2.241
fac(3000), 10 repetitions, tail-recursion with helper: 1.672
fac(3000), 10 repetitions, recursion: 1.605

LispWorks

fac(0) to fac(999), iteration: 5.684
fac(0) to fac(999), tail-recursion with opt args: 6.673
fac(0) to fac(999), tail-recursion with helper: 6.615
fac(0) to fac(999), recursion: 5.807
fac(3000), 10 repetitions, iteration: 1.987
fac(3000), 10 repetitions, tail-recursion with opt args: 2.157
fac(3000), 10 repetitions, tail-recursion with helper: 2.149
fac(3000), 10 repetitions, recursion: 2.018


--- the Lisp code ---

(in-package "CL-USER")

(defun fac-rec (n)
  (if (= n 0)
      1
      (* n (fac-rec (1- n)))))

(defun fac-tail-rec (n &optional (acc 1))
  (if (= n 0)
      acc
      (fac-tail-rec (1- n) (* n acc))))

(defun fac-tail-rec-with-helper (n)
  (fac-tail-rec-helper n 1))

(defun fac-tail-rec-helper (n acc)
  (if (= n 0)
      acc
      (fac-tail-rec-helper (1- n) (* n acc))))

(defun fac-iter (n)
  (do* ((i 1 (1+ i))
        (r 1 (* r i)))
       ((>= i n) r)))

(defmacro time-it (headline test-case)
  `(let ((start (get-internal-real-time)))
    ,test-case
    (format t ,(concatenate 'string
                            "~&" headline ": ~,3F~%")
     (/ (- (get-internal-real-time) start) internal-time-units-per-second))))

(defmacro make-test-case (n test-function &optional arg)
  `(dotimes (i ,n)
    (,test-function ,(if arg arg 'i))))

(time-it "fac(0) to fac(999), iteration" (make-test-case 1000 fac-iter))
(time-it "fac(0) to fac(999), tail-recursion with opt args" (make-test-case 1000 fac-tail-rec))
(time-it "fac(0) to fac(999), tail-recursion with helper" (make-test-case 1000 fac-tail-rec-with-helper))
(time-it "fac(0) to fac(999), recursion" (make-test-case 1000 fac-rec))
(time-it "fac(3000), 10 repetitions, iteration" (make-test-case 10 fac-rec 3000))
(time-it "fac(3000), 10 repetitions, tail-recursion with opt args" (make-test-case 10 fac-tail-rec 3000))
(time-it "fac(3000), 10 repetitions, tail-recursion with helper" (make-test-case 10 fac-tail-rec-with-helper 3000))
(time-it "fac(3000), 10 repetitions, recursion" (make-test-case 10 fac-rec 3000))
(time-it "fac(10000), 10 repetitions, iteration" (make-test-case 10 fac-rec 10000))
(time-it "fac(10000), 10 repetitions, tail-recursion with opt args" (make-test-case 10 fac-tail-rec 10000))
(time-it "fac(10000), 10 repetitions, tail-recursion with helper" (make-test-case 10 fac-tail-rec-with-helper 10000))
(time-it "fac(10000), 10 repetitions, recursion" (make-test-case 10 fac-rec 10000))


--- the C code ---

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include "gmp.h"

void fac_fake_rec (mpz_t *r, int n) {
    if (n == 0)
        mpz_set_si(*r, 1);
    else {
        fac_fake_rec(r, n - 1);
        mpz_mul_si(*r, *r, n);
    }
}

void fac_rec (mpz_t *r, int n) {
    mpz_t s;
    mpz_init(s);

    if (n == 0)
        mpz_set_si(s, 1);
    else {
        fac_rec(&s, n - 1);
        mpz_mul_si(s, s, n);
    }

    mpz_set(*r, s);
    mpz_clear(s);
}

void fac_iter (mpz_t *r, int n) {
    int i;

    mpz_set_si(*r, 1);
    for (i = 1; i <= n; i++)
        mpz_mul_si(*r, *r, i);
}

main (int argc, char **argv) {
    struct timeval tv;
    int i;
    long start, ustart;
    mpz_t r;
    mpz_init(r);

    gettimeofday(&tv, NULL);
    start = tv.tv_sec;
    ustart = tv.tv_usec;
    for (i = 0; i < 1000; i++)
        fac_rec(&r, i);
    gettimeofday(&tv, NULL);
    printf("fac(0) to fac(999), recursion: %.3f\n", (tv.tv_sec - start) + (float) (tv.tv_usec - ustart) / 1000000);

    gettimeofday(&tv, NULL);
    start = tv.tv_sec;
    ustart = tv.tv_usec;
    for (i = 0; i < 1000; i++)
        fac_fake_rec(&r, i);
    gettimeofday(&tv, NULL);
    printf("fac(0) to fac(999), fake recursion: %.3f\n", (tv.tv_sec - start) + (float) (tv.tv_usec - ustart) / 1000000);

    gettimeofday(&tv, NULL);
    start = tv.tv_sec;
    ustart = tv.tv_usec;
    for (i = 0; i < 1000; i++)
        fac_iter(&r, i);
    gettimeofday(&tv, NULL);
    printf("fac(0) to fac(999), iteration: %.3f\n", (tv.tv_sec - start) + (float) (tv.tv_usec - ustart) / 1000000);

    gettimeofday(&tv, NULL);
    start = tv.tv_sec;
    ustart = tv.tv_usec;
    for (i = 0; i < 10; i++)
        fac_rec(&r, 10000);
    gettimeofday(&tv, NULL);
    printf("fac(10000), 10 repetitions, recursion: %.3f\n", (tv.tv_sec - start) + (float) (tv.tv_usec - ustart) / 1000000);

    gettimeofday(&tv, NULL);
    start = tv.tv_sec;
    ustart = tv.tv_usec;
    for (i = 0; i < 10; i++)
        fac_fake_rec(&r, 10000);
    gettimeofday(&tv, NULL);
    printf("fac(10000), 10 repetitions, fake recursion: %.3f\n", (tv.tv_sec - start) + (float) (tv.tv_usec - ustart) / 1000000);

    gettimeofday(&tv, NULL);
    start = tv.tv_sec;
    ustart = tv.tv_usec;
    for (i = 0; i < 10; i++)
        fac_iter(&r, 10000);
    gettimeofday(&tv, NULL);
    printf("fac(10000), 10 repetitions, iteration: %.3f\n", (tv.tv_sec - start) + (float) (tv.tv_usec - ustart) / 1000000);
}