Memory consumption of sparse arrays in Node.js

Question

I have written a small program that produces arrays, which runs quite long (almost forever ;-)):

var results = [];
var i = 1;

while (true) {
  console.log(i++);
  results.push([]);
}

When, instead of an empty array, I create a sparse array of length i, the program crashes quite fast:

var results = [];
var i = 1;

while (true) {
  console.log(i);
  results.push(new Array(i++));
}

Actually I get up to i equal to 17424, then I get an error message telling me

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory
Abort trap: 6

and Node.js takes me back to the console. Since the only difference is that the second one produces "larger" empty arrays than the first ones, this implies that an empty sparse array of length n takes up n times the space of an empty array with length 1.

Am I right about this (specifically to Node.js)?

One more question: If I run

var results = [];
var i = 1;

while (true) {
  console.log(i);
  var temp = [];
  temp[i++] = i;
  results.push(temp);
}

then I get up to 1286175, then it again crashes with:

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - process out of memory
Abort trap: 6

Why does this behave differently than the other two options?

PS: I am using Node.js 0.12.0 to run this on OS X.

Stannfield

I fail to see the sparse array. You might want to remove that tag. – Alto

Answer 1

When you declare an array with a size

Array(1024);

You are doing so that it allocates space for 1024 elements. It has to allocate this space up-front, because this form of declaring an array is an optimization stating

"I need you to reserve 1024 locations so that you aren't constantly resizing the array as I push more elements onto it".

As you probably know, declaring an array with simply [] still allows you to push unlimited number of elements onto it, however the array is silently being resized (most likely memcpy()) behind the scenes to allow this behaviour.

EDIT:

The reason you get much higher iterations in your second example, is because you are now using a sparse array. With a sparse array doing

var arr = []
arr[1000000] = 1;

Does not mean your array is now using 1,000,000 entries in memory. Contrast this to a dense array

var arr = Array(1000000);

Which explicitly tells the runtime to reserve an array that can store 1000000 entries in memory.

Related StackOverflow question: https://mcmap.net/q/146505/-are-javascript-arrays-sparse

Harilda

Btw, if you use big indices in your sparse arrays you might experience this bug, so beware :) – Zed

Array(1024) does not have to allocate space. All it has to do is set the length value, and in V8 this creates a sparse/holey array that can be slower to use. – Amortize

Answer 2

V8, the JS engine in Node, uses 4 bytes for each element in a seemingly empty array. The best way to find this out for certain is by creating empty arrays in Chrome and using the profiler to see how much additional size the array has used up. See https://developer.chrome.com/devtools/docs/heap-profiling for details on how you can do this...

Achromatic