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.

Waverly

Answer 1

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 is large enough to contain the size in bytes of any object

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 multiple times as much memory as an array of type vector<char> (minus a small constant value), since int is usually bigger than char. Therefore, a vector<char> may contain more items than a vector<int> before memory is full. The same counts for raw C-style arrays like 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.

Exerciser

Also you can normally easily hit stack size limits, especially if using threads which again is implementation specific (but able to be changed). – Haplology

@Alaric: True. I didn't want to go too deep into system specifics because they differ very much and I'm no expert in any of them. – Exerciser

@Konrad, interesting point about allocator types and not something I was aware of. Thanks for the info. – Kropotkin

std::size_t is usually (always?) the size of a pointer, not the size of the biggest integer that has native hardware support in the integer math unit. On every x86 OS I've used, size_t is 32-bits for a 32-bit OS and 64-bits for a 64-bit OS. – Bruni

My understanding is that the maximum limit of an array is the maximum value of the processor's word. This is due to the indexing operator. For example, a machine may have a word size of 16 bits but an addressing register of 32 bits. A chunk of memory is limited in size by the parameter passed to new or malloc. A chunk of memory larger than an array can be accessed via pointer. – Martlet

Assuming wikipedia is correct ( en.wikipedia.org/wiki/Word_(computing) ), on x86, a word is 16-bits (and this is consistent with Microsoft's terminology at very least). I wonder what size_t would be for real mode 8088 (since the address space is 20 bits, it uses a 32-bit representation, but standard pointer arithmetic only works in 16 bit chunks). – Bruni

sorry for commenting on ancient reply, but take a look at this: Oct 15, 2011 at 8:06 PM comment : channel9.msdn.com/Shows/Checking-In-with-Erik-Meijer/… basically ptrdiff_t is signed, so that limits the size of array in 32b apps to 2^31, while size_t can support up to 2^32 – Systole

@Systole Is the array size / index encoded as a ptrdiff_t, then? – Exerciser

AFAIK no, but if I understand the link correctly you cant do ptr arithmetics on char arrays that have 2+GElements. Unfortunately all my OSes are 64b so I cant try to allocate 2^31+1 char array and do the pointer diff. – Systole

@Gabriel In 64 bit system, address of a location is stored in 8 bytes. So theoretically, maximum index of a byte array in a process would be (2^64)-1 isn't it? If I have more hardware memory than that, then also a process can't cross that limit. Is this assumption correct? Also, this limit is implied by the system itself, and not by the language right? – Sp

@SouravKannanthaB Yes, the limit is implied by the system rather than by the language (to the extent that the language limits itself to use natively supported data types for integers). And yes, if your hypothetical computer has more hardware than that, you won’t be able to address it. But neither will the operating system. And your computer won’t have more hardware than that: that’s 10 billion gigabytes. The world’s largest supercomputer has a tiny fraction of that. – Exerciser

Answer 2

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

Theorist

Preferred allocation of large arrays is not on a stack or globally defined but rather through dynamic allocation (via new or malloc). – Martlet

@Thomas Matthews: Not in my world. Dynamically allocated objects require management. If it needs to dynamically allocated I would use a stack object that representes the dynamically allocated memoory, like a std::vector. – Theorist

@LokiAstari int* a1 = new int[SIZE] – Frolic

There is one cornor case missing: Global Arrays, while not a beauty and best avoided, these do not fall under the restrictions of the stack, and you do not need malloc/free do work with them. – Subirrigate

@ted, why should global arrays be "best avoided"? To be more precise I think you mean statically allocated arrays. Their scope does not have to be global. I would argue they are better than dynamic arrays because you can use absolute addressing with them (at least on Linux) which you can't do with dynamically allocated arrays. – Massingill

@Zboson: NO I believe he means global accessible arrays. Because global mutable state is usually bad. Functions no longer depend on just their inputs but also on global state (that can be mutated elsewhere in the code). This makes unit test exceedingly hard to write and functional tests harder still. programmers.stackexchange.com/questions/148108/… – Theorist

@Zboson see Loki Astari s comment above, he explains it. Why do you think absolute addressing is such a benefit? What ever way you put it an array access with index is basically pointer to base plus index and once you have that base pointer loaded there is (afaik) no more performance penalty. – Subirrigate

@ted, in that case your "one corner case" was a good point but is too limited. Instead of saying a global array you should say a statically allocated array. foo() { static int x[10]; } is a statically allocated array the only difference between it and a global array is the scope. So although a global array may best be avoided a statically allocated array with function scope is a interesting case which is often overlooked. – Massingill

@ted, i regards to absolute addressing some ports such as port 7 on Haswell only work with [register + constant] and not [register + register]. Also microp-fusion as far as I can tell requires [register + constant]. – Massingill

@Zboson what do you mean by port? And yes while there are static arrays and I overlooked those you should mind the difference between global and static, which includes as you pointed out correctly, the different scope. – Subirrigate

@ted, port7 is described at anandtech.com/show/6355/intels-haswell-architecture/8. What other difference is there between a global array and one declared with the static keyword than scope? – Massingill

Very important point. I recently came across a "production-quality" open-source project that provided a configurable max-buffer size. All of the buffers were allocated on the stack, so configuring a large enough value would cause the program to immediately segfault on launch. – Chitkara

Answer 3

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.

Kropotkin

There are system calls that allow allocation of memory outside the program space; but this is OS dependent and not portable. We used them in embedded systems. – Martlet

Answer 4

As annoyingly non-specific as all the current answers are, they're mostly right but with many caveats, not always mentioned. The gist is, you have two upper-limits, and only one of them is something actually defined, so YMMV:

1. Compile-time limits

Basically, what your compiler will allow. For Visual C++ 2017 on an x64 Windows 10 box, this is my max limit at compile-time before incurring the 2GB limit,

unsigned __int64 max_ints[255999996]{0};

If I did this instead,

unsigned __int64 max_ints[255999997]{0};

I'd get:

Error C1126 automatic allocation exceeds 2G

I'm not sure how 2G correllates to 255999996/7. I googled both numbers, and the only thing I could find that was possibly related was this *nix Q&A about a precision issue with dc. Either way, it doesn't appear to matter which type of int array you're trying to fill, just how many elements can be allocated.

2. Run-time limits

Your stack and heap have their own limitations. These limits are both values that change based on available system resources, as well as how "heavy" your app itself is. For example, with my current system resources, I can get this to run:

int main()
{
    int max_ints[257400]{ 0 };
    return 0;
}

But if I tweak it just a little bit...

int main()
{
    int max_ints[257500]{ 0 };
    return 0;
}

Bam! Stack overflow!

Exception thrown at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000). Unhandled exception at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000).

And just to detail the whole heaviness of your app point, this was good to go:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[400]{ 0 };
    return 0;
}  

But this caused a stack overflow:

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[500]{ 0 };
    return 0;
}  

Privateer

Answer 5

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.

Vessel

I'm not sure if this is incorrect, or I misunderstood you, or something else. For example, this is prevented by the MSVC17 compiler: int oops[INT_MAX]{0}; It generates, C2148 - total size of array must not exceed 0x7fffffff bytes – Privateer

With 16GB DDR4 and about 66% memory currently used before launching my app as debug on Windows 10 with VS2017, I have an undefined limit on how large of an int-array I can initialize with 0. Sometimes I can do it with ~257k elements, sometimes I get a stack overflow. If I add anything to my app besides the main and the array, that number goes down (obviously). I had to experiment to determine this number, so I don't see how this metric can be relied upon beyond knowing your theoretical limits in a vacuum. – Privateer

Answer 6

To summarize the responses, extend them, and to answer your question directly:

No, C++ does not impose any limits for the dimensions of an array.

But as the array has to be stored somewhere in memory, so memory-related limits imposed by other parts of the computer system apply. Note that these limits do not directly relate to the dimensions (=number of elements) of the array, but rather to its size (=amount of memory taken). Dimensions (D) and in-memory size (S) of an array is not the same, as they are related by memory taken by a single element (E): S=D * E.

Now E depends on:

• the type of the array elements (elements can be smaller or bigger)
• memory alignment (to increase performance, elements are placed at addresses which are multiplies of some value, which introduces
  ‘wasted space’ (padding) between elements
• size of static parts of objects (in object-oriented programming static components of objects of the same type are only stored once, independent from the number of such same-type objects)

Also note that you generally get different memory-related limitations by allocating the array data on stack (as an automatic variable: int t[N]), or on heap (dynamic alocation with malloc()/new or using STL mechanisms), or in the static part of process memory (as a static variable: static int t[N]). Even when allocating on heap, you still need some tiny amount of memory on stack to store references to the heap-allocated blocks of memory (but this is negligible, usually).

The size of size_t type has no influence on the programmer (I assume programmer uses size_t type for indexing, as it is designed for it), as compiler provider has to typedef it to an integer type big enough to address maximal amount of memory possible for the given platform architecture.

The sources of the memory-size limitations stem from

• amount of memory available to the process (which is limited to 2^32 bytes for 32-bit applications, even on 64-bits OS kernels),
• the division of process memory (e.g. amount of the process memory designed for stack or heap),
• the fragmentation of physical memory (many scattered small free memory fragments are not applicable to storing one monolithic structure),
• amount of physical memory,
• and the amount of virtual memory.

They can not be ‘tweaked’ at the application level, but you are free to use a different compiler (to change stack size limits), or port your application to 64-bits, or port it to another OS, or change the physical/virtual memory configuration of the (virtual? physical?) machine.

It is not uncommon (and even advisable) to treat all the above factors as external disturbances and thus as possible sources of runtime errors, and to carefully check&react to memory-allocation related errors in your program code.

So finally: while C++ does not impose any limits, you still have to check for adverse memory-related conditions when running your code... :-)

Fluxmeter

Answer 7

As many excellent answers noted, there are a lot of limits that depend on your version of C++ compiler, operating system and computer characteristics. However, I suggest the following script on Python that checks the limit on your machine.

It uses binary search and on each iteration checks if the middle size is possible by creating a code that attempts to create an array of the size. The script tries to compile it (sorry, this part works only on Linux) and adjust binary search depending on the success. Check it out:

import os

cpp_source = 'int a[{}]; int main() {{ return 0; }}'

def check_if_array_size_compiles(size):
        #  Write to file 1.cpp
        f = open(name='1.cpp', mode='w')
        f.write(cpp_source.format(m))
        f.close()
        #  Attempt to compile
        os.system('g++ 1.cpp 2> errors')
        #  Read the errors files
        errors = open('errors', 'r').read()
        #  Return if there is no errors
        return len(errors) == 0

#  Make a binary search. Try to create array with size m and
#  adjust the r and l border depending on wheather we succeeded
#  or not
l = 0
r = 10 ** 50
while r - l > 1:
        m = (r + l) // 2
        if check_if_array_size_compiles(m):
                l = m
        else:
                r = m

answer = l + check_if_array_size_compiles(r)
print '{} is the maximum avaliable length'.format(answer)

You can save it to your machine and launch it, and it will print the maximum size you can create. For my machine it is 2305843009213693951.

Gilberto

Answer 8

I'm surprised the max_size() member function of std::vector has not been mentioned here.

"Returns the maximum number of elements the container is able to hold due to system or library implementation limitations, i.e. std::distance(begin(), end()) for the largest container."

We know that std::vector is implemented as a dynamic array underneath the hood, so max_size() should give a very close approximation of the maximum length of a dynamic array on your machine.

The following program builds a table of approximate maximum array length for various data types.

#include <iostream>
#include <vector>
#include <string>
#include <limits>

template <typename T>
std::string mx(T e) {
    std::vector<T> v;
    return std::to_string(v.max_size());
}

std::size_t maxColWidth(std::vector<std::string> v) {
    std::size_t maxWidth = 0;

    for (const auto &s: v)
        if (s.length() > maxWidth)
            maxWidth = s.length();

    // Add 2 for space on each side
    return maxWidth + 2;
}

constexpr long double maxStdSize_t = std::numeric_limits<std::size_t>::max();

// cs stands for compared to std::size_t
template <typename T>
std::string cs(T e) {
    std::vector<T> v;
    long double maxSize = v.max_size();
    long double quotient = maxStdSize_t / maxSize;
    return std::to_string(quotient);
}

int main() {
    bool v0 = 0;
    char v1 = 0;

    int8_t v2 = 0;
    int16_t v3 = 0;
    int32_t v4 = 0;
    int64_t v5 = 0;

    uint8_t v6 = 0;
    uint16_t v7 = 0;
    uint32_t v8 = 0;
    uint64_t v9 = 0;

    std::size_t v10 = 0;
    double v11 = 0;
    long double v12 = 0;

    std::vector<std::string> types = {"data types", "bool", "char", "int8_t", "int16_t",
                                      "int32_t", "int64_t", "uint8_t", "uint16_t",
                                      "uint32_t", "uint64_t", "size_t", "double",
                                      "long double"};

    std::vector<std::string> sizes = {"approx max array length", mx(v0), mx(v1), mx(v2),
                                      mx(v3), mx(v4), mx(v5), mx(v6), mx(v7), mx(v8),
                                      mx(v9), mx(v10), mx(v11), mx(v12)};

    std::vector<std::string> quotients = {"max std::size_t / max array size", cs(v0),
                                          cs(v1), cs(v2), cs(v3), cs(v4), cs(v5), cs(v6),
                                          cs(v7), cs(v8), cs(v9), cs(v10), cs(v11), cs(v12)};

    std::size_t max1 = maxColWidth(types);
    std::size_t max2 = maxColWidth(sizes);
    std::size_t max3 = maxColWidth(quotients);

    for (std::size_t i = 0; i < types.size(); ++i) {
        while (types[i].length() < (max1 - 1)) {
            types[i] = " " + types[i];
        }

        types[i] += " ";

        for  (int j = 0; sizes[i].length() < max2; ++j)
            sizes[i] = (j % 2 == 0) ? " " + sizes[i] : sizes[i] + " ";

        for  (int j = 0; quotients[i].length() < max3; ++j)
            quotients[i] = (j % 2 == 0) ? " " + quotients[i] : quotients[i] + " ";

        std::cout << "|" << types[i] << "|" << sizes[i] << "|" << quotients[i] << "|\n";
    }

    std::cout << std::endl;

    std::cout << "N.B. max std::size_t is: " <<
        std::numeric_limits<std::size_t>::max() << std::endl;

    return 0;
}

On my macOS (clang version 5.0.1), I get the following:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775807   |             2.000000             |
|        char |   9223372036854775807   |             2.000000             |
|      int8_t |   9223372036854775807   |             2.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   9223372036854775807   |             2.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

On ideone gcc 8.3 I get:

|  data types | approx max array length | max std::size_t / max array size |
|        bool |   9223372036854775744   |             2.000000             |
|        char |   18446744073709551615  |             1.000000             |
|      int8_t |   18446744073709551615  |             1.000000             |
|     int16_t |   9223372036854775807   |             2.000000             |
|     int32_t |   4611686018427387903   |             4.000000             |
|     int64_t |   2305843009213693951   |             8.000000             |
|     uint8_t |   18446744073709551615  |             1.000000             |
|    uint16_t |   9223372036854775807   |             2.000000             |
|    uint32_t |   4611686018427387903   |             4.000000             |
|    uint64_t |   2305843009213693951   |             8.000000             |
|      size_t |   2305843009213693951   |             8.000000             |
|      double |   2305843009213693951   |             8.000000             |
| long double |   1152921504606846975   |             16.000000            |

N.B. max std::size_t is: 18446744073709551615

It should be noted that this is a theoretical limit and that on most computers, you will run out of memory far before you reach this limit. For example, we see that for type char on gcc, the maximum number of elements is equal to the max of std::size_t. Trying this, we get the error:

prog.cpp: In function ‘int main()’:
prog.cpp:5:61: error: size of array is too large
  char* a1 = new char[std::numeric_limits<std::size_t>::max()];

Lastly, as @MartinYork points out, for static arrays the maximum size is limited by the size of your stack.

Alessandraalessandria

Answer 9

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

Fanfaronade

Have you got any suggestion on what I should use? – Waverly

If you can tell us what the data is that you're storing then maybe we can. (-: – Fanfaronade

Sorry Luis my first response was very flippant. It will be driven by the nature of your data. The relationaships of your data will drive the model you use to represent the data. Then the collection should be apparent from that. If not, I would worry about the data model. – Fanfaronade

not so flippant to me: how about a cached database with a toy like this? tweaktown.com/news/22066/… – Solifidian

Answer 10

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.

Syne

See also for Merge Sort on an example algorithm to handle data too large to fit into memory. – Martlet

Answer 11

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)).

Jud

Hmm, disks, arrays, ... anybody hear of virtual memory. OSes that support virtual memory will start using an external device for memory, such as a hard disk, and swap out chunks with internal memory. – Martlet

Answer 12

i would go around this by making a 2d dynamic array:

long long** a = new long long*[x];
for (unsigned i = 0; i < x; i++) a[i] = new long long[y];

more on this here https://mcmap.net/q/21711/-how-do-i-declare-a-2d-array-in-c-using-new

Karykaryl