Muddy
Recursion is a valid concept independent of the language. Algorithms that
are not `primitive recursive' are extremely difficult to code in an
`iterative'
fashion (Ackermann's function, for example).
I assume that your professor meant something like `Where both are possible,
a recursive solution to a problem is likely to perform poorly compared to an
iterative one, except for some languages like Lisp.' But even this is too
vague
a statement to evaluate.
> She stated the cost
> of each function call relatively much less than in C etc.
It depends on what is involved in making a function call. In the C
implementations
I have seen, a function call usually means pushing some arguments on the
stack,
pushing a return address and jumping to the entry point, saving the
base-of-frame
pointer and adjusting the stack for locals. When returning, you discard the
locals,
pop the base-of-frame, return to the caller, and discard the arguments.
A standard Lisp function call happens the same way. There may be some extra
processing of keyword, optional and rest args, and maybe some dynamic
binding,
but the functional call sequence is likely to be similar.
I'd have to say that unless you have special `function calling hardware'
that the cost
of a function call to an 'unknown function' in C and Lisp are comparable.
Lisp compilers can be very smart about calls to `known functions'. If a
function is
lexically nested within another, via FLET or LABELS, the compiler can often
perform
extensive optimizations that will reduce or eliminate the function call
overhead.
However, C doesn't have nested functions, so you can't compare the costs of
these
functions.
(On the other hand, C++ *can* have nested classes with which you can emulate
nested functions. C++ compilers generally do no optimization whatsoever on
these kind of function calls.)
> I have now
> read that this is true if a function is tail recursive.
Tail recursive calls can be compiled into jump statements. Instead of
calling
the target function, you replace your stack frame with the callees arguments
a jump to the callees entry point. Tail recursive calls to
`unknown' functions (i.e., the compiler knows nothing about the callee), are
unlikely to be any faster (and may be slightly slower) than
non-tail-recursive calls.
The primary savings here is in space. A tail recursive call pushes no
stack, so
the process will evolve iteratively.
Tail recursive calls to known functions (like self calls and calls to
lexically visible
functions) can often be turned into simple jump statements. These calls are
no more expensive than the iterative version of the code (in fact, it
probably
compiles into the same object code).
Lisp compilers have been doing tail-recursion elimination for years, but
some C
compilers can do tail-recursion elimination. Certain constructs in the C
and C++
language limit the applicability of tail-recursion elimination (as do some
in Lisp),
but where both compilers can do tail-recursion elimination, they will emit
similar code.
> However, this
> still seems odd to me since it requires compilers make some of those
> smart decisions they so often fail to do in practice.
Tail recursion elimination doesn't require the mythical `sufficiently smart
compiler'.
Simply tracking the continuation through the code is often sufficient, but
if
there is stack-allocated data, you might have to analyze the lifetime of the
data.
> Does anyone have
> any benchmarks that compare recursion and Interation for large data
> sets.
When you can compare tail recursion and iteration in those problems that can
be structured both ways, the results are similar. There are a few edge
cases
where the tail recursive solution is slightly slower because in general you
have
to build a new stack frame and copy it over the current one. But there are
also
cases where the iteration is slightly slower.
> Hopefully, the LISP benchmark writers will avoid the C vs C++
> war benchmarks where highly optimized routines from the version the
> author likes are compared against poorly written implementation in
> the hated alternative.
The GNU C compiler can do tail recursion elimination for self calls, so
there
wouldn't be any glaring differences.
-----
Where tail recursion wins is not in performance, but in expressability. If
your compiler
does not do tail recursion elimination, there will be a `hidden' factor of
O(N) space
added to your algorithm if you code it in a recursive fashion. You will
have to keep that
in mind when coding a solution. However, if your compiler does tail
recursion
elimination, you don't need to worry about when and where this extra O(n)
factor appears.
For instance, some algorithms are more naturally expressed as a set of
mutually
tail recursive functions. You would have to rework the algorithm if your
compiler does
not do tail recursion elimination.
Some algorithms are `mostly iterative'. For instance algorithms that deal
with list structure
that is `mostly' linear, but with the occasionally sub-branch. If the
compiler does tail-recursive
elimination, the solution will be `mostly iterative' as well. If not, it is
rather difficult to
code this as an iterative process with an explicit stack for the branching
alternatives.
Some algorithms have unusual flow of control. If you have first-class
functions, you can
exercise explicit control over the flow by coding in `continuation-passing'
style. In this
style, you never return a value from a function, instead you call a
`continuation' function.
If your compiler does not do tail-recursion elimination,
`continuation-passing' style programming
will quickly exhaust the stack.
Traditionally, implementors of functional languages have worked harder on
optimizing function calls, since the style of programming in these
languages is so dependent on them. It has been more common to write
recursive programs in these languages. This is where old professors
probably got the impression that function calls and recursion were more
efficient in these languages.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Robert Posey <mu...@raytheon.com> writes:
> Dear Gentle Persons,
> My Professor made the statement that LISP is one of the few languages where
> Recursion is a valid concept in nontrivial programs.
Recursion is a *necessary* concept in all inherently recursive
algorithms. E.g. Tree Traversal.
> She stated the cost
> of each function call relatively much less than in C etc. I have now
> read that this is true if a function is tail recursive. However, this
> still seems odd to me since it requires compilers make some of those
> smart decisions they so often fail to do in practice. Does anyone have
> any benchmarks that compare recursion and Interation for large data
> sets.
First get it right, then get it fast. If faster means nightmarishly
difficult to maintain, then keep the slower version. Usually
recursive solutions (especially for inherently recursive algorithms
and data-structures) are easier to get right and to maintain. Most of
the time they are also faster than the alternative , since a hand made
stack is most likely going to be slower than the one handled by the
compiler and runtime conventions of the host language. (If you do not
understand why I am talking about a stack, you need to do some more
reading :) )
Note that this comment is completely language independent.
> Hopefully, the LISP benchmark writers will avoid the C vs C++
> war benchmarks where highly optimized routines from the version the
> author likes are compared against poorly written implementation in
> the hated alternative. What I am looking for is reasonable attempts
> at ultimate performance for both methods.
Pardon my bluntness, but this is a bogus question. If your recursive
solution fits the bill (meets the specs, makes your customer happy,
whatever) why should you care? Meanwhile, as I said, *most likely*,
your recursive solution is going to be easier to maintain. This
should be enough.
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
> My Professor made the statement that LISP is one of the few languages where
> Recursion is a valid concept in nontrivial programs. She stated the cost
> of each function call relatively much less than in C etc.
Function call is cheap in C too these days. Lisp compilers
tend to put more effort into making function calls efficient,
because typical Lisp programs use quite a lot of function
calls; but, against that, some Lisp function calls have to
be more expensive than C function calls have to be, because
you can redefine functions in Lisp.
That is, if I do
(defun foo (x) (* x x))
(defun bar (x) (+ (foo x) (foo x)))
(defun foo (x) 0)
then the call in BAR now needs to call the new version of FOO.
To arrange this you have to do one of two things: (1) make
the call to FOO do one more level of indirection than it would
have to in a language like C, to look up the current meaning
of FOO; or, (2) arrange that when the definition of FOO changes
the code for BAR gets patched to refer to the new definition.
So far as I know, no actual Lisp system takes option (2).
Some Lisp function calls are a lot more expensive than this
because of complications like multiple values, optional
arguments, and (much worse than either of these) keyword
arguments.
In any case, in most compiled languages these days, most
function calls are very cheap. Sufficiently cheap that it's
hardly ever correct to avoid function calls for the sake
of efficiency -- not, at least, until you've finished the
program and found it's too slow and established that the
function calls add significantly to the time it takes.
Which just about never happens.
> I have now
> read that this is true if a function is tail recursive.
The point here is that a tail call (note: what matters here
isn't whether the *function* is tail-recursive, but whether
the *call* you're considering is a tail call) can often be
compiled as some assignments and a jump.
Unless you're concerned about running out of stack space,
though, full calls aren't usually that much more expensive
than tali calls.
[SNIP: request for benchmarks]
I realise that that request was really the main point of
your request, but I have none to offer. Sorry.
It might, however, be worth mentioning that good Lisp compilers
(CMU CL, for instance) will sometimes turn recursions into
iterations, producing exactly the same code for each formulation.
Here's a toy example. If you give CMU CL the (stupid)
definition
(defun f (x)
(declare (type (integer 0 1000) x))
(if (> x 0)
(f (1- x))
x))
then (on my machine, at least!) it will compile it to machine code
with the following structure.
function entry:
check that exactly one arg was passed (if not, jump to ZOG1)
check that the argument is a fixnum in [0,1000] (if not, jump to ZOG2)
move argument into a temporary register
jump to FOO
ZOG2:
error-handling code for wrong-type case
FOO:
compare temporary register with 0
if >0, jump to BAR
return from function call
BAR:
subtract 1 from temporary register
jump to FOO
ZOG1:
error-handling code for wrong-number-of-args case
It would be possible to shave a couple of cycles off
this code, but there's certainly nothing there that
resembles a recursive function call any more.
--
Gareth McCaughan Gareth.M...@pobox.com
sig under construction
> Dear Gentle Persons,
> My Professor made the statement that LISP is one of the few
> languages where Recursion is a valid concept in nontrivial
> programs.
Are you sure your professor didn't say "for TRIVIAL programs?"
In that case the statement would be true. If you are writing a
simple loop that needs to run fast, recursion is fine in Lisp but
should be avoided in most other languages.
But for NON-trivial programs, recursion is so valuable that you
will often want to use it even in languages that haven't been
optimized to handle it quickly.
For example, I heard some people have created an improved version
of Java, called Pizza. They wrote a translator (in Java) that
reads a Pizza program and translates it into an ordinary Java
program that any Java compiler can handle. I haven't read their
source code, but I'd be willing to bet that they used recursion,
even though Java is NOT optimized to handle recursion quickly.
Ask your professor if recursion is "valid" for implementing Quicksort,
in various languages. Personally I can't think of any language
except FORTRAN where I'd want to do Quicksort without recursion.
> She stated the cost of each function call relatively much less
> than in C etc. I have now read that this is true if a function
> is tail recursive. However, this still seems odd to me since it
> requires compilers make some of those smart decisions they so
> often fail to do in practice.
Dealing with tail recursion does not require an extremely smart
compiler. All the compiler has to do is notice that this function
does a function call and then immediately does a return, and doesn't
do any other useful work in between. Pretty simple.
> Does anyone have any benchmarks that compare recursion and
> Interation for large data sets. Hopefully, the LISP benchmark
> writers will avoid the C vs C++ war benchmarks where highly
> optimized routines from the version the author likes are compared
> against poorly written implementation in the hated alternative.
> What I am looking for is reasonable attempts at ultimate performance
> for both methods.
Benchmarks aren't necessary, because if you have a compiler that
achieves "ultimate performance for both methods," you can just
disassemble the compiled code and you'll see that both versions of
source code were compiled to the exact same machine language code.
-- Robert Munyer <mun...@mcs.com>
Marco Antoniotti wrote:
>
> Robert Posey <mu...@raytheon.com> writes:
>
> > Dear Gentle Persons,
>
> > Hopefully, the LISP benchmark writers will avoid the C vs C++
> > war benchmarks where highly optimized routines from the version the
> > author likes are compared against poorly written implementation in
> > the hated alternative. What I am looking for is reasonable attempts
> > at ultimate performance for both methods.
>
> Pardon my bluntness, but this is a bogus question. If your recursive
> solution fits the bill (meets the specs, makes your customer happy,
> whatever) why should you care? Meanwhile, as I said, *most likely*,
> your recursive solution is going to be easier to maintain. This
> should be enough.
I am looking for the first evidence that a nontrivial recursive
solution is not much slower than the alternative. I am also
curious why you think a recursive solution would be easier to
maintain, its sure a lot harder to debug. Its a major pain to
handle in a multi-tasking system where you either add level of
recursion counters or become completely lost. It there is a easy
way to debug recursion, I would be very happy to read about it. I
work in an embedded environment I will admit, but I have never seen
recursive code released. If your compiler is smart enough to
properly handle tail recursive solutions, I am at a lost to how you
would debug optimized recursive code.
Muddy
> I
> work in an embedded environment I will admit, but I have never seen
> recursive code released.
Erm? Quicksort. Any of the multitude of n-ary tree algorithms.
--tim
> then the call in BAR now needs to call the new version of FOO.
> To arrange this you have to do one of two things: (1) make
> the call to FOO do one more level of indirection than it would
> have to in a language like C, to look up the current meaning
> of FOO; or, (2) arrange that when the definition of FOO changes
> the code for BAR gets patched to refer to the new definition.
> So far as I know, no actual Lisp system takes option (2).
Genera on Ivory gets very close with the `Direct calls' feature. You
can say that calls to a number (or all) functions are to be
direct-linked, which bypasses the function cell. If you redefine a
function which is called in this way you get an error, and one of the
proceed options is to unlink direct calls to it. You could almost
certainly wrap some error-handling code around this to unlink & then
relink. Redefining a function would take minutes though...
--tim
At least in C, the performance of Quicksort can be improved quite a
bit(I hear) by Iteration. If I had easy access to a system that
I could do reasonable timing measurements on, I would attempt to prove it.
I will admit, that Quicksort is even harder to understand than usual
in Iterative form. I don't like it anyway, and would never use it
unless I had to. Its timing varies too much, on a small change, and
randomizing the input is a pain. Besides, in many cases Bucket sort
is faster and much easier. Classic example sorting incoming integers of
a know range is both much simpler and much faster using Bucket sort.
Quicksort is a good generic sort algorithm, but generic sort should
only be used when it not a performance driver, or the data types are
unknown in advance. In the Embedded world, both of these are unlikely.
Muddy
>
> --tim
Of course on most DSO and some general processor the cost of performing a
loop N times is a low fixed setup cost with zero per iteration cost.
Muddy
>
> --tim
I assume you agree that some problems are recursive by nature and
that an `iterative' solution isn't reasonable.
Given that, included is a program that will find the roots to an equation
using Newton's method. I tried to find a simple enough, but non-trivial
program that is in actual use. I copied the recursive version I found in
the scmutils package in use at MIT, I wrote the two iterative versions
myself.
All three versions run in just about the same time.
> I am also
> curious why you think a recursive solution would be easier to
> maintain, its sure a lot harder to debug.
Not that much harder.
> Its a major pain to
> handle in a multi-tasking system where you either add level of
> recursion counters or become completely lost.
I don't understand why you need `recursion counters'.
> It there is a easy
> way to debug recursion, I would be very happy to read about it. I
> work in an embedded environment I will admit, but I have never seen
> recursive code released.
I see it and write it all the time.
> If your compiler is smart enough to
> properly handle tail recursive solutions, I am at a lost to how you
> would debug optimized recursive code.
If your compiler is aggressively optimizing out tail calls, you are correct
in that you might find yourself in a function with no idea how you got
there.
A few calls to `trace' will generally solve that problem.
(in-package "USER")
(declaim (optimize (speed 3) (safety 1)))
(defun close-enuf? (a b eps)
(< (abs (- a b)) eps))
(defun average (a b)
(/ (+ a b) 2))
(defun newton-improve (f-and-df xn)
(multiple-value-bind (fn dfn)
(funcall f-and-df xn)
(- xn (/ fn dfn))))
(defun newton-search-rec (f-and-df this-guess eps)
(let ((next-guess (newton-improve f-and-df this-guess)))
(if (close-enuf? this-guess next-guess eps)
(average this-guess next-guess)
(newton-search-rec f-and-df next-guess eps))))
(defun newton-search-iter-1 (f-and-df start-guess eps)
(do ((next-guess (newton-improve f-and-df start-guess)
(newton-improve f-and-df next-guess))
(this-guess start-guess next-guess))
((close-enuf? this-guess next-guess eps) (average this-guess
next-guess))
))
(defun newton-search-iter-2 (f-and-df this-guess eps &aux next-guess)
(loop
(setq next-guess (newton-improve f-and-df this-guess))
(when (close-enuf? this-guess next-guess eps)
(return-from newton-search-iter-2 (average this-guess next-guess)))
(setq this-guess next-guess)))
(defun testit ()
(time (dotimes (i 100000)
(newton-search-rec
#'(lambda (x)
(values (cos x) (- (sin x))))
1.0d0
1d-15)))
(time (dotimes (i 100000)
(newton-search-iter-1
#'(lambda (x)
(values (cos x) (- (sin x))))
1.0d0
1d-15)))
(time (dotimes (i 100000)
(newton-search-iter-2
#'(lambda (x)
(values (cos x) (- (sin x))))
1.0d0
1d-15)))
)
;;; USER(24): (user::testit)
;;; cpu time (non-gc) 4,426 msec user, 0 msec system
;;; cpu time (gc) 321 msec user, 0 msec system
;;; cpu time (total) 4,747 msec user, 0 msec system
;;; real time 4,747 msec
;;; space allocation:
;;; 39 cons cells, 0 symbols, 84,000,160 other bytes, 0 static bytes
;;; cpu time (non-gc) 4,416 msec user, 0 msec system
;;; cpu time (gc) 290 msec user, 0 msec system
;;; cpu time (total) 4,706 msec user, 0 msec system
;;; real time 4,707 msec
;;; space allocation:
;;; 36 cons cells, 0 symbols, 84,000,160 other bytes, 0 static bytes
;;; cpu time (non-gc) 4,477 msec user, 0 msec system
;;; cpu time (gc) 260 msec user, 0 msec system
;;; cpu time (total) 4,737 msec user, 0 msec system
;;; real time 4,737 msec
;;; space allocation:
;;; 54 cons cells, 0 symbols, 84,000,256 other bytes, 0 static bytes
> At least in C, the performance of Quicksort can be improved quite a
> bit(I hear) by Iteration.
The c-library's quicksort under FreeBSD uses one recursive call and
one iterative call replacing the second recursive call. The reason
given is to save stack space:
Relevant part of code from qsort.c:
if ((r = pb - pa) > es)
qsort(a, r / es, es, cmp);
if ((r = pd - pc) > es) {
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}
/* qsort(pn - r, r / es, es, cmp);*/
}
Clearly a function call is more expensive than a goto. But if the
compiler can transform a function call into a goto, they become
identical.
So for the instances where recursion in the general sense is required
by the algorithm, the issue becomes whether the programmer can write a
recursion simulation (i.e. stuffing values by hand on a home-brew
stack) that is faster than the procedure-call mechanism.
BTW I've always felt that recursion is far easier to understand than
iteration for the non-initiated. Using the infamous factorial
example, I've always found the following code
unsigned
factorial(unsigned n)
{
if(n == 0)
return 1;
return n * factorial(n - 1);
}
to be easy to understand because it reflects the mathematical
specification of factorial, while
unsigned
factorial(unsigned n)
{
unsigned x = 1;
unsigned i;
if(n > 0)
for(i = 1; i <= n; i++)
x *= i;
return x;
}
introduces a bunch of extraneous stuff that must be understood
independently of the specification. For example, where does this `x'
come from? What's the `i' for? What does that weird `for' construct
mean?
--
Fred Gilham gil...@csl.sri.com
Is, then, the loving cup so often filled
that we may toss a draught aside?....
-Jeff Iverson
> At least in C, the performance of Quicksort can be improved quite a
> bit(I hear) by Iteration.
I'd love to see an iterative version of quicksort.
--tim
Here is a good one in C.
Marc Battyani
*Warning Old C code!*
The small runs are sorted by insertion sort which is more efficient.
/* QSort() -- Quicksort function
**
** Usage: qsort(base, nbr_elements, width_bytes, compare_function);
** char *base;
** unsigned int nbr_elements, width_bytes;
** int (*compare_function)();
**
** Sorts an array starting at base, of length nbr_elements, each
** element of size width_bytes, ordered via compare_function; which
** is called as (*compare_function)(ptr_to_element1, ptr_to_element2)
** and returns < 0 if element1 < element2, 0 if element1 = element2,
** > 0 if element1 > element2. Most of the refinements are due to
** R. Sedgewick. See "Implementing Quicksort Programs", Comm. ACM,
** Oct. 1978, and Corrigendum, Comm. ACM, June 1979.
*/
#define SWAP(a,b) {memcpy(Buf, a, Width); memcpy(a, b, Width); memcpy(b,
Buf, Width); }
#define COMP(a,b) (*Compare)(a, b)
void QSort (pChar Base, Short NbObjects, Short Width, Bool (*Compare)(pVoid
a, pVoid b))
{
char Buf[250];
char *stack[40], **sp; /* stack and stack pointer */
char *i, *j, *limit; /* scan and limit pointers */
unsigned thresh; /* size of MaxSpan elements in */
/* bytes */
thresh = MaxSpan * Width; /* init threshold */
sp = stack; /* init stack pointer */
limit = Base + NbObjects * Width; /* pointer past end of array */
while (1) /* repeat until done then return */
{
while (limit - Base > thresh) /* if more than MaxSpan elements
*/
{
/*swap middle, Base*/
SWAP (((unsigned)(limit - Base) >> 1) -
((((unsigned)(limit - Base) >> 1)) % Width) + Base, Base);
i = Base + Width; /* i scans from left to right */
j = limit - Width; /* j scans from right to left */
if ( COMP(i, j)) /* Sedgewick's */
SWAP(i, j); /* three-element sort */
if ( COMP(Base, j)) /* sets things up */
SWAP(Base, j); /* so that */
if ( COMP(i, Base)) /* *i <= *Base <= *j */
SWAP(i, Base); /* *Base is the pivot element */
while (1)
{
do /* move i right until *i >= pivot */
i += Width;
while (COMP (Base, i));
do /* move j left until *j <= pivot */
j -= Width;
while (COMP (j, Base));
if (i > j) /* break loop if pointers crossed */
break;
SWAP (i, j); /* else swap elements, keep scanning */
}
SWAP (Base, j); /* move pivot into correct place */
if (j - Base > limit - i) /* if left subfile is larger... */
{
sp[0] = Base; /* stack left subfile Base */
sp[1] = j; /* and limit */
Base = i; /* sort the right subfile */
}
else /* else right subfile is larger */
{
sp[0] = i; /* stack right subfile Base */
sp[1] = limit; /* and limit */
limit = j; /* sort the left subfile */
}
sp += 2; /* increment stack pointer */
}
/* Insertion sort on remaining subfile. */
i = Base + Width;
while (i < limit)
{
j = i;
while (j > Base && COMP (j - Width, j))
{
SWAP (j - Width, j);
j -= Width;
}
i += Width;
}
if (sp > stack) /* if any entries on stack... */
{
sp -= 2; /* pop the Base and limit */
Base = sp[0];
limit = sp[1];
}
else /* else stack empty, all done */
break; /* Return. */
}
}
> * Robert Posey wrote:
>
> > At least in C, the performance of Quicksort can be improved quite a
> > bit(I hear) by Iteration.
>
> I'd love to see an iterative version of quicksort.
#include <stdlib.h>
/* swap two ints */
int sw(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
return 0;
}
/* iterative quicksort (average execution time: O(NlogN)) */
int qs(int *h, int N)
{
int n=0,m=1,k=0,p=0,q=N,r,w,b,z;
int *x=malloc(sizeof(int)*N),*y=malloc(sizeof(int)*N);
if(!x||!y)return 1;
while(m<N)n++,m*=2;
while(k||q-p>1)
if(q-p<2)p=x[--k],q=y[k];
else
{
z=h[((w=r=p)+(b=q))/2];
while(w-b)h[w]<z?sw(h+r++,h+w++):h[w]-z?sw(h+--b,h+w):w++;
r-p<=q-w?x[k]=w,y[k++]=q,q=r:(x[k]=p,y[k++]=r,p=w);
}
return 0;
}
Christopher
What's wrong with you? This is obviously much more readable than the
equivalent prefix notation:
;(define (quick-sort! vector predicate)
; (define (outer-loop l r)
; (if (> r l)
; (if (= r (+ l 1))
; (if (predicate (vector-ref vector r)
; (vector-ref vector l))
; (exchange! l r))
; (let ((lth-element (vector-ref vector l)))
;
; (define (increase-i i)
; (if (or (> i r)
; (predicate lth-element (vector-ref vector i)))
; i
; (increase-i (+ i 1))))
;
; (define (decrease-j j)
; (if (or (<= j l)
; (not (predicate lth-element (vector-ref vector
j))))
; j
; (decrease-j (- j 1))))
;
; (define (inner-loop i j)
; (if (< i j) ;used to be <=
; (begin
; (exchange! i j)
; (inner-loop (increase-i (+ i 1))
; (decrease-j (- j 1))))
; (begin
; (if (> j l)
; (exchange! j l))
; (outer-loop (+ j 1) r)
; (outer-loop l (- j 1)))))
;
; (inner-loop (increase-i (+ l 1))
; (decrease-j r))))))
;
; (define-integrable (exchange! i j)
; (let ((ith-element (vector-ref vector i)))
; (vector-set! vector i (vector-ref vector j))
; (vector-set! vector j ith-element)))
;
; (if (not (vector? vector))
; (error:wrong-type-argument vector "vector" 'QUICK-SORT!))
; (outer-loop 0 (- (vector-length vector) 1))
; vector)
Basically, they performed the tail-recursion elimination in the source
code, rather than depending on the compiler to do it (reasonable, since
most C compilers don't).
> Here is a good one in C.
Erm.
> char *stack[40], **sp; /* stack and stack pointer */
That looks really like a stack to me! If you want to obscure the
recursion you'd be better doing what Christopher Barry did and posting
something that looks like line noise and hoping no one will notice the
stack.
Either it's recursive or it ain't quicksort.
--tim
If you've got a stack, you're recursive. You're not using the underlying
language's recursion features, you're simply reinventing it. After all,
how do you think recursion in C is implemented on the underlying hardware?
It translates it into instructions that manipulate a stack pointer register
and then perform a transfer, precisely analogous to your stack[] array.
Maclisp was doing option (2) 20 years ago, on both Multics and PDP-10's.
> Tim Bradshaw <t...@cley.com> wrote in message
> >
> > I'd love to see an iterative version of quicksort.
>
> Here is a good one in C.
...
> char *stack[40], **sp; /* stack and stack pointer */
Actually, it's still a recursive algorithm. Instead of having the
recursion explicit and using the built-in C function calling stack it is
handled internally in the function, which maintains its own stack.
It can handle at most 20 recursive calls to quicksort (each recursive
call requires to stack entries). Of course that does let you sort a
fair-sized input array. (Assuming perfect binary splits around pivots
this could be as big as 2^20 elements.
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
> >Here is a good one in C.
> ...
> > char *stack[40], **sp; /* stack and stack pointer */
>
> If you've got a stack, you're recursive. You're not using the underlying
> language's recursion features, you're simply reinventing it. After all,
> how do you think recursion in C is implemented on the underlying hardware?
> It translates it into instructions that manipulate a stack pointer register
> and then perform a transfer, precisely analogous to your stack[] array.
And sadly, it's not even precisely analogous to the stack array,
because the stack array uses a small, hard-coded, undocumented limit,
which is a really nice source of bugs, whereas the implementations
stack will usually have much wider, better documented limits, and much
better/clearer error handling...
Now one might argue that the home grown stack could be implemented
much more robustly, but IMHO that is missing the point: With the
implementation stack, I get this for free, whereas with my home-grown
stuff, I have to invest the time and effort, and still risk
introducing bugs or maintenance hassles.
Basically IMHO this boils down to the reason why we have higher level
languages and COTS implementations thereof: We want to leverage the
work of very knowledgable implementors implementing things once (and
improving them constantly), so that not everyone has to reinvent the
wheel badly all the time. So if you fell you need to simulate
recursion in your language/implementation for performance reasons --
unless you are operating under very special circumstances, like e.g. a
DSP, etc. -- then file a performance bug report instead, so that the
implementation can be enhanced, which will make the world a better
place for all.
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
> Now one might argue that the home grown stack could be implemented
> much more robustly, but IMHO that is missing the point: With the
> implementation stack, I get this for free, whereas with my home-grown
> stuff, I have to invest the time and effort, and still risk
> introducing bugs or maintenance hassles.
I think this `iterative' qsort is nearly a canonical example of the C
mindset. The C mindset being `wherever the language or hardware might
offer me some safety at some cost in performance, however minute, I
will either fail to provide or bypass those features'. About the only
place that you get any decent bounds checking in typical C programs is
stack overflow, and here we have someone carefully bypassing that last
remaining scrap of protection in the name of saving a few extra
cycles.
I believe that this is a compelling argument against the `modern
processors are C-machines' claim that was made here recently.
C-machines would not have memory protection or virtual memory, since
both those features get you safety at the cost of Quake frame-rate,
and Quake frame-rate is *all* that the C mindset cares about.
Of course, the C mindset has some problems here, because it's
stressing on about function call time when the time of a reasonably
sized qsort is likely to be massively dominated by memory access to
the object being sorted on any recent machine. But the C mindset
doesn't know about caching issues, because they never really got much
further than the PDP11, and their algorithms books all talk about
machines with uniform memory access times. You have to have the
FORTRAN-mindset (several stages up the evolutionary ladder) to know
about caching...
--tim
- How would you use anything other than recursion for algorithms that
manipulate trees?
- Or do you not use binary trees? Or quicksort? Or mergesort?
- Every RDBMS out there uses recursive code to manage B-trees of one
variation or another. I assume from your comments that you never
use database systems, as they *all* use recursive algorithms.
- If you don't make use of any recursive parsers, then I don't think
you can be writing code in any language other than FORTH, which
doesn't do the "recursive parsing" thing.
If you think that you don't make use of recursive code, then I am at a
loss to imagine what kind of computer systems you're using, as they
*all* have significant amounts of recursive code around if they're
using a language newer than FORTRAN-77.
--
"... the most important thing in the programming language is the name. A
language will not succeed without a good name. I have recently invented a
very good name and now I am looking for a suitable language.
-- D. E. Knuth, 1967
cbbr...@ntlug.org- <http://www.ntlug.org/~cbbrowne/lsf.html>
> BTW I've always felt that recursion is far easier to understand than
> iteration for the non-initiated. Using the infamous factorial
> example, I've always found the following code
>
> unsigned
> factorial(unsigned n)
> {
> if(n == 0)
> return 1;
>
> return n * factorial(n - 1);
> }
>
>
> to be easy to understand because it reflects the mathematical
> specification of factorial, while
>
> unsigned
> factorial(unsigned n)
> {
> unsigned x = 1;
> unsigned i;
>
> if(n > 0)
> for(i = 1; i <= n; i++)
> x *= i;
>
> return x;
> }
>
> introduces a bunch of extraneous stuff that must be understood
> independently of the specification. For example, where does this `x'
> come from? What's the `i' for? What does that weird `for' construct
> mean?
I don't think this is quite fair; C's |for| statement
is particularly obscure until one gets used to it.
Consider the following possibilities (not in any real
language):
define factorial(n):
product = 1
for i from 1 to n: product = product * i
return product
define factorial(n):
if n==0 then 1
else n * factorial(n-1)
define factorial(n):
product of i for i in [1..n]
It seems to me that the first is much clearer than
your iterative code (because it isn't full of C-isms);
the second is clearer than the first; and the clearest
of all is the last one, which is presumably iterative.
That's for a function one of whose most familiar
definitions is recursive. What about a program to
print the squares of the first 10 positive integers?
for n from 1 to 10:
print n*n
define print_in_range(first,last):
if first >= last: return
print first*first
print_in_range(first+1,last)
No contest, right?
... Or as few as 20 elements, if the array is already sorted, and the
pivots are *not* intelligently chosen. (Personally, I like the idea
of picking the pivot *at random.*)
--
16-inch Rotary Debugger: A highly effective tool for locating problems
in computer software. Available for delivery in most major
metropolitan areas. Anchovies contribute to poor coding style.
cbbr...@ntlug.org - - <http://www.ntlug.org/~cbbrowne/lsf.html>
OK sorry.
Next time I will read my message before posting it...
Marc Battyani
> Tim Bradshaw wrote:
> >
> > * Robert Posey wrote:
> >
> > > I
> > > work in an embedded environment I will admit, but I have never seen
> > > recursive code released.
> >
> > Erm? Quicksort. Any of the multitude of n-ary tree algorithms.
>
> At least in C, the performance of Quicksort can be improved quite a
> bit(I hear) by Iteration.
Quicksort is an inherently recursive algorithm. You cannot eliminate
recursion. The best that you can do is to introduce stacks to
*simulate* recursion, hence introducing the "recursion counters" you
talked about in a previous post.
> If I had easy access to a system that
> I could do reasonable timing measurements on, I would attempt to prove it.
> I will admit, that Quicksort is even harder to understand than usual
> in Iterative form. I don't like it anyway, and would never use it
> unless I had to. Its timing varies too much, on a small change, and
> randomizing the input is a pain. Besides, in many cases Bucket sort
> is faster and much easier. Classic example sorting incoming integers of
> a know range is both much simpler and much faster using Bucket sort.
It is not *easier* it is theoretically better since you are not using
a comparison based sort algorithm.
> Quicksort is a good generic sort algorithm, but generic sort should
> only be used when it not a performance driver, or the data types are
> unknown in advance. In the Embedded world, both of these are
> unlikely.
This is true. So, you know you have incoming integers (with
associated data, of course) in the 0-100 range and you have to sort
them. *Theory* tells you that you are better off using a
counting/radix/bucket sort (as per CLR terminology). This is
completely independent of the system being built and of the language
used.
#+with-personal-gripe
From experience, I'd say that the embedded world sometimes goes over
the board in making its life miserable :) by quibbling over
performance and loosing money on larger issues, such as
maintainability. :)
> Tim Bradshaw <t...@cley.com> writes:
>
> > * Robert Posey wrote:
> >
> > > At least in C, the performance of Quicksort can be improved quite a
> > > bit(I hear) by Iteration.
> >
> > I'd love to see an iterative version of quicksort.
>
>
> #include <stdlib.h>
>
> /* swap two ints */
> int sw(int *x, int *y)
> {
> int temp = *x;
> *x = *y;
> *y = temp;
> return 0;
> }
>
> /* iterative quicksort (average execution time: O(NlogN)) */
> int qs(int *h, int N)
> {
> int n=0,m=1,k=0,p=0,q=N,r,w,b,z;
> int *x=malloc(sizeof(int)*N),*y=malloc(sizeof(int)*N);
> if(!x||!y)return 1;
> while(m<N)n++,m*=2;
> while(k||q-p>1)
> if(q-p<2)p=x[--k],q=y[k];
> else
> {
> z=h[((w=r=p)+(b=q))/2];
> while(w-b)h[w]<z?sw(h+r++,h+w++):h[w]-z?sw(h+--b,h+w):w++;
> r-p<=q-w?x[k]=w,y[k++]=q,q=r:(x[k]=p,y[k++]=r,p=w);
> }
> return 0;
> }
>
Why all those newlines in the code? :)
(defun factorial (n)
(reduce #'* (iota n :start 1)))
> and Quake frame-rate is *all* that the C mindset cares about.
And the worst is that most people think that if "Quake frame rate on
El-Cheapo 3D board"
is higher than "Quake frame rate on SGI" the offering from Mountain View
does not make any sense
from a strictly gfx perspective.
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
Christopher Browne wrote:
>
> If you think that you don't make use of recursive code, then I am at a
> loss to imagine what kind of computer systems you're using, as they
> *all* have significant amounts of recursive code around if they're
> using a language newer than FORTRAN-77.
Of course my windows, linux, unix machines use recursion, but I don't write
deliverable code for those machines. On the embedded systems, I have
never seen recursion.
Muddy
Hey, I think I made that claim.
In Jonathan Rees's paper:
Jonathan A. Rees.
A Security Kernel Based on the Lambda-Calculus.
Ph.D. dissertation, MIT, 1995.
Reprinted in part as MIT AI Memo 1564, March 1996.
http://mumble.net/jar/pubs/secureos/
Rees claims:
`There are several approaches to eliminating the risks associated
with machine programs:
[among which is] Limitation: switch into a limited hardware-provided
"user mode" when invoking the machine program.
Limitation may be the only option if one has little influence over the
compiler and program being compiled. For example, most C programs
use pointers in ways that are difficult to guarantee safe by
verification
or sandboxing, and few C compilers generate object code that checks
validity of pointers.'
Lisp Machines ran all their processes in a single address space. Since
it was unusual to make bogus tagged objects on a Lisp machine, and since
the underlying microcode enforced safety, there was no need for `memory
protection'
in the traditional sense.
But running multiple C programs in the same address space without memory
protection is not particularly robust (see Windows 95/98).
That's my story and I'm sticking to it.
> What about a program to print the squares
> of the first 10 positive integers?
>
> for n from 1 to 10:
> print n*n
>
> define print_in_range(first,last):
> if first >= last: return
> print first*first
> print_in_range(first+1,last)
>
> No contest, right?
I think that by using "for" instead of a simpler looping construct,
you've applied to the iterative version a level of syntactic sugar
that you haven't applied to the recursive one. Also, the use of
an explicit "return" to break out of the function is not necessary
in structured languages. I'd rephrase your comparison like this:
define print_in_range(first,last):
n := first
while n < last:
print n * n
n := n + 1
define print_in_range(first,last):
if first < last:
print first*first
print_in_range(first+1,last)
-- Robert Munyer <mun...@mcs.com>
> I think this `iterative' qsort is nearly a canonical example of the C
> mindset. The C mindset being `wherever the language or hardware might
> offer me some safety at some cost in performance, however minute, I
> will either fail to provide or bypass those features'. About the only
> place that you get any decent bounds checking in typical C programs is
> stack overflow, and here we have someone carefully bypassing that last
> remaining scrap of protection in the name of saving a few extra
> cycles.
In the present instance, this isn't fair. Provided your
array can't be more than 2^40 elements in size (which is
probably a pretty safe guess) the posted quicksort routine
will never overflow its hard-coded stack, because it
always stacks the smaller subarray and iterates on the
larger.
This is not to disagree with the point you're making,
of course.
[I said:]
>> What about a program to print the squares
>> of the first 10 positive integers?
>>
>> for n from 1 to 10:
>> print n*n
>>
>> define print_in_range(first,last):
>> if first >= last: return
>> print first*first
>> print_in_range(first+1,last)
>>
>> No contest, right?
>
> I think that by using "for" instead of a simpler looping construct,
> you've applied to the iterative version a level of syntactic sugar
> that you haven't applied to the recursive one.
Quite true. I don't know of any comparable sugar that
can easily be applied to the recursive version. One of
the advantages of iteration is that we have good notations
for some particularly common looping constructs; and one
of the disadvantages of recursion is that it's a fairly
low-level construction: very powerful but sometimes hard
to follow. (Compare, though this isn't very fair, Scheme's
CALL-WITH-CURRENT-CONTINUATION versus the weaker but
more approachable THROW/CATCH.)
Of course, you can layer syntactic sugar on top of
recursion. You could, for instance, give a definition
of that "for i from 1 to 10" construct in terms of
recursion. But it seems to me that this amounts to
disguising recursion as iteration. There's nothing
wrong with that, but it's evidence that for some
purposes iteration is easier to understand than
recursion.
> Also, the use of
> an explicit "return" to break out of the function is not necessary
> in structured languages.
I know it's not necessary. I think it's often clearer,
though if you prefer the other version
> define print_in_range(first,last):
> if first < last:
> print first*first
> print_in_range(first+1,last)
then I have no quarrel with that. On reflection, I think
I too prefer it here.
[I said:]
>> To arrange this you have to do one of two things: (1) make
>> the call to FOO do one more level of indirection than it would
>> have to in a language like C, to look up the current meaning
>> of FOO; or, (2) arrange that when the definition of FOO changes
>> the code for BAR gets patched to refer to the new definition.
>>
>> So far as I know, no actual Lisp system takes option (2).
>
> Maclisp was doing option (2) 20 years ago, on both Multics and PDP-10's.
Excellent! I stand corrected.
This seems to me to be the error that some introductory courses on
Lisp/Scheme make; they too often inflict on students the notion that
recursion is the *only* tool available for use.
*Can* you express everything using recursion? Surely.
- There are many things that recursion is useful to express.
- It can be *convenient* to transform iteration into recursion, when
there is some express purpose to this.
- But to force everything into a recursive mould can be as restrictive
as an attempt to force everything into an iterative mould.
For instance, the sum:
\[ S = \sum_{i=1}^{n}{ V_i } \]
would tend to be considered an iterative expression.
--> If you're trying to prove something about the properties of the
expression, it is common to use proof by induction, which is
inherently recursive.
--> If you're trying to *perform* the addition of the expression, it
may be natural to use a recursive recurrence, where
\[ S_{k+1} = S_k + V_i \]
--> If all you want to do is to baldly *describe* the expression, it
is more natural to merely indicate the iteration. Particularly if
you've got a macro expander that will turn this into recursion
behind the scenes.
--
As Will Rogers would have said, "There is no such thing as a free
variable." -- Alan Perlis
cbbr...@ntlug.org - - <http://www.hex.net/~cbbrowne/lisp.html>
> Barry Margolin wrote:
>
> [I said:]
> >> To arrange this you have to do one of two things: (1) make
> >> the call to FOO do one more level of indirection than it would
> >> have to in a language like C, to look up the current meaning
> >> of FOO; or, (2) arrange that when the definition of FOO changes
> >> the code for BAR gets patched to refer to the new definition.
> >>
> >> So far as I know, no actual Lisp system takes option (2).
> >
> > Maclisp was doing option (2) 20 years ago, on both Multics and PDP-10's.
>
> Excellent! I stand corrected.
On the Lisp machine you can remove the indirection.
Rainer Joswig, ISION Internet AG, Harburger Schlossstraße 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: rainer...@ision.de , WWW: http://www.ision.de/
[I wrote:]
> In the present instance, this isn't fair. Provided your
> array can't be more than 2^40 elements in size (which is
> probably a pretty safe guess) the posted quicksort routine
> will never overflow its hard-coded stack, because it
> always stacks the smaller subarray and iterates on the
> larger.
Oops. I didn't read the code carefully enough. The limit
is actually 2^20. That's bad.
Yes, recursion can cost more than iteration. But it often has more value to
understanding and maintainability than its cost in memory or speed. As long
as the cost of using a recursive algorithm is less than the cost of using an
iterative one, it doesn't matter how much it costs from a baseline basis.
This is a common business fallacy, as well. People will say let's not do X
because it costs too much, but they often don't consider what it will cost
not to do X.
Finally, the cost one is willing to pay for something is usually tied up in
its percieved value. Until one states what their valuation function is
(i.e., are maintainability and extensibility out of the picture entirely, is
this in the inner loop of an FFT or just in the outer loop of some little
used event handling code, etc.), it is unlikely that any agreement can ever
be reached.
All-in-all, I think that this is more a warning against making blanket
statements like "recursion is more expensive than iteration" than anything
else.
faa
> --> If you're trying to prove something about the properties of the
> expression, it is common to use proof by induction, which is
> inherently recursive.
> --> If you're trying to *perform* the addition of the expression, it
> may be natural to use a recursive recurrence, where
> \[ S_{k+1} = S_k + V_i \]
Although I actually agree with your post, I think that one could
disagree with this pair of statements. If you want it to be
relatively easy to prove (formally or informally) that your program is
doing what you think, it may be better to implement the expression
about which you reasoned, rather than another expression which (you
think) is equivalent but is somehow `cheaper'. In particular you
might want to rely on a mechanical process (a compiler...) to convert
one to the other.
I think this argument doesn't only apply to the `we implement all our
programs in first-order-typed-fashionable-theory-of-the-week thus
ensuring complete formal-correctness and also that we never ship
anything' brigade, but also is relevant to the more human `we happily
use delta functions and assume everything is suitably differentiable'
people.
--tim
While I happen to like that construct, and I happen to be very
`pro-tail-recursive', I don't see a compelling argument here that
would persuade an `iteration is not recursion' person to change
their mind.