Segmentation Fault with big input

Question

So I wrote this program in C++ to solve COJ(Caribbean Online Judge) problem 1456. http://coj.uci.cu/24h/problem.xhtml?abb=1456. It works just fine with the sample input and with some other files I wrote to test it but I kept getting 'Wrong Answer' as a veredict, so I decided to try with a larger input file and I got Segmentation Fault:11. The file was 1000001 numbers long without the first integer which is the number of inputs that will be tested. I know that error is caused by something related to memory but I am really lacking more information. Hope anyone can help, it is driving me nuts. I program mainly in Java so I really have no idea how to solve this. :(

#include <stdio.h>

int main(){

long singleton;
long N;

scanf("%ld",&N);
long arr [N];
bool sing [N];

for(int i = 0; i<N; i++){
    scanf("%ld",&arr[i]);
}

for(int j = 0; j<N; j++){   

    if(sing[j]==false){     

        for(int i = j+1; i<N; i++){

            if(arr[j]==arr[i]){
                sing[j]=true;
                sing[i]=true;
                break;
            }


        }
    }

    if(sing[j]==false){
        singleton = arr[j];
        break;
    }
}

printf("%ld\n", singleton);
}

In C you can't do `long arr[N];` when N is a variable... and even in C++ allocating that many elements will cause a seg fault. You need to allocate memory in some other way - say with `malloc`. — Floris, Apr 01 '14 at 23:01
Actually, it depends on your compile options. But this is a bit extreme. — Deduplicator, Apr 01 '14 at 23:04
Sorry for the wrong tag, it is written in C++. @Floris , so if I want to create an array depending on the input what do I do? Or would it be easier to make the array the maximum size? Isn't that a waste of space? If I cant do `long arr[N]` in C++ how does java manages no to fall in a StackOverflow? Sorry for the basic questions. — Darwin57721, Apr 01 '14 at 23:08
Java uses different memory allocation. In C, the way you declare your array puts the memory on the stack - which is typically finite in size. See my answer for the way to allocate "as large an array as you want" (within memory limits - but at least bigger than the stack allows). — Floris, Apr 01 '14 at 23:12
@Deduplicator - see http://stackoverflow.com/a/8594242/1967396 . Apparently the gcc compiler allows some chicanery like that... — Floris, Apr 01 '14 at 23:15
Yes, I know that the gcc compiler allows some C constructs in C++ and the other way around in non-compliant mode. Does not make it C (or C++). — Deduplicator, Apr 01 '14 at 23:17

Floris · Accepted Answer · 2014-04-01T23:13:31.963

2

If you are writing in C, you should change the first few lines like this:

#include <stdio.h>
#include <stdlib.h>

int main(void){

  long singleton;
  long N;

  printf("enter the number of values:\n");
  scanf("%ld",&N);

  long *arr;
  arr = malloc(N * sizeof *arr);
  if(arr == NULL) {
    // malloc failed: handle error gracefully
    // and exit
  }

This will at least allocate the right amount of memory for your array.

update note that you can access these elements with the usual

arr[ii] = 0;

Just as if you had declared the array as

long arr[N];

(which doesn't work for you).

edited Apr 01 '14 at 23:13

answered Apr 01 '14 at 23:06

Floris

45,857
6
70
122

Ok, so let me see if I get it right. When I run my program it allocates some memory for it to use but since it is a VLA it doesn't know how much and it eventually falls in a StackOverflow if the input is too large and that is why I need to allocate some memory by myself? – Darwin57721 Apr 01 '14 at 23:25
More or less. Obviously your compiler allows VLA (not standard C/C++), but it attempts to allocate from the stack. If you try to make your array to big, it fails immediately (you try to access memory you don't "own"). – Floris Apr 01 '14 at 23:29
1

C still allows VLA, Floris. But it only has bool with stdbool.h included. – Deduplicator Apr 01 '14 at 23:31
1

@Deduplicator - you are right... I am still an old K&R/ANSI C guy who never learnt the differences introduced with C99, let alone C11. `They didn't have a need for that nonsense in MY days` – Floris Apr 01 '14 at 23:40
@MattMcNabb no - but we _did_ have to worry about "near pointers" and "far pointers", and even "huge pointers" as we struggled to deal with the 640k memory limit imposed by the original Intel/DOS architecture. You couldn't just grab a block of memory and be done! – Floris Apr 02 '14 at 02:56
1

I programmed on a system once that had 16-bit "code" pointers and 16-bit "data" pointers (these were two different pages), and `void *` was 3 bytes; with one bit of the third byte indicating whether it was pointing to code page or data page – M.M Apr 02 '14 at 02:58

Deduplicator · Answer 2 · 2014-04-01T23:35:38.197

0

To make it proper C++, you have to convince the standard committee to add Variable length arrays to the language. To make it valid C, you have to include <stdbool.h>.

Probably your VLA nukes your stack, consuming a whopping 4*1000001 byte. (The bool only adds a quarter to that) Unless you use the proper compiler options, that is probably too much.

Anyway, you should use dynamic memory for that.

Also, using sing without initialisation is ill-advised.

BTW: The easiest C answer for your programming challenge is: Read the numbers into an array (allocated with malloc), sort (qsort works), output the first non-duplicate.

edited Apr 01 '14 at 23:35

answered Apr 01 '14 at 23:08

Deduplicator

44,692
7
66
118

Sorry, I don't know what the standard committee is and how do I convince it? So I'm actually trying to use more memory than what it is allocated in the first place for my program? Thats why I need to use malloc()? Oh, how do I initialise it for all the array to be false, is it something like `sing[N]={false}` ? how can I do that if the program doesn't know the actual size of the array wouldn't that cause problems? – Darwin57721 Apr 01 '14 at 23:22
Your platform gives you a standard stack for stack variables and function calls. Unless you say your compiler to make a note for the platform, this space is too small for your demands, yes. That error is fatal. – Deduplicator Apr 01 '14 at 23:25

score 0 · Answer 3 · answered Apr 01 '14 at 23:59

When you write long arr[N]; there is no way that your program can gracefully handle the situation where there is not enough memory to store this array. At best, you might get a segfault.

However, with long *arr = malloc( N * sizeof *arr );, if there is not enough memory then you will find arr == NULL, and then your program can take some other action instead, for example exiting gracefully, or trying again with a smaller number.

Another difference between these two versions is where the memory is allocated from.

In C (and in C++) there are two memory pools where variables can be allocated: automatic memory, and the free store. In programming jargon these are sometimes called "the stack" and "the heap" respectively. long arr[N] uses the automatic area, and malloc uses the free store.

Your compiler and/or operating system combination decide how much memory is available to your program in each pool. Typically, the free store will have access to a "large" amount of memory, the maximum possible that a process can have on your operating system. However, the automatic storage area may be limited in size , as well as having the drawback that if allocation fails then you have to have your process killed or have your process go haywire.

Some systems use one large area and have the automatic area grow from the bottom, and free store allocations grow from the top, until they meet. On those systems you probably wouldn't run out of memory for your long arr[N], although the same drawback remains about not being able to handle when it runs out.

So you should prefer using the free store for anything that might be "large".

Segmentation Fault with big input

3 Answers3