I've just started learning Common Lisp and as a simple exercise of what I've
learned so far I thought I might write a program that allows one to play around
a bit with Collatz sequences.
I thus produced the following program:

(defun coll-step (n)
  (if (= (mod n 2) 0) (/ n 2) (+ 1 (* 3 n))))
(defun coll-max (n)
  "Computes the maximum of the collatz sequence starting with its argument"
  (coll-max-iter n n n))
(defun coll-max-iter (n a b)
  (if (< n a) b (coll-max-iter (coll-step n) a (max b n))))
(defun max-lst (n)
  "prints out all n up to its argument which have the property that
coll-max(m)>=coll-max(n) ==> m >= n"
  (max-lst-iter 3 n (coll-max 3)))
(defun max-lst-iter (n range mx)
  (if (> n range) mx
    (max-lst-iter (+ n 4) range (next n (coll-max n) mx))))
(defun next (n am mx)
  (if (> am mx) (toscreen n am) mx))
(defun toscreen (n am)
  (write (list n am))
  am)

The program works fine, except for the fact that I am not feeling well about
its performance speed-wise. Does anyone on this group have any tips to offer
regarding improvements in this respect? (I am working with Allegro Common
Lisp).

Try using the TIME macro to see if you're consing alot.  If your Lisp
implementation has a profiling feature, try using that to see where the
bottleneck is.

Will Fitzgerald

Some mistakes are regrettably easy to make, and if you think I'm
calling you "stupid," the moniker would have to apply just as much to
myself...

  Evaluate (excl::explain-compiler-settings) and turn on the various
  :explain options.  The amount of output even exceeds CMUCL at its worst,
  but it can be very helpful in realizing when and how to declare stuff.

  What were the types of variables in the C version?  How much time does a
  function call usually take?  Do you have an example?

..

#include <stdio.h>

     int main(void)
     {   long int nmax=0;

         int new_max = 0;
         long long a, amax = 0;
         scanf("%d",&nmax);

         for (int n = 3; n <= nmax; n=n+4)
         {
             a = n;

             while (a >= n)
             {
                 if (a&1)
                 {
                     a = 3*a + 1;

                     if (a > amax)
                     {
                         amax = a;

                         if (!new_max) new_max = 1;
                     }
                 }
                 else
                 {
                     a = a >> 1;
                 }
             }

             if (new_max)
             {
                 new_max = 0;

                 printf("%d : %e\n", n, (double) amax);
             }

         }

         return 0;
     }

On my machine and compiled with lcc-win32, this takes around 0.6 seconds to do
the equivalent of evaluating max-lst(1000000), which in turn takes just under 6
seconds on my machine under allegro common lisp. The number type I'm using in C
is long long, which happens to go just high enough for this application and
reasonable input values.

If the recursion gets very deep, you could be taking more page faults on
the stack.  Iterative solutions don't have this problem.  Are you assuming
tail-recursion elimination in the Lisp version?  Lisp isn't Scheme, and
many Lisp implementations don't do tail-call optimization, or they only do
them with specific optimization settings enabled.

What happens if you change both programs to use double-precision floating
point?

Maybe it's a combination of the bignum arithmetic and the recursion
vs. iteration difference.

Anyway, I rewrote your program using LOOP and type declarations:

  (defun iterative-max-list (range)
    (declare (type (unsigned-byte 64) range))
    (flet ((coll-max (a)
             (loop for n of-type (unsigned-byte 64) = a
                       then (if (evenp n) (floor n 2) (1+ (* 3 n)))
                   for b of-type (unsigned-byte 64) = n then (max b n)
                     until (< n a)
                   finally (return (max b n)))))
      (loop with max of-type (unsigned-byte 64) = (coll-max 3)
            for n of-type (unsigned-byte 64) from 3 to range by 4
            for am of-type (unsigned-byte 64) = max then (coll-max n)
            when (> am max)
              do (princ (list n am))
                 (setf max am)
            finally (return max))))

I compiled both versions in CMUCL with
(optimize (speed 3) (safety 1) (compilation-speed 0) (space 0))
and your C version with gcc.

On my Celeron 500 under linux:

"echo 1000000 | ./max_list", compiled with gcc -O
  Min: 0.273s
  Max: 0.721s
  Mean: 0.48250000000000004s

"echo 1000000 | ./max_list", compiled with gcc -O3
  Min: 0.45s
  Max: 0.628s
  Mean: 0.5326s

(iterative-max-list 1000000)
  Min: 0.84s
  Max: 0.85s
  Mean: 0.85s

(max-lst 1000000)
  Min: 2.14s
  Max: 2.17s
  Mean: 2.17s

Each test was run 11 times, and only counted the last 10 runs.  So,
counting only the best versions in C and Lisp:

  Min: 311.11% of C
  Max: 118.06% of C
  Mean: 177.08% of C

It could be better, but it's not too bad.  And certainly better than
1000% :-).  Also, changing that type declaration to integer instead of
(unsigned-byte 64) runs at 150% of the long-long-equivalent version,
which is an option you don't have in C :-).  Also, be sure to bind
*print-pretty* to nil when you run the Lisp version or it might spend
a lot of time formatting its output.

I've written my own iterative version of my program in the meantime. It's not
nearly as fast as yours, because I didn't put in the appropriate declarations,
but it is significantly faster than my first try nonetheless.
On my machine and under Allegro Common Lisp, your code seems to be around 3.5
times slower than the C program. I guess the difference to your measurements
can be attributed to me having used another compiler than you; I probably ought
to finally get me Linux and CMUCL ;)...

I've done a few minor changes on your program now, which seem to give a speedup
of an additional ten percent on my system :)... :

(defun iterative-max-list (range)
    (declare (type (unsigned-byte 64) range))
  (flet ((coll-max (a)
                   (let* ((b a))
                       (loop for n of-type (unsigned-byte 64) = a
                           then (if (evenp n) (floor n 2) (progn
                                                            (setf x (1+ (* 3
n)))
                                                      (setf b (max x b))
                                                            (floor x 2)))
                             for x of-type (unsigned-byte 64) = a
                     until (< n a)
                   finally (return (max b n))))))
      (loop with max of-type (unsigned-byte 64) = (coll-max 3)
            for n of-type (unsigned-byte 64) from 3 to range by 4
            for am of-type (unsigned-byte 64) = max then (coll-max n)
            when (> am max)
              do (princ (list n am))
                 (setf max am)
            finally (return max))))

I don't think that what I did here looks very elegant. If someone has something
better to offer, I'd be glad to see it.

  (defun iterative-max-list (range)
    (declare (type (unsigned-byte 64) range))
    (flet ((coll-max (a)
                     (let* ((b a))
                       (loop for n of-type (unsigned-byte 64) = a
                                 then (if (evenp n)
                                          (floor n 2)
                                        (prog1
                                            (setf x (1+ (* 3 n)))
                                          (setf b (max x b))))
                             for x of-type (unsigned-byte 64) = a
                             until (< n a)
                             finally (return (max b n))))))
           (loop with max of-type (unsigned-byte 64) = (coll-max 3)
                 for n of-type (unsigned-byte 64) from 3 to range by 4
                 for am of-type (unsigned-byte 64) = max then (coll-max n)
                 when (> am max)
                   do (princ (list n am))
                      (setf max am)
                 finally (return max))))

  (defun iterative-max-list (range)
    (declare (type (unsigned-byte 64) range))
      (loop with max of-type (unsigned-byte 64) = 0
            for a of-type (unsigned-byte 64) from 3 to range by 4
            for am of-type (unsigned-byte 64) = max
                then (let ((n a))
                       (declare (type (unsigned-byte 64) n))
                       (loop if (evenp n)
                               do (setq n (floor n 2))
                             else
                               maximize (setq n (1+ (* 3 n)))
                             until (< n a)))
            when (> am max)
              do (princ (list a
                              (setf max am)))
            finally (return max)))

or, if you're only interested in the maximum value,

  (defun iterative-max-list (range)
    (declare (type (unsigned-byte 64) range))
      (loop for a of-type (unsigned-byte 64) from 3 to range by 4
            for am of-type (unsigned-byte 64) = 0
                then (let ((n a))
                       (declare (type (unsigned-byte 64) n))
                       (loop if (evenp n)
                               do (setq n (floor n 2))
                             else
                               maximize (setq n (1+ (* 3 n)))
                             until (< n a)))
            maximize am))

I have to add that I wasn't able to get ratios as good as Thomas
F. Burdick's on my machine (CMUCL 18c, P3 850, 256 MB RAM, Linux
2.4.10) - even with the same compilation options and with
*PRINT-PRETTY* set to NIL. The C program - compiled with -O3 - was
about 3 times as fast. If I compared the last version with a modified
C program that also only prints the final result it got even worse:
The C program was about 5 to 6 times as fast as CMUCL.

On the other hand, CMUCL was significantly faster than AllegroCL, ECL,
or LispWorks - which didn't surprise me very much...

#include <stdio.h>

     int main(void)
     {   long int nmax=0;

         int new_max = 0;
         long long a, amax = 0;
         nmax=1000000;
                 // scanf("%d",&nmax);

         for (int n = 3; n <= nmax; n=n+4)
         {
             a = n;

             while (a >= n)
             {
                 if (a&1)
                 {
                     a = 3*a + 1;

                     if (a > amax)
                     {
                         amax = a;

                         if (!new_max) new_max = 1;
                     }
        a=a >> 1;         }
                 else
                 {
                     a = a >> 1;
                 }
             }

             if (new_max)
             {
                 new_max = 0;

                 printf("%d : %e\n", n, (double) amax);
             }

         }

         return 0;
     }

compiled with lcc-win32, I get a ratio of just under five versus the version of
the lisp program I posted recently (I get a runtime of 0.5 seconds on my
machine for C vs. 2.35 seconds for Lisp).
What do you get here with CMUCL?

I just compared the two programs again, doing the equivalent of evaluating
(iterative-max-list 100000000) in both Lisp and C. I get runtimes of 746
seconds for Lisp versus 33.5 seconds for C, which is a 22:1 disadvantage for
Lisp :(...