66

I understand that hardware will limit the amount of memory allocated during program execution. However, my question is without regard to hardware. Assuming that there was no limit to the amount of memory, would there be no limit to the array?

Improve this question
3
  • 2
    Actually software (OS) is the thing that will normally cause the memory limit seen by your C program. Commented Feb 21, 2012 at 23:33
  • 2
    Without a limit on memory, there is no limit on the pointer size. Without a limit on pointer size, all bets are off. Commented Feb 21, 2012 at 23:34
  • 4
    it would be limited by the size of the pointer (32 bit versus 64 bit) Commented Feb 21, 2012 at 23:34

7 Answers 7

Reset to default
64

There is no fixed limit to the size of an array in C.

The size of any single object, including of any array object, is limited by SIZE_MAX, the maximum value of type size_t, which is the result of the sizeof operator. (It's not entirely clear whether the C standard permits objects larger than SIZE_MAX bytes, but in practice such objects are not supported; see footnote.) Since SIZE_MAX is determined by the implementation, and cannot be modified by any program, that imposes an upper bound of SIZE_MAX bytes for any single object. (That's an upper bound, not a least upper bound; implementations may, and typically do, impose smaller limits.)

The width of the type void*, a generic pointer type, imposes an upper bound on the total size of all objects in an executing program (which may be larger than the maximum size of a single object).

The C standard imposes lower bounds, but not upper bounds, on these fixed sizes. No conforming C implementation can support infinite-sized objects, but it can in principle support objects of any finite size. Upper bounds are imposed by individual C implementations, by the environments in which they operate, and by physics, not by the language.

For example, a conforming implementation could have SIZE_MAX equal to 21024-1, which means it could in principle have objects up to 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137215 bytes.

Good luck finding hardware that actually supports such objects.

Footnote: There is no explicit rule that no object can be bigger than SIZE_MAX bytes. You couldn't usefully apply the sizeof operator to such an object, but like any other operator, sizeof can overflow; that doesn't mean you couldn't perform operations on such an object. But in practice, any sane implementation will make size_t big enough to represent the size of any object it supports.

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

15 Comments

@J.C.Leitão: In principle, I suppose a compiler could use an arbitrary precision library to implement very wide integer types. But you can't do that as a programmer; actual integer types (with literals, operators, and so forth) are limited to what the compiler provides.
does the existence of far pointers and the correspoing memory model change your answer in any way?
@J.F.Sebastian: I've never used far pointers myself, but my understanding is that they include both the segment number and the offset within the segment. If a 16-bit pointer can access 20 bits worth of address space, there must be at least 4 bits of implicit information somewhere else, which as I understand it is exactly what far pointers don't do. In a conforming C implementation, a void* can uniquely address every byte of every object that currently exists.
@caot: Your array is defined inside a function without the static keyword, so it has automatic storage duration. On most implementations, such objects are allocated on the stack. It's likely your system limits the size of the stack. Use static, or define it globally, or use malloc().
@M.M: There's nothing in the standard that forbids objects bigger than SIZE_MAX bytes, but in practice any reasonable implementation that can support objects bigger than, say, 2**32 bytes will make size_t wider than 32 bits. An implementation that lets you define such large objects but doesn't bother to make size_t big enough to hold their size might be conforming, but it would be perverse.
|
14

C99 5.2.4.1 "Translation limits" minimal size

The implementation shall be able to translate and execute at least one program that contains at least one instance of every one of the following limits: 13)

  • 65535 bytes in an object (in a hosted environment only)
  1. Implementations should avoid imposing fixed translation limits whenever possible.

This suggests that a conforming implementation could refuse to compile an object (which includes arrays) with more than short bytes.

PTRDIFF_MAX also imposes some limits on array says

The C99 standard 6.5.6 Additive operators says:

9 When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined.

Which implies to me that arrays larger than ptrdiff_t are allowed in theory, but then you cannot take the difference of their addresses portabibly.

So perhaps for this reason, GCC just seems to limit you to ptrdiff_t. This is also mentioned at: Why is the maximum size of an array "too large"?

Experiments

Maybe what ultimately matters is whatever your compiler will accept, so here we go:

main.c

#include <stdint.h>

TYPE a[(NELEMS)];

int main(void) {
    return 0;
}

sizes.c

#include <stdint.h>
#include <stdio.h>

int main(void) {
    printf("PTRDIFF_MAX 0x%jx\n", (uintmax_t)PTRDIFF_MAX);
    printf("SIZE_MAX    0x%jx\n", (uintmax_t)SIZE_MAX);
    return 0;
}

And then we try to compile with:

gcc -ggdb3 -O0 -std=c99 -Wall -Wextra -pedantic -o sizes.out sizes.c
./sizes.out
gcc -ggdb3 -O0 -std=c99 -Wall -Wextra -pedantic -o main.out \
  -DNELEMS='((2lu << 62) - 1)' -DTYPE=uint8_t main.c

Results:

  • PTRDIFF_MAX: 0x7fffffffffffffff = 2^63 - 1

  • SIZE_MAX: 0xffffffffffffffff = 2^64 - 1

  • -DNELEMS='((2lu << 62) - 1)' -DTYPE=uint8_t: compiles (== 2^63 - 1). Running it segfaults immediately on my mere 32 GB RAM system :-)

  • -DNELEMS='(2lu << 62)' -DTYPE=uint8_t: compilation fails with:

    error: size of array ‘a’ is too large

  • -DNELEMS='(2lu << 62 - 1)' -DTYPE=uint16_t: compilation fails with:

    error: size ‘18446744073709551614’ of array ‘a’ exceeds maximum object size ‘9223372036854775807’

    where 9223372036854775807 == 0x7fffffffffffffff

So from this we understand that GCC imposes two limitations with different error messages:

  • number of elements cannot exceed 2^63 (happens to == PTRDIFF_MAX)
  • array size cannot exceed 2^63 (also happens to == PTRDIFF_MAX)

Tested on Ubuntu 20.04 amd64, GCC 9.3.0.

See also

Improve this answer

6 Comments

gcc doesn't support dynamic arrays larger than half the pointer width either. Note that pointer-subtraction results are scaled by the object size, so in theory a 3GiB array of int on an ILP32 target should work, and end - start should give 3 * 1024**3 / 4, calculated without overflow, because the C standard says it's not UB if final result is representable. But gcc emits code that does subtraction with pointer width and then arithmetic right-shifts that, losing the carry-out from the subtraction. godbolt.org/g/NG6zZ6.
I tested with -m32 and got -536870896 (pointer subtraction) vs. 536870928 (manual). Glibc malloc did succeed for an allocation of 2GiB + 16, on in 32-bit user-space on x86 (under a 64-bit kernel). It failed for a 3GiB allocation, though. Anyway, apparently this is "not a bug", because gcc considers PTRDIFF_MAX the max object size: developers.redhat.com/blog/2017/02/22/…. -Walloc-size-larger-than=PTRDIFF_MAX is enabled by -Wall, and I got that warning while compiling my test program.
Is that limit (PTRDIFF_MAX) the limit in number of elements, or in bytes? As I see it, that's a limit in elements, but if elements are big enough, you could easily hit first the hard limit in bytes (SIZE_MAX). That would be dangerous though, because functions that access that array through a char * could be problematic.
@CacahueteFrito my thinking is that you can ways typecast the pointer of the larger size to uint8_t, and then you would be able to reach differences larger than PTRDIFF_MAX. Just a heuristic of why GCC seems to do what it does though. I improved the experiments a bit now.
@alx: It's in bytes. The reason is that pointer-subtraction is required to be accurate when it doesn't overflow the final value even if the byte distance wouldn't fit (if the pointers had been cast to char* before subtracting). Setting an implementation limit means GCC can implement end - start for wider types as raw integer subtraction of the pointers, and division by sizeof(T) (using a shift or multiplicative inverse of course). If that had to give accurate results even for pointers 2.1 GiB apart on a 32-bit system, it would need ext prec. or rotate the carry flag in to divide by 2.
|
5

Without regard for memory, the maximum size of an array is limited by the type of integer used to index the array.

Improve this answer

1 Comment

When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand (C11 n1570, section 6.5.6 Additive operators). So using an integer type wider than a pointer isn't allowed to give you access to more memory than you could access otherwise. (Recall that arr[idx] is exactly equivalent to *((arr) + (idx)), and that's in fact how the C standard defines the [] array subscript operator.) Anyway, that's a limit that all C implementations share, but in practice implementations have smaller limits, like PTRDIFF_MAX for gcc.
5

A 64-bit machine could theoretically address a maximum of 2^64 bytes of memory.

Improve this answer

9 Comments

Good luck putting that amount of memory into a computer. Even with Moore's law that's a long time coming.
I could imagine it happening within my lifetime though.
This answer is plain wrong. I have accessed 22-bits of address space on a 16-bit machine. There is no reason a “64-bit machine,” which has no firm definition, is restricted to 64 bits of address space.
@EricPostpischil you can theoretically combine any amount of unitary information type in order to access a higher magnitude of adresses. But that is not the point. A pointer, as is defined, is 64 bits, and therefore adresses 2^64 addresses of memory. You can't make enough combinations with 16 bits and address every single cell of memory in a 22 bit machine.
@AntónioOliveira: This answer does not say a pointer defined to be 64 bits can address a maximum of 2^64 addresses, which would be true (except of course for the null pointer value). It says a 64-bit machine can address a maximum of 2^64 addresses, which is false. The term “64-bit machine“ does not have a single technical definition. Generally, it can mean the general processor registers are 64 bits wide, or the bus is 64 bits wide, or instructions “mostly” operate on 64-bit-wide data, and so on…
|
2

I guess the biggest theoretical array would be the max value of "unsigned long" (or whatever the biggest integer number the latest standard / your compiler supports)

Improve this answer

1 Comment

Not if that's wider than a pointer. (e.g. long long on an implementation with 32-bit pointers).
2

The size of the pointer will limit the memory you are able to access. Even if the hardware offers support for unlimited memory, if the largest datatype you are able to use is 64 bit, you'll only be able to access 2^64 bytes of memory.

Improve this answer

Comments

0

I was looking for a way to determine the maximum size for an array. This question seems to ask the same, so I want to share my findings.

Initially, C does not provide any function to determine the maximum number of elements allocable in an array in compilation time. This is because it will depend of the memory of available in the machine where it will be executed.

On the other hand, I have found, that memory allocation functions (calloc() and malloc()) enable to allocate larger arrays. Moreover, these functions allows you to handle runtime memory allocation errors.

Hope that helps.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.