Create huge dictionary

Question

In my quest to the primes, I've already asked this question : Can't create huge arrays which lead me to create my own class of fake arrays based on a dictionary of arrays... : private Dictionary<int, Array> arrays = new Dictionary<int, Array>();

I can know create fake arrays of a lot of bool (like 10 000 000 000) using the code below:

public class CustomArray
{
    private Dictionary<int, Array> arrays = new Dictionary<int, Array>();

    public CustomArray(ulong lenght)
    {
        int i = 0;
        while (lenght > 0x7FFFFFC7)
        {
            lenght -= 0x7FFFFFC7;
            arrays[i] = new bool[0x7FFFFFC7];
            i++;
        }
        arrays[i] = new bool[lenght];
    }
}

But it crashes as soon as I ask for a CustomArray of 100 000 000 000 elements. It works well for the 25 first iterations (my Dictionary contains 25 arrays of 0x7FFFFFC7 elements) but then it crashes with an OutOfMemory exception.

_{As a remainder, I've got 16GB memory, VS2013, the program is compiled in 64bits, I've enabled the gcAllowVeryLargeObjects option and I don't see any memory peak in the Task Manager.}

How can I avoid this error?

Why dictionaries out of all things? Wouldn't a jagged array be more appropriate? — Luaan, Jun 18 '15 at 13:08
also bool is not an efficient type for storing information. You could simply store 64 bools in a ulong (8 bytes) rather than a 64 bool array (64 bytes) — Andrei Tătar, Jun 18 '15 at 13:09
Well, you *don't* have enough memory for `100 000 000 000` `bool`s, not even by far. Each `bool` takes a byte, so your 16 GiB will run out with just 16 billion items. You don't see a spike because the *physical* memory doesn't necessarily get allocated (it's all zeroes, so it's mapped to zero-page), but that's just a hidden optimization. C# `bool` isn't a single bit. 25 arrays of 0x7FFFFFC7 elements takes *50 GiB*! — Luaan, Jun 18 '15 at 13:18
@Andrey I'm using this [kind of code](http://rosettacode.org/wiki/Sieve_of_Eratosthenes#C.23) — Thomas Ayoub, Jun 18 '15 at 13:28
@Thomas it is not suitable method for generation of large amount of primes — Andrey, Jun 18 '15 at 13:37
@Andrey well, if you have any recommendation, I'll be glad to take a look to it ! — Thomas Ayoub, Jun 18 '15 at 14:24
@Thomas https://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers — Andrey, Jun 18 '15 at 14:27
@Andrey well I'm confused. I use a Sieve and both of your links points to a Sieve... Did I miss something? — Thomas Ayoub, Jun 18 '15 at 14:55
@Thomas you are right, I thought I was there something more efficient. Well, if you want to use sieve for such large numbers you need to implement pagination and store unused pages on disk. — Andrey, Jun 18 '15 at 15:31

score 8 · Accepted Answer · edited Jun 18 '15 at 13:21

8

100000000000 bools means ~93 GB of memory. You only have @50 GB (including the default allocated virtual memory).

Storing them as bits (not as bytes), would get you down to ~12GB.

Look at System.Collection.BitArray

edited Jun 18 '15 at 13:21

Rohit Vipin Mathews

11,629
15
57
112

answered Jun 18 '15 at 13:19

Andrei Tătar

7,872
19
37

Create huge dictionary

1 Answers1