Recent

Author Topic: [SOLVED]How to avoid Stack Overflow with recursive procedure  (Read 464 times)

BeanzMaster

  • Full Member
  • ***
  • Posts: 168
Hi to all

In my project i'd like to implement a some simple flood fill  : the boundary 4 and 8 fill algorithm
but i have a stack overflow if i call recursively more three time the procedure  :o

Code: Pascal  [Select]
  1. procedure TBZBitmapCanvas.FloodFill(px,py : Single; Const SearchColor, NewColor: TBZColor);
  2. Var
  3.   SrcColor : TBZColor;
  4.   pxi,pyi : Integer;
  5.  
  6.   function IsInside(x,y:Integer): Boolean;
  7.   begin
  8.     Result := (Ord(X < 0) + Ord(X > FOwnerBitmap.MaxWidth) Shl 1 + Ord(Y < 0) Shl 2 + Ord(Y > FOwnerBitmap.MaxHeight) Shl 3) = 0;
  9.   end;
  10.  
  11. begin
  12.   pxi := Round(px);
  13.   pyi := Round(py);
  14.   if not(IsInside(pxi, pyi)) then exit;
  15.   SrcColor := FOwnerBitmap.getPixel(pxi, pyi);
  16.   if (SrcColor = SearchColor) and (SrcColor <> NewColor) then
  17.   begin
  18.     PutPixel(pxi,pyi,NewColor);
  19.  
  20.     // if i comment one of this line below, all work fine, if i let as is a stack overflow is raise
  21.     if IsInside(pxi+1,pyi) then FloodFill(px+1,py,SearchColor, NewColor);
  22.     if IsInside(pxi,pyi+1) then FloodFill(px,py+1,SearchColor, NewColor);
  23.     if IsInside(pxi-1,pyi) then FloodFill(px-1,py,SearchColor, NewColor);
  24.     if IsInside(pxi,pyi-1) then FloodFill(px,py-1,SearchColor, NewColor);
  25.  
  26.  
  27.   end;
  28. end;

Do you have some clues or solutions to avoid this problem ?

Thanks in advance

Best regards
« Last Edit: June 11, 2019, 01:56:55 am by BeanzMaster »

BeanzMaster

  • Full Member
  • ***
  • Posts: 168
Re: How to avoid Stack Overflow with recursive procedure
« Reply #1 on: June 10, 2019, 10:48:42 pm »
Ok i'm find the solution by putting
Code: Pascal  [Select]
  1. {$MAXSTACKSIZE $7FFFFFFF}
  in my application project.
 
But now is there a solution to place it in a package, without to put it in application ?

Is there a way to control, configure the size of the call stack outside the application (in my runtime package) or in the header of my unit ?

Cheers
« Last Edit: June 10, 2019, 10:51:32 pm by BeanzMaster »

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: How to avoid Stack Overflow with recursive procedure
« Reply #2 on: June 10, 2019, 11:07:08 pm »
Ok i'm find the solution by putting
Code: Pascal  [Select]
  1. {$MAXSTACKSIZE $7FFFFFFF}
  in my application project.
 
But now is there a solution to place it in a package, without to put it in application ?

Is there a way to control, configure the size of the call stack outside the application (in my runtime package) or in the header of my unit ?

Cheers
Just a question, how large is TBZColor ?

I ask because, unless the structure is quite large, you shouldn't be getting a stack overflow _unless_ recursion is happening a large number of times.

Have you checked how many times the routine is calling itself recursively ? (for testing purposes, keep a recursion counter someplace, it may be larger than you expect)

HTH.
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 5390
    • wiki
Re: How to avoid Stack Overflow with recursive procedure
« Reply #3 on: June 10, 2019, 11:32:01 pm »
It recurses once per pixel. It could do some of it in a loop.

rvk

  • Hero Member
  • *****
  • Posts: 3693
Re: How to avoid Stack Overflow with recursive procedure
« Reply #4 on: June 10, 2019, 11:36:37 pm »
Besides what martin says...

Why do you have SrcColor, pxi and pyi declared?
As I see it you don't need pxi and pyi becuase they are the same as px and py. Just declare those as integers in the function headet and call the initial floodfill with an integer value.

I would also remove the SrcColor and just put the getpixel in the if. You only use SrcColor once (in the if) and local declared variables are very expensive in a recursive function.

It recurses once per pixel. It could do some of it in a loop.
Yes, but that's probably not the exercise  :D

https://www.geeksforgeeks.org/boundary-fill-algorithm/
Quote
Boundary Fill Algorithm is recursive in nature.

lucamar

  • Hero Member
  • *****
  • Posts: 1546
Re: How to avoid Stack Overflow with recursive procedure
« Reply #5 on: June 11, 2019, 12:39:58 am »
https://www.geeksforgeeks.org/boundary-fill-algorithm/
Quote
Boundary Fill Algorithm is recursive in nature.

That doesn't mean that you can't get it by replacing (at least) some recursion with loops. It's the same than with the "standard" recursion example: factorials, which is best implemented with a simple loop.
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 1.8.4 & 2.0.2 w/FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

BeanzMaster

  • Full Member
  • ***
  • Posts: 168
Re: How to avoid Stack Overflow with recursive procedure
« Reply #6 on: June 11, 2019, 01:56:29 am »
[
Just a question, how large is TBZColor ?

I ask because, unless the structure is quite large, you shouldn't be getting a stack overflow _unless_ recursion is happening a large number of times.

Have you checked how many times the routine is calling itself recursively ? (for testing purposes, keep a recursion counter someplace, it may be larger than you expect)

HTH.

This is the structure of TBZColor

Code: Pascal  [Select]
  1. TBZColor32Type = packed array[0..3] of byte;
  2.   { Color format RGBA 32 bits }
  3.   TBZColor32 = Record
  4.   private
  5.     function getColorComponent(Index : Integer): byte;
  6.     procedure SetColorComponent(Index : Integer; aValue:Byte);
  7.   public
  8.     { Create from x,y,z,w values. Default value for W = 255 }
  9.     procedure Create(const aRed, aGreen, aBlue : Byte; const aAlpha : Byte=255); overload;
  10.     { Create from a TBZColor24 and w value. Default value for W = 255 }
  11.     procedure Create(Const aValue : TBZColor24 ; const aW : Byte = 255); overload; //TBZColor24
  12.     { Create from a TBZVector3b  and w value. Default value for W = 255 }
  13.     procedure Create(Const aValue : TBZVector3b ; const aW : Byte = 255); overload; //TBZColor24
  14.     { Return Vector to a formatted string eg "(x, y, z, w)" }
  15.     function ToString : String;
  16.     { Add two TBZColor32.
  17.               Alpha is not compute, default Alpha same As first Operand A.
  18.               Use AddWithAlpha instead if you want compute Alpha to.}
  19.     class operator +(constref A, B: TBZColor32): TBZColor32; overload;
  20.     { Sub two TBZColor32.
  21.               Alpha is not compute, default Alpha same As first Operand A.
  22.               Use SubWithAlpha instead if you want compute Alpha to.}
  23.     class operator -(constref A, B: TBZColor32): TBZColor32; overload;
  24.     { Multiply two TBZColor32.
  25.               Alpha is not compute, default Alpha same As first Operand A.
  26.               Use MulWithAlpha instead if you want compute Alpha to.}
  27.     class operator *(constref A, B: TBZColor32): TBZColor32; overload;
  28.     { Divide two TBZColor32.
  29.               Alpha is not compute, default Alpha same As first Operand A.
  30.               Use DivWithAlpha instead if you want compute Alpha to.}
  31.     class operator Div(constref A, B: TBZColor32): TBZColor32; overload;
  32.     { Add one Byte to each component of a TBZColor32.
  33.               Alpha is not compute, default Alpha same As first Operand A.
  34.               Use AddWithAlpha instead if you want compute Alpha to.}
  35.     class operator +(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  36.     { Sub one Byte to each component of a TBZColor32.
  37.               Alpha is not compute, default Alpha same As first Operand A.
  38.               Use SubWithAlpha instead if you compute Alpha to.}
  39.     class operator -(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  40.     { Multiply each component of a TBZColor32 by one Byte.
  41.               Alpha is not compute, default Alpha same As first Operand A.
  42.               Use MulWithAlpha instead if you compute Alpha to.}
  43.     class operator *(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  44.     { Multiply each componentof a TBZColor32 by one Float.
  45.               Alpha is not compute, default Alpha same As first Operand A.
  46.               Use MulWithAlpha instead if you compute Alpha to.}
  47.     class operator *(constref A: TBZColor32; constref B:Single): TBZColor32; overload;
  48.     { Divide each component of a TBZColor32by one Byte.
  49.               Alpha is not compute, default Alpha same As first Operand A.
  50.               Use DivWithAlpha instead if you compute Alpha to.}
  51.     class operator Div(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  52.     { Compare if two TBZColor32 are equal with Alpha }
  53.     class operator =(constref A, B: TBZColor32): Boolean;
  54.     { Compare if two TBZColor32 are not equal  with Alpha }
  55.     class operator <>(constref A, B: TBZColor32): Boolean;
  56.     { Operator @bold(AND) two TBZColor32
  57.               Alpha is not compute, default Alpha same As first Operand A. }
  58.     class operator And(constref A, B: TBZColor32): TBZColor32; overload;
  59.     { Operator @bold(OR) two TBZColor32
  60.               Alpha is not compute, default Alpha same As first Operand A. }
  61.     class operator Or(constref A, B: TBZColor32): TBZColor32; overload;
  62.     { Operator @bold(XOR) two TBZColor32
  63.               Alpha is not compute, default Alpha same As first Operand A. }
  64.     class operator Xor(constref A, B: TBZColor32): TBZColor32; overload;
  65.     { Operator @bold(AND) one TBZColor32 and one Byte
  66.               Alpha is not compute, default Alpha same As first Operand A. }
  67.     class operator And(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  68.     { Operator @bold(OR) one TBZColor32 and one Byte }
  69.     class operator or(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  70.     { Operator @bold(XOR) one TBZColor32 and one Byte
  71.              Alpha is not compute, default Alpha same As first Operand A. }
  72.     class operator Xor(constref A: TBZColor32; constref B:Byte): TBZColor32; overload;
  73.   .....
  74.     { Access properties }
  75.     Case Integer of
  76.      0 : (V:TBZColor32Type);               //< Array access
  77.      1 : (X, Y, Z, W : Byte);              //< Legacy vector access
  78.      //2 : (Red, Green, Blue,  Alpha:Byte);  //< As Color component
  79.      2 : (AsVector3b : TBZVector3b);       //< As TBZVector3b
  80.      3 : (AsInteger : Cardinal);            //< As 32 bit Integer
  81.   end;
  82.   PBZColor32 = ^TBZColor32;
  83.  
  84.   TBZColor = TBZColor32;    

Besides what martin says...

Why do you have SrcColor, pxi and pyi declared?
As I see it you don't need pxi and pyi becuase they are the same as px and py. Just declare those as integers in the function headet and call the initial floodfill with an integer value.

I would also remove the SrcColor and just put the getpixel in the if. You only use SrcColor once (in the if) and local declared variables are very expensive in a recursive function.

It recurses once per pixel. It could do some of it in a loop.
Yes, but that's probably not the exercise  :D
https://www.geeksforgeeks.org/boundary-fill-algorithm/
Quote
Boundary Fill Algorithm is recursive in nature.

You're right and not.
First for ScrColor the is use twice so don't need call getpixel twice, just one time ;)
Code: Pascal  [Select]
  1.  SrcColor := FOwnerBitmap.getPixel(pxi, pyi);
  2.   if (SrcColor = SearchColor) and (SrcColor <> NewColor) then
For pxi and pyi. The Integer here is due of how i have constructed my classes. In my "Bitmap" i'm using integer by default for accessing to the pixels,  but my in Canavs i'm using Single. Why ? Because TBZBitmapCanvas have a common parent and i have a certain vision of my project for example i'm using the same base  class for constructing opengl canvas and i don't want overload functions . I'm loosing some little performance because i must Round value with "traditionnal bitmap" but the calculation accuracy is more important with single than integer.
With this case of FloodFill function i'll can do an exception. I will think about it and see how the implementation of my project materializes

And for why i'm using Boundary it's just provided from my read https://en.wikipedia.org/wiki/Flood_fill and i'm trying to implements some differents algorithms
and ill try the Alternatives-method

And i'm apologize, i didn't read this sentence  :-[
 
Quote
Though easy to understand, the implementation of the algorithm used above is impractical in languages and environments where stack space is severely constrained

https://www.geeksforgeeks.org/boundary-fill-algorithm/
Quote
Boundary Fill Algorithm is recursive in nature.

That doesn't mean that you can't get it by replacing (at least) some recursion with loops. It's the same than with the "standard" recursion example: factorials, which is best implemented with a simple loop.

Yes but recurse in this case it's the best   :P and Sure  i'll can do it without recurse but not fair and the performance will decrease.
Subsequently anyway I will implement the filling by scanline or / and the large scale behaviours technics. 8-)

PS : I'm also trying by using Global Var and without any local var instead. The result is the same without {$MAXSTACKSIZE} directive
Perhaps with an ASM function And the nostackframe........


440bx

  • Hero Member
  • *****
  • Posts: 826
Re: [SOLVED]How to avoid Stack Overflow with recursive procedure
« Reply #7 on: June 11, 2019, 03:06:40 am »
Your routine consumes too much stack to be recursive.

Here is a quick calculation of how much stack a single invocation of that routine consumes (in 32bit, it will be at least twice as bad in 64bit):

4 parameters for floodfill @ 4 bytes each = 16 bytes
return address = 4 bytes
3 locals @ 4 bytes each = 12
one stack frame = 4

total 36 bytes

the nested function consumes

3 @ 4 bytes = 12 bytes  (3, not 2, because of Result)
1 stack frame = 4
1 hidden pointer to the stack frame of the procedure it is nested in = 4
1 return address = 4

total 24 bytes

adding them together gives 60 bytes.

A recursive routine should not consume that much stack _unless_ it is guaranteed to recurse very few times.

presuming a full 1 megabyte of stack entirely usable by the procedure (which is not the case), that allows for (ideally) 17476 calls before the stack blows up.


In your first post you mention getting a stack overflow after the third recursion.  It's quite likely that a lot of recursion occurred in the first three times that you didn't realize.

Count the number of times the routine is recursing.  That should be the first thing you should do.

HTH.









« Last Edit: June 11, 2019, 03:09:28 am by 440bx »
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

rvk

  • Hero Member
  • *****
  • Posts: 3693
Re: How to avoid Stack Overflow with recursive procedure
« Reply #8 on: June 11, 2019, 11:03:36 am »
I would also remove the SrcColor and just put the getpixel in the if. You only use SrcColor once (in the if) and local declared variables are very expensive in a recursive function.
You're right and not.
First for ScrColor the is use twice so don't need call getpixel twice, just one time ;)
Code: Pascal  [Select]
  1.  SrcColor := FOwnerBitmap.getPixel(pxi, pyi);
  2.   if (SrcColor = SearchColor) and (SrcColor <> NewColor) then
True. But you need to be a bit more creative. You can solve this in 2 ways.

First... this
Code: Pascal  [Select]
  1.  SrcColor := FOwnerBitmap.getPixel(pxi, pyi);
  2. if (SrcColor = SearchColor) and (SrcColor <> NewColor) then
is the same as
Code: Pascal  [Select]
  1. if (FOwnerBitmap.getPixel(pxi, pyi) = SearchColor) and (SearchColor <> NewColor) then
Note that the second SrcColor <> NewColor is changed in SearchColor. You can do this because the first check was getPixel = SearchColor.
You can even leave out the (SearchColor <> NewColor) and put that at the top of the function because SearchColor may never be the same as NewColor.
Code: Pascal  [Select]
  1. if (SearchColor <> NewColor) then exit;

Otherwise, if you really want to keep the SrcColor (which isn't necessary like I showed you) you can make SrcColor a global variable. It's only needed in two lines which are consecutive. So there is no danger overwriting a previous value. Just don't declare such large variable locally if you know it's going to be called lots of times.

Quote
For pxi and pyi. The Integer here is due of how i have constructed my classes. In my "Bitmap" i'm using integer by default for accessing to the pixels,  but my in Canavs i'm using Single.
Yes, but in the function itself you directly do a round(pxi) and round(pyi). And that for ALL the pixels the function recursively calls. And you don't even need the px as single because you only use the rounded value with +1 and -1 etc.

So it's better to define the function header with integers and call your FIRST initial call to floodfill with
Code: Pascal  [Select]
  1. Self.FloodFill(round(px), round(py), SearchColor, NewColor);
That way you don't have to assign and round the single back to an integer each time the function is called. It will be faster too.
« Last Edit: June 11, 2019, 11:05:15 am by rvk »

BeanzMaster

  • Full Member
  • ***
  • Posts: 168
Re: [SOLVED]How to avoid Stack Overflow with recursive procedure
« Reply #9 on: June 12, 2019, 10:37:07 am »
@440bx : Thanks for information. I didn't know how to compute memory needed in stack call  8-)

@rvk : Thanks, you're right for "Searchcolor/newColor" and i think i'll add overload function for using integer


By the way i'v found how to do it without recursion by using a Stack array

Code: Pascal  [Select]
  1. Var
  2.   StackPoint : Array of TBZVector2i;
  3.   StackIndex : Integer;
  4.  
  5. procedure InitStack;
  6. begin
  7.   StackIndex := 0;
  8.   SetLength(StackPoint, 1024);
  9. end;
  10.  
  11. procedure FreeStack;
  12. begin
  13.   StackIndex := 0;
  14.   SetLength(StackPoint, 0);
  15.   StackPoint := nil;
  16. end;
  17.  
  18. Procedure StackPush(Point : TBZVector2i);
  19. Begin
  20.   Inc(StackIndex);
  21.   If StackIndex > high(StackPoint) Then
  22.   Begin
  23.     SetLength(StackPoint, high(StackPoint) + 256);
  24.   End;
  25.   StackPoint[StackIndex] := Point;
  26. End;
  27.  
  28. Procedure StackPush(X,Y : Integer);
  29. Begin
  30.   Inc(StackIndex);
  31.   If StackIndex > high(StackPoint) Then
  32.   Begin
  33.     SetLength(StackPoint, high(StackPoint) + 256);
  34.   End;
  35.   StackPoint[StackIndex].x := X;
  36.   StackPoint[StackIndex].y := Y;
  37. End;
  38.  
  39. Function StackPop(Var Point : TBZVector2i) : Boolean;
  40. Begin
  41.   Result := True;
  42.   Point := StackPoint[StackIndex];
  43.   Dec(StackIndex);
  44.   if StackIndex < 0 then result := False;
  45. End;
  46.  
  47. procedure TBZBitmapCanvas.FloodFill_Boundary4(px, py : Single; const SearchColor, NewColor : TBZColor);
  48. var
  49.   pxi, pyi, MaxH, MaxW : Integer;
  50.   P: TBZVector2i;
  51.   SrcColor : TBZColor;
  52. begin
  53.   if (SearchColor = NewColor) then exit;
  54.   pxi := Round(px);
  55.   pyi := Round(py);
  56.   if (FOwnerBitmap.getPixel(pxi, pyi)<>SearchColor) then exit;
  57.   InitStack;
  58.   p.Create(pxi,pyi);
  59.   MaxH := FOwnerBitmap.MaxHeight;
  60.   MaxW := FOwnerBitmap.MaxWidth;
  61.   StackPush(p);
  62.   While (StackPop(p)) do
  63.   begin
  64.     PutPixel(P.x, P.y, NewColor);
  65.  
  66.     if ((P.x + 1) <= MaxW) then
  67.       if (FOwnerBitmap.getPixel(P.x + 1, P.y) = SearchColor) then StackPush(P.x + 1,P.y);
  68.  
  69.     if ((P.x - 1) >= 0) then
  70.       if (FOwnerBitmap.getPixel(P.x - 1, P.y) = SearchColor) then StackPush(P.x - 1,P.y);
  71.  
  72.     if ((P.y - 1) >= 0) then
  73.       if (FOwnerBitmap.getPixel(P.x, P.y - 1) = SearchColor) then StackPush(P.x,P.y - 1);
  74.  
  75.     if ((P.y + 1) <= MaxH ) then
  76.       if (FOwnerBitmap.getPixel(P.x, P.y + 1) = SearchColor) then StackPush(P.x,P.y + 1);
  77.  
  78.   end;
  79.   FreeStack;
  80. end;        
  81.  

Thanks for suggestions  8-)
« Last Edit: June 12, 2019, 10:54:51 am by BeanzMaster »