JS: Call stack size exceeded

ยท

3 min read

Some time ago I was working with big arrays of about 2.000.000 elements. One of the operations was to find the maximum value in the array.

Sounds simple, right? We can use Max.max:

const arr = new Array(2000000);
...
const max = Math.max(...arr);

However, if you try to execute it, you will have an error:

Math%20max%20maximum%20call%20stack%20size%20exceeded%20%5Bru%5D%20db4a5ad20eda400f9ae083b75022bc30/Untitled.png

Looks weird... Probably the issue is with the spread operator?

Math%20max%20maximum%20call%20stack%20size%20exceeded%20%5Bru%5D%20db4a5ad20eda400f9ae083b75022bc30/Untitled%201.png

No, it's not. So why do we have such an error?

The first thing I was thinking of is that the Math.max uses recursion.

However, it looks weird, that v8 developers could use recursion for that. Let's check it in v8 sources: https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021d964952728/src/builtins/math.tq#L134-L144

// ES6 #sec-math.max
extern macro Float64Max(float64, float64): float64;
transitioning javascript builtin
MathMax(js-implicit context: NativeContext)(...arguments): Number {
  let result: float64 = MINUS_V8_INFINITY;
  const argCount = arguments.length;
  for (let i: intptr = 0; i < argCount; i++) {
    const doubleValue = TruncateTaggedToFloat64(arguments[i]);
    result = Float64Max(result, doubleValue);
  }
  return Convert<Number>(result);
}

Of course, we have recursion here, but the depth of it is only 2 functions. The first one is MathMax and the second one compares exactly 2 values.

Maybe I have an old v8 version? We can dig into 2014-2015 chrome versions: https://chromium.googlesource.com/v8/v8/+/4.3.21/src/math.js?autodive=0%2F%2F#86 and we can see that the old implementation doesn't have recursion:

function MathMax(arg1, arg2) {  // length == 2
  var length = %_ArgumentsLength();
  if (length == 2) {
    arg1 = TO_NUMBER_INLINE(arg1);
    arg2 = TO_NUMBER_INLINE(arg2);
    if (arg2 > arg1) return arg2;
    if (arg1 > arg2) return arg1;
    if (arg1 == arg2) {
      // Make sure -0 is considered less than +0.
      return (arg1 === 0 && %_IsMinusZero(arg1)) ? arg2 : arg1;
    }
    // All comparisons failed, one of the arguments must be NaN.
    return NAN;
  }
  var r = -INFINITY;
  for (var i = 0; i < length; i++) {
    var n = %_Arguments(i);
    if (!IS_NUMBER(n)) n = NonNumberToNumber(n);
    // Make sure +0 is considered greater than -0.
    if (NUMBER_IS_NAN(n) || n > r || (r === 0 && n === 0 && %_IsMinusZero(r))) {
      r = n;
    }
  }
  return r;
}

So, what was the problem?

To find this out we can use the best tool which developers have. Let's take a long patient look once again:

const arr = new Array(2000000);
...
const max = Math.max(...arr);

How do we call this function?

When we call a function that has 2 Number arguments:

function test(a, b) {
}
test(1,2);

The arguments, which are primitive types, are transmitted by their values. We will write to the call stack 2 numbers: 1 and 2.

Now, let's call the function using the reference (object) type:

function test(a, b) {
}
test(new Array(2000000));

In this case, we create an array for 2.000.000 elements. Array elements are stored in the heap, and therefore the function receives only the reference to the array.

If you're interested in getting more information about Primitive and Reference types you can check this article: dev.to/xnimorz/javascript-memory-management..

๐Ÿ“ When we use apply or spread operator javascript converts each element from your Iterable object to a separate argument. And therefore you may pass not a reference, but a lot of primitive values.

When we call this code:

Math%20max%20maximum%20call%20stack%20size%20exceeded%20%5Bru%5D%20db4a5ad20eda400f9ae083b75022bc30/Untitled%202.png

In the third example, we transmit a million numbers as primitives to our test function. We try to write every single array element to the call stack. More info about the call stack: https://en.wikipedia.org/wiki/Call_stack#Structure

It's how we exceeded the call stack limit. Be careful with the spread operator ๐Ÿ™ˆ

ย