Benchmarking. Введение для начинающих

С таким понятием, как измерение производительности рано или поздно сталкивается, наверное, абсолютно каждый программист.

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

Инструментарий

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

Date

Нативная структура данных описывающая дату/время.
Все замеры сводятся к тому, что мы замеряем дату перед функцией, затем дату после функции, и берем разницу.
Стоит ли говорить, что ни о какой избыточной точности таких замеров не может идти речи из-за особенности хранения даты в ОС.

Системные часы инициализируются от аппаратных при загрузке операционной системы, и далее системное время поддерживаются с помощью регулярных прерываний от таймера. (Wikipedia)

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

Единственный случай, где Date может пригодиться, это если вы заменяете скрипты, которые выполняются по несколько секунд, и разница в 100 мс для вас не играет никакой роли. Я вообще не рекомендую пользоваться Date для замеров.

Performance.now()

Возвращает временную метку измеряемую в миллисекундах с точностью до одной тысячной миллисекунды.

Для Node.js измерение идет с отсчетом от начала выполнения текущего потока выполнения, а для браузеров от события PerformanceTiming.navigationStart.

Замер времени выполнения функции выглядит вот так:

    const start = performance.now();    myAwesomeFunc();    const end = performance.now();    // Переводим в секунды    const diffSec = (end - start) / 1000;    // Выводим кол-во выполнений в секунду.    console.log('op/sec: ' + (1 / diffSec);

Мне приятнее сравнивать числа в формате op/sec, нежели в виде 0.00000546654.

Performance.now() не только точнее чем Date, но и куда удобнее. Вам не придется проводить каких-либо дополнительных манипуляций с переводом даты в timestamp и обратно, вы сразу получаете число в удобных единицах измерения.

Benchmark.js

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

    var suite = new Benchmark.Suite;    // add tests    suite.add('RegExp#test', function() {        /o/.test('Hello World!');    })    .add('String#indexOf', function() {        'Hello World!'.indexOf('o') > -1;    })    .add('String#match', function() {        !!'Hello World!'.match(/o/);    })    // add listeners    .on('cycle', function(event) {        console.log(String(event.target));    })    .on('complete', function() {        console.log('Fastest is ' + this.filter('fastest').map('name'));    })    // running    .run();

Benchmark.js довольно гибко позволяет писать тесты. Я вообще использую их в связке с mocha, чтобы их можно было удобно запускать в нужных папках, не запуская при этом ненужные.

Распространенные Ошибки

Замеры производительности только кажутся простым делом. На самом деле есть много подводных камней, которые могут испортить вам всю малину: от компилятора и самого js, до операционной системы.

Оптимизация компилятора

Ошибка характерная только для микробенчмарков и можно ее выразить во фразе:

Хочешь рассмешить компилятор покажи ему микробенчмарки, которые собираешься сделать.

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

Функция для замера

    function checkLen(array: number[]) {        let len = 0;        for (let i = 0; i< 1_000_000; i++) {            len = array.length;        }        return len;    }

Результат*: 720.4278 op/sec

*- Этот и все нижеприведенные результаты являются средним значением для тысячи вызовов.

Это количество вызовов функции за секунду, если вас интересует результат по получении поля то надо это время домножить на миллион.

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

На самом деле в итоговом значении еще учитывается стоимость вызова функции и стоимость итерации, но это, пожалуй, мелочи.

Так вот, казалось бы в чем проблема Hrodvitnir? А в том, что это все наглая ложь и не правда. Давайте-ка, запустим вот эту функцию:

    function checkLen(array: number[]) {        let len = 0;        len = array.length;        for (let i = 0; i< 1_000_000; i++) {        }        return len;    }

Результат: 718.3247 op/sec

А теперь внимание вопрос: мы один раз обратились к полю и выполнили на две операции в секунду меньше.

Ну давайте честно: две операции разницы это разница в 0.28%, и мы можем этим смело пренебречь, и считать оба этих результата эквивалентными. А вот это, в свою очередь должно нас озаботить.

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

И это не единственный вариант, как такое может произойти.
Компилятор умеет манипулировать кодом в циклах, умеет встраивать функции, и т. д. Конкретно эта оптимизация называется LICM.

Вместо этого, мы можем проверить обращение к полю вот так:

    function checkLen(        array: number[],        len: number[] // массив на 1000000 элементов        ) {        for (let i = 0; i< 1_000_000; i++) {            len[i] = array.length;        }        return len;    }

Результат: 330.0807

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

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

Замер одних и тех же данных

Это та ошибка, которая водила меня некоторое время за нос.

В качестве аргумента выступает массив от 1 до 1,000,000.

    const testArray = _.range(1, 1_000_000).toArray();    // Массив со значениями от 1 до 1,000,000

Ниже приведен метод из моей библиотеки, которым мы отфильтровываем все нечетные значения:

    function checkFilter(array: number[]) {        return _(array).where(item => !!(item % 2)).toArray()    }

Результат: 23.4559

В общем-то, неплохо, быстрее даже чем нативный filter и быстрее, чем lodash.
Мы с вами, даже это проверили в статье Нативный не значит быстрый

Но если мы замерим эту функцию на еще раз на неотсортированном массиве, то получим уже вот такой результат:

Результат: 13.3961

На неотсортированном массиве фильтрация идет в два раза дольше. При чем и у меня, и у lodash, и у нативной реализации.
А казалось, всего-то проверили на другом массиве.

Однократный замер

Давайте снова обратимся к замеру отсортированного массива из предыдущего примера и сделаем несколько разовых замеров:

Как видите, первый замер отличается от последнего более чем в два раза, при этом среднее неумолимо отклоняется от первой строчки.

Давайте отметим, это не 10 замеров подряд, это 10 запусков скрипта с одним замером.

Разница так велика, банально, оттого, что замеры происходят при разной загрузке ЦП.
Кроме того, мы замеряем не боевую функцию, а "холодную", ту, что выполняется интерпретируемо, а не ту, что уже скомпилирована в байт-код. В общем, все говорит о том, что разовые замеры не говорят ни чего о том, как эта функция будет вести себя в бою.

Замер в разных условиях

Эта ошибка косвенно связана с предыдущей: делайте замеры выключив все лишние программы.
Чем чище диспетчер задач тем лучше.
Просто, если вы делаете замеры, а параллельно открываете/закрываете браузер, играете в игры и т. д., то, я готов поспорить, что некоторые бенчмарки наверняка покажут причудливые результаты.
Желательно вообще никак не трогать машину. Чем меньше взаимодействия с ней, тем точнее результаты.

Хорошие практики

С вариантами, как запороть тесты мы разобрались, теперь давайте поговорим о том, как сделать их репрезентативнее.

Профилактика оптимизаций компилятора

(О боже, я сказал это вслух).

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

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

Иными словами:
Лучше делать так:

    function checkFilter(array: number[]) {        return _(array).where(item => !!(item % 2)).toArray()    }

Чем так:

    function checkFilter(array: number[]) {        _(array).where(item => !!(item % 2)).toArray()    }

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

Замеры на разных данных

Если ваш код многозадачен, а под этим я подразумеваю то, что он используется на разных данных, то проверяйте на его на всевозможных разных данных.
Я поясню, проверяйте на лучших из возможных, на худших из возможных, проверяйте на наборе из средних данных. У вас должна быть полноценная картина о том, насколько ваш код хорош.
В этом плане бенчмарки, как юнит-тесты покрытие должно быть полным.
В моей библиотеке используется паттерн стратегия и при определенных длинах массивов выбираются определенные алгоритмы и вследствие этого я делаю проверки на массивах длинными от 10,000,000 до 75 элементов.
Возможно вы назовете это избыточным, но я хочу видеть динамику времени работы методов от количества элементов.

Замеры на боевых данных

Нет лучше данных для проверки, чем данные из продакшена. Особенно, если они покрывают лучшие и худшие варианты.
Если лучшие и худшие варианты априори не возможны, то можно их пропустить.
Если мы проверяем производительность функции, которая обрабатывает нажатие клавиш в текстовое поле из расчета, что клавиши будут нажиматься не чаще, чем 10 символов в секунду, то нет смысла проверять на частоте в 200 символов в секунду.

Да и вполне вероятно, если пользователь вбивает 200 символов в секунду, ему скорее нужен врач, чем отзывчивый интерфейс.

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

Ведение статистики

Мало собрать данные по производительности кода. Надо их еще правильно обработать, чтобы сделать корректные выводы.

Я, лично, работаю с межквартильным средним.

Формула проста удаляем 25% самых медленных значений, удаляем 25% самых быстрых значений, а для оставшихся высчитываем среднее. Это позволяет удалить выбросы из выборки и оценивать результаты по средним значениям.

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

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

Интерпретация значений

У нас есть функция:

    function checkFilter(array: number[]) {        return _(array).where(item => !!(item % 2)).toArray()    }

У нее есть результат:

Результат: 23.4559

А теперь давайте подумаем: это много или мало? Вот на машине помощнее будет в два раза быстрее, а на машине послабее в два раза медленнее. И что нам делать?

Нужен этанол эталон. Выбирать можно какие-то нативные вещи или какие-то аналогичные реализации вашего функционала. Например, для своей библиотеки я выбрал нативные методы класса Array и lodash, и, при разработке ориентируюсь на них.
Возможно это будет ранее написанный вами функционал, и тогда вы сможете оценивать прогресс/регресс вашего кода.

Итоги

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

Спасибо за внимание!