catch/throw

catch/throw

[Lars Magne Ingebrigtsen]

One other stylistic thing I've started doing lately is using
catch/throw.  Like this:

(defun gnus-or (&rest elems)
  "Return non-nil if any of the elements are non-nil."
  (catch 'found
    (while elems
      (when (pop elems)
	(throw 'found t)))))

where I would have written something like the following before:

(defun gnus-or (&rest elems)
  (let (found)
    (while (and elems
                (not found))
      (when (pop elems)
        (setq found t)))
    found))

or

(defun gnus-or (&rest elems)
  (let (found)
    (while elems
      (when (pop elems)
        (setq found t
              elems nil)))
    found))

I don't know.  catch/throw has gives me the visceral thrill of being
able to say "I've found what I'm looking for!  Stop iterating this
instance and return THIS!  Right now!"  But catch/throw is just goto
under another name, isn't it?  And doesn't one frown on goto?

The second version is quite clear with the explicit test for whether
we have found what we're looking for, but is, of course, slow.  The
third is probably fastest of these three, although the logic here
seems a bit unclear at first peek.  (I'm assuming catch sets up an
unwind-protect form, which probably isn't extremely efficient,
although I haven't really benchmarked...)

(I wouldn't bother going on about this is such length, but these sorts 
of loops are so extremely common...)

(In Common Lisp, we have functions that make many of these types of
loops unnecessary, but I'm not allowed to use the cl functions in
Gnus.)

I've now done benchmarking, and the catch/throw thing seems like it's
10% slower than the other two...

Hm.

But perhaps we should be glad that I can't use the cl functions in
Gnus, since

(defun gnus-or (&rest elems)
  (find-if-not 'null elems))

takes 10 times longer to run than the versions at the top.  :-)

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@ifi.uio.no * Lars Magne Ingebrigtsen

Re: catch/throw

[Justin Sheehy]

Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:

> I don't know.  catch/throw has gives me the visceral thrill of being
> able to say "I've found what I'm looking for!  Stop iterating this
> instance and return THIS!  Right now!"  But catch/throw is just goto
> under another name, isn't it?  And doesn't one frown on goto?

Nah.  Goto as a general control structure is rightly frowned upon, but 
using goto-like constructs for nonlocal exits is a Good Idea.

catch/throw (and your way of using it) is one of the more common
examples of situations in which Scheme programmers use call/cc

-Justin

Re: catch/throw

[Hrvoje Niksic]

Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:
[...]

This is slightly off the topic you set, but still...  Note that you
might wish to use CL's `block' and `return-from', them being lexically
scoped.  (They are also macros).  Take mappers, for example:

(defun map-over (mapfun data)
  (catch 'found
    (while ...
      (while ...
        (apply #'mapfun ...)
        ...
        (if condition (throw 'found))))))

Now, if you use MAP-OVER like this:

(catch 'found
  (map-over
    (lambda (&rest data)
      ... examine the data ...
      (when something          ; wow, we've done it...  skip the
                               ; expensive mapping.
        (throw 'found)))
    my-data))

The (throw 'found) in the body of the anonymous function will hit the
wrong `found', which can be very surprising, especially if you haven't
examined the source of MAP-OVER (the above example is of course
flawed, but it should serve to demonstrate the point.)

Now, if you change (catch 'found ...) with (block found ...) and
(throw 'found) with (return-from found), CL will do the right thing.

> I don't know.  catch/throw has gives me the visceral thrill of being
> able to say "I've found what I'm looking for!  Stop iterating this
> instance and return THIS!  Right now!"  But catch/throw is just goto
> under another name, isn't it?  And doesn't one frown on goto?

The name is setjmp/longjmp.  :-) No, I don't think goto is frowned
upon as long as you know what you're doing.  And using goto to jump
out of a nested block is definitely a legitimate use of the construct.

> (I'm assuming catch sets up an
> unwind-protect form, which probably isn't extremely efficient,
> although I haven't really benchmarked...)

Exactly.  catch/throw is much slower than the explicit loop, because
in addition to the setjmp/longjmp hoops, Emacs has to fill up all
kinds of internal structures and examine them later, to implement
catch/throw correctly.  I sure hope `gnus-or' is not heavily called
within the inner loops of speed-critical sections of Gnus.  :-)

> The second version is quite clear with the explicit test for whether
> we have found what we're looking for, but is, of course, slow.  The
> third is probably fastest of these three, although the logic here
> seems a bit unclear at first peek.

I don't think version 2 is much slower than version 3 -- the optimizer
will do a decent jobs of optimizing it.  The disassemblies look almost
the same:

byte code for gnus-or-2:           byte code for gnus-or-3:
  args: (&rest elems)		     args: (&rest elems)    
0	constant  nil		   0       constant  nil    
1	varbind	  found		   1       varbind   found  
2:1	varref	  elems		   2:1     varref    elems  
3	goto-if-nil 2		   3       goto-if-nil 3    
5	varref	  found		   5:2     varref    elems  
6	goto-if-not-nil 2	   6       dup              
8	varref	  elems		   7       cdr              
9	dup	  		   8       varset    elems  
10	cdr	  		   9       car              
11	varset	  elems		   10      goto-if-nil 1    
12	car	  		   12      constant  t      
13	goto-if-nil 1		   13      varset    found  
15	constant  t		   14      constant  nil    
16	varset	  found		   15      dup              
17	goto	  1		   16      varset    elems  
19:2	varref	  found		   17      goto-if-not-nil 2
20	unbind	  1		   19:3    varref    found  
21	return	  		   20      unbind    1      
				   21      return           

Someone should benchmark the compiled versions against a huge number
of runs to see if there is any difference in execution.  I think the
catch/throw one must be much slower than either of these.

Re: catch/throw

[Lars Magne Ingebrigtsen]

Hrvoje Niksic <hniksic@srce.hr> writes:

> The (throw 'found) in the body of the anonymous function will hit the
> wrong `found', which can be very surprising,

Ah, yes, I hadn't thought of that.

> > (I'm assuming catch sets up an
> > unwind-protect form, which probably isn't extremely efficient,
> > although I haven't really benchmarked...)
> 
> Exactly.  catch/throw is much slower than the explicit loop, because
> in addition to the setjmp/longjmp hoops, Emacs has to fill up all
> kinds of internal structures and examine them later, to implement
> catch/throw correctly.  I sure hope `gnus-or' is not heavily called
> within the inner loops of speed-critical sections of Gnus.  :-)

:-)

> Someone should benchmark the compiled versions against a huge number
> of runs to see if there is any difference in execution.  I think the
> catch/throw one must be much slower than either of these.

Using a list of 100000 nils,

(benchmark 1000000
  (gnus-or that-list))

showed that the catch/throw version was about 15% slower than the
other two, which were about identical in speed.  (2xPII350, XEmacs
21.2).

Of course, a list of a hundred thousand is unrealistic.  More typical
would be a list of 10, which would make the catch/throw thing much
more of a pain.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: catch/throw

[Hrvoje Niksic]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> Hrvoje Niksic <hniksic@srce.hr> writes:
> 
> > The (throw 'found) in the body of the anonymous function will hit
> > the wrong `found', which can be very surprising,
> 
> Ah, yes, I hadn't thought of that.

Few people do; I've actually been bitten by this, and it once again
shows how dynamic scoping sucks, just about anywhere.

> > Someone should benchmark the compiled versions against a huge
> > number of runs to see if there is any difference in execution.  I
> > think the catch/throw one must be much slower than either of
> > these.
> 
> Using a list of 100000 nils,
> 
> (benchmark 1000000
>   (gnus-or that-list))
> 
> showed that the catch/throw version was about 15% slower than the
> other two, which were about identical in speed.  (2xPII350, XEmacs
> 21.2).

Interesting.  While I expected the latter two to be identical in speed 
due to the work of byte-optimizer, it surprises me that the
catch/throw version is only 15% slower.

Perhaps you should try the same benchmark on XEmacs 20.4, and on FSF
Emacs 19.34 and 20.3?  The bytecode interpreter was rewritten for
speed in XEmacs 21.2.5.

> Of course, a list of a hundred thousand is unrealistic.  More
> typical would be a list of 10, which would make the catch/throw
> thing much more of a pain.

I don't understand this.

Re: catch/throw

[Lars Magne Ingebrigtsen]

Hrvoje Niksic <hniksic@srce.hr> writes:

> Interesting.  While I expected the latter two to be identical in speed 
> due to the work of byte-optimizer, it surprises me that the
> catch/throw version is only 15% slower.

I've now done some timings with lists of various lengths:

10 elements; 1000000 iterations
catch: 17.9056009054184
found: 18.0493860244751
not-found: 16.19237506389618

10000 elements; 1000 iterations
catch: 8.583660006523132
found: 10.29576706886292
not-found: 8.556339979171753

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: catch/throw

[Hallvard B Furuseth]

Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:

>   "Return non-nil if any of the elements are non-nil."
> 
> where I would have written something like the following before:
> 
> (defun gnus-or (&rest elems)
>   (let (found)
>     (while (and elems
>                 (not found))
>       (when (pop elems)
>         (setq found t)))
>     found))

What's wrong with this?

  (defun gnus-or (&rest elems)
    (while (and elems (null (car elems)))
      (setq elems (cdr elems)))
    (consp elems))

> I don't know.  catch/throw has gives me the visceral thrill of being
> able to say "I've found what I'm looking for!  Stop iterating this
> instance and return THIS!  Right now!"

You mean like this?

   (while
     (and (progn code ...      continue?)
          (progn more code ... continue?)
          (progn more code ... continue?)))

> But catch/throw is just goto under another name, isn't it?

So are while and if.  Like them, catch/throw is a structured goto:
A block of code with one entry and one exit point, so it's easy to
analyze the control flow.  That's fine, except that it slows down elisp.

> And doesn't one frown on goto?

Unstructured goto, yes.  Also, when a function contains a label, both
the compiler and the human reader must search the entire function for
goto-spaghetti.  Both may have trouble analyzing the control flow.

> (I'm assuming catch sets up an unwind-protect form,

Yes.  Well, more like condition-case, actually.

> which probably isn't extremely efficient,

True.  For one thing, the body even of byte-compiled catch is evalled as
a separate lisp form (so it gets a separate byte-code form).

> (In Common Lisp, we have functions that make many of these types of
> loops unnecessary, but I'm not allowed to use the cl functions in
> Gnus.)

You could always invent gnus-variants of some forms that do not
need throw/catch:-)  e.g. something like
  (gnus-while-cond (condition form...) (condition form...) ...)
where the first failed condition test will terminate the loop.

-- 
Hallvard

Re: catch/throw

[Lars Magne Ingebrigtsen]

Hallvard B Furuseth <h.b.furuseth@usit.uio.no> writes:

> What's wrong with this?
> 
>   (defun gnus-or (&rest elems)
>     (while (and elems (null (car elems)))
>       (setq elems (cdr elems)))
>     (consp elems))

Nothing wrong with that, but one frequently wants to return the
element that satisfied whatever predicate you're iterating over the
list for.  But then the final form could just be

  (and (consp elems)
       (car elems))

So you're right.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen