C Сбои программы (Ошибка сегментации) для большого размера входного массива. Как это предотвратить, не используя static/global/malloc?

Question

Следующая программа предназначена для сортировки большого массива случайных чисел с помощью heapsort. Выходные данные программы - общее время выполнения рекурсивной функции heapSort (в микросекундах). Размер входного массива определяется макросом SIZE.

Программа отлично работает на РАЗМЕР до 1 миллиона (1000000). Но когда я пытаюсь выполнить программу с размером 10 миллионов (10000000), программа генерирует ошибку сегментации (дамп памяти).

Примечание. Я уже пытался увеличить мягкие и жесткие ограничения стека с помощью команды ulimit -s в Linux(128 МБ). SEGFAULT все еще сохраняется.

Пожалуйста, предложите мне любые изменения необходимого кода или любого метода, который преодолеет существующую болезнь SEGFAULT, не объявляя массив динамически или как глобальный / статический. /* Программа для реализации алгоритма Heap-Sort */

#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

Итак, как только вы планируете придерживаться подхода, основанного только на стеке, вы должны понимать, кто является основным потребителем вашего стекового пространства.

• Игрок № 1: Массив A[]. В зависимости от ОС / сборки он потребляет ок. 40 или 80 Мбайт стека. Только один раз.
• Игрок № 2: Остерегайтесь рекурсии! В вашем случае это функция heapify(). Каждый вызов использует приличный кусок стека для обслуживания соглашения о вызовах, выравнивания стека, например, стековых фреймов и т. Д. Если вы делаете это миллион раз и в виде древовидной схемы, у вас здесь тоже тратятся десятки мегабайт. Таким образом, вы можете попытаться повторно реализовать эту функцию нерекурсивным способом, чтобы уменьшить давление на размер стека.