Subject: [clisp-list] tail recursion optimization

From: Elvin Peterson <[email-masked]>
Date: Wed Jul 28 10:02:36 2004

Hello,
  One of the stated advantages is tail recursion is
that it can be optmized automatically into loops.

(defun three-n (n m)
	   (cond
	     ((= n 1) m)
	     ((oddp n) (three-n (1+ (* 3 n)) (1+ m)))
	     (t (three-n (/ n 2) (1+ m)))))

This function remains unoptimized even after I call
compile.  Is there any command to force such
optimization?

TIA.

__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - Send 10MB messages!
http://promotions.yahoo.com/new_mail

---

From: Pascal J.Bourguignon <[email-masked]>
Date: Wed Jul 28 11:02:59 2004

> compile.  Is there any command to force such

I see it optimized:

CL-USER> (defun three-n (n m)
	   (cond
	     ((= n 1) m)
	     ((oddp n) (three-n (1+ (* 3 n)) (1+ m)))
	     (t (three-n (/ n 2) (1+ m)))))
THREE-N
CL-USER> (compile 'three-n)
THREE-N
NIL
NIL
CL-USER> (disassemble 'three-n)

Disassembly of function THREE-N
(CONST 0) = 1
(CONST 1) = 3
(CONST 2) = 1/2
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
22 byte-code instructions:
0     L0
0     (LOAD&PUSH 2)
1     (CONST&PUSH 0)                      ; 1
2     (CALLSR&JMPIF 1 45 L22)             ; =
6     (LOAD&PUSH 2)
7     (CALLS2&JMPIF 148 L25)              ; ODDP
10    (CONST&PUSH 2)                      ; 1/2
11    (LOAD&PUSH 3)
12    (CALLSR 2 55)                       ; *
15    L15
15    (PUSH)
16    (LOAD&INC&PUSH 2)
18    (JMPTAIL 2 5 L0)
22    L22
22    (LOAD 1)
23    (SKIP&RET 3)
25    L25
25    (CONST&PUSH 1)                      ; 3
26    (LOAD&PUSH 3)
27    (CALLSR&PUSH 2 55)                  ; *
30    (CALLS2 150)                        ; 1+
32    (JMP L15)
NIL
CL-USER> (lisp-implementation-version)
"2.33.1 (2004-05-22) (built 3297451256) (memory 3297451635)"
CL-USER> 

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein

---

From: Elvin Peterson <[email-masked]>
Date: Wed Jul 28 11:23:54 2004

> 27    (CALLSR&PUSH 2 55)                  ; *

This is what I get too.  I have the following code:

(defun max-cycle-len (n m)
	   (let ((max-len 0))
	     (dotimes (i (- m n) max-len)
	       (setf max-len (max (three-n (+ i n) 1)
max-len)))))

Since this is purely iterative, shouldn't the memory
requirements be constant?  However, I cannot run this
for values greater than 1,00,000, as it takes a lot of
time and space.

This is a problem I found on this site:
http://acm.uva.es/p/v1/100.html
And they have stated that C/C++ solutions run in time
0.00 for values of n,m close to 1,000,000.

TIA.

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

---

From: Pascal J.Bourguignon <[email-masked]>
Date: Wed Jul 28 14:00:44 2004

> for values greater than 1,00,000, as it takes a lot of

Did you try to evaluate the complexity of three-n?
There is even yet no proof that it will terminate for all integer input!

> 0.00 for values of n,m close to 1,000,000.

Same here in clisp:

CL-USER> (time (max-cycle-len 1000000 1000010))

Real time: 0.001348 sec.
Run time: 0.0 sec.
Space: 0 Bytes
259

---

From: Sam Steingold <[email-masked]>
Date: Wed Jul 28 14:41:11 2004

> * Elvin Peterson <[email-masked]> [2004-07-28 11:17:13 -0700]:
>
> Since this is purely iterative, shouldn't the memory requirements be
> constant?  However, I cannot run this for values greater than
> 1,00,000, as it takes a lot of time and space.

let us investigate:

(defun cycle-length (n &optional (len 1) (top 0))
  (cond ((= n 1) (values len top))
        ((evenp n) (cycle-length (ash n -1) (1+ len) (max top n)))
        (t (let ((next (1+ (* 3 n))))
             (cycle-length next (1+ len) (max top next))))))

(defun max-cycle-length (n m)
  (loop :with arg :and len = 0 :and top :for i :from n :to m :do
    (multiple-value-bind (le to) (cycle-length i)
      (when (> le len) (setq arg i len le top to)))
    :finally (return (values arg len top))))

thus we are getting not just the max cycle-length, but also the number
for which this maximum is achieved and the top intermediate number in
the sequence whose length is the cycle-length.

then let us see what data is actually allocated:

(ext:times (max-cycle-length 1000000 4000000))

                                            Permanent            Temporary
Class                                  instances   bytes    instances   bytes
-----                                  --------- ---------  --------- ---------
BIGNUM                                         1        16   13346541 160531616
-----                                  --------- ---------  --------- ---------
Total                                          1        16   13346541 160531616

Real time: 269.785242 sec.
Run time: 254.7262784 sec.
Space: 160566840 Bytes
GC: 18, GC time: 0.1702448 sec.
3732423 ;
597 ;
294475592320

so, the max cycle-length is 597, it is achieved on 3732423 and the
maximum number in the cycle is 294475592320 -- which is a bignum!

that's what you see in the TIMES output: there were 13346541 temporary
BIGNUMs allocated (for all the numbers in the cycles of all the integers
between 1000000 and 4000000) and a single permanent bignum for the
return value.

So the code operates in fixed stack space but it has to cons up some
bignums.

Note that

     (integer-length 294475592320) ==> 39

i.e. 32-bit integers are insufficient to perform the above calculations
(contrary to http://acm.uva.es/p/v1/100.html).

E.g.,

(defun max-cycle-length (n m)
  (loop :with arg :and len = 0 :and top :for i :from n :to m :do
    (multiple-value-bind (le to) (cycle-length i)
      (when (> (integer-length to) 32)
        (format t "~:D --> ~:D, ~:D~%" i le to))
      (when (> le len) (setq arg i len le top to)))
    :finally (return (values arg len top))))

(max-cycle-length 500000 1000000)
502,441 --> 333, 24,414,590,536
504,057 --> 196, 17,202,377,752
538,271 --> 178, 17,202,377,752
540,542 --> 408, 24,648,077,896
540,543 --> 408, 24,648,077,896
559,785 --> 165, 4,711,755,904
565,247 --> 328, 24,414,590,536
567,065 --> 191, 17,202,377,752
577,230 --> 390, 24,648,077,896
577,231 --> 390, 24,648,077,896
581,883 --> 204, 6,973,568,800
608,111 --> 403, 24,648,077,896
626,331 --> 509, 7,222,283,188
629,759 --> 160, 4,711,755,904
630,527 --> 240, 8,501,092,072
637,948 --> 186, 17,202,377,752
637,949 --> 186, 17,202,377,752
637,950 --> 186, 17,202,377,752
640,641 --> 416, 24,648,077,896
649,385 --> 385, 24,648,077,896
654,619 --> 199, 6,973,568,800
655,359 --> 292, 5,516,201,896
656,415 --> 292, 12,601,065,832
665,215 --> 442, 52,483,285,312
669,921 --> 336, 24,414,590,536
687,871 --> 380, 20,077,607,536
689,639 --> 212, 6,973,568,800
704,511 --> 243, 56,991,483,520
704,623 --> 504, 7,222,283,188
717,694 --> 181, 17,202,377,752
717,695 --> 181, 17,202,377,752
720,722 --> 411, 24,648,077,896
720,723 --> 411, 24,648,077,896
730,559 --> 380, 24,648,077,896
736,447 --> 194, 6,973,568,800
747,291 --> 248, 8,501,092,072
753,662 --> 331, 24,414,590,536
753,663 --> 331, 24,414,590,536
756,086 --> 194, 17,202,377,752
756,087 --> 194, 17,202,377,752
763,675 --> 318, 10,296,265,264
769,641 --> 393, 24,648,077,896
780,391 --> 331, 23,996,686,912
807,407 --> 176, 17,202,377,752
810,814 --> 406, 24,648,077,896
810,815 --> 406, 24,648,077,896
822,139 --> 344, 23,996,686,912
829,087 --> 194, 13,428,962,944
833,775 --> 357, 5,697,379,672
839,678 --> 163, 4,711,755,904
839,679 --> 163, 4,711,755,904
840,702 --> 243, 8,501,092,072
840,703 --> 243, 8,501,092,072
847,871 --> 326, 24,414,590,536
850,596 --> 189, 17,202,377,752
850,597 --> 189, 17,202,377,752
850,598 --> 189, 17,202,377,752
854,191 --> 419, 24,648,077,896
859,135 --> 313, 10,296,265,264
865,846 --> 388, 24,648,077,896
865,847 --> 388, 24,648,077,896
872,825 --> 202, 6,973,568,800
886,953 --> 445, 52,483,285,312
901,119 --> 251, 4,494,683,032
906,175 --> 445, 8,368,783,432
912,167 --> 401, 24,648,077,896
917,161 --> 383, 20,077,607,536
919,518 --> 215, 6,973,568,800
919,519 --> 215, 6,973,568,800
920,559 --> 308, 5,516,201,896
924,907 --> 339, 23,996,686,912
937,599 --> 339, 5,618,306,500
939,497 --> 507, 7,222,283,188
944,639 --> 158, 4,711,755,904
945,791 --> 238, 8,501,092,072
956,924 --> 184, 17,202,377,752
956,925 --> 184, 17,202,377,752
956,926 --> 184, 17,202,377,752
960,962 --> 414, 24,648,077,896
960,963 --> 414, 24,648,077,896
974,078 --> 383, 24,648,077,896
974,079 --> 383, 24,648,077,896
975,015 --> 321, 7,597,578,112
981,929 --> 197, 6,973,568,800
983,039 --> 290, 5,516,201,896
984,623 --> 290, 12,601,065,832
997,823 --> 440, 52,483,285,312

837,799 ;
525 ;
2,974,984,576

note that max LEN and max TOP are achieved on different arguments!

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
When we write programs that "learn", it turns out we do and they don't.

---

From: Elvin Peterson <[email-masked]>
Date: Wed Jul 28 19:44:02 2004

> There is even yet no proof that it will terminate

Indeed there is no proof.  I think it is an example
problem in "A Gentle Introduction to Lisp".  However,
it has been verified for very large numbers, and in
this case the limit is 1,000,000.

> CL-USER> (time (max-cycle-len 1000000 1000010))

It will be much longer if you actually want to find
the maximum length, i.e., 

(max-cycle-len 1 1000000)

Thanks.

---

From: Elvin Peterson <[email-masked]>
Date: Wed Jul 28 19:54:01 2004

> > * Elvin Peterson <[email-masked]>

Does this mean that the output of times is not the
actual maximum memory that is used by the function?

> (contrary to http://acm.uva.es/p/v1/100.html).

So the performance problem is purely due to BIGNUM
allocation?  I suppose then the code will run very
fast on a machine with 64 bit integers.

> (max-cycle-length 500000 1000000)

This makes sense in light of the earlier explanation.

Thanks for all the help!

---

From: Pascal J.Bourguignon <[email-masked]>
Date: Wed Jul 28 21:37:01 2004

Elvin Peterson writes:
> > > And they have stated that C/C++ solutions run in
> > > time 0.00 for values of n,m close to 1,000,000.
> > 
> > Same here in clisp:
> > 

But 1 is not close to 1000000, at least by my undestanding of
close. Do you believe that max_cycle_len(1,1000000) would take only 0
second in C? (While still giving you correct results on a 32bit processor?)

---

From: Edi Weitz <[email-masked]>
Date: Wed Jul 28 23:17:13 2004

On Thu, 29 Jul 2004 06:35:56 +0200, Pascal J.Bourguignon <[email-masked]> wrote:

> Do you believe that max_cycle_len(1,1000000) would take only 0

You can try yourself:

  <http://online-judge.uva.es/problemset/data/p100.c.html>

Of course, it doesn't complete in 0.0 seconds - I killed the program
after it had consumed 100% of my CPU (PIII 1200) for about five
minutes. And of course, as Sam Steingold has pointed out, this
"solution" fails miserably as soon as the numbers involved don't fit
into 32 bits anymore while a Lisp program will yield correct results.

Cheers,
Edi.

---

From: Sam Steingold <[email-masked]>
Date: Thu Jul 29 06:45:07 2004

> * Elvin Peterson <[email-masked]> [2004-07-28 19:53:38 -0700]:
>
> --- Sam Steingold wrote:
>
>> 

both EXT:TIMES and TIME print the total memory allocated.
(not the maximum memory used)

> So the performance problem is purely due to BIGNUM allocation?

no, it's not just allocations, it's also calculations.

the larger the numbers, the longer the cycle and the more expensive is
the cycle-length computation because bignum operations are more
expensive for larger bignums.

> I suppose then the code will run very fast on a machine with 64 bit
> integers.

as long as everything fits into fixnums, performance is better.
unfortunately, even on a 64 bit machine, fixnums are rarely large
(32 bits on CLISP right now, see
<https://sourceforge.net/tracker/?func=detail&atid=351355&aid=999750&group_id=1355>).

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
Booze is the answer. I can't remember the question.

---

From: Elvin Peterson <[email-masked]>
Date: Thu Jul 29 07:42:01 2004

--- Sam Steingold wrote:

> > * Elvin Peterson <[email-masked]>
> 
> >> Note that
> >> 
> >> i.e. 32-bit integers are insufficient to perform
> the
> >> above calculations
> allocation?

Looks like it will take a lot of effort to implement
64 bit in clisp.  But it may be a long time before
systems are 64 bit by default (I know several Solaris
installations which are still 32 bit, lowest common
denominator and everything).

---

From: Elvin Peterson <[email-masked]>
Date: Thu Jul 29 07:54:07 2004

--- Edi Weitz wrote:

> On Thu, 29 Jul 2004 06:35:56 +0200, Pascal
> J.Bourguignon wrote:
> 
> > second in C? (While still giving you correct
> results on a 32bit
> > processor?)
> 
> You can try yourself:
> 
>  
>
> into 32 bits anymore while a Lisp program will yield

Ack!  If you can't trust a random site on the
Internet, who can you trust?  However, in their
results page, they had the top 20 people finishing
with time 0.00.

Thanks again to all those who replied.

__________________________________
Do you Yahoo!?
Read only the mail you want - Yahoo! Mail SpamGuard.
http://promotions.yahoo.com/new_mail

---

From: Raymond Toy <[email-masked]>
Date: Thu Jul 29 08:09:05 2004

>>>>> "Sam" == Sam Steingold <[email-masked]> writes:

    Sam> as long as everything fits into fixnums, performance is better.
    Sam> unfortunately, even on a 64 bit machine, fixnums are rarely large
    Sam> (32 bits on CLISP right now, see
    Sam> <https://sourceforge.net/tracker/?func=detail&atid=351355&aid=999750&group_id=1355>).

Do you mean running a 32-bit lisp on a 64-bit machine?  Then yes,
you're right.  But a 64-bit lisp on a 64-bit machine would presumably
have fixnum that are close to 60 bits in length.  I'm pretty sure that
64-bit ACL uses 60-bit fixnums.  I suspect cmucl and sbcl will have
60-bit fixnums if the amd64 port ever gets done.

Ray

---

From: Raymond Toy <[email-masked]>
Date: Thu Jul 29 09:27:02 2004

>>>>> "Elvin" == Elvin Peterson <[email-masked]> writes:

    Elvin> Looks like it will take a lot of effort to implement
    Elvin> 64 bit in clisp.  But it may be a long time before
    Elvin> systems are 64 bit by default (I know several Solaris
    Elvin> installations which are still 32 bit, lowest common
    Elvin> denominator and everything).

What kind of Sun machines are they running?  Ultra 2 slower than 170
MHz?  Or maybe they're still running Solaris 2.5?  All Ultra machines
are 64-bit, but I don't think Solaris became 64-bit until 2.6 or 2.7.
(Could be wrong, though.)

Ray

---

From: Elvin Peterson <[email-masked]>
Date: Thu Jul 29 09:47:01 2004

> (Could be wrong, though.)

Only a few of them were older OSes, but going 64 bit
would cause a lot of administrative overhead with the
binaries (on NFS) for different machines.

__________________________________
Do you Yahoo!?
Yahoo! Mail - 50x more storage than other providers!
http://promotions.yahoo.com/new_mail

---

From: Raymond Toy <[email-masked]>
Date: Thu Jul 29 09:57:19 2004

>>>>> "Elvin" == Elvin Peterson <[email-masked]> writes:

    Elvin> Only a few of them were older OSes, but going 64 bit
    Elvin> would cause a lot of administrative overhead with the
    Elvin> binaries (on NFS) for different machines.

Don't see how that follows.  I only run 32-bit apps on the 64-bit Sun
boxes at work.  I have no need for 64-bit apps, and I don't we have
any anywhere either. :-)

But this no longer has anything to do with clisp, so....

Ray

---

From: Edi Weitz <[email-masked]>
Date: Thu Jul 29 10:16:12 2004

On Thu, 29 Jul 2004 07:53:03 -0700 (PDT), Elvin Peterson <[email-masked]> wrote:

> Ack!  If you can't trust a random site on the Internet, who can you
> trust?  However, in their results page, they had the top 20 people
> finishing with time 0.00.

To make this clear: The C program took more than five minutes for the
input that you proposed. That doesn't mean it couldn't perform in 0.0
seconds for other input. I think the contest site only posted the
timing results but not the input that was used.

Edi.