开发者

Suggestion for chkstk.asm stackoverflow exception in C++ with Visual Studio

I am working with an implementation of merge sort. I am trying with C++ Visual Studio 2010 (msvc). But when I took a array of 300000 integers for timing, it is showing an unhandled stackoverflow exception and taking me to a readonly file named "chkstk.asm". I reduced the size to 200000 and it worked. Again the same code worked with C-free 4 editor (mingw 2.95) without any problem while the size was 400000. Do you have any suggestion to get the code working in Visual Studio?

May be the recursi开发者_StackOverflow社区on in the mergesort is causing the problem.


Problem solved. Thanks to Kotti for supplying the code. I got the problem while comparing with that code. The problem was not about too much recursion. Actually I was working with a normal C++ array which was being stored on stack. Thus the problem ran out of stack space. I just changed it to a dynamically allocated array with the new/delete statements and it worked.


I'm not exactly sure, but this may be a particular problem of your implementation of yor merge sort (that causes stack overflow). There are plenty of good implementations (use google), the following works on VS2008 with array size = 2000000.

(You could try it in VS2010)

#include <cstdlib>
#include <memory.h>

// Mix two sorted tables in one and split the result into these two tables.
void Mix(int* tab1, int *tab2, int count1, int count2)
{
   int i,i1,i2;
   i = i1 = i2 = 0;
   int * temp = (int *)malloc(sizeof(int)*(count1+count2));

   while((i1<count1) && (i2<count2))
   {
      while((i1<count1) && (*(tab1+i1)<=*(tab2+i2)))
      {
         *(temp+i++) = *(tab1+i1);
         i1++;
      }
      if (i1<count1)
      {
         while((i2<count2) && (*(tab2+i2)<=*(tab1+i1)))
         {
            *(temp+i++) = *(tab2+i2);
            i2++;
         }
      }
   }

   memcpy(temp+i,tab1+i1,(count1-i1)*sizeof(int));
   memcpy(tab1,temp,count1*sizeof(int));

   memcpy(temp+i,tab2+i2,(count2-i2)*sizeof(int));
   memcpy(tab2,temp+count1,count2*sizeof(int));
   free(temp);
}

void MergeSort(int *tab,int count) {
   if (count == 1) return;

   MergeSort(tab, count/2);
   MergeSort(tab + count/2, (count + 1) /2);
   Mix(tab, tab + count / 2, count / 2, (count + 1) / 2);
}

void main() {
   const size_t size = 2000000;
   int* array = (int*)malloc(sizeof(int) * size);
   for (int i = 0; i < size; ++i) {
      array[i] = rand() % 5000;
   }

   MergeSort(array, size);
}


My guess is that you've got so much recursion that you're just running out of stack space. You can increase your stack size with the linker's /F command line option. But, if you keep hitting stack size limits you probably want to refactor the recursion out of your algorithm.


_chkstk() refers to "Check Stack". This happens in Windows by default. It can be disabled with /Gs- option or allocating reasonably high size like /Gs1000000. The other way is to disable this function using:

#pragma check_stack(off)  // place at top header to cover all the functions

Official documentation.
Reference.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜