Как стать автором
Обновить

Комментарии 11

О, перевод очень клёвой статьи. Рекомендую к внимательному прочтению целиком.


@impwx, спасибо, теперь буду людей сюда посылать за версией на русском.

Давно такой годноты на хабре не видал. Хабр снова чуть чуть торт!
Спасибо!
Допустим теоретический пример:
function f(o) {
    let r = '';
    for(let key in o) {
        r += `${key} = ${o[key]}\n`;
    }
    return r;
}

// определяем рабочую переменную
let temp = {};
let result = [];

//первый набор данных
temp = {x:0, y:1};
//шаблонная работа с набором данных
result.push(f(temp));

//второй набор данных
temp = {a:1, b:2}
//шаблонная работа с набором данных
result.push(f(temp));
//и так далее, много разных наборов

Данные разные, но работа с ними примерно одинакова. Например, в jade, при определенном сценарии использования, по сути что-то такое и есть, когда на входе данные с атрибутами, а на выходе сформированная html строка

Получается, пока атрибуты примерно одинаковые (всегда только class или href), то всё работает быстро, как только начали в шаблонизатор попадать разнообразные атрибуты (хотя бы 1 раз на тысячу вызовов), f() переходит рано или поздно в «мегаморфизм» и оптимизации будут минимальны

И допустим, чтобы оставаться быстрым для стандартных случаев, уже нужно самим вводить вручную фильтрацию на атрибуты — если какой-то стандартный набор, то вызываем f1(), если что-то новенькое то f2(), если сходу видно что что-то экзотическое (допустим attributes.lenght > 5), то вообще f3(). При этом, естественно, f1(), f2(), f3() будут одинаковыми

Что-то в этом духе или это бессмысленно?
В данном примере, имхо, особого выигрыша в производительности от разделения на несколько функций не получите: все равно объекты будут заведомо произвольными, а определяющий конкретный вид функции код сам по себе тоже нужно выполнять. Зато абсолютно точно усложнится поддержка кода.

Но лучше всего устроить микробенчмарк и убедиться.

Написал тест и получил сперва неожиданный результат.


Если формируем объект вида {x: 1, [customProperty]: null} (где customProperty разный для всех объектов), то мегаморфный алгоритм выполняется даже быстрее мономорфного. Но если поменять поля местами, вот тогда скорость мегаморфного алгоритма падает, а мономорфного – не изменяется.


По всей видимости в первом случае ускорение возникает из-за того, что x – первое поле в объекте, а алгоритм кеширования медленнее, чем извлечение первого поля.


Для функции вида:


function test(x) {
    return x.x + x.x;
}

Результат перебора массива из 100 000 элементов:


Monomorphic x 2,213 ops/sec ±0.66% (80 runs sampled)
Polymorphic x 1,661 ops/sec ±0.71% (82 runs sampled)
Да, по поводу скорости работы с {x: 1, ...} автор упоминал:
С другой стороны, V8 может сформировать эффективное промежуточное представление, если поле располагается по одинаковому смещению во всех формах.

Для меня не очевидным осталось, что v8 дополнительно смотрит именно на определение объекта. А уже затем на набор полей как таковой. Обновил тест, добавив типизированный объект. Последний вариант оставил всех позади:


Monomorfic x 2,056 ops/sec ±0.79% (79 runs sampled)
Polymorfic x 1,573 ops/sec ±0.63% (79 runs sampled)
Typed x 2,540 ops/sec ±0.73% (82 runs sampled)

И почему-то даже для мономорфного объекта нахождение свойства x в начале списка полей сказывается негативно.

На самом деле ваш мегаморфный совсем отнюдь не мегаморфный, потому что в массиве poly встречаются объекты всего двух разных скрытых классов: с быстрыми элементами и с разреженными.

// запускать с --allow-natives-syntax для доступа к %HaveSameMap
let maps = [poly[0]];
for (let i = 1; i < poly.length; i++) {
  let found = false;
  for (let o of maps) {
    if (%HaveSameMap(o, poly[i])) {
        found = true;
        break;
    }
  }

  if (!found) maps.push(poly[i]);
}
console.log(maps.length);  // напечает 2


Происходит это потому, что V8 отделяет числовые свойства (т.е. свойствами с именами "0", "1", "2", ...) от других свойств. Сделано это для ускорения работы масивов.

Вам нужно написать что-нибудь типа poly[i]["k" + i] = null; для создания полноценного мегаморфизма.

Спасибо, за дополнение. Теперь результат оптимизации стал очевидным, а разница я бы сказал чудовищной:


Monomorfic x 2,046 ops/sec ±0.81% (78 runs sampled)
Polymorfic x 46.91 ops/sec ±0.90% (58 runs sampled)
Typed x 2,540 ops/sec ±0.99% (68 runs sampled)
Если посмотреть на код, который V8 делает для Typed и Monorphic бенчмарков, то оказывается, что он один и тот же. А производительность почему-то разная. А если переписать код

// Pregenerate objects
for (let i = 0; i < n; i++) {
  typed[i] = new Type(i);
}

for (let i = 0; i < n; i++) {
  poly[i] = {};
  poly[i]["k" + i] = null;
  poly[i].x = i;
}

for (let i = 0; i < n; i++) {
    mono[i] = {
        x: i,
        n: i, // Add n to balance memory usage
    };
}


то на моей машине внезапно все выравнивается, что намекает на какие-то мистические источники разницы.

Если переписать объявление полиморфного объекта на декларацию объекта:


poly[i] = {
    ['k' + i]: null,
    x: i,
};

То результат мономорфного и типизированного тестов так же выравнивается, что я тоже не могу объяснить.


P.S. В дополнение к материалу можно добавить еще один тест. В случае, когда использование объекта с переменным набором полей необходимо, лучше использовать Map (если это возможно). Производительность вырастает в 2-3 раза:


Objects x 44.69 ops/sec ±2.86% (53 runs sampled)
Maps x 120 ops/sec ±3.14% (63 runs sampled)
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории