Is the size of an array constrained by the upper limit of int (2147483647)?

Question

I'm doing some Project Euler exercises and I've run into a scenario where I have want arrays which are larger than 2,147,483,647 (the upper limit of int in C#).

Sure these are large arrays, but for instance, I can't do this

// fails
bool[] BigArray = new BigArray[2147483648];

// also fails, cannot convert uint to int
ArrayList BigArrayList = new ArrayList(2147483648);

So, can I have bigger arrays?

EDIT: It was for a Sieve of Atkin, you know, so I just wanted a really big one :D

Answer 1

Anytime you are working with an array this big, you should probably try to find a better solution to the problem. But that being said I'll still attempt to answer your question.

As mentioned in this article there is a 2 GB limit on any object in .Net. For all x86, x64 and IA64.

As with 32-bit Windows operating systems, there is a 2GB limit on the size of an object you can create while running a 64-bit managed application on a 64-bit Windows operating system.

Also if you define an array too big on the stack, you will have a stack overflow. If you define the array on the heap, it will try to allocate it all in one big continuous block. It would be better to use an ArrayList which has implicit dynamic allocation on the heap. This will not allow you to get past the 2GB, but will probably allow you to get closer to it.

I think the stack size limit will be bigger only if you are using an x64 or IA64 architecture and operating system. Using x64 or IA64 you will have 64-bit allocatable memory instead of 32-bit.

If you are not able to allocate the array list all at once, you can probably allocate it in parts.

Using an array list and adding 1 object at a time on an x64 Windows 2008 machine with 6GB of RAM, the most I can get the ArrayList to is size: 134217728. So I really think you have to find a better solution to your problem that does not use as much memory. Perhaps writing to a file instead of using RAM.

Answer 2

The array limit is, afaik, fixed as int32 even on 64-bit. There is a cap on the maximum size of a single object. However, you could have a nice big jagged array quite easily.

Worse; because references are larger in x64, for ref-type arrays you actually get less elements in a single array.

See here:

I’ve received a number of queries as to why the 64-bit version of the 2.0 .Net runtime still has array maximum sizes limited to 2GB. Given that it seems to be a hot topic of late I figured a little background and a discussion of the options to get around this limitation was in order.

First some background; in the 2.0 version of the .Net runtime (CLR) we made a conscious design decision to keep the maximum object size allowed in the GC Heap at 2GB, even on the 64-bit version of the runtime. This is the same as the current 1.1 implementation of the 32-bit CLR, however you would be hard pressed to actually manage to allocate a 2GB object on the 32-bit CLR because the virtual address space is simply too fragmented to realistically find a 2GB hole. Generally people aren’t particularly concerned with creating types that would be >2GB when instantiated (or anywhere close), however since arrays are just a special kind of managed type which are created within the managed heap they also suffer from this limitation.

Answer 3

I believe that even within a 64 bit CLR, there's a limit of 2GB (or possibly 1GB - I can't remember exactly) per object. That would prevent you from creating a larger array. The fact that Array.CreateInstance only takes Int32 arguments for sizes is suggestive too.

On a broader note, I suspect that if you need arrays that large you should really change how you're approaching the problem.

Answer 4

You don't need an array that large at all.

When your method runs into resource problems, don't just look at how to expand the resources, look at the method also. :)

Here's a class that uses a 3 MB buffer to calculate primes using the sieve of Eratosthenes. The class keeps track of how far you have calculated primes, and when the range needs to be expanded it creates a buffer to test another 3 million numbers.

It keeps the found prime numbers in a list, and when the range is expanded the previos primes are used to rule out numbers in the buffer.

I did some testing, and a buffer around 3 MB is most efficient.

public class Primes {

   private const int _blockSize = 3000000;

   private List<long> _primes;
   private long _next;

   public Primes() {
      _primes = new List<long>() { 2, 3, 5, 7, 11, 13, 17, 19 };
      _next = 23;
   }

   private void Expand() {
      bool[] sieve = new bool[_blockSize];
      foreach (long prime in _primes) {
         for (long i = ((_next + prime - 1L) / prime) * prime - _next;
            i < _blockSize; i += prime) {
            sieve[i] = true;
         }
      }
      for (int i = 0; i < _blockSize; i++) {
         if (!sieve[i]) {
            _primes.Add(_next);
            for (long j = i + _next; j < _blockSize; j += _next) {
               sieve[j] = true;
            }
         }
         _next++;
      }
   }

   public long this[int index] {
      get {
         if (index < 0) throw new IndexOutOfRangeException();
         while (index >= _primes.Count) {
            Expand();
         }
         return _primes[index];
      }
   }

   public bool IsPrime(long number) {
      while (_primes[_primes.Count - 1] < number) {
         Expand();
      }
      return _primes.BinarySearch(number) >= 0;
   }

}

Answer 5

I'm very much a newbie with C# (i.e. learning it this week), so I'm not sure of the exact details of how ArrayList is implemented. However, I would guess that as you haven't defined a type for the ArrayList example, then the array would be allocated as an array of object references. This might well mean that you are actually allocating 4-8Gb of memory depending on the architecture.