Re: recursion. was: stack size. should be: on a different list
Re: recursion. was: stack size. should be: on a different list
On Fri, Jun 20, 2003 at 05:45:34PM -0600, Markian Hlynka wrote:
>
> That's as may be, but for some things it just doesn't make sense. Can
> you conceive of writing alpha-beta or iterative deepening search
> non-recursively? It just doesn't make sense, and makes a mess of the
> programming by mixing the algorithm with details of its implementation
> at the lowest level. Fortunately, this doesn't usually seem to be a
> problem [yet] for search algorithms. But I'm sure there are other
> problems that are similar, where doing the recursion "manually" is
> counter-intuitive and counter-productive.
It's not very nice, I agree, but it's a fairly standard thing to do to
get performance. You write the code the elegant way first, so that you
know the algorithm works, and then you re-write those portions that are
slow for speed. Writing for speed typically results in code that isn't
very readable; loop unrolling for example usually looks pretty nasty.
Rearranging code so that memory access is as linear as possible makes
things more complex still.
I once wrote a routine for translating DNA into protein. It was written
with nice elegant C code. It was about 10 lines long, plus a lookup
table. It ran like a dog. I reimplemented it purely for speed. It's
now well over 100 lines long, is hand unrolled three times, contains no
function calls, very few internal conditionals, is full of binary
operations, and almost totally unreadable. But it is almost 50 times
the speed of the original version - on our systems at work it translates
DNA in all six reading frames at about 25MB/sec (which is faster than
most disk drives can provide it with the raw data)
Recursion has a performance problem because it involves subroutine
calls. Not only are they expensive in themselves, because of all the
stack work, but they also usually stop the compiler from doing much
optimisation, because the compiler doesn't know what happens inside the
function call. This results in pipeline stalls in the CPU and so on.
The iterative implementation allows the compiler much more scope for
optimisation, since it can see everything. It's also more likely to
deal with very large problems precisely because it doesn't have stack
limit problems.
Tim
--
Dr Tim Cutts
Informatics Systems Group
Wellcome Trust Sanger Institute, Hinxton, Cambridge, CB10 1SA, UK
_______________________________________________
x11-users mailing list | email@hidden
Help/Unsubscribe/Archives: http://www.lists.apple.com/mailman/listinfo/x11-users
X11 for Mac OS X FAQ: http://developer.apple.com/qa/qa2001/qa1232.html
Report issues, request features, feedback: http://developer.apple.com/bugreporter
Do not post admin requests to the list. They will be ignored.