eliminating recursion
Author
I got a raytracer and I'm going back to optimoze the heck out of it. one thing I'm considering doing is eliminating the recursion but it seems like a royal pain to do, one thing is certian, I still need a stack for variables so the only thing I'm really saving on is
a) the function calls
b) the register saving and extranious data pusing
say the function rarely exceeds 10 levels of recursion, and it's a ray tracer so it's called billions of times so I'm wondering if it's wouth the effort.. hmmm any people out there done something similiar with good results? bacailly if I only save a min on the hour I don't consider it wourth it. I just can't gage how much time I'll be saving simply by thinking about it. anyone have any ideas?
Tim
What does the recursive call look like? With some, it may be possible for the compiler to do a tail-recursion optimization (which just turns it into a loop).
Author
I don't think it's quite that nice, it can be recursed in many different places (at least 4 I'm guessing) depending on different conditions.
Even if it isn't tail-recursive (which, for a raytracer, it might well not be), modern compilers are able to inline recursive calls up to a finite recursion level. You may want to examine your compiler documentation to determine if this is supported.
Author
thanks I've heard about that but it never occured to me. hmm I'm gonna check it out. so you think the advantage of maintaing your own stack would be so minimal as to not try it?
FWIW, GCC (with -foptimize-sibling-calls (-O2 adds this flag)) and Sun Workshop (with -O2), can do tail call optimizations. That includes tail recursion. I'm not sure about other compilers. Check the documentation.
Unforunately, it's pretty clear that an raytracer will not be a tail recursive function. I don't think changing it to a stack will be useful in any way, unless you are hitting the stack space limit with too many levels of recursion. You should probably try to optimize the alogrithms involved in your raytracer. For example, instead of doing 4x4 AA, you might do adaptive AA. Similarily, you could do bounding box ray intersections first before doing the more expensive intersections.
You're probably right that it isn't even going to speed things up by as much as 2%. If it were me though, I'd just do it if it's possible, because it's become very easy for me after years of practice. High-level optimisations first though.
However, there's nothing we can do here without seeing some code. Actually come to think of it, you haven't mentioned what language you're using.
Profile!
However, there's nothing we can do here without seeing some code. Actually come to think of it, you haven't mentioned what language you're using.
Profile!
I'm not so sure it would speed-up too much. First do the other optimisations, after try to do this change from recursive to loops in a simpler code just to see if it realy helps. Usualy compilers do nice optimizations using cpu registers, and recursion could be faster than rewriting it with loops.
Good luck anyway.. writing raytracers is cool, I wrote one some time ago :
http://dinf.unicruz.edu.br/~manuelb
Good luck anyway.. writing raytracers is cool, I wrote one some time ago :
http://dinf.unicruz.edu.br/~manuelb
Do you have good spatial subdivision structures? You can turn an average O(n) lookup into O(logN).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
