none
Why can I not catch a StackOverflowException? RRS feed

  • Question

  • I have written a recursive QuickSort routine in VB.Net as part of a comparison of multiple sorting techniques.  When I give that routine a sorted (or reversed) list with more than 2500 elements, it generates a StackOverflowException, which I can not catch (since .Net 2.0), even though I could change the sort algorithm to a slower iterative process instead during the exception handler, or at least gracefully close the thread I am running this in without taking out my entire application.

    Here is the way I tried solving my StackOverflowException before finding out that I can not actually catch that particular exception.

    	Public Sub QuickSort(Of T As IComparable)(ByRef NumberList() As T)
    		If NumberList IsNot Nothing Then
    			QuickSort(NumberList, 0, NumberList.GetUpperBound(0))
    		End If
    	End Sub
    
    	Private Sub QuickSort(Of T As IComparable)(ByRef NumberList() As T, intStart As Integer, intEnd As Integer)
    		Dim intPivot As Integer
    		Dim intP1, intP2 As Integer
    
    		If intStart < intEnd Then
    			intPivot = intStart
    			intP1 = intStart + 1
    			intP2 = intEnd
    
    			Do While intP1 < intP2
    				Do While intP1 < intP2 AndAlso NumberList(intPivot).CompareTo(NumberList(intP1)) >= 0
    					intP1 += 1
    				Loop
    				Do While intP1 < intP2 AndAlso NumberList(intPivot).CompareTo(NumberList(intP2)) <= 0
    					intP2 -= 1
    				Loop
    				If intP1 < intP2 Then
    					Swap(NumberList(intP1), NumberList(intP2))
    				End If
    			Loop
    			While intP2 > intPivot AndAlso NumberList(intP2).CompareTo(NumberList(intPivot)) > 0
    				intP2 -= 1
    			End While
    			REM Move the pivot value into the correct location.
    			Swap(NumberList(intPivot), NumberList(intP2))
    			Try
    				QuickSort(NumberList, intStart, intP2 - 1)
    			Catch ex As StackOverflowException
    				REM Not enough stack space.  Try non-recursive sort (Linear Insertion) for this section.
    				LinearInsertion(NumberList, intStart, intP2 - 1)
    			End Try
    			Try
    				QuickSort(NumberList, intP2 + 1, intEnd)
    			Catch ex As StackOverflowException
    				REM Not enough stack space.  Try non-recursive sort (Linear Insertion) for this section.
    				LinearInsertion(NumberList, intP2 + 1, intEnd)
    			End Try
    		End If
    	End Sub
    

    I guess I have two questions: 1) Why was StackOverflowException changed in version 2.0 to disallow any kind of recovery?  2) What would be the way to prevent StackOverflowExceptions from occurring in this context?  Is there a way to determine how much room the current stack frame uses and how much room is left on the stack?  That way, when the current stack frame is larger than the space available, I can change strategy, or do something else anyway.

    Sunday, January 31, 2016 3:21 PM

Answers

  • Still, I am curious why we are no longer allowed to catch StackOverflowException?

    Did you specifically trap for that type exception (then let it fall out to a general one)?

    If you did then I don't know why.


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    It is not possible to catch StackOverflowException, think about it: to catch this error it might overflow even more causing infinite errors, right? And to check if it is close to overflowing might be too expensive - I am not expert just my thoughts 

    My goal of posting is to make you and I better educated programmers while solving our problems ✘

    Sunday, January 31, 2016 7:18 PM

All replies

  • You're calling QuickSort from within QuickSort. Isn't that a problem?
    Sunday, January 31, 2016 3:28 PM
  • Don't look to much at given messages when you are using recursive calls . The memory is mostly not enough. 

    Are you sure it is the fault of 2.0 or is it just an coincidence that there is no memory anymore quicker. 


    Success
    Cor

    Sunday, January 31, 2016 4:12 PM
  • David,

    That's always a potential issue with recursion.

    From this MSDN document:

    "Another problem that can occur with recursion is that a recursive function can use all the available resources (such as system memory and stack space). Each time a recursive function calls itself (or calls another function that calls the original function), it uses some resources. These resources are freed when the recursive function exits, but a function that has too many levels of recursion may use all the available resources. When this happens, an exception is thrown."


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    Sunday, January 31, 2016 4:32 PM
  • @DennisBakker71

    Calling a function from within itself is called recursion, which is a standard way of calling the same code over and over again.  Each time you call a procedure from within itself, it creates a new area to store information, called a stack frame, for this pass of the procedure, which is released when procedure is done.  Recursion can cause problems if you do not have a well-defined way to stop calling itself at some point in the execution.

    The typical QuickSort algorithm taught in computer science classes is recursive: Move everything less than a given value, called the pivot, to the beginning of the array and everything after the pivot to the end of the array, move the pivot into the correct location and then call QuickSort on just the part before the pivot and then call QuickSort again on the part after the pivot.  The recursion exits when the number of elements passed to QuickSort is less than 2.

    The problem with using a sorted list with QuickSort is that it essentially generates a new stack frame for each element of the array, which can quickly fill up the available stack space.  This is generally not a problem for a list that is sufficiently random.  This is what happened to me, but I had been hoping to trap the signal that I had run out of stack space.



    Sunday, January 31, 2016 6:15 PM
  • @Cor Ligthert

    When I read the VB.Net documentation deeply enough, I noticed that StackOverflowException could be caught in a Try-Catch block in .Net versions 1.0 and 1.1, but as of .Net 2.0, that particular exception will still be thrown, but can not be caught, which is a little annoying as I would like to have the chance to clean up from this kind of problem, instead of just killing my program.  Maybe abort my corrupted thread, but leave the rest of my application running.


    Sunday, January 31, 2016 6:19 PM
  • ...but I had been hoping to trap the signal that I had run out of stack space.

    And then do what? Rework your code?

    Ok, you've got the signal to rework your code.


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    Sunday, January 31, 2016 6:19 PM
  • Hello,

    Along with the link Frank mentioned I would read the following and key in on the last paragraph.


    Please remember to mark the replies as answers if they help and unmark them if they provide no help, this will help others who are looking for solutions to the same or similar problem. Contact via my Twitter (Karen Payne) or Facebook (Karen Payne) via my MSDN profile but will not answer coding question on either.Stack over flow profile. VB Forums - moderator

    Sunday, January 31, 2016 6:22 PM
    Moderator
  • @Frank L. Smith

    This is more or less what I did.  Inspired by something I read elsewhere, I added a queue to store the starting and ending points and looped, instead of using recursion to keep track of the state information.

    	Private Structure StartStop
    		Public m_intStart, m_intEnd As Integer
    	End Structure
    
    	Public Sub QuickSort(Of T As IComparable)(ByRef NumberList() As T)
    		Dim intPivot As Integer
    		Dim intP1, intP2 As Integer
    		Dim stsCurrent, stsNew As StartStop
    		Dim queStartStop As New Queue(Of StartStop)
    
    		If NumberList IsNot Nothing Then
    			stsNew.m_intStart = 0
    			stsNew.m_intEnd = NumberList.GetUpperBound(0)
    			queStartStop.Enqueue(stsNew)
    
    			While queStartStop.Count > 0
    				stsCurrent = queStartStop.Dequeue()
    				If stsCurrent.m_intStart < stsCurrent.m_intEnd Then
    					intPivot = stsCurrent.m_intStart
    					intP1 = intPivot + 1
    					intP2 = stsCurrent.m_intEnd
    					Do While intP1 < intP2
    						Do While intP1 < intP2 AndAlso NumberList(intPivot).CompareTo(NumberList(intP1)) >= 0
    							intP1 += 1
    						Loop
    						Do While intP1 < intP2 AndAlso NumberList(intPivot).CompareTo(NumberList(intP2)) <= 0
    							intP2 -= 1
    						Loop
    						If intP1 < intP2 Then
    							Swap(NumberList(intP1), NumberList(intP2))
    						End If
    					Loop
    					While intP2 > intPivot AndAlso NumberList(intP2).CompareTo(NumberList(intPivot)) > 0
    						intP2 -= 1
    					End While
    					REM Move the pivot value into the correct location.
    					Swap(NumberList(intPivot), NumberList(intP2))
    					stsNew.m_intStart = stsCurrent.m_intStart
    					stsNew.m_intEnd = intP2 - 1
    					queStartStop.Enqueue(stsNew)
    					stsNew.m_intStart = intP2 + 1
    					stsNew.m_intEnd = stsCurrent.m_intEnd
    					queStartStop.Enqueue(stsNew)
    				End If
    			End While
    		End If
    	End Sub
    
    


    Sunday, January 31, 2016 6:39 PM
  • David,

    Call me Frank please. ;-)

    The point that I was making was that it doesn't matter that you didn't catch the exception programmatically - you now know it exists.

    Rework your code (Cadefia seems to have some thoughts on that), but as for your question, my answer is "It makes no difference - you now know a problem exists".

    Know what I mean?


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    Sunday, January 31, 2016 6:43 PM
  • I am familiar with recursion and its issues from my 20+ years of C and C++ and other programming.  I have been working with .Net languages (VB.Net, C#) for only a couple of years so far.  I realize that recursion can bite you big time if you are not careful, which is what the article Frank mentioned was talking about. (BTW, Factorial is actually a poor example for recursion; refactoring into a For loop is much more efficient and more explosion-proof.  Same with generating the Fibinocci sequence, another common classroom example of recursion; refactoring it into a loop with 3 variables makes for much faster and safer code.) 

    The answer to my second question is to rewrite the procedure to use a loop, using a data structure to store the needed data from pass to pass instead of using the execution stack, which is what I have done.  Still, I am curious why we are no longer allowed to catch StackOverflowException?  If you can catch the exception and deal with it nicely, in an intelligent way instead just crashing the program, I would prefer to do that.  It can really reduce the number of phone calls from angry and confused clients if programs do not unexpectedly crash.

    Sunday, January 31, 2016 7:08 PM
  • Still, I am curious why we are no longer allowed to catch StackOverflowException?

    Did you specifically trap for that type exception (then let it fall out to a general one)?

    If you did then I don't know why.


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    Sunday, January 31, 2016 7:14 PM
  • Still, I am curious why we are no longer allowed to catch StackOverflowException?

    Did you specifically trap for that type exception (then let it fall out to a general one)?

    If you did then I don't know why.


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    It is not possible to catch StackOverflowException, think about it: to catch this error it might overflow even more causing infinite errors, right? And to check if it is close to overflowing might be too expensive - I am not expert just my thoughts 

    My goal of posting is to make you and I better educated programmers while solving our problems ✘

    Sunday, January 31, 2016 7:18 PM
  • It is not possible to catch StackOverflowException, think about it: to catch this error it might overflow even more causing infinite errors, right? And to check if it is close to overflowing might be too expensive - I am not expert just my thoughts

    You might be right but I don't follow the logic there, honestly.

    I guess we'll see by the end of this. ;-)


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    Sunday, January 31, 2016 7:23 PM
  • Cadefia,

    According to this MSDN document, it looks like you're right.


    Knowledge rests not upon truth alone, but upon error also. Carl Jung

    Sunday, January 31, 2016 7:31 PM