Math.max maximum call stack size exceeded [ru]

Обсудить пост: https://t.me/fxnim/25

Некоторое время назад мне нужно было обработать массив. Большой массив на около 2.000.000 элементов. Чтобы понять, как эти элементы обрабатывать мне нужно было найти максимальное значение в этом массиве.

Что приходит самым первым в голову? Math.max:

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

Запускаем код:

Хммм, возможно дело в spread operator?

Как же так происходит?

Первое, что приходит в голову — Math.max использует рекурсию! Что я грешным делом и затвитил здесь:

https://twitter.com/nikmostovoy/status/1370420091360264194

Однако, в тот же день закралось сомнение. Ведь это крайне странно.

Хорошо, идем в исходники v8: 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);
}

Здесь конечно есть рекурсия, но ее глубина — только две функции. Одна — которую мы вызвали. Вторая — сравнение всегда 2 значений.

Окей, может быть у меня старая версия v8? Давайте посмотрим на версию хрома 2014-2015 года: 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;
}

Здесь мы тоже не можем умереть в рекурсии.

Так в чем же проблема?

Воспользуемся лучшим инструментом разработки. Долгим мучительным взглядом. Посмотрим еще раз на код:

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

Как происходит вызов функции?

Когда мы вызываем функцию от 2 аргументов:

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

Primitive type передается по значению. Это означает, что мы записываем в стек непосредственно два значения 1 и 2.

Давайте теперь вызовем функцию не используя primitive type.

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

В этом случае мы создаем массив на 2.000.000 элементов. Данные хранятся в куче (heap) и в функцию передается только ссылка на массив.

Если вы изучали C++, то скорее всего вспомните про работу указателей, разыменовывания и т.п.

Когда же мы используем apply или spread оператор javascript действительно честно превратит каждый элемент вашего Iterable объекта в отдельный аргумент. Никакой защиты "от дурака" язык не предоставляет. Таким образом вызвав этот код:

Мы в третьем примере взяли и передали миллион Number как primitive type в нашу test функцию. И каждый элемент массива попытался записаться в стек.

Вот таким образом мы и превысили call stack лимит. Будьте осторожнее со spread операторами 🙈

А что со строками?

Строки немного хитрее. У них есть несколько особенностей:

1. Строки иммутабельны по своей природе. Это означает, что если мы используем несколько строк "hello" все переменные будут указывать на одну и ту же "физическую" строку. Изменение строки (добавление нового символа, перестановка букв, что угодно) порождает новую строку.
2. У строк есть максимальная длина. Например, такой код упадет:

Причем мы успеем записать немало информации:

268Mb — это не максимальное ограничение строки, так как в нашем случае мы каждой операцией увеличивали размер строки в 2 раза (то есть мы не смогли задвоить размер). Например в v8 это около 512Mb. Больше про ограничения строка хорошо расписано у Ромы Дворнова: https://t.me/gorshochekvarit/106

Попробуем теперь передать эту радость в функцию:

И... все будет работать. Почему? Так как строки иммутабельны и переменная это только "указатель, откуда строку брать", то мы не отправляем 8 раз по 268Mb в стек. А отправляем только ссылки "откуда строку брать".