Math.max maximum call stack size exceeded [en]

Posted: March 14, 2021

Some days ago I worked with big arrays of about 2.000.000 elements. One of the operations to process the array was finding the maximum value.

Okay, it's not a problem. We can use Math.max:

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

Let's run the code:

An image from Notion

Wat? Maybe spread operator is a problem? We can replace it with apply:

An image from Notion

What was happen?

The first thing which strikes me 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 which is called by ourself and the second one which 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

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;
}

But even here we cannot die because of recursion (as we don't have it)

So, what was the problem?

To find out this, we can use the best tool which developers have. A long, patient look:

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

How this function is called?

When we call a function that has 2 arguments:

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

Primitive types are transmitted by their values. It means we will write to the call stack 2 numbers: 1 and 2.

Now, let's call the function using 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 heap, so the function receives only the reference to the array.

If you learned C++, it's likely, you remember how pointers work, how to get the element using the pointer, and so on. Modern languages hide all this work under the hood, but the essence is the same.

When we use apply or spread operator javascript converts each element from your Iterable object to a separate argument. You don't have any protection from unoptimized code

So when we call this code:

An image from Notion

In the third example, we transmit a million numbers as primitive types to our test function. Each array element is tried to be written 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 🙈

What about strings?

The strings are trickier. They have several features:

  1. Strings are immutable. When we use several "hello" strings all the variables will point to the same physical string. Changing the string (by adding a new char or moving chars, literally anything) will create a new string.
  2. Strings have the maximum length. Just as an instance:
An image from Notion

However, we store a lot of data:

An image from Notion

268Mb is not the maximum length, as with each cycle, we increase the string size by 2 times. Different js engines have different limitations. v8 has about 512Mb. Node.js has the same limitation: https://nodejs.org/api/buffer.html#buffer_buffer_constants

We can send lots of arrays to the function:

An image from Notion

And... everything will work. Why? As strings are immutable and the variable is just "a pointer where you can get a string" we don't send 8 times per 268 Mb to stack. We just send 8 pointers.