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

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



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

Игра 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.

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

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

RUVDS.com
1 048,37
RUVDS – хостинг VDS/VPS серверов
Поделиться публикацией

Похожие публикации

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

    +12

    Вообще говоря, любое преждевременное что-то — зачастую корень бед, и оптимизация тут не стоит особняком. Я бы даже сказал, что сейчас маятник качнулся в другую сторону, и никакая оптимизация не выполняется даже там, где она нужна. Тормозящие сайты и непропорциональный рост системных требований это подтверждают.

      +4
      Не совсем так. Преждевременная оптимизация (о которой говорит Кнут) — это не про процесс оптимизации вообще (математической или инженерной), это, скорее, про мыслительные паттерны, когда вместо реализации бизнес-логики программист начинает заморачиваться на тактах и байтах. Написал for вместо forEach, например, чтобы сэкономить на тактах, а в итоге убил возможность скомпозировать функции на более абсраткнтом уровне, уровне бизнес-логики, на котором оптимизация могла бы вообще радикально поменять цикломатическую сложность алгоритма. Тормозащие сайты и непропорциональный рост системных требований — это отчасти и есть следствие преждевременной оптимизации, оптимизации локальных мест, построенных не на реальных метриках использования ресурсов, а на суевериях программиста. И именно эти оптимизации и налипают как снежный ком на кодовую базу, делая её непригодной для правильной, полезной оптимизации.
        +2

        На кризис ожиревших сайтов и 80 XHR запросов в Gmail явно повлияли преждевременные микрооптимизациии, в самом-то деле

          +1
          Легко понять что преждевременная оптимизация приводит к таким же результатам как отсутствие оптимизации, для этого достаточно вспомнить что ресурсы используемые для создания программы всегда ограниченны.
          Начали оптимизировать до того как поняли где же находятся ботлнеки системы — потратили время бесполезно. Пришло время релиза и откладывать уже ничего нельзя, система выходит как есть.
            0

            Всё же если говорить об оптимизации вычресурсов, то без преждевременной оптимизации ко времени релиза должно быть больше функциональности и/или меньше багов. Другое дело, что можно получить "кирпич" когда дело дойдёт до рабочих нагрузок.

          0
          Мне кажется это обоюдная проблема, когда не хотят оптимизировать и оптимизируют заранее. Например используя для реализации заранее «оптимизированное» API или оборудование. Которое для какой то рекламируемой задачи оптимально, но для поставленной — реализуется с костылями.
            0
            У нас есть «пример безпримерного примера» — игра Stalker. Когда вместо того, чтобы делать собственно игру и приближать релиз разработчики пилили кучу механик, каждую из которых хотели сделать идеальной. Пока не пришлось издатель и не выкинул половину этого всего в мусорку, но зато игра таки релизнулась.
          +6
          Интересно, что мешало запустить профилировщик?
            +7

            NIH-синдром

            +2
            Тут ещё интересно не только то, как быстрее работают эти функции, а ещё как потом движок работает с тем, что они создали. Например, гугловцы крайне рекомендуют использовать мономорфные объекты — то есть те, у которых в одних и тех же полях одни и те же типы данных. Причём даже не обычные типы, а те что использует движок. Так 32-битное целое (smi) — это тип, отличный от 64-битного с плавающей запятой (float).

            Если в массив, который состоял из целых чисел, добавляется дробное, то движок пересоздаёт объект. А если массив создан сразу с дырками, то у него изначально будет менее оптимальная структура. Увы, код
            new Array(arr.length);
            делает именно это. Такая деоптимизация может съесть всю выгоду от быстрых методов. Бенчмарки такое не показывают, нужны более изощрённые тесты, а лучше — профилирование.
              +2
              Я думаю стоит разделять оптимизацию на спичках и заложенную архитектуру с учётом повышенных требований к производительности.
              Если изначально известно что будет требоваться высокая производительность то лучше это учесть заранее. В геймдеве, например, переделать на data oriented design после будет сложнее чем заранее.
              Важно понимать где именно узкое место в производительности, в некоторых случаях это можно определить заранее.
                +4
                Преждевременная оптимизация времен Кнута и сейчас — это две большие разницы.

                И применительно к JS это выглядит как издевка.
                  –1
                  А может изначально не нужно писать ресурсоемкие игры на скриптовых тормозах и убожествах типа JS?
                  На худой конец уже давно как появился WebAssembly.
                    –1
                    У меня в Palemoon нет никакого WebAssembly.
                      +1
                      В IE 7 и в каком-нибудь Dillo тоже нет. Но это не значит, что нужно на них ориентироваться.

                      WASM, кстати, можно fallback'ать в asm.js, он везде поддерживается (правда, само собой, не настолько эффективно).
                      0

                      Брать WebAssembly там где он не нужен – еще одна преждевременная оптимизация. Вот пример.

                        0
                        Так дело не в языке, а в прокладке между креслом и монитором. Производительный код в любом случае требует более аккуратного подхода и больше времени. Но если не знать язык и техники оптимизации, не уметь профилировать, то ничего не выйдет, независимо от языка.
                        0

                        Такое ощущение, что нынче вообще мало кто об оптимизации кода думает — хоть преждевременной, хоть своевременной. По крайней мере в сфере сайтостроения это постоянно вижу. Куда проще посоветовать заказчику железа прикупить.

                          0
                          Потому что оптимизация затрат важнее оптимизации кода в наши дни.
                            +1

                            Оптимизация затрат {для бизнеса) всегда была важнее. Просто раньше оптимизация кода была эффективным способом оптимизировать затраты, а то и доходы (программа, которая не поместится в 105 байт никаких доходов вообще не принесёт), а в наши дни зачастую есть более эффективные способы оптимизироаать расходы и доходы.

                          +1
                          С той далекой поры, как Кнут сказал эти слова, у него накопились приличные проценты по техническому долгу
                            0
                            Статья хорошая и актуальная, но если бы не существовало профилировщиков...вот более актуальная и полезная статья по этой теме с примерами и подробным разбором профилирования JavaScript. Умение пользоваться профилировщиком — это база для любого разработчика и чем раньше это понять, тем более качественней будет Ваш код.
                              +2

                              Беда только в том, что часто профайлер показывает более-менее равномерную размазанность медленности по большому куску кода (когда каждый отдельно взятый вызов занимает не больше 1%, например), и становится непонятно, как оптимизировать.

                                0

                                Так смысл статьи в том, что прежде чем что-то оптимизировать нужно стратегически убедиться, что оптимизируешь узкое место. С помощью профилировщика убеждаться, бенчмарков или ещё как — это тактика.

                                +2
                                А по-моему автор перепутал преждевременную оптимизацию с необоснованной (назовём так) :)
                                Имхо, случай преждевременной оптимизации — это когда в процессе написания кода жертвуешь его ясностью и временем на имплементацию в угоду воображаемой эффективности. А когда код уже написан — без профилирования что-то оптимизировать — это необоснованная.
                                  +1

                                  Мне вообще не кажется корректным называть оптимизацией изменения, которые на скорости работы программы сказались никак.

                                  +1
                                  В моём, почти 20-летнем опыте разработки, ни разу не было задачи что-то оптимизировать, что ранее было сделано неоптимально. Всем нужны новые фичи, а не красивый и быстрый код или архитектура. И если изначально что-то не написать оптимально, оно ни когда не будет оптимизировано. Но надо понимать, что всё не оптимизируешь, понимать, где будет нагрузка, что даст оптимизация и во что эта оптимизация обойдётся.

                                  Между чёрным и белым очень много оттенков серого, для кого-то один код будет преждевременной оптимизацией, для кого-то нет, все мы пишем по-разному.
                                    0
                                    В моём, почти 20-летнем опыте разработки, ни разу не было задачи что-то оптимизировать, что ранее было сделано неоптимально.
                                    стесняюсь спросить, но все же — какая область? какой язык программирования?
                                      +2
                                      В основном C/C++, PHP, MySQL, системы управление рекламой. Были ASP, PHP, Java, Node.js, MSSQL Server, Oracle и всякое другое…
                                      0
                                      Значит или вы не писали ничего, что работает в реалтайме, или эта статья именно для вас, особенно с учетом вашего утверждения
                                      если изначально что-то не написать оптимально, оно ни когда не будет оптимизировано.
                                        0
                                        А я смотрю, вы удачно подобрали ник :)
                                      +1

                                      Для меня ценная мысль в том, что не проверив гипотезу — не двигайся вперед. Гуру берут в руки отладчик и профилируют ночами на пролет RC релизы, факт.

                                        0
                                        Это же не преждевременная оптимизация, если бы автор оптимизировал еще в процессе написания кода — была бы она.

                                        А так это просто оптимизация основанная на субъективный характеристиках (жопой чую, тормозят массивы!), когда объективные характеристики (данные профилировщика) показывают абсолютно другое (а массивы то там почти и не используются...)

                                        В целом очень актуальная статья, много раз замечал это среди коллег, да и сам ловил себя на таком разок. Практически всегда это обусловленно лишь тем, что человек просто хочет попробовать новую технологию/расширить резюме, а тут еще повод какой, оптимизация. «Тормозит сайт? А давайте Монгу прикрутим, будет намного быстрее!». Так и тут, автору было настолько интересно написать кодогенерацию, чтобы обойти смый быстрый фреймворк, что он даже не подумал про замеры. Но это не преждевременная оптимизация, нет.
                                          0

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

                                            0

                                            Некоторым приходит, пускай не в тактах, а микросекнудах или и того меньше...


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

                                              0
                                              Сейчас никому не придет в голову считать каждый байт и каждый такт до того как в этом возникнет острая необходимость.

                                              Вы недооцениваете человечество.

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое