Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Memory consumption of sparse arrays in Node.js

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.

like image 989
Golo Roden Avatar asked Apr 23 '15 06:04

Golo Roden


People also ask

How much memory does node js take?

By default, Node. js (up to 11. x ) uses a maximum heap size of 700MB and 1400MB on 32-bit and 64-bit platforms, respectively.

How is memory allocated for arrays in JavaScript?

Javascript allocates a contiguous memory for 'arr' after reading the first statement. Then javascript reads the second statement and allocates the memory for that element in memory. But here is the thing, it will not allocate memory for index 3 to index 49. Instead it will just allocate memory for index 50.

What is a sparse array JS?

What are sparse arrays? A sparse array is one in which the elements are not sequential, and they don't always start at 0. They are essentially Array s with "holes", or gaps in the sequence of their indices. So an example would be: let array = []; array[100] = "Holes now exist"; array. length // 101, but only 1 element.

What is sparse and dense array?

A sparse array is an array of data in which many elements have a value of zero. This is in contrast to a dense array, where most of the elements have non-zero values or are “full” of numbers. A sparse array may be treated differently than a dense array in digital data handling.


2 Answers

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://stackoverflow.com/a/1510842/276949

like image 169
14 revs, 12 users 16% Avatar answered Oct 13 '22 05:10

14 revs, 12 users 16%


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...

like image 32
Hamza Kubba Avatar answered Oct 13 '22 05:10

Hamza Kubba