Re: Was not making tail recursion elmination a mistake?

From: Duane Rettig (duane_at_franz.com)
Date: 06/18/04 

Date: 18 Jun 2004 10:17:19 -0700

Aurélien Campéas <aurelien.aa@wanadoo.fr> writes:

> Le Thu, 17 Jun 2004 22:07:25 -0400, Rahul Jain a écrit :
>
> > However, THROW/CATCH in Lisp
> > implementations is usually very fast compared to throw/catch in C++ or
> > Java.
>
> Just curious, but what makes it so fast in Lisp (implementations) ? Is
> there something special about the language that helps
> implementors write fast throw/catches ?

Not the language; the implementation techniques. Many systems are
written with C and C calling conventions in mind, and the exception
handling and nonlocal-jumping are sometimes implemented in C in terms
of setjmp/longjump, which might not suit the requirements of the
language. CL implementations can also do this. I suspect, however,
that most CL implementations go directly to the machine level, defining
their own context saving and restoring structures and mechanisms that are
best suited to the CL problem sets. Some lisps do this via assembler
language. A disadvantage of this is that the implementation must be
ported to each architecture, but once this is done, the speed advantage
is fairly good.

Note that a throw must make stops at all unwind-protect markers on the
way out, so this is definitely a YMMV thing; you can slow down a throw
to a catch far away to arbitrary lengths of time simply by loading up
your code with large numbers of cleanup forms that do a lot of work.

> Is the handler-bind/signal pair equally fast ?

Don't forget handler-case as well as restart-case/restart-bind.

These are all built with catch/throw as building blocks, but they are not
the only building blocks used, and throws may not necessarily be involved.
When they are, they would tend to be longer, since handlers and restarts
need to be looked up in order to find out where to perform the throw.
If a throw isn't done, though, it might be faster, depending on the
speed of the lookups vs the throw itself. But such throws usually
involve unwind-protect cleanups to remove intermediate restarts and
handlers, so I wold guess that on average it is slower.

> > But why does it matter? We're talking about Lisp here, not C++.
>
> Sure. Nevertheless, there is a myth out there saying "don't use exception
> handling, for it's dog slow".

Whenever you hear or read something that you can recognize as hyperbole,
it is always a good idea to discount the statement and find out what
is _really_ meant, precisely (and I think that that is what you're
doing by asking these questions). But what is "Dog Slow" to one
person is "Blindingly Fast" to another. What would you say if I told
you that an operation took 100 cpu cycles to complete? If we were
talking about a single floating-point operation, it would be "dog slow",
and if we were talking about an interrupt-handling round-trip, it would
be "reasonably fast". If you were talking about a database transaction,
I might disbelieve you, but if you were to convince me that it really
occurs, I would call it "blazingly fast".

> Norvig's site shows EH speed of Java roughly
> equivalent to its C++ couterpart : so both languages have slow exception
> signalment.
>
> Now, I like the idea of abusing the EH system to escape from deep
> contexts, or to set up some protocol between two parts of the same
> non-threaded program. (... getting even more off-topic ...) I may try to
> build coroutines on top of the CL exception handling mecanism... just to
> see if it makes sense ...

That would be an informative experiment for you to try. It would
give you a feel for exactly what kinds of scaling you are dealing with. 

-- 
Duane Rettig    duane@franz.com    Franz Inc.  http://www.franz.com/
555 12th St., Suite 1450               http://www.555citycenter.com/
Oakland, Ca. 94607        Phone: (510) 452-2000; Fax: (510) 452-0182

Relevant Pages

  • Re: Implementing Exception Handling in a VM
    ... Given that the implementing language has SEH, can ... I leverage this fact to add exception support in my Pascal-like ... handling system in your VM. ...
    (comp.compilers)
  • Re: HOWTO: Re-raise an error?
    ... Well, if you look at any of the scripts Microsoft ships with IIS, error handling is done by just checking Err.Number anywhere they expect something to have failed. ... From that perspective, examples of "real world exception handling" are documented, but there are more practical ways of doing it. ... Ideally, if you know what you're looking for in terms of another language, you could find out whether anyone's thought of a good way to simulate it in VBScript. ... ActiveState O'Reilly Python cookbook code samples ratings review ...
    (microsoft.public.scripting.vbscript)
  • Re: Exceptions
    ... I used to "believe" in checked exception handling, ... The *practical* effect of checked exceptions, ... Mind you, with the use of a non-garbage collected language like Ada, one would ...
    (comp.lang.ada)
  • Re: initial lang spec: SXIL...
    ... Shouldn't some of that functionality be moved into the exception ... but, of course, natively using SEH requires compiler support. ... throws a fixed exception code in my case, and generic handlers are used. ... It took many years, and a language review, before I realized that my fond ...
    (comp.lang.misc)
  • Re: c++ documentation
    ... Alternatives to understanding how the language maps onto the metal? ... One can do a lot with C++ without ever using a raw pointer directly if one ... Code that is not exception safe impedes this. ... I do agree that some programmers overuse the ...
    (comp.os.linux.development.apps)