Outofmemory exception in array

Question

I want to make an array of size 10^9 elements where each elements can be an integer of the same size. I always get an OutOfMemoryException at the initialization line. How can I achieve this?

If this is not possible, please suggest alternative strategies?

Declaring array is simple. int []array = new int [size]; You getting runtime exception? — fhnaseer, Jan 28 '13 at 11:26
"where each elements can be an integer of the same size".. :S (it's an array.. not an ArrayList or Tuple). And get more RAM I guess. — Lews Therin, Jan 28 '13 at 11:27
I mean that My array is not allowed to have elements repeated, so if its size is 10^9 elements, then it needs to store elements of range 10^9 each. — Samarth Agarwal, Jan 28 '13 at 11:28
32bit integer means 4byte integer multiplied by the size of the array (your case 1billion) => Array Size 4billion bytes => 4,000,000,000 B = 3,906,250 kB = 3,814 MB, 714 kB = 3 GB, 742 MB, 714 kB. Maximum Size of an array is http://stackoverflow.com/questions/1391672/what-is-the-maximum-size-that-an-array-can-hold --> 2GB / 4GB > 2GB -> Array not possible — jAC, Jan 28 '13 at 11:31
I have a dream that one day my 1 billion ints will live in an array where each element can be of the same size — default locale, Jan 28 '13 at 11:36
It is a program and the constraints are given as (1 <= k <= 10^5, k < n <= 10^9). Here k elements are already known while rest n-k will need to be calculated and filled in the array! Total elements are n — Samarth Agarwal, Jan 28 '13 at 11:38
@SamarthAgarwal Do you need to provide random access to all 10^9 elements (all of the elements are heavily used)? Or you need just output them once? I mean, maybe you don't need to store them all at once, and just use [online algorithm](http://en.wikipedia.org/wiki/Online_algorithm) — default locale, Jan 28 '13 at 11:54

CodesInChaos · Answer 1 · 2013-01-28T11:35:33.160

6

Arrays are limited to 2GB in .net 4.0 or earlier, even in a 64 bit process. So with one billion elements, the maximum supported element size is two bytes, but an int is four bytes. So this will not work.

If you want to have a larger collection, you need to write it yourself, backed by multiple arrays.

In .net 4.5 it's possible to avoid this limitation, see Jon Skeet's answer for details.

edited Jan 28 '13 at 11:35

answered Jan 28 '13 at 11:28

CodesInChaos

106,488
23
218
262

are you sure that arrays are limited to 2GB in 64 bit? do you have any reference? – daryal Jan 28 '13 at 11:34
@daryal http://msdn.microsoft.com/en-us/library/ms241064%28VS.80%29.aspx but it is for .NET 2.0 – Soner Gönül Jan 28 '13 at 11:34
1

"By default, when you run a 64-bit managed application on a 64-bit Windows operating system, you can create an object of no more than 2 gigabytes (GB). However, in the .NET Framework 4.5, you can increase this limit. For more information, see the `` element." – CodesInChaos Jan 28 '13 at 11:37
@SonerGönül this is for 32 bit as you have stated; I am not confident whether there is a limitation for 64 bit. – daryal Jan 28 '13 at 11:37
@CodesInChaos then I think you need to change the answer. – daryal Jan 28 '13 at 11:38

Jon Skeet · Accepted Answer · 2013-01-28T11:45:12.927

5

Assuming you mean int as the element type, you can do this using .NET 4.5, if you're using a 64-bit CLR.

You need to use the <gcAllowVeryLargeObjects> configuration setting. This is not on by default.

If you're using an older CLR or you're on a 32-bit machine, you're out of luck. Of course, if you're on a 64-bit machine but just an old version of the CLR, you could encapsulate your "one large array" into a separate object which has a list of smaller arrays... you could even implement IList<int> that way so that most code wouldn't need to know that you weren't really using a single array.

(As noted in comments, you'll still only be able to create an array with 2³¹ elements; but your requirement of 10⁹ is well within this.)

edited Jan 28 '13 at 11:45

answered Jan 28 '13 at 11:29

Jon Skeet

1,421,763
867
9,128
9,194

Interesting, didn't know .net 4.5 allows this. – CodesInChaos Jan 28 '13 at 11:30
In a 32 bit process he's out of luck, even when using multiple arrays. 4GB simply doesn't fit the address space. So he'd need to keep part of the data elsewhere. – CodesInChaos Jan 28 '13 at 11:31
Note that even if you enable this, you will STILL be limited to a max of approx 2^31 addressable elements regardless of their size. – Matthew Watson Jan 28 '13 at 11:44
@MatthewWatson: True, but that's well within the 10^9 required by the OP. Will edit it in anyway. – Jon Skeet Jan 28 '13 at 11:44

ppetrov · Answer 3 · 2013-01-28T11:47:40.420

I think you shouldn't load all this data into memory, store it somewhere in a file, and make a class that could work as an array but actually reads and writes data from and in the file

this is the general idea (this won't work as it is of course, plus you'll have to convert your int values into byte[] array before writing it and some other things)

public class FileArray
{
   Stream s;

   public this[int index]
   {
      get { s.Position = index * 4; return s.Read(); }
      set { s.Position = index * 4; s.Write(value); }
   }
}

that way you would have something that works just like an array, but the data would be stored on your hard drive

Done! That's the way I'd deal with this problem (btw this is pseudo code just to explain a little better the idea) — ppetrov, Jan 28 '13 at 11:46

Outofmemory exception in array

3 Answers3