Stack overflow, expand your stack? Change your algorithm!
In the last post, Area fill algorithm: crayons and coloring book, I showed a program that emulates a kid drawing in a coloring book.
However, the algorithm wasn’t very efficient, and would explode even if you had a simple drawing: it was using the stack to store where to go.
The heart of the routine:
void AreaFill(Point ptcell)
{
if (ptcell.X >= 0 && ptcell.X < m_numCells.Width)
{
if (ptcell.Y >= 0 && ptcell.Y < m_numCells.Height)
{
// System.Threading.Thread.Sleep(100);
if (DrawACell(ptcell, m_brushFill))
{
m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));
m_brushFill = new SolidBrush(m_oColor);
AreaFill(new Point(ptcell.X - 1, ptcell.Y));
AreaFill(new Point(ptcell.X + 1, ptcell.Y));
AreaFill(new Point(ptcell.X, ptcell.Y + 1));
AreaFill(new Point(ptcell.X, ptcell.Y - 1));
}
}
}
}
It just checks boundaries, Draws the current point, then calls itself to draw the points North, South, East and West. Doing this for thousands of pixels eats up the current thread’s stack very fast.
One way to fix this is to expand the stack size.
You can examine the default stack size of an executable (EXE or DLL) by opening a Visual Studio command prompt (Start->Programs->VS2008->VSToos->VSCommand prompt), then type
link /dump /headers d:\dev\cs\Fill\bin\Debug\Fill.exe
Microsoft (R) COFF/PE Dumper Version 9.00.21022.08
Copyright (C) Microsoft Corporation. All rights reserved.
Dump of file Fill.exe
PE signature found
File Type: EXECUTABLE IMAGE
FILE HEADER VALUES
14C machine (x86)
3 number of sections
4A1ECBC2 time date stamp Thu May 28 10:37:06 2009
0 file pointer to symbol table
0 number of symbols
E0 size of optional header
10E characteristics
Executable
Line numbers stripped
Symbols stripped
32 bit word machine
OPTIONAL HEADER VALUES
10B magic # (PE32)
8.00 linker version
2000 size of code
800 size of initialized data
0 size of uninitialized data
3E7E entry point (00403E7E)
2000 base of code
4000 base of data
400000 image base (00400000 to 00407FFF)
2000 section alignment
200 file alignment
4.00 operating system version
0.00 image version
4.00 subsystem version
0 Win32 version
8000 size of image
200 size of headers
0 checksum
2 subsystem (Windows GUI)
540 DLL characteristics
Dynamic base
NX compatible
No structured exception handler
100000 size of stack reserve
1000 size of stack commit
100000 size of heap reserve
1000 size of heap commit
This is a little misleading, because the default stack size is 100000 Hex, which is 1,048,576, or about 1 Megabyte.
You can change the stack size using Editbin.exe
D:\dev\cs\Fill\bin\Debug>link /dump /headers Fill.exe | find "stack"
100000 size of stack reserve
1000 size of stack commit
D:\dev\cs\Fill\bin\Debug>editbin /stack:10000,1000 Fill.exe
Microsoft (R) COFF/PE Editor Version 9.00.21022.08
Copyright (C) Microsoft Corporation. All rights reserved.
D:\dev\cs\Fill\bin\Debug>link /dump /headers Fill.exe | find "stack"
2710 size of stack reserve
3E8 size of stack commit
A better way to fix this is to use heap memory , rather than the stack:
//* More efficient algorithm: don't use the stack to store state
void AreaFill(Point ptcell)
{
Queue<Point> queueCells = new Queue<Point>();
queueCells.Enqueue(ptcell);
while (queueCells.Count > 0)
{
ptcell = queueCells.Dequeue();
if (ptcell.X >= 0 && ptcell.X < m_numCells.Width)
{
if (ptcell.Y >= 0 && ptcell.Y < m_numCells.Height)
{
// System.Threading.Thread.Sleep(100);
if (DrawACell(ptcell, m_brushFill))
{
m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));
m_brushFill = new SolidBrush(m_oColor);
queueCells.Enqueue(new Point(ptcell.X - 1, ptcell.Y));
queueCells.Enqueue(new Point(ptcell.X + 1, ptcell.Y));
queueCells.Enqueue(new Point(ptcell.X, ptcell.Y + 1));
queueCells.Enqueue(new Point(ptcell.X, ptcell.Y - 1));
}
}
}
}
}
This solution is almost the same as the first: however, instead of recurring to go North, etc, the routine just puts the points to work on into a queue.
The VB solution is analogous:
Sub AreaFill(ByVal ptcell As Point)
Dim queueCells = New Queue(Of Point)
queueCells.Enqueue(ptcell)
While queueCells.Count > 0
ptcell = queueCells.Dequeue()
If (ptcell.X >= 0 And ptcell.X < m_numCells.Width) Then
If (ptcell.Y >= 0 And ptcell.Y < m_numCells.Height) Then
' System.Threading.Thread.Sleep(100);
If (DrawACell(ptcell, m_brushFill)) Then
Me.m_oColor = Color.FromArgb((((Me.m_oColor.ToArgb And &HFFFFFF) + 140) And &HFFFFFF) Or &HFF000000)
' m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));
m_brushFill = New SolidBrush(m_oColor)
queueCells.Enqueue(New Point(ptcell.X - 1, ptcell.Y))
queueCells.Enqueue(New Point(ptcell.X + 1, ptcell.Y))
queueCells.Enqueue(New Point(ptcell.X, ptcell.Y + 1))
queueCells.Enqueue(New Point(ptcell.X, ptcell.Y - 1))
End If
End If
End If
End While
End Sub
See also:
Comment/Uncomment code to switch versions quickly without using macros