Sign in to follow this  
timw

eliminating recursion

Recommended Posts

timw    598
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

Share this post


Link to post
Share on other sites
Roboguy    794
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).

Share this post


Link to post
Share on other sites
timw    598
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.

Share this post


Link to post
Share on other sites
Sneftel    1788
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.

Share this post


Link to post
Share on other sites
timw    598
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?

Share this post


Link to post
Share on other sites
flangazor    516
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.

Share this post


Link to post
Share on other sites
risingdragon3    382
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.

Share this post


Link to post
Share on other sites
iMalc    2466
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!

Share this post


Link to post
Share on other sites
manuelb    152
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

Share this post


Link to post
Share on other sites
timw    598
thanks for the suggestions guys. I'm looking for sub algorithmic optimozations at this point, if I could speed it up by 10 percent, I'd be very happy. I already have efficent acceleration structures, my raytracer is rather far along, I have k-d trees, adaptive grids, bvh. so I'm gonna probably rewrite the acceleration structures in assembly. now I'm just thinking that the acceleration structures probably have an average recursion depth much greater then the ray tracer itself lol. The language is cpp of course.

Tim

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this