1

I'm working on an algorithm that sorts inputted integers in ascending order.

The input should be of sort

5
32
45
32
55
67

and the output of sort

32
32
45
55
67

where the first integer input is the number of integers that will be inputted.

n.b. the integer inputted n is 1 <= n <= 10,000,000.

Here is my code:

#include <stdio.h>

int main() {
    int N;
    scanf("%d", &N); // receives the number of integers that will be inputted
    int countArray[10000000] = {0}; // creates an array that will store the number of times a number is inputted. the inputted number is the corresponding address e.g. countArray[number-1] stores the amount of times the number 'number' is inputted.

    int inputArray[N]; // creates an array of the numbers inputted
    for (int i=0; i<N; i++) {
        scanf("%d", &inputArray[i]); // receives the numbers inputted and stores them in the inputArray
    }
    for (int i=0;i<N;i++) {
        countArray[inputArray[i]-1]++; // counts the number of times a number occurs in inputArray and increments the corresponding value in the countArray.
    }
    int i=0;
    while (i<10000000) {
        if (countArray[i] > 0) {
            for (int j=0;j<countArray[i];j++) { // prints out the numbers only if count is greater than 0.
                printf("%d\n", i+1);
            }
        }
        i++;
    }
    return 0;
}

I know my code isn't the most efficient way to sort the inputs; I'm just curious as to why I get a "Thread 1: EXC_BAD_ACCESS" error when the size of the array is 10,000,000 but not when it is 1,000,000. It works just fine if the array is of size 1,000,000 but not when it is 10,000,000.

uprspr
  • 25
  • 3
  • 1
    What kind of system are you running on? How large does the system allow the stack to grow? – EOF Sep 21 '20 at 15:20
  • 1
    You would need 40 megabytes (assuming 32-bit integers) of stack space for that array. – tevemadar Sep 21 '20 at 15:22
  • https://stackoverflow.com/questions/571945/getting-a-stack-overflow-exception-when-declaring-a-large-array – Retired Ninja Sep 21 '20 at 15:31
  • 1
    Dear OP, I recommend using dynamic allocation to heap with `malloc()` when working with such large chunks of memory, since as @tevemadar rightly pointed out, 40 `MiB` does not sounds more apt for `malloc()` :) My guess is possible *stack overflow* ... – A P Jo Sep 21 '20 at 15:38
  • Does anyone else see a problem with `int inputArray[N]` since `N` is a run-time variable and arrays are static ? I get `8:19: warning: variable length array used [-Wvla]` .... – user13863346 Sep 21 '20 at 16:28
  • I'm running the code on a Mac in Xcode. I'm not sure about how large the stack is allowed to be... – uprspr Sep 22 '20 at 13:40
  • https://stackoverflow.com/questions/2092495/increase-stack-size-with-xcode ? – tevemadar Sep 23 '20 at 07:10

1 Answers1

1

Your sample code does compile at least, but does not run. It seg-faults on start .

With GCC + Linux, and I get Segmentation fault (core dumped) and it exits with code 139 , while on my Mac with Clang, I get Segmentation fault: 11 with the same exit code. I suspect your EXEC_BAD_ACCESS is some version with the same basic issue underlying it.

As pointed out by @tevemadar , you are asking for ~ 40 MiB of data in your stack, which, very evidently, you are not going to get.

So, instead of this :

int countArray[10000000];

do this :

int *countArray = malloc(10000000*sizeof(int));

OR

static int countArray[10000000];

Which should work (don't forget to check for NULL ! ) , since malloc() will return a pointer to memory it allocated in the heap, and global variables are also put in the heap, where the size limits are not as restrictive as the stack, and for most practical purposes not important to keep in mind.

Now, onto some rambling of mine -

You are essentially going very much beyond the allowed stack size. I do not claim to be an expert, but by now this much is surely self-evident to you too.

Your attempt is somewhat of an abuse of the stack and perhaps arises from not being told the idea behind the stack's purpose - something most C textbooks and courses are guilty of :(

I am not an expert, and will not ruin the beauty of the concept for you, but to summarise -

The stack is for storing smaller, local variables of functions, like counters, strings to print, return values, etc. It's where everything, generally speaking, will go unless you malloc() , fopen() or static it. Its okay for small, handy variables which would be silly to malloc().

The heap is a huge region of memory , intended for bulk usage as in linked lists, long arrays, trees, big structs and what not. It's where you should store seriously-sized variables which store large amount of data.

So, TL;DR , use the heap for large datatypes, use the stack of small variables that would be silly to malloc().

A P Jo
  • 446
  • 1
  • 4
  • 15