Optimizing recursive function calls

I have a function that does a huge number of iterations. I suspect that the function calls themselves are resulting in overhead. I tried passing by reference instead of by value, but this slowed things down. If I use global variables, this will speed things up at least some, but I'm weary of global variables. I could probably do the whole thing with goto statements, and that would probably be the fastest, but it will be ugly.

My function iterates in a tree-like pattern, but there is no actual tree data structure, so the memory foot print is not overly large.

I have a lot of input variables. I could lump them all into one structure or one class and just pass that single object. I'm not sure if this would actually do anything though.

Is there anything that I should be aware of if I want to optimize a recursive function?

Code?

You have it backward. Iterating a function call will not increase your "overhead". But recursion surely will.

Quote:

---

If I use global variables, this will speed things up at least some, but I'm weary of global variables. I could probably do the whole thing with goto statements, and that would probably be the fastest, but it will be ugly.

---

Using globals might provide an advantage, but goto won't.

Recursive functions have pretty big overhead compared to iterative methods. The best way to increase speed is to see if it is possible to convert the function into an iterative loop instead of a recursive one.

If you can implement the whole thing with gotos, then you should be able to do it with a for/while loop.

Without seeing code, or knowing exactly what you are doing, it will be hard for us to give you any good suggestions on how to improve speed. But here are some suggestions anyways.

One of the most common methods for speeding up recursive functions is using whats known as dynamic programming. The gist of dynamic programming is storing off the results of a function call and referencing those results rather then recomputing everything all over again. The down side is that the function must preform the same for a given input, and it requires the memory to store all the information for each function call.

As was mentioned above, using an iterative loop will dramatically increase the code. However, it isn't always possible. For example, quicksort can't be converted to an iterative method (AFAIK) as the bounds and the results of the next loop require the computations of the last (It can be done with a stack, however, you really don't gain anything from it.)

Next, ensuring that you are using the algorithm with the best efficiency for the expected data will go a long ways. Don't just use quicksort because it is O(n log n), consider something else if your data is sufficiently small (like selection sort). A O(n log n) algorithm may be fast for large n, however, for small n often a less efficient O(n^2) algorithm will go faster.

Finally, if all else fails, break out the assembly. Reordering instructions, aligning loops, and using SSE instructions where applicable can work miracles. On the other had, a bad assembly program can hang you pretty quickly. (heck, generally humans do a better job at register usage then the compiler does. Compilers may be pretty smart, but a good assembly programmer can still beat a good compiler). This route isn't for the faint of heart, some may even call me retarded for mentioning it. But if performance is a concern then it is hard to top. At very least, looking at the assembly will let you know what goes fast and what goes slow. Your mention of gotos is an example where the people here that know assembly are thinking "Nope, not faster." because they know it will most likely break down to two jmp instructions (one to avoid the goto, and the goto itself.) instead of the one a while loop would give you.

Quote:

---

Originally Posted by MK27

You have it backward. Iterating a function call will not increase your "overhead". But recursion surely will.

Using globals might provide an advantage, but goto won't.

---

But using goto will make my recursive function work in a way that is more similar to an iterating function.

I was thinking that each time the recursive function is called, copies of variable are made, at least if I pass by value. If I pass by reference, than I think the address might be copied, but I'm not sure.

My thought is that using either global variables or goto prevents function calls and therefore eliminates the need for variables to be copied.

Quote:

---

Originally Posted by thetinman

But using goto will make my recursive function work in a way that is more similar to an iterating function.

I was thinking that each time the recursive function is called, copies of variable are made, at least if I pass by value. If I pass by reference, than I think the address might be copied, but I'm not sure.

My thought is that using either global variables or goto prevents function calls and therefore eliminates the need for variables to be copied.

---

The reason not to use goto is not because you're not supposed to write iterative code - it's because almost everything can be solved without using goto, and the things that can't are often strange hacks.
If you use goto, reading your code will be like driving around town to pick up notes that direct you to the next note, which will always be way across town.
It's called "spaghetti code."

By all means, implement your code iteratively -- recursion is probably never the most efficient way to do something, because you do indeed make multiple copies of the local variables. If your function allocates a 256 byte buffer on the stack, that 256 byte buffer is allocated every function call, and eventually, you'll run out of stack space. But whatever you do, avoid goto like the plague.

Quote:

---

Originally Posted by thetinman

But using goto will make my recursive function work in a way that is more similar to an iterating function.

---

So why not just make it iterative to start with?

Quote:

---

I was thinking that each time the recursive function is called, copies of variable are made, at least if I pass by value. If I pass by reference, than I think the address might be copied, but I'm not sure.

---

Yeah, that is part of the overhead of a function call, and the address is copied. However, copying a pointer is extremely trivial, I think probably only a few lines of ASM.

What's more significantly expensive with a function call is allocating memory for it's internal procedures. If you have an iterative function -- one which exits before it is called again -- the allocation only needs to happen ONCE, the same region of memory will be reused. With a recursive function, however, allocation has to happen at each level of recursion. So the only good time to use recursion is when, for example, you need to compound data, in which case an iterative function would be allocating and returning data each time, or else there is no clear and easy iterative method. Bad reasons to use recursion:

1) Because it's cool.
2) Because it will be fewer lines of code.

Quote:

---

My thought is that using either global variables or goto prevents function calls and therefore eliminates the need for variables to be copied.

---

It's true that globals eliminate the need for copying, but again, passing pointers is a negligible expense, and most parameters should be either pointers or pointer sized (ints). There is almost never a reason to pass an array or struct by value.

WRT goto, I am not sure that it is any faster than an equivalent function call (which would be "void myfunc(void)"), but I doubt it. WRT to memory, the code your goto goes to must pre-exist just the same as the code in a function must (and does) pre-exist.

The only place I have seen goto used in source code is for error handling, eg, if you have a function which does some set-up/allocation, then performs several tests before it proceeds (if a file exists to read, then if there is data in it, then if the data is usable) where any test failing indicates the function should also fail and return, but it needs to clean-up first (and the clean-up is always the same), then there might be a bit of code at the end (after the sucessful return) that can be called with goto.

Other than that I've never seen it used for anything and methinks that by using it you are failing to learn more normative and efficient techniques.

Quote:

---

Originally Posted by thetinman

But using goto will make my recursive function work in a way that is more similar to an iterating function.

I was thinking that each time the recursive function is called, copies of variable are made, at least if I pass by value. If I pass by reference, than I think the address might be copied, but I'm not sure.

My thought is that using either global variables or goto prevents function calls and therefore eliminates the need for variables to be copied.

---

You're missing the point completely. if a goto will make the function more iterative, then you can do the same thing with a while loop and variables. If you don't need the variables from more then one function call back (which is suggested by the fact that you can get away with using a global variable for variable passing) then you should be able to do this iteratively. (IE while loop/for loop). In short, use a loop, gotos and globals are do not need to be applied in this situation.

Function calling is slower then looping for several reasons. you have to unroll the stack, return, and remove variables passed into the function from the stack for every function call. Not to mention saving and restoring the stack pointer, it has several instructions associated with it, and difficult branch prediction as well (Pretty much kills your iCache, as well as breaking pipelining). Loops, on the other had, don't have to deal with half that stuff. most will fit completely in the icache. they allocate space for needed variables once, and they have no return pointer pushed on the stack with each function call. In short, they are the best option for anything that involves repeating a step.

The naive goto implementation (I'll have to compile something to confirm it, but I'm fairly certain compiler writers are leaping out of their seats to make goto more efficient) has MORE overhead associated with it then a loop will (multiple jump commands vs 1) and makes your code retardedly unreadable.

Again, Don't use gotos for this, they are slower then a while loop, and less readable then a recursive call. Plus, anywhere you can use the goto for looping, you could have used a while loop instead.

If you want anything optimized here, we must see the actual code, as Bubba already asked. Without posting that you wont get anywhere.

The code iterates in a tree like fashion. In the extreme case, the tree would only be 40 levels deep, so the memory footprint is relatively small. Each node on the tree though, would have 40 children, so there would be a huge number of leaves (I don't actually traverse to all of the leaves).

I see now how I can do this with loops. I will need to create a few additional arrays to hold data that would have been generated recursively (and held) at the nodes.

Maybe I should take this back:

Quote:

---

Originally Posted by MK27

Bad reasons to use recursion:

1) Because it's cool.

---

It's actually not that bad a reason if it simplifies the code in a case like this, but it is not a path to optimizing performance either.

If you do not show some code any advice we offer is going to be a huge guess. You may not need to optimize your recursion but may need to optimize what you are doing during the recursion. Or you may need to do the operation iteratively, or you may have memory issue, or you may have.........the list goes on.

Show some code. If it is proprietary code then show some that illustrates the problem but does not reveal proprietary information. No one is asking you to violate an NDA here but we do need to see an example of your issue prior to giving you a nudge in the right direction.

"there is no actual tree data structure" "The code iterates in a tree like fashion".
Newflash: If you are iterating in a tree-like fashion, then you have a tree data structure! It doesn't matter whether you're storing each node in a separately new'd object, or lumping them all in an array, and it makes no difference whether you are accessing the children via pointers or item indexes. There are many many ways to represent a tree. Unless you have a tree where you can follow links and end up revisiting nodes (i.e. a graph), then you have a tree data structure. Or if the data is heirarchial in any sense, you basically have a tree. It is not the way it is stored in memory that defines it as a tree, but the way you perform operations on it that defines it as a tree - got it!?!? If it walks like a duck and quacks like a duck, then it's a duck!

Quote:

---

I have a lot of input variables. I could lump them all into one structure or one class and just pass that single object. I'm not sure if this would actually do anything though.

---

There is no correct answer to that statement. It always depends on the details, details that are either too difficult to describe accurately here, and that you'd most likely misintrepret anyway. It can certainly be a good idea to combine several of the input parameters (usually not all) in a specific set of circumstances.

Every optimisation rule has an exception, and it does not make sense to discuss any low-level optimisation techniques outside the context of actual code. We don't really have enough information to describe high-level optimisations here either.

You are in contact with some optimisation experts here. If you want code optimised, no matter how messy it looks etc, you gotta post it. It's as simple as that. Last chance to stop beating around the bush.

Quote:

---

Originally Posted by MK27

Maybe I should take this back:



It's actually not that bad a reason if it simplifies the code in a case like this, but it is not a path to optimizing performance either.

---

The same goes with 2) fewer lines of codes.

Bad reasons are mostly when the big number of function calls might result in a stack overflow. Meaning that if a big number of function calls are possible or you simply don't know, you shouldn't do it recursively.

Performance depends. If the time needed to execute the function is much greater than a function call, then you might not care about the overhead. If you have X amount of time to optimize your code then a simplier code will increase your possiblities of optimizations. So it all depends.