Is there a max array length limit in C++?

Question

Is there a max length for an array in C++?

Is it a C++ limit or does it depend on my machine? Is it tweakable? Does it depend on the type the array is made of?

Can I break that limit somehow or do I have to search for a better way of storing information? And what should be the simplest way?

What I have to do is storing long long int on an array, I'm working in a Linux environment. My question is: what do I have to do if I need to store an array of N long long integers with N > 10 digits?

I need this because I'm writing some cryptographic algorithm (as for example the p-Pollard) for school, and hit this wall of integers and length of arrays representation.

Answer 1

Max array length depends on the size of an int on your hardware, I would say. Most of the time this would be 32 bit in this day.

Answer 2

There are two limits, both not enforced by C++ but rather by the hardware.

The first limit (should never be reached) is set by the restrictions of the size type used to describe an index in the array (and the size thereof). It is given by the maximum value the system's std::size_t can take. This data type should always be the largest integer type of a system.

The other limit is a physical memory limit. The larger your objects in the array are, the sooner this limit is reached because memory is full. For example, a vector<int> of a given size n typically takes about four times as much memory as an array of type vector<char> (minus a small constant value). Therefore, a vector<char> may contain more items than a vector<int> before memory is full. The same counts for the native C-style arrays int[] and char[].

Additionally, this upper limit may be influenced by the type of allocator used to construct the vector because an allocator is free to manage memory any way it wants. A very odd but nontheless conceivable allocator could pool memory in such a way that identical instances of an object share resources. This way, you could insert a lot of identical objects into a container that would otherwise use up all the available memory.

Apart from that, C++ doesn't enforce any limits.

Answer 3

I would agree with the above, that if you're intializing your array with

 int myArray[SIZE]

then SIZE is limited by the size of an integer. But you can always malloc a chunk of memory and have a pointer to it, as big as you want so long as malloc doesnt return NULL.

Answer 4

Looking at it from a practical rather than theoretical standpoint, on a 32 bit Windows system, the maximum total amount of memory available for a single process is 2 GB. You can break the limit by going to a 64 bit operating system with much more physical memory, but whether to do this or look for alternatives depends very much on your intended users and their budgets. You can also extend it somewhat using PAE.

The type of the array is very important, as default structure alignment on many compilers is 8 bytes, which is very wasteful if memory usage is an issue. If you are using Visual C++ to target Windows, check out the #pragma pack directive as a way of overcoming this.

Another thing to do is look at what in memory compression techniques might help you, such as sparse matrices, on the fly compression, etc... Again this is highly application dependent. If you edit your post to give some more information as to what is actually in your arrays, you might get more useful answers.

Edit: Given a bit more information on your exact requirements, your storage needs appear to be between 7.6 GB and 76 GB uncompressed, which would require a rather expensive 64 bit box to store as an array in memory in C++. It raises the question why do you want to store the data in memory, where one presumes for speed of access, and to allow random access. The best way to store this data outside of an array is pretty much based on how you want to access it. If you need to access array members randomly, for most applications there tend to be ways of grouping clumps of data that tend to get accessed at the same time. For example, in large GIS and spatial databases, data often gets tiled by geographic area. In C++ programming terms you can override the [] array operator to fetch portions of your data from external storage as required.

Answer 5

One thing I don't think has been mentioned in the previous answers.

I'm always sensing a "bad smell" in the refactoring sense when people are using such things in their design.

That's a huge array and possibly not the best way to represent your data both from an efficiency point of view and a performance point of view.

cheers,

Rob

Answer 6

As has already been pointed out, array size is limited by your hardware and your OS (man ulimit). Your software though, may only be limited by your creativity. For example, can you store your "array" on disk? Do you really need long long ints? Do you really need a dense array? Do you even need an array at all?

One simple solution would be to use 64 bit Linux. Even if you do not physically have enough ram for your array, the OS will allow you to allocate memory as if you do since the virtual memory available to your process is likely much larger than the physical memory. If you really need to access everything in the array, this amounts to storing it on disk. Depending on your access patterns, there may be more efficient ways of doing this (ie: using mmap(), or simply storing the data sequentially in a file (in which case 32 bit Linux would suffice)).

Answer 7

Nobody mentioned the limit on the size of the stack frame.

There are two places memory can be allocated:

• On the heap (dynamically allocated memory).
  The size limit here is a combination of available hardware and the OS's ability to simulate space by using other devices to temporarily store unused data (i.e. move pages to hard disk).
• On the stack (Locally declared variables).
  The size limit here is compiler defined (with possible hardware limits). If you read the compiler documentation you can often tweak this size.

Thus if you allocate an array dynamically (the limit is large and described in detail by other posts.

int a1 = new int[SIZE];  // SIZE limited only by OS/Hardware

Alternatively if the array is allocated on the stack then you are limited by the size of the stack frame. N.B. vectors and other containers have a small presence in the stack but usually the bulk of the data will be on the heap.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame

Answer 8

I would really like to know is for what do you need a vector with ...

store an array of N integers with N > 10 digits

Answer 9

If you have to deal with data that large you'll need to split it up into manageable chunks. It won't all fit into memory on any small computer. You can probably load a portion of the data from disk (whatever reasonably fits), perform your calculations and changes to it, store it to disk, then repeat until complete.