CPU's optimised for recursive algorithms?

[K.I.L.E.R]

I've read off an Internet forum that todays CPU's have the ability to process recursive algorithms just as fast, if not faster than traditional methods using loops.

Is this really true?
The person was babbling on about function addresses or something, I didn't quite get what was said. This was a while back but I'd just like to know if this is indeed true.

 

[maaoouud]

I would not go so far as to call them optimized for recursion. But it is true that some types of recursion is extremely well suited for execution on modern cpus. You're pretty much guaranteed that all the code needed is loaded into cache (after first run of the function), you don't have to update and keep track of a counter to check for termination of the loop.

However, recursion may not be a good way of solving the particular problem, and you need to be certain that your code will run without troubles. Troubles can be that you run the function so many times that you loose track of where to resume execution of the program after the recursive function has terminated (return adress is spammed off the stack). Or that you fail to terminate the function (very common error) and end up with a nonresponsive program.

Also you most likely still need some kind of check to see when to terminate the function which will often have just as much overhead as the countermanagement in a loop, so the gained performance may not be that great.

Proper implementation of a recursive solution to a problem can however give amazing results. Say you terminate the function by killing it's thread from the main thread of the program, then there is no need to check for termination in the recursive function (can be a huge boost if it involves calling other functions). The code can be very easy to overlook and understand (it may well be the opposite too tho ), I've seen a recursive solution to a chess problem that put the entire program to like 15 lines of code - the regular structured solution was like 50-ish for the function.

Ah gotta go fetch the laundry.. might put up another post about it later though.

 

[maaoouud]

Ok I hope the first post gave a general explanation of recursion for you. There is no straight answer to the question (it depends on alot of things), but it is generally true I'd say, recursion is often just as fast as using loops or it might even be faster.

I'll just generally sum it up for you, if you want a more indepth answer I suggest you try google, there's bound to be tons of information about recursion.

Recursion is very much dependant of how well the problem is suited to a recursive solution, this is the most important reason of whether it will run well with recursion in my oppinion.

Recursion demands that you are very much "on top" of the problem, you need to know the implications of what you do. Calling a function has some overhead in most languages, you might run into limitations of the hardware/software which may be documented but the definition may not be easy to find. You may be forced to work around limitations in the language you're using (optimize with assembler or link in a portion of code from another language) or settle for a not quite optimal solution.


I don't want to scare you away from using it, but in the big common languages you often need to put more effort into solving a problem with recursion. I've heard that there's languages designed for recursive solutions but I haven't tried any myself but they're bound to take away most of the problems with recursion. Also you need to get into the recursive way of thinking to solve problems with it and that may take some real effort the first few times.

 

[3dilettante]

Like what was said, recursive code can probably be cached very easily if it is compact.

For that at least, recursion does pretty well. On the other hand, a loop of similar code size would benefit just as much, and modern hardware design seems pretty fixed on loop-based code as an optmization target.

There would be some complications resulting from how recursion is carried out. I believe it is usually implemented as a repeated function call, and I am not sure if this might make it harder to schedule instructions for an out of order processor. I know speculation can carry over jumps, but I don't know enough to say if it will skip over a function call.

A function call usually means the processor has to put something on the stack, which means an access to cache at the very least for setting up the return address and stack frame. If there are local variables, they will be placed in the stack frame as well.

On out of order processors or properly optimized and unrolled loops, this overhead is either hidden or reduced. In addition, intelligent loop unrolling can save on redundant variable allocation and skip over a lot of address calculations.

I do not believe modern hardware is smart enough to pick up on recursive calls to figure out more optimal ways to handle stack and allocation issues. Software optimizations might be.

Then there's the danger of a stack overflow if something recursive goes on for too long. Even trivial recursive solutions can overtax the small amount of local storage on a processor. How the stack works in a multiprocessor environment might also be an issue, if the processors repeatedly fight over access to it.

Unfortunately, I am not very proficient in the low level issues of recursion on modern hardware. I welcome corrections to any misconceptions I may have.

 

[Dawgmatix]

Look up tail recursive recursion

Tail recursive programs run just as efficiently as loops because (as of my understanding),
the program does not have to save the stack for each recursive call. Instead the value of the last iteration is passed as a value to the new iteration. All other information is dumped.
I might not have done a good job explaining it , but google it up. This is pretty much how you can write recursive lisp code with acceptable performance levels. (The technique itself applies to all compilers which optimise tail recursive functions(most compilers do)).

 

[3dilettante]

Isn't it also true that tail recursion can be easily converted to iteration anyway?

That may be what most software optimizers would do anyway.

 

[LeGreg]

Isn't it also true that tail recursion can be easily converted to iteration anyway?
That may be what most software optimizers would do anyway.

depends on what your compiler is.
OCAML compiler will iterate tail recursions but vc++ won't at least not since last time I checked.
But yes it can be "easily" converted by hand. If you followed the course.

 

[K.I.L.E.R]

I use recursion frequently and NEVER had any performance issues with it, some cases even noticed performance improvement. The performance improvement IMO was from bringing the amount of code down to a very small size.
I find recursion to naturally allow me to implement some optimisations which are much harder to do in loops.

I just had to know whether harderware contributed to performance with recursion.
Thanks.

 

[RussSchultz]

Its hard to have performance problems on a 3Ghz machine unless you really don't know what you're doing.

I would say that recursion on an ARM processor is worse than iteration unless your code only uses 5-ish registers. The standard calling mechanism demands you exit the function you called without disturbing registers R4-R11, and every time you go to a subroutine you must save off the link register.

 

[pcchen]

I think, if your compiler is not converting tail recursion to a loop, recursion is going to be slower, because it has to store the return address in stack which is not necessary.