Jump to content
  • Advertisement
Sign in to follow this  
timw

eliminating recursion

This topic is 4667 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!