From: Cheung, M. G <mgc...@hr...> - 2011-06-14 16:38:37
|
One thing that has never been clear to me was whether SBCL will by default use tail recursion optimisations. I wrote a general "repeated squaring" function that takes as it's arguments a "squaring" function a "multiply" function, the base and the exponent and I wrote it tail recursively. This was to be used for both modular exponentiation and point multiplication on an elliptic curve. So can I assume SBCL will optimise by default? This question is probably more general lisp, but is it considered a better practice when writing a function using tail recursion to use a local function to do the actual tail recursion? Is it a bad idea to use an optional or keyword parameter to store the results of the intermediate calculations? In this case it seemed like it was a good idea since this function would be acting on different types of objects so I could tell it to start with 1 if I was doing modular exponentiation or the point at infinity for the elliptic curve case. Thanks. |
From: Nikodemus S. <nik...@ra...> - 2011-06-14 16:53:44
|
On 14 June 2011 19:38, Cheung, Matthew G <mgc...@hr...> wrote: > One thing that has never been clear to me was whether SBCL will by > default use tail recursion optimisations. I wrote a general "repeated Tail-merging is done if (> SPACE DEBUG) or (> SPEED DEBUG) -- not by default. > This question is probably more general lisp, but is it considered a > better practice when writing a function using tail recursion to use a > local function to do the actual tail recursion? Is it a bad idea to use Depends on the case, but if eg. floating point arguments are involved a local call may be more efficient. > an optional or keyword parameter to store the results of the > intermediate calculations? In this case it seemed like it was a good Stylistically it's fine. >From micro-efficiency POV it is less than ideal. &OPTIONAL is pretty cheap, but unless the function is inlined &KEY incurs a runtime cost for keyword parsing. Cheers, -- nikodemus |
From: Jim W. <jw...@dr...> - 2011-06-14 18:30:58
|
"Cheung, Matthew G" <mgc...@hr...> writes: > One thing that has never been clear to me was whether SBCL will by default > use tail recursion optimisations. I wrote a general "repeated squaring" > function that takes as it's arguments a "squaring" function a "multiply" > function, the base and the exponent and I wrote it tail recursively. This > was to be used for both modular exponentiation and point multiplication on > an elliptic curve. So can I assume SBCL will optimise by default? Nikodemus pointed out the combination of optimization vs. debug declarations you need to make TCO happen. Beyond that, TCO has behaved very well for me -- I have a largish hardware simulator (a (currently subset of a) simulator of Knuth's MIX) that I've used for testing, written entirely in CPS, and I've left it running a loop for a large number of iterations without seeing stack growth. -- Jim Wise jw...@dr... |
From: Faré <fa...@gm...> - 2011-06-14 21:31:57
|
On 14 June 2011 14:30, Jim Wise <jw...@dr...> wrote: > "Cheung, Matthew G" <mgc...@hr...> writes: > >> One thing that has never been clear to me was whether SBCL will by default >> use tail recursion optimisations. I wrote a general "repeated squaring" >> function that takes as it's arguments a "squaring" function a "multiply" >> function, the base and the exponent and I wrote it tail recursively. This >> was to be used for both modular exponentiation and point multiplication on >> an elliptic curve. So can I assume SBCL will optimise by default? > > Nikodemus pointed out the combination of optimization vs. debug > declarations you need to make TCO happen. > > Beyond that, TCO has behaved very well for me -- I have a largish > hardware simulator (a (currently subset of a) simulator of Knuth's MIX) > that I've used for testing, written entirely in CPS, and I've left it > running a loop for a large number of iterations without seeing stack > growth. > jsnell once gave me this recipe to ensure that SBCL will do TCO is: (declaim (optimize #+sbcl (sb-c::merge-tail-calls 3) #+sbcl (sb-c::insert-debug-catch 0)) More generally, I've created a library ptc on common-lisp.net to let people semi-portably declare their code to require proper tail-calls. git clone http://common-lisp.net/~frideau/git/ptc.git Patches welcome. —♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• http://fare.tunes.org I'd rather write programs that write programs than write programs — Dick Sites |
From: Teemu L. <tli...@ik...> - 2011-07-13 17:38:34
|
* 2011-06-14T19:53:36+03:00 * Nikodemus Siivola wrote: > On 14 June 2011 19:38, Cheung, Matthew G <mgc...@hr...> wrote: >> One thing that has never been clear to me was whether SBCL will by >> default use tail recursion optimisations. I wrote a general >> "repeated > > Tail-merging is done if (> SPACE DEBUG) or (> SPEED DEBUG) -- not by > default. Is the TRACE output a reliable way to tell whether optimization on recursive calls has occurred? See the following toy example. It is recursive but, if I understand correctly, there is no tail-call. Without much speed optimization: (defun sum (numbers) (declare (optimize (speed 0) (debug 0))) (if numbers (+ (first numbers) (sum (rest numbers))) 0)) CL-USER> (trace sum) (SUM) CL-USER> (sum '(1 2 3 4)) 0: (SUM (1 2 3 4)) 1: (SUM (2 3 4)) 2: (SUM (3 4)) 3: (SUM (4)) 4: (SUM NIL) 4: SUM returned 0 3: SUM returned 4 2: SUM returned 7 1: SUM returned 9 0: SUM returned 10 10 Now the same thing with more speed: (defun sum (numbers) (declare (optimize (speed 3) (debug 0))) (if numbers (+ (first numbers) (sum (rest numbers))) 0)) CL-USER> (sum '(1 2 3 4)) 0: (SUM (1 2 3 4)) 0: SUM returned 10 10 It seems that the was only one call to SUM so either there is some optimization or TRACE couldn't track what's really happening. |
From: Nikodemus S. <nik...@ra...> - 2011-07-13 17:55:36
|
On 13 July 2011 20:38, Teemu Likonen <tli...@ik...> wrote: > Is the TRACE output a reliable way to tell whether optimization on > recursive calls has occurred? See the following toy example. It is > recursive but, if I understand correctly, there is no tail-call. Nope. Tail-merging has no effect on whether TRACE shows the call or not. What you're seeing is the effect of self-calls being optimized to local calls, instead of going through the FDEFINITION -- which TRACE has instrumented. Cheers, -- nikodemus |
From: Teemu L. <tli...@ik...> - 2011-07-13 18:13:20
|
* 2011-07-13T20:55:29+03:00 * Nikodemus Siivola wrote: > Tail-merging has no effect on whether TRACE shows the call or not. > What you're seeing is the effect of self-calls being optimized to > local calls, instead of going through the FDEFINITION -- which TRACE > has instrumented. Thanks. I suspected something like that. TRACE couldn't see those local calls. |
From: Gabriel D. R. <gd...@in...> - 2011-07-13 19:25:55
|
On Wed, Jul 13, 2011 at 12:55 PM, Nikodemus Siivola <nik...@ra...> wrote: > Tail-merging has no effect on whether TRACE shows the call or not. > What you're seeing is the effect of self-calls being optimized to > local calls, instead of going through the FDEFINITION -- which TRACE > has instrumented. Does this mean SBCL functions defined with FLET or LABELS? Or, from SBCL point of view, there is no effect, it is just stylistic? -- Gaby |
From: Nikodemus S. <nik...@ra...> - 2011-07-14 13:22:37
|
On 13 July 2011 22:25, Gabriel Dos Reis <gd...@in...> wrote: >> Tail-merging has no effect on whether TRACE shows the call or not. >> What you're seeing is the effect of self-calls being optimized to >> local calls, instead of going through the FDEFINITION -- which TRACE >> has instrumented. > > Does this mean SBCL functions defined with FLET or LABELS? > Or, from SBCL point of view, there is no effect, it is just > stylistic? I'm not sure I understand the question, but I'll try to answer anyways. If SPEED or SPACE is > DEBUG, and FOO calls itself (tail or non-tail call doesn't come into it) (defun foo (...) ...) is compiled approximately as if you had written (defun foo (...) (labels ((foo (...) ...)) (foo ...))) instead. When you do (TRACE FOO) something along the lines of (let ((orig (fdefinition 'foo))) (setf (fdefinition 'foo) (lambda (&rest args) (trace-call 'foo args) (let ((values (multiple-value-list (apply orig args)))) (trace-return 'foo values) (values-list values))))) takes place. Put these two together, and it should be fairly obvious why the optimization in question makes trace miss the self-calls. Cheers, -- nikodemus |
From: Gabriel D. R. <gd...@in...> - 2011-07-19 07:49:17
|
On Thu, Jul 14, 2011 at 8:22 AM, Nikodemus Siivola <nik...@ra...> wrote: > On 13 July 2011 22:25, Gabriel Dos Reis <gd...@in...> wrote: > >>> Tail-merging has no effect on whether TRACE shows the call or not. >>> What you're seeing is the effect of self-calls being optimized to >>> local calls, instead of going through the FDEFINITION -- which TRACE >>> has instrumented. >> >> Does this mean SBCL functions defined with FLET or LABELS? >> Or, from SBCL point of view, there is no effect, it is just >> stylistic? > > I'm not sure I understand the question, but I'll try to answer anyways. > > If SPEED or SPACE is > DEBUG, and FOO calls itself (tail or non-tail > call doesn't come into it) > > (defun foo (...) > ...) > > is compiled approximately as if you had written > > (defun foo (...) > (labels ((foo (...) > ...)) > (foo ...))) > > instead. > > When you do > > (TRACE FOO) > > something along the lines of > > (let ((orig (fdefinition 'foo))) > (setf (fdefinition 'foo) (lambda (&rest args) > (trace-call 'foo args) > (let ((values (multiple-value-list > (apply orig args)))) > (trace-return 'foo values) > (values-list values))))) > > takes place. That answers the question. Thanks. |
From: DS <sb...@so...> - 2011-07-15 18:31:49
|
On 13 Jul 2011, at 19:38, Teemu Likonen wrote: > See the following toy example. It is > recursive but, if I understand correctly, there is no tail-call. > > (defun sum (numbers) > (declare (optimize (speed 0) (debug 0))) > (if numbers > (+ (first numbers) (sum (rest numbers))) > 0)) That call to sum is not in a tail position, its result is passed to #'+. Tail-merging is not possible here. You should use an accumulator. (defun sum (numbers &optional (accum 0)) (if numbers (sum (rest numbers) (+ accum (first numbers))) accum)) Regards. -Daniel |
From: Teemu L. <tli...@ik...> - 2011-07-15 18:52:09
|
* 2011-07-15T20:02:50+02:00 * DS wrote: > That call to sum is not in a tail position, its result is passed to > #'+. Tail-merging is not possible here. I know. My point was that TRACE output for that function shows a single call to the function and then I asked if there was some optimization done even for this kind non-tail-call recursion. The answer was "no". The call was just short-circuited so that TRACE couldn't see the calls. > You should use an accumulator. That's what I do when I want one. :-) |