C 程序因大尺寸输入数组而崩溃（分段错误）。不使用static/global/malloc如何预防呢？

Question

下面的程序是使用heapsort对大量随机数进行排序。程序的输出是递归heapSort函数的总执行时间（以微秒为单位）。输入数组的大小由 SIZE 宏定义。

该程序适用于 SIZE 高达 100 万 (1000000)。但是当我尝试使用 SIZE 1000 万（10000000）执行程序时，程序会生成分段错误（核心已转储）。

注意：我已经尝试在 Linux(128 MB) 上使用 ulimit -s 命令增加堆栈的软硬限制。 SEGFAULT 仍然存在。

请建议我对所需代码的任何更改或任何无需动态声明数组或 global/static 即可克服现有 SEGFAULT 问题的方法。 /* 实现堆排序算法的程序 */

#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

因此，一旦您打算坚持使用 stack-only 方法，您就必须了解谁是堆栈的主要消费者 space。

玩家#1：数组A[]本身。根据 OS/build，它消耗大约。 40 或 80 Mb 的堆栈。仅 One-time。
玩家 #2：当心递归！在您的例子中，这是 heapify() 函数。每次调用都会消耗体面的堆栈块来满足调用约定、堆栈对齐（如 stack-frames 等）。如果你这样做一百万次和 tree-like 模式，你也会在这里花费数十兆字节。所以，你可以尝试re-implement这个函数以non-recursive的方式来降低堆栈大小的压力。

C 程序因大尺寸输入数组而崩溃（分段错误）。不使用static/global/malloc如何预防呢？

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

c

segmentation-fault

heapsort

ulimit

timespec