Creating a large array of numbers (10^9 size)

Question

I want to create an array that is capable of storing 10^9 numbers(long int).If i try doing this my compiler crashes.What is the maximum size array allowed in C++.Also if i do this dynamically too i get the same problem.How can i accomplish the task i am looking to acheive? Thanks, any help would be appreciated.

Solution 1

The maximum array size is dependent on the data you store (and the integers available to index them).

So on a 32bit system, you can only index 2³² elements at most if you're lucky, which is a bit above 10⁹. On a 64bit system, you can index 2⁶⁴ elements, which is a bit above 10¹⁹. This is essentially the maximum array size. Being able to index that does not imply that you can also actually get that much from the operating system, as the actual virtual address space might be much smaller. On Linux, a virtual adress space of approx. 64 Terabytes is available per process on 64bit, which are 2⁴² bytes.

However, if you actually try to allocate this, you need that much amount of bytes! So if you try to allocate an array of long int which will probably be 64bits of size, you need 8 Gigabytes of memory.

On a 32bit system, this is impossible. On a 64bit system, you need to have that amount of ram and swap space to work.

If you're on a 32bit system or on a 64bit system without enough memory, you'll get a out of memory error, which is probably the reason for the behaviour you see.

If you also try to create the array statically in a .data section of your executable, the executable may end up with being 8 GBytes large, where you could run into filesystem limits (fat32 anyone?). Also the compiler probably chokes on the amount of data (on 32bit, it'll probably crash).

If you're allocating on stack (this is, as a statically sized local variable array), you'll also run into stack limits on certain operating systems.

Solution 2

An array of 10^9 longs would typically take up at least 4GB of memory, which would already be prohibitive in all 32-bit systems.

Even if that much memory is available in a 64-bit system you certainly cannot expect to allocate 4GB on the stack like this:

void foo() {
    long arr[1000000000]; // stack size is a typically few MBs!
}

Solution 3

I want to create an array

Do you really need an array? In other words, do you require your integers to be in one memory block, or you simply want to access them by index? If you don't care about the memory layout, but still want to have fast access to elements, you should use std::deque. Instead of allocating one chunk of memory, it'll store your numbers in many small chunks, so as long as you have enough memory to store all your numbers together, you'll be fine.

Solution 4

I don't think it's your compiler crash, it's your memory crash (out of memory or something like this), e.g in windows 32 bit, at most you could use 2^32 bit of memory space which is smaller than 10^9*64 so you will get memory exception. You could use it by paging and loading smaller parts from file to memory.

Edit: As Tobias Langner mentioned in comments, compiler also could raise this error but original problem is from memory.

View more solutions

Comments

[Tobias Langner]

If the array is allocated on the stack, even the compiler may crash (depending on what it does there). But you are right, it's the memory for sure (one way or the other).

[Saeed Amiri]

@TobiasLangner, interesting note, I wasn't care about it, thanks.

[WiSaGaN]

Current 64bit systems implement a virtual address space of 48 bits. So it would not be possible to support 2^64-1 elements.

[nhahtdh]

IIRC, there is also the problem of cannot find an area of contiguous memory that can be allocated for the array.

[Saeed Amiri]

I don't know why you saying 2³²-1 ? how you find this -1, the address space is 32 bit means 2³². also too many space will be used by OS and other programs.

[Jonas Schäfer]

@nhahtdh: when getting the memory from the operating system, this may me mitigiated by mapping different areas of physical memory to a contigous block.

[Jonas Schäfer]

@WiSaGaN, SaeedAmiri: You're both right, I'm going to correct my post.

[nhahtdh]

@JonasWielicki: I'm talking at virtual memory level. Even if it is virtual, it is still partitioned into different regions. I think it may be possible that the partition prevents contiguous, large amount of memory to be allocated.

[Jonas Schäfer]

@nhahtdh This is a problem of the C memory manager in that case and of course a risk. However, if you're doing the block allocation early enough in the program (i.e. before any memory fragmentation happens) and malloc gets its memory from the OS directly, it should work out. Watching my memory consumption it seems like malloc at some level (kernel or userspace) is allocating blockwise already, still it works (tried with 4GBytes).

[nhahtdh]

@JonasWielicki: Thanks for the reply. I understand that it is not that of a problem early in the program. I just want to confirm that it is also one possible case that allocation may fail for request of big chunk of memory.

[ffttyy]

Could you explain the answer a little bit more? How is stack size a typically few MBs?

[Waihon Yew]

@ffttyy not sure what can be explained there. Stack size of the main thread of a process is decided by the OS executable loader, which in turn takes suggestions from values found inside the executable, which in turn means it's indirectly decided by the build tools (compiler/linker) that were used to create it. For additional threads, the kernel call that creates them also provides a way of specifying stack size for the new thread. In all such cases, mainstream desktop OSes and build tools default to something in the low megabytes range.