Coding question - recursion
category: general [glöplog]
I'm coding a little recursive program (kd-tree traversal) and I'm completely lost. I remember that making an algorithm iterative instead of recursive made it faster due the absence of function callings.
This time it is not true and I have no idea why. I've done two iterative versions, one based in 2 dimentional array and one based in a stack array. Both are slower (about 20%-30% slower) than the true recursive version - the stack a bit faster than the 2-dimentional array one. I can't understand it.
I'm using gcc as compiler and a Core 2 Duo, running all in a single core.
So, my question is... maybe in the newadays computers the true recursion is faster than the iterative? Maybe I'm doing something extremely wrong?
This is not the first time I converse a recursive algorithm to an iterative version, and in my older computers, the iterative versions used to be much faster always... Now I'm completely puzzled... Do you have any ideas? Have you experienced similar things?
Thanks in advance :)
This time it is not true and I have no idea why. I've done two iterative versions, one based in 2 dimentional array and one based in a stack array. Both are slower (about 20%-30% slower) than the true recursive version - the stack a bit faster than the 2-dimentional array one. I can't understand it.
I'm using gcc as compiler and a Core 2 Duo, running all in a single core.
So, my question is... maybe in the newadays computers the true recursion is faster than the iterative? Maybe I'm doing something extremely wrong?
This is not the first time I converse a recursive algorithm to an iterative version, and in my older computers, the iterative versions used to be much faster always... Now I'm completely puzzled... Do you have any ideas? Have you experienced similar things?
Thanks in advance :)
Guess seeing the source code would help.
One possibility is that the recursive version happens to be more cache efficient due to the locality of accessed data.
Another possibility is that you iterative version is not efficiently implemented :)
Generally speaking, when I have algorithms that perform differently I tend to check memory bottlenecks, either due to bad alignment of data, or cache misses.
When accessing a 2d array, reading all the cells by row and then by column, or by column and then by row, can be an order of magnitude faster depending of the speed of memory, bank selection, and cache behavior.
One possibility is that the recursive version happens to be more cache efficient due to the locality of accessed data.
Another possibility is that you iterative version is not efficiently implemented :)
Generally speaking, when I have algorithms that perform differently I tend to check memory bottlenecks, either due to bad alignment of data, or cache misses.
When accessing a 2d array, reading all the cells by row and then by column, or by column and then by row, can be an order of magnitude faster depending of the speed of memory, bank selection, and cache behavior.
Update: I've now a faster iterative version. I was having problems with cache... the iterative version is not much faster, but at least now I know where is the problem :P Thanks
I used to have the exact same problem when comparing the speed of recursive kd-tree traversal vs iterative one. the recursive was 20 to 30% faster. In my case it was due to std::stack... after removing that shitty template both versions were same speed or so. if i recall correctly... but yep as you have seen it is possible to optimize the iterative version. you can get more speed by removing some conditional branches, i like to keep one in mine instead of removing all branches as people do usually, and it is little faster.
