Не попадайте в ловушку преждевременной оптимизации

Дональд Кнут однажды сказал слова, ставшие впоследствии знаменитыми: «Настоящая проблема заключается в том, что программисты, не там, где нужно, и не тогда, когда нужно, тратят слишком много времени на заботу об эффективности. Преждевременная оптимизация — корень всех зол (или, по крайней мере, большей их части) в программировании».



Автор материала, перевод которого мы сегодня публикуем, хочет рассказать о том, как он однажды попал в ловушку преждевременной оптимизации, и о том, как он на собственном горьком опыте понял, что преждевременная оптимизация — это корень всех зол.

Игра GeoArena Online

Несколько лет назад я работал над веб-игрой GeoArena Online (потом я её продал, новые владельцы разместили её на geoarena.io). Это была мультиплеерная игра, в стиле «последний, оставшийся в живых». Там игрок управлял кораблём, сражаясь один на один против другого игрока.


Игра GeoArena Online


Игра GeoArena Online

Работа динамичной игры, мир которой полон частиц и эффектов, требует серьёзных вычислительных ресурсов. В результате игра на некоторых старых компьютерах «подтормаживала» в особо напряжённые моменты. Я — человек, неравнодушный к вопросам производительности, с интересом взялся за решение этой проблемы. «Как мне ускорить клиентскую JavaScript-часть GeoArena», — спросил я себя.

Библиотека fast.js

Поискав немного в интернете, я обнаружил библиотеку fast.js. Она представляла собой «коллекцию микро-оптимизаций, нацеленных на упрощение разработки очень быстрых JavaScript-программ». Ускорения программ эта библиотека добивалась за счёт наличия в ней более быстрых реализаций встроенных стандартных методов наподобие Array.prototype.forEach().

Мне это показалось крайне интересным. В GeoArena использовалось множество массивов, выполнялось много операций с массивами, поэтому применение fast.js вполне могло помочь мне в деле ускорения игры. В README к fast.js были включены следующие результаты исследования производительности forEach().

Native .forEach() vs fast.forEach() (10 items)
  ✓  Array::forEach() x 8,557,082 ops/sec ±0.37% (97 runs sampled)
  ✓  fast.forEach() x 8,799,272 ops/sec ±0.41% (97 runs sampled)

  Result: fast.js is 2.83% faster than Array::forEach().

Как метод, реализованный в некоей внешней библиотеке, может быть быстрее его стандартной версии? Всё дело в том, что тут была одна хитрость (они, эти хитрости, встречаются везде, куда ни глянешь). Библиотека подходила только для работы с массивами, которые не были разреженными (sparse).

Вот пара простых примеров таких массивов:

// Это - разреженный массив: по индексу 1 ничего нет.

const sparse1 = [0, , 1];
console.log(sparse1.length); // 3

// Это - пустой массив
const sparse2 = [];

// ...а теперь он - разреженный. По индексам 0 - 4 в нём ничего нет.

sparse2[5] = 0;
console.log(sparse2.length); // 6

Для того чтобы понять — почему библиотека не может нормально работать с разреженными массивами, я заглянул в её исходный код. Оказалось, что реализация forEach() в fast.js основана на циклах for. Быстрая реализация метода forEach() при этом выглядела примерно так:

// Ради краткости код немного упрощён.
function fastForEach(array, f) {
  for (let i = 0; i < array.length; i++) {
    f(array[i], i, array);
  }
}

const sparseArray = [1, , 2];
const print = x => console.log(x);

fastForEach(sparseArray, print); // Вызывает print() 3 раза.
sparseArray.forEach(print); // Вызывает print() только 2 раза.

Вызов метода fastForEach() приводит к выводу трёх значений:

1
undefined
2

Вызов же sparseArray.forEach() приводит лишь к выводу двух значений:

1
2

Это различие появляется из-за того, что спецификации JS, касающиеся использования функций-коллбэков, указывают на то, что такие функции не должны вызываться на удалённых или неинициализированных индексах массивов (их ещё называют «дырами»). Реализация fastForEach() не выполняла проверку массива на наличие «дыр». Это вело к повышению скорости ценой корректности работы с разреженными массивами. Мне это идеально подходило, так как в GeoArena разреженные массивы не использовались.

В этот момент мне следовало бы просто устроить быстрое тестирование fast.js. Мне стоило бы установить библиотеку, поменять стандартные методы объекта Array на методы из fast.js и испытать производительность игры. Но вместо этого я двинулся в совсем другую сторону.

Моя разработка, названная faster.js

Маниакальный перфекционист, живущий во мне, хотел выжать из оптимизации производительности игры абсолютно всё. Библиотека fast.js попросту не казалась мне достаточно хорошим решением, так как её использование подразумевало вызов её методов. Тогда я подумал: «А что если я заменю стандартные методы массивов, просто встроив в код новые, более быстрые реализации этих методов? Это избавило бы меня от необходимости в вызовах библиотечных методов».

Именно эта мысль привела меня к гениальной идее, которая заключалась в создании компилятора, который я нагло назвал faster.js. Его я планировал использовать вместо fast.js. Например, вот исходный фрагмент кода:

// Исходный код
const arr = [1, 2, 3];
const results = arr.map(e => 2 * e);

Этот код компилятор faster.js преобразовывал бы в следующий — более быстрый, но выглядящий хуже:

// Результат преобразования кода с помощью faster.js
const arr = [1, 2, 3];
const results = new Array(arr.length);
const _f = (e => 2 * e);
for (let _i = 0; _i < arr.length; _i++) {
  results[_i] = _f(arr[_i], _i, arr);
}

К созданию faster.js меня подтолкнула та же идея, которая лежала в основе fast.js. А именно, речь идёт о микро-оптимизациях производительности за счёт отказа от поддержки разреженных массивов.

На первый взгляд faster.js казался мне чрезвычайно успешной разработкой. Вот некоторые результаты исследования производительности faster.js:

  array-filter large
    ✓ native x 232,063 ops/sec ±0.36% (58 runs sampled)
    ✓ faster.js x 1,083,695 ops/sec ±0.58% (57 runs sampled)
faster.js is 367.0% faster (3.386μs) than native

  array-map large
    ✓ native x 223,896 ops/sec ±1.10% (58 runs sampled)
    ✓ faster.js x 1,726,376 ops/sec ±1.13% (60 runs sampled)
faster.js is 671.1% faster (3.887μs) than native

  array-reduce large
    ✓ native x 268,919 ops/sec ±0.41% (57 runs sampled)
    ✓ faster.js x 1,621,540 ops/sec ±0.80% (57 runs sampled)
faster.js is 503.0% faster (3.102μs) than native

  array-reduceRight large
    ✓ native x 68,671 ops/sec ±0.92% (53 runs sampled)
    ✓ faster.js x 1,571,918 ops/sec ±1.16% (57 runs sampled)
faster.js is 2189.1% faster (13.926μs) than native

Полные результаты испытаний можно посмотреть здесь. Они проводились в среде Node v8.16.1, на 15-дюймовом MacBook Pro 2018.

Моя разработка на 2000% быстрее стандартной реализации? Столь серьёзный прирост производительности — это, без всякого сомнения, то, что способно оказать сильнейшее позитивное влияние на любую программу. Верно?
Нет, не верно.

Рассмотрим простой пример.

• Представим, что средняя игра GeoArena требует 5000 миллисекунд (мс) вычислений.
• Компилятор faster.js ускоряет выполнение методов массивов, в среднем, в 10 раз (это — приблизительная оценка, к тому же — завышенная; в большинстве реальных приложений нет даже двукратного ускорения).

А вот вопрос, который нас реально интересует: «Какая часть из этих 5000 мс тратится на выполнение методов массивов?».

Предположим, что половина. То есть — 2500 мс уходит на методы массивов, остальные 2500 мс — на всё остальное. Если так, то применение faster.js даст огромнейший прирост производительности.


Условный пример: время выполнения программы очень сильно сократилось

В результате оказывается, что общее время выполнения вычислений сократилось на 45%.

К несчастью, все эти рассуждения очень и очень далеки от реальности. В GeoArena, конечно, используется много методов массивов. Но настоящее распределение времени выполнения кода по разным задачам выглядит примерно так, как показано ниже.


Суровая реальность

Печально — что тут сказать.

Это — именно та ошибка, о которой предупреждал Дональд Кнут. Я приложил усилия не к тому, к чему их стоило бы прикладывать, и сделал это не тогда, когда это стоило бы делать.

Тут в дело вступает простая математика. Если нечто занимает лишь 1% времени выполнения программы, то оптимизация этого даст, в самом лучшем случае, лишь 1% увеличения производительности.

Именно это имел в виду Дональд Кнут, когда говорил «не там, где нужно». А если подумать о том, что такое «там, где нужно», то окажется, что это те части программ, которые представляют собой «узкие места» производительности. Это те фрагменты кода, которые вносят значительный вклад в общую производительность программы. Здесь понятие «производительность» используется в очень широком смысле. Оно может включать в себя и время выполнения программы, и размер её скомпилированного кода, и что-нибудь другое. 10% улучшение в том месте программы, которое очень сильно влияет на производительность — это лучше, чем 100% улучшение в какой-нибудь мелочи.

Кнут ещё говорил о приложении усилий «не тогда, когда нужно». Смысл этого в том, что оптимизировать нечто нужно только тогда, когда это необходимо. Конечно, у меня была веская причина задуматься об оптимизации. Но вспомните о том, что я занялся разработкой faster.js и перед этим даже не попробовал испытать в GeoArena библиотеку fast.js? Минуты, потраченные на тестирование fast.js в моей игре помогли бы мне сэкономить недели работы. Надеюсь, вы не попадёте в ту же ловушку, в которую попал я.

Итоги

Если вам интересно поэкспериментировать с faster.js — можете взглянуть на эту демонстрацию. То, какие результаты вы получите, зависит от вашего устройства и браузера. Вот, например, что получилось у меня в Chrome 76 на 15-дюймовом MacBook Pro 2018.


Результаты испытания faster.js

Возможно, вам интересно узнать о реальных результатах применения faster.js в GeoArena. Я, когда ещё игра была моей (как я уже говорил, я её продал), провёл некоторые базовые исследования. В результате выяснилось следующее:

• Использование faster.js ускоряет выполнение главного игрового цикла в типичной игре примерно на 1%.
• Из-за применения faster.js размер бандла игры вырос на 0.3%. Это немного замедлило загрузку страницы игры. Размер бандла вырос из-за того, что faster.js преобразует стандартный краткий код в код более быстрый, но и более длинный.

В целом, у faster.js есть свои плюсы и минусы, но эта моя разработка не оказала особого влияния на производительность GeoArena. Я бы понял это гораздо раньше, если бы потрудился сначала протестировать игру с использованием fast.js.

Пусть моя история послужит вам предостережением.

Уважаемые читатели! Попадали ли вы в ловушку преждевременной оптимизации?