понедельник, 13 февраля 2017 г.

Про преждевременную оптимизацию

Большинство программистов считает, что преждевременная оптимизация  зло. Они рассуждают в следующем ключе: для бизнеса важнее написать работающую программу и побыстрее, поэтому пишем неоптимизированный код, а потом, если будет тормозить, то возьмём профайлер и оптимизируем горячие места.
Мне кажется, в этих рассуждениях упущен один важный момент: когда вы начнёте оптимизировать программу, может случиться так, что вы не найдёте очевидных мест просадки производительности (или после оптимизации программа будет всё равно работать медленно). Просто неэффективный код будет размазан по всему проекту.
Допустим, рендеринг страницы состоит из последовательного вызова 30 функций. Тогда общее время рендеринга будет равно (t1 + Δt1) + (t2 + Δt2) + ... (t30 + Δt30), где ti  время выполнения оптимизированной функции, а ti + Δti – время выполнения неоптимизированной функции. Тогда просадка производительности будет равна Δt1 + Δt2 + ... + Δt30. Благо, если вы найдёте большие Δti, виновные в тормозах приложения. А если все Δti приблизительно одного порядка? Тогда придётся анализировать весь код, что может быть очень затратно. Одно дело – сразу оптимизировать код во время написания, другое – оптимизировать этот же код спустя пару месяцев, когда все детали успешно забыты.
Так что же делать? Однозначного ответа на этот вопрос нет. Я стараюсь поступать следующим образом. При написании программы я оптимизирую код, если:
  • переписанный код не потеряет в надёжности, безопасности и читаемости по сравнению с оригинальным неоптизированным кодом,
  • переписывание кода не займёт у меня слишком много времени,
  • я точно уверен, что переписывание действительно улучшит быстродействие приложения.
Например, если я знаю, что в ArrayList'е всегда будет лежать как минимум несколько тысяч элементов, то я заменяю вызов дефолтного конструктора ArrayList'а на конструктор с указанием initialCapacity. Такая замена тривиальна и нисколько не ухудшает читаемость кода, зато может сэкономить пару микросекунд времени выполнения алгоритма.
Или, например, HashMap<Integer, Integer> я заменяю на TIntIntMap из trove4j. В этом случае безопасность даже повышается, т.к. у TIntIntMap сигнатуры более строгие, чем у Map, и не позволяют, к примеру, написать map.containsKey("abc").
Самое трудное – это выполнить третий пункт. Дело в том, что очень часто трудно понять, имеет ли вообще смысл оптимизация, ведь современные компиляторы сложны и непредсказуемы. И поэтому в кодах программ встречается огромное количество бессмысленных оптимизаций, в результате чего в среде программистов и сложилось мнение, что вообще все преждевременные оптимизации зло. Но ведь не все оптимизации бессмысленны, верно?

понедельник, 14 сентября 2015 г.

Поездка на Пихтовый Гребень

12 сентября в субботу наша группа любителей велопокатушек устроила очередную вылазку на природу. Так как кататься по окрестностям Академгородка нам надоело, то на этот раз мы решили выбраться куда-нибудь подальше и предприняли попытку заехать на одну из высочайших вершин Новосибирской области – Пихтовый Гребень (аж целых 494 метра).

Для читателей разного уровня ленивости я выкладываю два варианта отчёта о поездке: сокращённый и полный.


Сокращённый

Мы не доехали.


Полный

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

Где-то в 12:45 мы приехали на территорию горнолыжного комплекса "Юрманка", где полюбовались красотою осеннего вида горы Глухариная, собрали велосипеды и поехали.

Расстояние до Гребня было 32 км. Если ехать со стандартной средней скоростью велосипеда в 15 км/ч, то это приблизительно 2 часа до Гребня и 2 часа обратно. Однако оказалось, что местность и рельеф в окрестностях Пихтового Гребня довольно сильно отличаются от того, к чему мы привыкли, поэтому средняя скорость оказалась не 15 км/ч, а где-то 7 км/ч.

Первая же преграда оказалась буквально через несколько километров после старта: река Ик, через которую не было моста. Однако погода стояла тёплая, поэтому ребята не испугались, сняли кроссовки и смело пошли вброд:

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

Ещё через несколько километров мы опять наткнулись на Ик. Я сразу подумал: зачем какой-то дурак проложил дорогу так, что она два раза пересекает одну и ту же реку.

Не проехав и пятидесяти метров после брода, мы наткнулись на какой-то мелкий приток Ика, не отмеченный на карте:

Мелкий приток оказался коварной речкой – его небольшая ширина создала ложное впечатление, что его можно преодолеть прямо на велосипеде, что и попытался сделать Лёха (предварительно разогнавшись до большой скорости). Итог: брызги и замоченные шорты. Далее Люда, чтобы не нести кроссовки на себе, попыталась их перебросить на другой берег, но неудачно замахнулась и кроссовок улетел в Ик. В этот момент у меня ёкнуло сердце, так как я думал, что кроссовок сейчас уплывёт, и кому-то придётся догонять его вплавь. К счастью, кроссовок попал на кочку, и Лёха героически пошёл в кусты его доставать:

Далее было ещё два брода, много сложных подъёмов и грязи (несмотря на то, что всю неделю до этого стояла тёплая сухая погода).

В 17:00 мы вновь наткнулись на Ик:

На Ике мы встретили толпу квадрациклистов, возвращавшихся с Гребня, которые сказали нам, что видели свежие следы медведя. Тут я окончательно понял, что Гребень нам не светит, и мы развернулись. Пока мы ехали обратно, мы придумывали тактику отбивания от медведя.

В 20:00 мы были в Юрманке.

P.S. Серёга всю дорогу ехал без футболки:

пятница, 21 августа 2015 г.

Про tail call elimination или почему с диалектами Haskell нужно быть осторожным

В последнее время развелось много различных диалектов Haskell: PureScript, Frege, GHCJS, Elm, Haste и т.д.

В этой статье мы рассмотрим, насколько ли хорошо эти диалекты пригодны для функционального программирования. Анализ мы будем проводить с точки зрения наличия в компиляторах этих языков одной важной для функционального программирования оптимизации – устранения хвостовых вызовов (tail call elimination, далее TCE).

Мотивация

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

isOdd x = if (x == 0) then False else isEven (x - 1)
isEven x = if (x == 0) then True else isOdd (x - 1)

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

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

match :: Eq a => [a] -> [a] -> [a] -> Bool
match list list1 list2 = match1 list where

    match1 [] = True
    match1 list | list1 `isPrefixOf` list = match2 $ drop (length list1) list
    match1 _ = False

    match2 [] = True
    match2 list | list2 `isPrefixOf` list = match1 $ drop (length list2) list
    match2 _ = False

Например, если вызвать match с аргументами [1,1,2,1,1,2] [1,1] [2], то он вернёт True.

Ещё один пример – свёртка списка функций в одну функцию:

composeAll :: [Int -> Int] -> (Int -> Int)
composeAll [] = id
composeAll (x:xs) = composeAll xs . x

Этот пример сворачивает список функций [f1, f2, ... , fn] в одну функцию fn ∘ ... ∘ f2 ∘ f1, т.е. каждая функция вызывает следующую функцию в хвостовой позиции. Для того чтобы конечная функция не упала с переполнением стека на большом списке, компилятор должен поддерживать TCE.

Далее мы рассмотрим, насколько хорошо поддерживают TCE различные диалекты Хаскелля.

PureScript

PureScript – это строгий диалект Хаскелля, транслирующий в JavaScript. Установку PureScript я выполнил по этой инструкции и реализовал вышеописанные примеры.

Пример с isOdd и isEven выглядит следующим образом:

import Prelude
import Data.List
import Control.Monad.Eff.Console

isOdd n = if n == 0 then false else isEven $ n - 1
isEven n = if n == 0 then true else isOdd $ n - 1

main = isOdd 1000000 # show # log

Функции isOdd и isEven транслировались вот в такой JS-код:

var isOdd = function (n) {
    var _0 = n === 0;
    if (_0) {
        return false;
    };
    if (!_0) {
        return isEven(n - 1);
    };
    throw new Error("Failed pattern match: " + [ _0.constructor.name ]);
};
var isEven = function (n) {
    var _1 = n === 0;
    if (_1) {
        return true;
    };
    if (!_1) {
        return isOdd(n - 1);
    };
    throw new Error("Failed pattern match: " + [ _1.constructor.name ]);
};

Как видно, никакой TCE здесь не пахнет. Запуск этой программы через Node.js (который не поддерживает TCE) падает с ошибкой переполнения стека:

var isEven = function (n) {
                      ^
RangeError: Maximum call stack size exceeded
    at isEven (D:\temp\purescript\output\Main\index.js:16:23)
    at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
    at isEven (D:\temp\purescript\output\Main\index.js:22:16)
    at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
    at isEven (D:\temp\purescript\output\Main\index.js:22:16)
    at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
    at isEven (D:\temp\purescript\output\Main\index.js:22:16)
    at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
    at isEven (D:\temp\purescript\output\Main\index.js:22:16)
    at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
* ERROR: Subcommand terminated with error code 1

Второй пример я реализовывать не стал, но зато реализовал третий:

composeAll :: List (Int -> Int) -> (Int -> Int)
composeAll Nil = id
composeAll (Cons x xs) = composeAll xs <<< x

fs :: List (Int -> Int)
fs = replicate 100000 (+1)

main = 100 # composeAll fs # show # log

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

Frege

С Хаскеллем под JVM всё обстоит почти так же плохо, как и с PureScript. JVM, как и Node.js, не поддерживают TCE, а значит TCE ложиться на плечи транслятора в Java. Но Frege выполнил эту задачу лишь частично. Из трех примеров без StackOverflowError выполнился только первый. Второй и третий упали приблизительно с такой ошибкой:

java.lang.StackOverflowError
 at frege.runtime.Fun1$1.eval(Fun1.java:63)
 at frege.runtime.Delayed.call(Delayed.java:198)
 at frege.runtime.Delayed.forced(Delayed.java:257)
 at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4921)
 at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4915)
 at frege.runtime.Fun2$1.eval(Fun2.java:58)
 at frege.runtime.Fun1$1.eval(Fun1.java:63)
 at frege.runtime.Delayed.call(Delayed.java:198)
 at frege.runtime.Delayed.forced(Delayed.java:257)
 at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4921)
 at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4915)
 at frege.runtime.Fun2$1.eval(Fun2.java:58)
 at frege.runtime.Fun1$1.eval(Fun1.java:63)
 at frege.runtime.Delayed.call(Delayed.java:198)
 ...

Elm и Haste

Elm и Haste – ещё два диалекта Haskell, транслирующиеся в JS (первый строгий, второй ленивый). Elm упал с переполнением стека на примере с isOdd и isEven. Haste упал на втором примере со списком из 500 тыс. значений.

GHCJS

Последняя надежда осталась на GHCJS – транслятор Haskell в JS. Особенность это транслятора заключается в том, что он полностью совместим с Хаскеллем, в отличие от всех вышеперечисленных диалектов. Также он поддерживает практически все стандартные модули Haskell. Из минусов этого компилятора – большой размер сгенерированных js-файлов, в которых невозможно разобраться, и медленный старт, а также сложность установки GHCJS (я так и не смог установить GHCJS под Windows, пришлось тестировать на Linux).

Все три примера успешно скомпилировались через GHCJS "как есть". Сгенерированный код я запускал через Node.js, и во всех трёх случаях код отрабатывал без ошибок, какие бы большие числа/списка я не подсовывал.

Итог

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