Javascript Increase max array size

Question

I am trying to create an array of size 2^32 = 4294967296, because I am trying to get all the prime numbers till 2^32 by running the sieve algorithm. However any operation in that array I get the following error:

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory

Abort trap: 6

What can I do in above situation?

That's 4 billion elements. Why do you need an array that size? — Andy, Apr 09 '16 at 22:03
I'd suggest that you explain the actual problem you're trying to solve so we can offer you other ways to solve it besides allocating a ginormous array. — jfriend00, Apr 09 '16 at 22:21
Basically, I am trying to get all the prime numbers up to 2^32 by running sieve. — Muhammad Raihan Muhaimin, Apr 09 '16 at 23:04

score 10 · Accepted Answer · answered Apr 09 '16 at 22:52

10

Arrays can't be that big, the maximum length is 2³²-1. According to ECMAScript spec,

Every Array object has a length property whose value is always a nonnegative integer less than 2³².

A String property name P is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 2³²−1.

answered Apr 09 '16 at 22:52

Oriol

274,082
63
437
513

Think his tag is `node.js` and the story is different than. – skobaljic Apr 09 '16 at 23:24
@skobaljic Node.js is an ECMAScript implementation. – Oriol Apr 09 '16 at 23:33
Guess you know better. As far as I know it is just built on Javascript's engine and you can extend it many ways, far different than Javascript in browser. – skobaljic Apr 10 '16 at 00:02

score 7 · Answer 2 · answered Apr 09 '16 at 22:04

7

An array of 2^32 elements is basically 4 GB * size of an element, so there are high chances it will not fit into memory.

The error you are getting is exactly that: the allocator cannot allocate enough space. You might want to consider another solution than allocating a several gigabytes array. Having a little more detail about what you are trying to achieve could help putting you on the right track! :)

answered Apr 09 '16 at 22:04

christophetd

3,834
20
33

I am trying to get all the prime numbers till 2^32 and trying to run the sieve algorithm. – Muhammad Raihan Muhaimin Apr 09 '16 at 23:02
There's a high chance it will not fit into memory because of an artificial limitation... – Lu4 Oct 22 '19 at 22:13

score 4 · Answer 3 · answered Apr 09 '16 at 22:18

4

For node.js just install big-array.

A resizable array using non-sequential block memory allocation. Growing or shrinking the array does not require reallocation of the entire array. Useful when you need to track a few trillion data points.

answered Apr 09 '16 at 22:18

skobaljic

9,379
1
25
51

Chris Hartwig · Answer 4 · 2016-04-10T12:45:01.317

For a sieve algorithm, you need just one bit for each number to test...

Look for a bitset implementation (https://github.com/tdegrunt/bitset for instance). This one will grow dynamically as you set bits in it. You can set and get bits, and each bit will tell you if n is a prime.

However, I recommend you test with max 100, not 2^32... because it will be slow...

Actually, bitset breaks between 10M and 100M on my Mac. I guess they don't use a byte array.

In coffee-script because it's less verbose...

Bitset = require 'bitset'

sieve = (maxSize)=>

    mark = (bitset)->
        markMultiplesOf = (n)->
            bitset.set(n*each) for each in [2..(maxSize / n)]

        markMultiplesOf each for each in [2..(maxSize / 2)] when bitset.get(each) is false

    showPrimes = (bitset)->
        console.log each for each in [0..(bitset.length())] when bitset.get(each) is false

    timestamp = Date.now()

    bitset = new Bitset(maxSize)
    mark bitset, maxSize

    console.log "took #{Date.now() - timestamp} ms"
    showPrimes(bitset)

sieve(10000000) # takes < 4s

Javascript Increase max array size

4 Answers4

Linked