16
Jun
14

Recursive versus Iterative Algorithm Results Follow-up

A few week ago I did some preliminary investigation into the performance difference between recursive and iterative procedures/algorithms. The problem I chose to solve was path finding in an imperfect maze as there are algorithms which have the same theoretical complexity. I also already had some code lying around for both generating mazes and finding paths. I created iterative and recursive versions of the depth first search algorithm to compare with each other and included breadth first search for comparison to a known “slower” algorithm.

The first results I got were interesting, both the dfs (short for depth first search) algorithms were fairly close in terms of rates until the size of the mazes got larger. The results however were inconsistent because of the small number of mazes used for testing and differences in the behavior of the two dfs algorithms. Clearly I needed to test across a larger set of mazes and fix the behavior difference before I’d get good results. It wasn’t a waste of time as it did illustrate that it is possible for both types of algorithm to out-perform the other given even minor differences in behavior.

So I carefully adjusted the code so that both implementations of the dfs algorithms behaved in the same manner. Again I ran some initial tests and this time the iterative version of dfs out-performed the others in general. Satisfied that the code is behaving correctly I up-scaled the tests to 1000 different mazes across many sizes so I could graph the results.

alg-rate

You can see the rate for all the algorithms drops of very quickly! It is quite difficult to see much detail in this graph so I did some number crunching to determine the average time per search for each algorithm and size of maze.

alg-msec-per-search

This graph makes the difference much more clear. Note the parabola shape, this is because the worst case for all the algorithms is to search the entire maze, which obviously is the square of the X axis in this graph. The interesting part is how they compare with each other. The iterative dfs graph is very shallow compared to the others, it is in fact quite difficult to see much of an increase. It is however increasing in a similar fashion just not anywhere near as dramatic as both recursive dfs and iterative bfs (breadth first search).

So why the huge difference between iterative dfs and the others? The big difference between the two dfs algorithms is the cost of recursion. The extra cost is per square visited in the maze, so a doubling in the processing overhead per square produces a times four increase in the total overhead.

To get a good idea of why the overhead is so comparably large in the recursive case we need to think about how it is implemented at the machine code level. Basically for every square visited in the maze there is a function call to the recursive function and a return at the end. A function call and return involves a number of relatively expensive operations. Firstly information from the calling code needs to be pushed onto the stack (usually important register information), then the processor can “call” the function code which basically pushes a return address onto the stack and jumps to the function code. The first thing the newly called function must do is allocate space on the stack for its local variables, then it can do whatever processing it requires. Once finished the function will place the return value in either the stack or a register, remove local variables from the stack and then return control to the code that called it. This involves restoring the stack to remove the local variable information and then using the return address stored there to return to the calling code. The calling code can then retrieve anything it pushed on the stack before the call and continue operation. Quite the involved process!

Lets contrast that with what an iterative algorithm needs to do differently. Firstly any iterative algorithm needs to set up storage space for the body of the algorithm. In this case a stack (in the data segment or heap) for storing the current search and some variables for tracking the current location. Then the body can begin, usually this will be a loop of some kind, either a for loop or a while loop. These loops involve checking a condition and jumping at either the beginning or end, but are only short-range jumps within the function. The body of the code simply does the search updating the stack as it goes.

So for every square of the maze visited the recursive version has to deal with function call overhead (stack operations and far calls) where the iterative version has to only check a condition and make a short jump. There is more to it with the effects of the L1 and L2 caches, but I’ll leave that out because it’s x86 specific.

So the cost of recursion is high, in this case almost as bad as iterative breadth first search and it doesn’t guarantee the shortest path. Also because of limited program stack space, the recursive function cannot search as large a maze lest there be a stack overflow. So in general I’d recommend people stick with writing iterative code except where the complexity of a recursive function is significantly better. Your code should be faster and put less strain on the limited stack space.

Advertisements

0 Responses to “Recursive versus Iterative Algorithm Results Follow-up”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Blogs I Follow

Enter your email address to follow this blog and receive notifications of new posts by email.


Mister G Kids

A daily comic about real stuff little kids say in school. By Matt Gajdoš

Random Battles: my life long level grind

completing every RPG, ever.

Gough's Tech Zone

Reversing the mindless enslavement of humans by technology.

Retrocosm's Vintage Computing, Tech & Scale RC Blog

Random mutterings on retro computing, old technology, some new, plus radio controlled scale modelling.

ancientelectronics

retro computing and gaming plus a little more

Retrocomputing with 90's SPARC

21st-Century computing, the hard way

lazygamereviews

MS-DOS game reviews, retro ramblings and more...

%d bloggers like this: