Maximum size array program in C?

Question

with the following code, I am trying to make an array of numbers and then sorting them. But if I set a high arraysize (MAX), the program stops at the last 'randomly' generated number and does not continue to the sorting at all. Could anyone please give me a hand with this?

#include <stdio.h>

#define MAX 2000000

int a[MAX];
int rand_seed=10;

/* from K&R
   - returns random number between 0 and 62000.*/
int rand();
int bubble_sort();

int main()
{
    int i;

    /* fill array */
    for (i=0; i < MAX; i++)
    {
        a[i]=rand();
        printf(">%d= %d\n", i, a[i]);
    }

    bubble_sort();

/* print sorted array */
printf("--------------------\n");
for (i=0; i < MAX; i++)
printf("%d\n",a[i]);

    return 0;
}

int rand()
{
    rand_seed = rand_seed * 1103515245 +12345;
    return (unsigned int)(rand_seed / 65536) % 62000;
}

int bubble_sort(void)
{
    int t, x, y;
    /* bubble sort the array */
    for (x=0; x < MAX-1; x++)
        for (y=0; y < MAX-x-1; y++)
            if (a[y] > a[y+1])
            {
                t=a[y];
                a[y]=a[y+1];
                a[y+1]=t;
            }
     return 0;
}

Since your array is declared in file scope, this is most probably not your problem. What is probably not a good idea is to use a cooked version of rand() instead of just the library function. Also the syntax of forward declarations is more specific in modern C. Use (void) for functions that don't receive parameters. — Jens Gustedt
– Jens Gustedt, Commented Nov 25, 2013 at 11:10

Deepthought · Accepted Answer · 2013-11-25 11:05:22Z

4

The problem is that you are storing the array in global section, C doesn't give any guarantee about the maximum size of global section it can support, this is a function of OS, arch compiler.
So instead of creating a global array, create a global C pointer, allocated a large chunk using malloc. Now memory is saved in the heap which is much bigger and can grow at runtime.

answered Nov 25, 2013 at 11:05

Deepthought

2,9512 gold badges32 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

dhein Over a year ago

C doesn't say what has to be stored on stack and what on heap. But overall your answer is a good one.

Deepthought Over a year ago

@Artur U are right... I ran that code on a modest machine about an hour back and it's still running :D .... and yes the array is not a part of the executable file and my executable is just 8.5k...

Artur Over a year ago

@Deepthought: removed my comment and made an answer out of it.

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

Your array will land in BSS section for static vars. It will not be part of an image but program loader will allocate required space and fill it with zeros before your program starts 'real' execution. You can even control this process if using embedded compiler and fill your static data with anything you like. This array may occupy 2GB or your RAM and yet your exe file may be few kilobytes. I've just managed to use over 2GB array this way and my exe was 34KB. I can believe a compiler may warn you when you approach maybe 2³¹-1 elements (if your int is 32bit) but static arrays with 2m elements are not a problem nowadays (unless it is embedded system but I bet it is not).

The problem might be that your bubble sort has 2 nested loops (as all bubble sorts) so trying to sort this array - having 2m elements - causes the program to loop 2*10¹² times (arithmetic sequence):

inner loop:

1: 1999999 times

2: 1999998 times

...

2000000: 1 time

So you must swap elements

2000000 * (1999999+1) / 2 = (4 / 2) * 1000000² = 2*10¹² times

(correct me if I am wrong above)

Your program simply remains too long in sort routine and you are not even aware of that. What you see it just last rand number printed and program not responding. Even on my really fast PC with 200K array it took around 1minute to sort it this way.

It is not related to your os, compiler, heaps etc. Your program is just stuck as your loop executes 2*10¹² times if you have 2m elements.

To verify my words print "sort started" before sorting and "sort finished" after that. I bet the last thing you'll see is "sort started". In addition you may print current x value before your inner loop in bubble_sort - you'll see that it is working.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Nov 25, 2013 at 11:49

Artur

7,3572 gold badges28 silver badges40 bronze badges

2 Comments

gernud7 Over a year ago

Thank you for the answer. But still, I've added: printf("bubble start"); just before bubble_sort(), but the notification never apears on the terminal.

Artur Over a year ago

@user3031004: Cannot believe it - what CPU, RAM, OS, compiler do you have? Instead of invoking rand - try to just initialize your array with any value. Will it start sorting?

Community · Accepted Answer · 2020-06-20 09:12:55Z

0

Dynamic Array

int *Array;
Array= malloc (sizeof(int) * Size);

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Nov 25, 2013 at 11:07

Kevin Dong

5,45910 gold badges34 silver badges66 bronze badges

8 Comments

dhein Over a year ago

malloc doesn't "Put array on heap" malloc just returns a pointer to requested data area, but its compiler decision where to store.

unwind Over a year ago

@Zaibis I don't think that is a very accurate objection. The manual page states "Normally, malloc() allocates memory from the heap, and adjusts the size of the heap as required, using sbrk(2)", for instance. The compiler can't do anything in particular as long as malloc() is being called as it should; it's just a (library) function.

Kevin Dong Over a year ago

@Zaibis So, this is incorrect?

dhein Over a year ago

@unwind Isn't that what I said? Well I'm refering to C standard, where is not stated where the memory has to be stored. so the system could feel free in the way when to store where data. Or am I wrong about that?

dhein Over a year ago

@KVD well, the solution of using malloc() is correct, but our description is in my view incorrect.

|

user2486495 · Accepted Answer · 2013-11-26 05:03:31Z

The original C standard (ANSI 1989/ISO 1990) required that a compiler successfully translate at least one program containing at least one example of a set of environmental limits. One of those limits was being able to create an object of at least 32,767 bytes.

This minimum limit was raised in the 1999 update to the C standard to be at least 65,535 bytes.

No C implementation is required to provide for objects greater than that size, which means that they don't need to allow for an array of ints greater than

(int)(65535 / sizeof(int)).

In very practical terms, on modern computers, it is not possible to say in advance how large an array can be created. It can depend on things like the amount of physical memory installed in the computer, the amount of virtual memory provided by the OS, the number of other tasks, drivers, and programs already running and how much memory that are using. So your program may be able to use more or less memory running today than it could use yesterday or it will be able to use tomorrow.

Many platforms place their strictest limits on automatic objects, that is those defined inside of a function without the use of the 'static' keyword. On some platforms you can create larger arrays if they are static or by dynamic allocation.

Collectives™ on Stack Overflow

Maximum size array program in C?

4 Answers 4

3 Comments

2 Comments

Dynamic Array

8 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

2 Comments

Dynamic Array

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related