Hello fellow
lispers,
Pedantic optimization question
follow.
I have functions that traverse trees recursively
like:
(defun find-in-tree (start val)
(if (value-match start val)
start
(foreach-child (start el) (find-in-tree el val))))
Now, that works peachy. My second iteration, just to make the
TRACE
simple and for the love of premature optimization I throw/
catch.
(defun find-in-tree (start val)
(labels ((find-in-tree-fn (node)
(if (value-match node val)
(throw 'found val)
(foreach-child (node el) (find-in-tree-fn el)))))
(catch 'found
(find-in-tree-fn start))))
My question is, do I gain anything with this approach? Does
the
throw gain me anything over just returning back up the
stack?
William Halliburton <············@gmail.com> writes:
> Hello fellow
> lispers,
>
> Pedantic optimization question
> follow.
>
> I have functions that traverse trees recursively
> like:
>
> (defun find-in-tree (start val)
> (if (value-match start val)
> start
> (foreach-child (start el) (find-in-tree el val))))
>
> Now, that works peachy. My second iteration, just to make the
> TRACE
> simple and for the love of premature optimization I throw/
> catch.
>
> (defun find-in-tree (start val)
> (labels ((find-in-tree-fn (node)
> (if (value-match node val)
> (throw 'found val)
> (foreach-child (node el) (find-in-tree-fn el)))))
> (catch 'found
> (find-in-tree-fn start))))
>
> My question is, do I gain anything with this approach? Does
> the
> throw gain me anything over just returning back up the
> stack?
Since the throw and catch are in a single scope, you don't gain
anything using them instead of block/return-from:
(defun find-in-tree (start val)
(labels ((recurse (node)
(if (value-match node val)
(return-from find-in-tree val)
(foreach-child (node el) (recurse el)))))
(recurse start)))
; (the block is automatically generated by defun)
--
__Pascal Bourguignon__
On Jun 21, 12:00 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> William Halliburton <············@gmail.com> writes:
> > My question is, do I gain anything with this approach? Does
> > the
> > throw gain me anything over just returning back up the
> > stack?
>
> Since the throw and catch are in a single scope, you don't gain
> anything using them instead of block/return-from:
>
> (defun find-in-tree (start val)
> (labels ((recurse (node)
> (if (value-match node val)
> (return-from find-in-tree val)
> (foreach-child (node el) (recurse el)))))
> (recurse start)))
This is a good suggestion, but it still leaves the question: will it
be any faster than just returning? I wouldn't expect it to make much
difference, but I suppose it could make a little. It's not going to
improve the time complexity of your algorithm, though, so I don't
think I would bother unless it somehow made the code for FOREACH-CHILD
clearer.
-- Scott
-- Scott
Scott Burson <········@gmail.com> writes:
> On Jun 21, 12:00�pm, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> William Halliburton <············@gmail.com> writes:
>> > My question is, do I gain anything with this approach? Does
>> > the
>> > throw gain me anything over just returning back up the
>> > stack?
>>
>> Since the throw and catch are in a single scope, you don't gain
>> anything using them instead of block/return-from:
>>
>> (defun find-in-tree (start val)
>> � (labels ((recurse (node)
>> � � � � � � � (if (value-match node val) �
>> � � � � � � � � �(return-from find-in-tree val)
>> � � � � � � � � �(foreach-child (node el) (recurse el)))))
>> � � (recurse start)))
>
> This is a good suggestion, but it still leaves the question: will it
> be any faster than just returning? I wouldn't expect it to make much
> difference, but I suppose it could make a little. It's not going to
> improve the time complexity of your algorithm, though, so I don't
> think I would bother unless it somehow made the code for FOREACH-CHILD
> clearer.
If the recursive call is a terminal call, then RETURN-FROM will just
be a jump (there's no unwinding in this case). But a TCO compiler
would have noticed that even with a mere RETURN.
Otherwise, it might still be faster to unstack n frames at once than n
times one frame.
--
__Pascal Bourguignon__
On Jun 22, 2:12 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> Scott Burson <········@gmail.com> writes:
> > On Jun 21, 12:00 pm, ····@informatimago.com (Pascal J. Bourguignon)
> > wrote:
> >> William Halliburton <············@gmail.com> writes:
> >> > My question is, do I gain anything with this approach? Does
> >> > the
> >> > throw gain me anything over just returning back up the
> >> > stack?
>
> >> Since the throw and catch are in a single scope, you don't gain
> >> anything using them instead of block/return-from:
>
> >> (defun find-in-tree (start val)
> >> (labels ((recurse (node)
> >> (if (value-match node val)
> >> (return-from find-in-tree val)
> >> (foreach-child (node el) (recurse el)))))
> >> (recurse start)))
>
> > This is a good suggestion, but it still leaves the question: will it
> > be any faster than just returning? I wouldn't expect it to make much
> > difference, but I suppose it could make a little. It's not going to
> > improve the time complexity of your algorithm, though, so I don't
> > think I would bother unless it somehow made the code for FOREACH-CHILD
> > clearer.
>
> If the recursive call is a terminal call, then RETURN-FROM will just
> be a jump (there's no unwinding in this case). But a TCO compiler
> would have noticed that even with a mere RETURN.
>
> Otherwise, it might still be faster to unstack n frames at once than n
> times one frame.
>
> --
> __Pascal Bourguignon__
Yes. That's kinda what I was looking for. "Pedantic optimization
question." I should probably have mentioned that the find-in-tree was
a set of methods so your suggestion, while accurate for the data, was
not what I was looking. So much for simplifying the question to its
core.
So, if I understand correctly, if the recusive call is the terminal
call, the compiler should be smart enough to do the same thing since
it is performing tail-call optimization. Makes sense.
What about under TRACE? Does TRACE somehow inhibit the tail-call
optimization jump? Currently the difference is like:
(defun recur (num)
(if (= 0 num) t
(recur (1- num))))
(defun recur2 (num)
(if (= 0 num) (throw 'found t)
(recur2 (1- num))))
CL> (trace recur)
(RECUR)
CL> (trace recur2)
(RECUR2)
CL> (recur 5)
0: (RECUR 5)
1: (RECUR 4)
2: (RECUR 3)
3: (RECUR 2)
4: (RECUR 1)
5: (RECUR 0)
5: RECUR returned T
4: RECUR returned T
3: RECUR returned T
2: RECUR returned T
1: RECUR returned T
0: RECUR returned T
T
CL> (catch 'found (recur2 5))
0: (RECUR2 5)
1: (RECUR2 4)
2: (RECUR2 3)
3: (RECUR2 2)
4: (RECUR2 1)
5: (RECUR2 0)
William Halliburton <············@gmail.com> writes:
> So, if I understand correctly, if the recusive call is the terminal
> call, the compiler should be smart enough to do the same thing since
> it is performing tail-call optimization. Makes sense.
>
> What about under TRACE? Does TRACE somehow inhibit the tail-call
> optimization jump?
Indeed.
> Currently the difference is like:
>
> (defun recur (num)
> (if (= 0 num) t
> (recur (1- num))))
>
> (defun recur2 (num)
> (if (= 0 num) (throw 'found t)
> (recur2 (1- num))))
>
> CL> (trace recur)
> (RECUR)
>
> CL> (trace recur2)
> (RECUR2)
>
> CL> (recur 5)
> 0: (RECUR 5)
> 1: (RECUR 4)
> 2: (RECUR 3)
> 3: (RECUR 2)
> 4: (RECUR 1)
> 5: (RECUR 0)
> 5: RECUR returned T
> 4: RECUR returned T
> 3: RECUR returned T
> 2: RECUR returned T
> 1: RECUR returned T
> 0: RECUR returned T
> T
>
> CL> (catch 'found (recur2 5))
> 0: (RECUR2 5)
> 1: (RECUR2 4)
> 2: (RECUR2 3)
> 3: (RECUR2 2)
> 4: (RECUR2 1)
> 5: (RECUR2 0)
Nice examples! :-)
TRACE usually works by substituting the (symbol-function 'recur), so
if a call is inlined or optimized out such as the recursive tail call,
it won't go thru the symbol-function and you won't see a trace.
Since throw is a non-local _dynamic_ exit, in the case of recur2 the
compiler concludes it cannot optimize out the recursive call (since
the function called in the tail call could establish a new dynamic
contour ; here a smarter compiler could note that it's not just a tail
call, but it's a recursive tail call, and that that function doesn't
catch the literal data (that's another difficulty, the object thrown
and caught is known only at run-time in general), and could in theory
still optimize out that recursive tail call, but it's too hard for the
current version of sbcl).
When there's no catch, throw returns normally, so trace can log each
exit from recur2, but when there's a catch, throw jumps directly to it
and the code installed by trace for the exit doesn't get executed.
With BLOCK and RETURN-FROM you couldn't omit the BLOCK.
--
__Pascal Bourguignon__