Hi, how good is lispworks at tail-call (non-self) elimination? I have a pretty simple code with interchanging tail calls, and all while all other lisps optimize it into a loop, lispworks does not. I can work around it, but its a pity not to have this in a lisp. David
On דצמ 12, 2005, at 13:55, David Tolpin wrote:
> Hi,
>
> how good is lispworks at tail-call (non-self) elimination?
For example, the following code:
(declaim (optimize (speed 3) (debug 0)))
(defun LEN (s)
(declare (type string s))
(let ((end (length s)))
(declare (type fixnum s))
(labels ((UX (i n)
(declare (type fixnum n))
(if (zerop n) (left (1+ i))
(ux i (1- n))))
(LEFT (i)
(declare (type fixnum i))
(if (>= i end) i
(ux i 1))))
(left 0))))
does not seem to compile into a loop, and this call:
(len (make-array 1000000 :element-type 'base-char :initial-element
#\Space))
causes stack overflow. Meanwhile, in CMU CL, Allegro and OpenMCL it
runs in a fraction of a second.
David
David Tolpin wrote: > how good is lispworks at tail-call (non-self) elimination? According to the Lispworks User Manual (section 9.4), tail calls will be eliminated for a DEBUG level less than 3. (I think the default DEBUG level is 3.)
On 12 Dec 2005, at 10:55, David Tolpin wrote: > Hi, > > how good is lispworks at tail-call (non-self) elimination? I have a > pretty simple code with interchanging tail calls, and all while all > other lisps optimize it into a loop, lispworks does not. I can work > around it, but its a pity not to have this in a lisp. See Section 9.4 in the LispWorks User Guide. Essentially, if debug<=2 tail calls will be merged, and if debug<2 and safety<2, self calls will be optimized (IIUC). Pascal -- Pascal Costanza, mailto:pc@p-cos.net, http://p-cos.net Vrije Universiteit Brussel, Programming Technology Lab Pleinlaan 2, B-1050 Brussel, Belgium
Hi, I think you need to turn off source debugging in LW (hcl:toggle-source-debugging nil) see http://www.lispworks.com/kb/f35acd8100dfd9ba8525670b0074a8d6.html cheers paulm At 11:29 12/12/2005, David Tolpin wrote: >On ××¦× 12, 2005, at 13:55, David Tolpin wrote: > >>Hi, >> >>how good is lispworks at tail-call (non-self) elimination? > >For example, the following code: > >(declaim (optimize (speed 3) (debug 0))) >(defun LEN (s) > (declare (type string s)) > (let ((end (length s))) > (declare (type fixnum s)) > (labels ((UX (i n) > (declare (type fixnum n)) > (if (zerop n) (left (1+ i)) > (ux i (1- n)))) > (LEFT (i) > (declare (type fixnum i)) > (if (>= i end) i > (ux i 1)))) > (left 0)))) > >does not seem to compile into a loop, and this call: > >(len (make-array 1000000 :element-type 'base-char :initial-element #\Space)) > >causes stack overflow. Meanwhile, in CMU CL, Allegro and OpenMCL it runs >in a fraction of a second. > >David >
On Mon, 12 Dec 2005 16:25:55 +0400, David Tolpin <dvd@davidashen.net> wrote: > With (declaim (optimize (speed 3) (space 3) (safety 0) (debug 0))) DECLAIM? Where did you have your DECLAIM statements? Did you try with a DECLARE declaration within the functions? > the following code snippet is NOT optimized: > > (defun UX (s i n) > (if (zerop n) (left s (1+ i)) > (ux s i (1- n)))) > > (defun LEFT (s i) > (if (>= i (length s)) i > (ux s i 1))) > > (defun LEN (s) > (left s 0)) I don't know what makes you sure enough to use such a strong wording but if I look at the disassemblies of these functions, even without declarations, I see JMPs from UX to LEFT, from LEFT to UX, and from LEN to LEFT - pretty much what one would expect. > and the following calll causes stack overflow: > > (len (make-array 1000000 :initial-element #\Space :element-type > base-char)) Not on my machine (LispWorks 4.4.6 pro on Windows and Linux). Cheers, Edi.