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

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

Программа отлично работает для SIZE до 1 миллиона (1000000). Но когда я пытаюсь выполнить программу с размером SIZE 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;
}

person Akash Das    schedule 01.03.2018    source источник
comment
Выделите массив динамически, используя malloc() или что-то подобное.   -  person Jonathan Leffler    schedule 01.03.2018
comment
Я хочу сделать это без использования malloc или глобального объявления или объявления массива как статического. Я увеличил размер стека до 128 МБ. Но это все равно не помогает. Можете ли вы предложить мне какой-нибудь другой способ?   -  person Akash Das    schedule 01.03.2018
comment
Кратко, нет. Как вы установили больший размер стека? Вы уверены, что это действительно подействовало? Я предполагаю, что это не так, потому что код дает сбой. Может быть и другая причина, но я, вероятно, не стал бы тратить столько времени, сколько мне нужно, чтобы напечатать этот комментарий, думая об этом. Я бы продолжил с динамическим размещением.   -  person Jonathan Leffler    schedule 01.03.2018
comment
Большое спасибо. Я также продолжил динамическую реализацию.   -  person Akash Das    schedule 01.03.2018
comment
Еще одним преимуществом динамического размещения является то, что вы можете указать размер сортировки в качестве аргумента командной строки и запускать все различные размеры без необходимости перекомпилировать программу между запусками. И его едва ли сложнее написать, чем код с фиксированным размером во время компиляции.   -  person Jonathan Leffler    schedule 01.03.2018
comment
@JonathanLeffler Верно!   -  person Akash Das    schedule 02.03.2018


Ответы (1)


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

  • Игрок №1: сам массив A[]. В зависимости от ОС/сборки потребляет ок. 40 или 80 Мб стека. Только один раз.
  • Игрок №2: Остерегайтесь рекурсии! В вашем случае это функция heapify(). Каждый вызов потребляет приличный фрагмент стека для обслуживания соглашения о вызовах, выравнивания стека, такого как кадры стека и т. д. Если вы делаете это миллион раз и используете древовидную схему, вы также тратите десятки мегабайт здесь. Таким образом, вы можете попытаться повторно реализовать эту функцию нерекурсивным способом, чтобы уменьшить давление на размер стека.
person Yury Schkatula    schedule 01.03.2018
comment
Спасибо за понимание. Я сомневался, хватит ли 128 МБ для реализации рекурсивной пирамидальной сортировки для массива размером 10 миллионов. Я считаю, что единственный оставшийся способ реализовать его без использования глобальных/статических/динамических массивов - использовать внешнюю пирамидальную сортировку. - person Akash Das; 02.03.2018