Обсудить пост: 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 операторами 🙈
Строки немного хитрее. У них есть несколько особенностей:
Причем мы успеем записать немало информации:
268Mb — это не максимальное ограничение строки, так как в нашем случае мы каждой операцией увеличивали размер строки в 2 раза (то есть мы не смогли задвоить размер). Например в v8 это около 512Mb. Больше про ограничения строка хорошо расписано у Ромы Дворнова: https://t.me/gorshochekvarit/106
Попробуем теперь передать эту радость в функцию:
И... все будет работать. Почему? Так как строки иммутабельны и переменная это только "указатель, откуда строку брать", то мы не отправляем 8 раз по 268Mb в стек. А отправляем только ссылки "откуда строку брать".