i know what causes the segfault, but why?

Question

Ok, so I have a simple c++ program that's supposed to run a couple sorting algorithms on an array composed of ints and track the time each one takes.. pretty basic, however I've run into a problem.

When the program first starts, it asks how many items you would like in the array. My assignment involves setting the array at specific lengths from 100 items all the way to 750000. It'll handle many values, including up to around 600000. When I try 750000 however it immediately segfaults. A couple couts here and there led me to discover that the error happens when the fourth array (all of the same length) is initialized. The weird thing is that it only happens on my OS; at my school it works no problem. (i'm on the latest ubuntu while my school uses redhat. not sure if that's useful)

I'll include the complete code just for reference but the segfault occurs at line 27:

int array1[num], array2[num], array3[num], array4[num]; // initialize arrays 

I know this because I initialized each array on separate lines and put couts in between. array1, 2, and 3 were initialized, then it segfaults. Again this ONLY happens when the arrays are longer than about 600000 or so. Anything less works fine.

Full code:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void insertionSort(int array[], int size);
void bubbleSort(int array[], int size);
void mergeSort(int array[], int first, int last, int size);
void quickSort(int array[], int size);

int main()
{

    cout << endl << endl << "\t\t**** Extra Credit Assignment- Sorting ****" << endl << endl << endl;
    cout << "Enter the number of items to sort: ";
    int num; 
    cin >> num;
    while(cin.fail()) // while cin does not recieve an integer 
    {
        cin.clear();
        cin.ignore(1000, '\n');
        cout << "Invalid entry. Try again: "; // try again
        cin >> num;
    }

    int array1[num], array2[num], array3[num], array4[num]; // initialize arrays 

    int randNum, sizeOfArray = sizeof(array1)/sizeof(array1[0]); // random number, size of the arrays 
    srand(time(NULL)); // random seed (used with rand()) 

    for(int i = 0; i < sizeOfArray; i++) // traverse through the array
    {
        randNum = rand() % 2147483647+1; // establish random number (from 1 to 2147483647)
        array1[i] = array2[i] = array3[i] = array3[i] = randNum; // set randNum to all arrays at current index
    }

    time_t beginTime, endTime; 
    double elapsedTime;

    cout << endl << "Elapsed time:" << endl << "\tInsertion Sort-\t";

    time(&beginTime);
    insertionSort(array1, sizeOfArray);
    time(&endTime);

    elapsedTime = difftime(endTime, beginTime);
    cout << elapsedTime << " seconds" << endl << "\tBubble Sort-\t";

    time(&beginTime);
    bubbleSort(array2, sizeOfArray);
    time(&endTime);

    elapsedTime = difftime(endTime, beginTime);
    cout << elapsedTime << " seconds" << endl << "\tMerge Sort-\t";

    time(&beginTime);
    mergeSort(array3, 0, sizeOfArray-1, sizeOfArray);
    time(&endTime);

    elapsedTime = difftime(endTime, beginTime);
    cout << elapsedTime << " seconds"<< endl; 





/* ********************* TESTING *************************
// *******************************************************

    cout << "Insertion->Unsorted:\t";
    for(int i = 0; i < sizeOfArray; i++)
    {
        cout <<  array1[i] << " ";
    }
    cout << endl;

    insertionSort(array1, sizeOfArray);

    cout << "Insertion->Sorted:\t";
    for(int i = 0; i < sizeOfArray; i++)
    {
        cout <<  array1[i] << " ";
    }
    cout << endl;




    cout << "Bubble->Unsorted:\t";
    for(int i = 0; i < sizeOfArray; i++)
    {
        cout <<  array2[i] << " ";
    }
    cout << endl;

    bubbleSort(array2, sizeOfArray);

    cout << "Bubble->Sorted:\t\t";
    for(int i = 0; i < sizeOfArray; i++)
    {
        cout <<  array2[i] << " ";
    }
    cout << endl;




    cout << "Merge->Unsorted:\t";
    for(int i = 0; i < sizeOfArray; i++)
    {
        cout <<  array3[i] << " ";
    }
    cout << endl;

    mergeSort(array3, 0, sizeOfArray-1, sizeOfArray);

    cout << "Merge->Sorted:\t\t";
    for(int i = 0; i < sizeOfArray; i++)
    {
        cout <<  array3[i] << " ";
    }
    cout << endl; */

    return 0;
}

void insertionSort(int array[], int size)
{
    for(int i = 1; i < size; i++)
    {
        int item = array[i], index = i;
        while(index > 0 && array[index-1] > item)
        {
            array[index] = array[index-1];
            index--;
        }
        array[index] = item;
    }
}

void bubbleSort(int array[], int size)
{
    bool sorted = false;
    for(int i = 1; i < size && !sorted; i++)
    {
        sorted = true;
        for(int i2 = 0; i2 < size-i; i2++)
        {
            int nextI = i2+1;
            if(array[i2] > array[nextI])
            {
                swap(array[i2], array[nextI]);
                sorted = false;
            }
        }
    }
}

void merge(int array[], int first, int mid, int last, int size)
{
    int tempArray[size];
    int first1 = first, first2 = mid+1;
    int last1 = mid, last2 = last;
    int index = first1;

    while(first1 <= last1 && first2 <= last2)
    {
        if(array[first1] < array[first2])
        {
            tempArray[index] = array[first1];
            first1++;
        }
        else
        {
            tempArray[index] = array[first2];
            first2++;
        }
        index++;
    }
    while(first1 <= last1)
    {
        tempArray[index] = array[first1];
        first1++;
        index++;
    }
    while(first2 <= last2)
    {
        tempArray[index] = array[first2];
        first2++;
        index++;
    }

    for(index = first; index <= last; index++)
    {
        array[index] = tempArray[index];
    }
}

void mergeSort(int array[], int first, int last, int size)
{
    if(first < last)
    {
        int mid = (first+last)/2;
        mergeSort(array, first, mid, size);
        mergeSort(array, mid+1, last, size);
        merge(array, first, mid, last, size);
    }
}

Any help is greatly appreciated. It might be a memory limitation on my system? I really don't know lol just a thought.

Answer 1

You can't allocate such big arrays on the stack which has a fixed limited size, try:

int* array1 = new int[num];

Answer 2

You've allocated very large arrays on the stack and you're overflowing the stack. If you new them or make them static, they'll be allocated on the heap and you won't fail.

Answer 3

As others have noted, the SEGV you're getting is due to overflowing the stack. The reason it happens on your ubuntu machine and not your school's redhat machine is likely due to differences in the default stack size.

You may be able to change your default stack size with ulimit -s which, with no additional arguments, will print your current stack size in kilobytes. For example, on my machine, that prints 8192 or 8 megabytes. I can raise it to 16MB with ulimit -s 16384

An array of 750000 ints will require about 3MB of stack space (4 bytes per int), so 4 such arrays (like you have) will require 12MB...

Answer 4

It's because the stack is not an infinite resource. When you do int x[big_honkin_number], it tries to allocate enough space on the stack for that array.

You can usually compile/link your code to give you more stack but a better solution is to use dynamic memory allocation (i.e., new).