Segmentation fault on large size array with heap allocation

Question

The following code gives me a segmentation fault when run on a 4Gb machine even after i dynamically allocate the space to the array holding 10 million entries. It works fine with 1 million entries i.e. n = 1000000. The following code sorts integer values along with their index value using radix sort. What should i do to make this program work for 10 million entries.?

int main()
{
    int n=10000000; // 10 million entries
    int *arr=new int [n]; // declare heap memory for array 
    int *arri=new int [n]; // declare heap memory for array index

    for(int i=0;i<n;i++)  // initialize array with random number from 0-100
        {
            arr[i]=((rand()%100)+0);
        }

    for(i=0;i<n;i++)   // initialize index position for array
        {
            arri[i]=i;
        }

    radixsort(arr, n ,arri);
    return 0;
}

// The main function to that sorts arr[] of size n using Radix Sort
void radixsort(int *arr, int n,int *arri)
{   int m=99; //getMax(arr,n,arri);

    // Find the maximum number to know number of digits


    // Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i
    // where i is current digit number
    for (int exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp,arri);


}

void countSort(int *arr, int n, int exp,int *arri)
{
    int output[n],output1[n]; // output array
    int i, count[10] = {0};

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        {
            count[ (arr[i]/exp)%10 ]++;

        }

    // Change count[i] so that count[i] now contains actual
    //  position of this digit in output[]
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (i = n - 1; i >= 0; i--)
        {

            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
            output1[count[ (arr[i]/exp)%10 ] - 1] = arri[i];
            count[ (arr[i]/exp)%10 ]--;
        }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (i = 0; i < n; i++)
        {
            arr[i] = output[i];
            arri[i]=output1[i];
        }

}

Note that variable-length arrays are not standard C++. They're in C, and your compiler is allowing them as an extension. — Barmar
– Barmar, Commented Aug 18, 2016 at 3:37

Barmar · Accepted Answer · 2016-08-18 03:40:47Z

2

The problem is in countSort. The output and output1 arrays are local arrays, not dynamically allocated, and they're too big for local variables. You're also using the C feature of variable-length arrays, which aren't part of standard C++. Change them to:

int *output = new int[n];
int *output1 = new int[n];

and add

delete[] output;
delete[] output1;

at the end of the function.

answered Aug 18, 2016 at 3:40

Barmar

789k57 gold badges554 silver badges669 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Remy Lebeau Over a year ago

Better to use std::vector instead. Let it manage the memory for you.

dxiv Over a year ago

Or maybe, depending on platform and toolchain, set the appropriate linker flags to reserve enough stack room to accommodate the local arrays.

Barmar Over a year ago

@RemyLebeau I didn't want to redesign the program, just show the simple fix to his error. He thought he wasn't using local arrays, he missed this place.

Collectives™ on Stack Overflow

Segmentation fault on large size array with heap allocation

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related