gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

C/C++ > Using recursion

#3068 - Vortex - Mon Feb 17, 2003 5:07 pm

Hello,

I am using a FloodFill like algorithm, which is recursive. I am wondering how deep the GBA stack is, or in other words, how deep the recursion could be. I tried to convert the algorithm to a non-recursive one, but it is not very efficient.

Thanks

#3073 - col - Mon Feb 17, 2003 7:28 pm

Vortex wrote:
Hello,

I am using a FloodFill like algorithm, which is recursive. I am wondering how deep the GBA stack is, or in other words, how deep the recursion could be. I tried to convert the algorithm to a non-recursive one, but it is not very efficient.

Thanks


The available stack space depends on how much of the iwram you are using for other things - code, data...

The amount of stack space used by each recursion depends on how complicated the algorithm is - how many variables need to be pushed on to the stack.
If you use the --save-temps(i think?) switch, you can check the asm output to see how much stack each recursion is using.

you can use gcc to create a map file, then check this to see how much iwram is left for the stack, you can then edit your linkscript to give the stack more iwram:
if you're using Jeffs linkscript and crt0, look in the linkscript for the line
__iheap_end = 0x3008000 - 0x400;
increase the 0x400 to give yours stack more space and the iwram heap less.
(my stack can use as much as 10k of iwram sometimes :))

Recursive algorithms are great on gba - they can be very much faster than non-recursive alternatives. All the data is accessed from zero waitstate
And there is no cache so, no worries about cache misses.

cheers

Col

#3109 - Paul Shirley - Tue Feb 18, 2003 2:33 pm

removed

Last edited by Paul Shirley on Sun Mar 28, 2004 9:40 pm; edited 1 time in total

#3115 - tepples - Tue Feb 18, 2003 4:32 pm

Paul Shirley wrote:
Recursive floodfill algorithms are notoriously inefficient and wasteful of stack. Researching the alternatives would do more good...

The completely non-recursive flood fill algorithms that were once used for vector graphics in 8-bit adventure games can't handle upward or downward convex edges. You'll still have to maintain some sort of stack of edges to check.

However, the searches for similar-colored pixels to the left and to the right can be done correctly without recursion, which saves a ton of space and time.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.