C Program crashes(Segmentation Fault) for large size of input array. How to prevent it without using static/global/malloc?

Question

The following program is to sort a large array of random numbers using heapsort. The output of the program is the total execution time of the recursive heapSort function(in microseconds). The size of the input array is defined by the SIZE macro.

The program works fine for SIZE up to 1 million(1000000). But when I try to execute the program with SIZE 10 million(10000000), the program generates segmentation fault(core dumped).

Note: I have already tried increasing the soft and hard limits of the stack using ulimit -s command on Linux(128 MB). The SEGFAULT still persists.

Please suggest me any alterations to the code needed or any method which will overcome the existing SEGFAULT malady without having to declare the array dynamically or as global/static. /* Program to implement Heap-Sort algorithm */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

long SIZE = 10000000; // Or #define SIZE 10000000

long heapSize;

void swap(long *p, long *q)
{
    long temp = *p;
    *p = *q;
    *q = temp;
}

void heapify(long A[], long i)
{
    long left, right, index_of_max;
    left = 2*i + 1;
    right = 2*i + 2;

    if(left<heapSize && A[left]>A[i])
        index_of_max = left;
    else
        index_of_max = i;

    if(right<heapSize && A[right]>A[index_of_max])
        index_of_max = right;

    if(index_of_max != i)
    {
        swap(&A[index_of_max], &A[i]);
        heapify(A, index_of_max);
    }       
}

void buildHeap(long A[])
{
    long i;

    for(i=SIZE/2; i>=0 ; i--)
        heapify(A,i);
}

void heapSort(long A[])
{
    long i;

    buildHeap(A);

    for(i=SIZE-1 ; i>=1 ; i--)
    {
        swap(&A[i], &A[0]);
        heapSize--;
        heapify(A, 0);
    } 
}

int main()
{
    long i, A[SIZE];
    heapSize = SIZE;
    struct timespec start, end;

    srand(time(NULL));
    for(i = 0; i < SIZE; i++)
        A[i] = rand() % SIZE;

    /*printf("Unsorted Array is:-\n");
    for(i = 0; i < SIZE; i++)
        printf("%li\n", A[i]);
    */

    clock_gettime(CLOCK_MONOTONIC_RAW, &start);//start timer
    heapSort(A);
    clock_gettime(CLOCK_MONOTONIC_RAW, &end);//end timer

    //To find time taken by heapsort by calculating difference between start and stop time.
    unsigned long delta_us = (end.tv_sec - start.tv_sec) * 1000000 \
                            + (end.tv_nsec - start.tv_nsec) / 1000;

    /*printf("Sorted Array is:-\n");
    for(i = 0; i < SIZE; i++) 
        printf("%li\n", A[i]);
    */

    printf("Heapsort took %lu microseconds for sorting of %li elements\n",delta_us, SIZE);

    return 0;
}

Answer 1

So, once you plan to stick with stack-only approach, you have to understand who is the main consumer(s) of your stack space.

• Player #1: Array A[] itself. Depending to the OS/build, it consumes approx. 40 or 80 Mb of stack. One-time only.
• Player #2: Beware recursion! In your case, this is heapify() function. Each call consumes decent stack chunk to serve a calling convention, stack alignment like stack-frames etc. If you do that million times and tree-like schema, you have tens of megabytes spent here too. So, you can try to re-implement this function to non-recursive way to decrease stack size pressure.