# Глава 18. Space leak Да, я должен рассказать вам правду: есть у ленивой стратегии вычислений тёмная сторона, получившая название space leak (букв. «утечка пространства»). И вот в чём её суть. ## Причины space leak [Вспомним](/courses/haskell/chapters/haskell_chapter_0170#block-strange) пример с делением: ```haskell {.example_for_playground .example_for_playground_001} main :: IO () main = print . strange $ 2 `div` 0 ``` Как мы помним, деления на ноль так и не произошло за ненадобностью его результата. В этом случае выражение осталось в виде thunk. Возникает вопрос: что же с ним стало? У нас есть функция `div` и есть два значения типа `Int`, `2` и `0`. Если функция `div` так и не была применена к ним, где же всё это хозяйство находилось в процессе работы нашей программы? Оно находилось в памяти, в виде особого графа, который можно изобразить так: ``` ┌─────────────┐ │ div │ │ │ └─────────────┘ │ │ v v ┌───┐ ┌───┐ │ 2 │ │ 0 │ └───┘ └───┘ ``` То есть сама функция и два значения, которые должны были занять место двух её аргументов. И вот этот граф в памяти так и остался невостребованным. Казалось бы, ну и в чём проблема? А проблема в количестве. Если мы смогли написать код, при работе которого в память отложился один thunk, значит теоретически мы можем написать и такой код, количество thunk-ов при работе которого будет исчисляться миллионами. А учитывая тот факт, что каждый thunk занимает в памяти хотя бы несколько байт, вы можете себе представить масштаб проблемы. Причём возникнуть эта проблема может из весьма невинного на первый взгляд кода: ```haskell bad :: [Int] -> Int -> Int bad [] c = c bad (_:others) c = bad others $ c + 1 ``` Простенькая рекурсивная функция, пробегающаяся по ненужному ей списку и увеличивающаяся свой второй аргумент на единицу. Но я не просто так назвал её `bad`. Давайте применим её: ```haskell bad [1, 2, 3] 0 ``` Подставим в определение, содержащее зацикливание: ```haskell bad (_: others) c = bad others $ c + 1 bad [1, 2, 3] 0 = bad [2, 3] $ 0 + 1 ``` «Голова» списка откусывается и игнорируется, а к `0` прибавляется `1`. Но поскольку результат сложения пока что никому не нужен, сложение не производится. Вместо этого, на второй итерации, мы видим следующее: ```haskell bad [2, 3] $ 0 + 1 = bad [3] $ (0 + 1) + 1 ``` К предыдущему выражению вновь прибавляется единица — и мы опять входим в очередную итерацию, так и не выполнив сложения: ```haskell bad [3] $ (0 + 1) + 1 = bad [] $ ((0 + 1) + 1) + 1 ``` Опа! Упёрлись в пустой список, вспоминаем правило выхода из рекурсии: ```haskell bad [] c = c ``` Итак, в этом случае мы просто возвращаем значение второго аргумента. Сделаем же это: ```haskell bad [] $ ((0 + 1) + 1) + 1 = ((0 + 1) + 1) + 1 = 3 ``` И вот только здесь мы реально вычисляем второй аргумент, складывая три единицы. Вы спросите, почему же мы накапливали эти сложения вместо того, чтобы делать их сразу? Потому что мы ленивы: раз результат сложения понадобился нам лишь на последней итерации, значит до этой итерации никакого сложения не будет, ведь лень вынуждает нас откладывать работу до конца. Вот в этом-то накоплении вся беда. Представим, что мы написали так: ```haskell main :: IO () main = print $ bad [1..50000000] 0 ``` 50 миллионов элементов, а значит, 50 миллионов раз сложение второго аргумента с единицей будет откладываться, накапливая гигантский «хвост» из (пока что) невычисленных выражений. Хотите знать, что произойдёт при запуске такой программы? Её выполнение, на MacBook Pro 2014 года, займёт приблизительно 63 секунды и скушает, ни много ни мало, 6,4 ГБ памяти! А теперь представьте, что случилось бы, если бы элементов в списке было не 50 миллионов, а 50 миллиардов... Иногда space leak ошибочно путают с другой проблемой, называемой memory leak (англ. «утечка памяти»), однако это вовсе не одно и то же. Утечка памяти — это ошибка, характерная для языков с ручным управлением памятью, например, C. Если мы выделим память в куче (англ. heap), а затем потеряем указатель, связывающий нас с этой памятью — всё, выделенная память утекла, она потеряна для нас навеки. Но в случае space leak мы не теряем память: когда весь этот «хвост» из сложений в конце концов вычислится, память, занимаемая миллионами thunk-ов, освободится. Мы не теряем память, мы просто используем её слишком много. ## Борьба Проблема space leak вытекает из самой природы ленивых вычислений. Многие программисты, узнав об этой проблеме, отворачиваются от Haskell. Мол, если в этом языке можно легко написать код, сжирающий уймищу памяти, значит этот язык точно не подходит для серьёзного использования. Но не так страшен чёрт, как его малюют. Я расскажу о двух способах борьбы со space leak. Впрочем, с концептуальной точки зрения способ всего один. Задумаемся: если в примере выше лень явилась причиной откладывания сложений на потом, что же можно сделать? Ответ прост: мы должны убрать излишнюю ленивость и заменить её строгостью. В этом случае применение оператора сложения уже не будет откладываться до последнего, а будет производиться тут же, как в языках со строгой моделью вычислений. И как же мы можем разбавить лень строгостью? Вот два способа. ### Оптимизация Первый способа самый простой — оптимизация. Когда компилятор превращает наш код в программу, его можно попросить оптимизировать наш код, сделав его более эффективным, по тем или иным критериям. Чтобы попросить компилятор провести оптимизацию, мы должны использовать специальный флаг. Откроем сборочный файл нашего проекта `real.cabal`, найдём секцию `executable real-exe`, в которой есть строка: ```haskell ghc-options: ... ``` Эта строка содержит различные опции компилятора GHC, и оптимизационный флаг дописывается именно сюда. Попробуем подставить туда сначала флаг `-O0`, а затем `-O2`. Результаты запуска программы будут такими: ```bash Оптимизация Время Память -O0 63 c 6,4 ГБ -O2 3,2 с 104 кБ ``` Впечатляющая разница, не правда ли? Флаг `-O0` говорит компилятору о том, чтобы тот не производил никакую оптимизацию, в этом случае говорят о нулевом уровне оптимизации. Флаг `-O2`, напротив, устанавливает стандартный для production-проектов уровень оптимизации. Так вот при стандартном уровне компилятор способен распознать излишнюю ленивость в нашем коде и добавить чуток жадности. В примере выше компилятор увидит накопление thunk-ов сложения и пресечёт оное. Согласитесь, с гигабайтов прыгнуть сразу на килобайты — это круто. Так что же, проблемы нет? Ну, если оптимизация `-O2` и так стандартна — так давайте ставить её в наши проекты и забудем про space leak! К сожалению, не всё так просто. Во-первых, компиляторная оптимизация сродни чёрной магии, на неё трудно полагаться. Мы очень благодарны компилятору GHC за попытку помочь нам, но эта помощь не всегда соответствует нашим ожиданиям. И во-вторых, к сожалению, компилятор не всегда способен распознать излишнюю лень в нашем коде, и в этом случае нам приходится-таки прибегнуть ко второму способу борьбы со space leak. ### Вручную Вернёмся к определению функции `bad`: ```haskell bad :: [Int] -> Int -> Int bad [] c = c bad (_:others) c = bad others $ c + 1 ``` Проблема, как мы уже поняли, во втором аргументе. Именно `c + 1` приводит к накоплению thunk-ов. ```haskell bad others $ c + 1 ``` Превратим же злую функцию в добрую: ```haskell good :: [Int] -> Int -> Int good [] c = c good (_:others) c = good others $! c + 1 ``` Этот код даст нам приблизительно такой же выигрыш, что и оптимизация уровня `-O2`: секунды вместо минуты и килобайты вместо гигабайтов. Что же изменилось? Смотрим внимательно: ```haskell good others $! c + 1 ``` Вместо привычного оператора применения `$` мы видим оператор строгого применения `$!` (англ. strict application operator). Этот оператор говорит аргументу: «Забудь о лени, я приказываю тебе немедленно вычислиться до слабой головной формы». Вот потому-то наш «хвост» из thunk-ов и не будет накапливаться, ведь на каждой из 50 миллионов итераций будет происходить незамедлительное применение оператора сложения. Таким образом, заставить аргумент тут же вычислиться до слабой головной или нормальной формы можно как посредством того, что этот аргумент прямо сейчас кому-то понадобился, так и посредством строгого применения. Помните функцию `myLength` из задачи в главе про рекурсию? Она принимает список и возвращает его длину. А теперь напишите эту функцию так, чтобы функция не накапливала «хвост» из thunk-ов. {.task_text} ```haskell {.task_source #haskell_chapter_0180_task_0010} module Main where -- Your code here main :: IO() main = do print $ myLength [] print $ myLength [1] print $ myLength [1, 2, 3] print $ myLength [1, 2, 3, 4, 5, 6] ``` Воспользуйтесь оператором строго применения `$!`. {.task_hint} ```haskell {.task_answer} module Main where myLength :: [Int] -> Int myLength [] = 0 myLength (_:t) = 1 + (myLength $! t) main :: IO() main = do print $ myLength [] print $ myLength [1] print $ myLength [1, 2, 3] print $ myLength [1, 2, 3, 4, 5, 6] ``` ## Лень и строгость вместе Функцию называют ленивой по тем аргументам, которые не вычисляются, и строгой по тем аргументам, которые вычисляются. Примитивный пример: ```haskell fakeSum :: Int -> Int -> Int fakeSum x _ = x + 100 ``` Функция `fakeSum` строга по своему первому аргументу и ленива по своему второму аргументу. Первый аргумент `x` непременно будет вычислен, ведь он передаётся оператору сложения. Второй же аргумент игнорируется, оставшись невычисленным. И кстати, существует простой способ проверить, строга ли функция по некоторому аргументу или ленива. В стандартной библиотеке Haskell определена особая функция `undefined`. Это — чёрная дыра: при попытке прикоснуться к ней программа гарантированно падает с ошибкой. Проверяем: ```haskell {.example_for_playground .example_for_playground_002} main :: IO () main = print $ fakeSum 1 undefined ``` В этом случае мы получим результат: ```bash 101 ``` Чёрная дыра была проигнорирована, ведь функция `fakeSum` ленива по второму аргументу. Если же мы напишем так: ```haskell {.example_for_playground .example_for_playground_003} main :: IO () main = print $ fakeSum undefined 45 ``` программа, попытавшись передать `undefined` оператору сложения, аварийно остановится. Что выведет этот код? В случае ошибки (в том числе из-за применения функции `undefied`) напишите `error`. {.task_text} ```haskell {.example_for_playground} module Main where main :: IO () main = print . head $ [23, undefined, undefined] ``` ```consoleoutput {.task_source #haskell_chapter_0180_task_0020} ``` Функция `head` строга лишь по первому элементу переданного ей списка, остальное содержимое оного её абсолютно не интересует. Но если попробуете вытащить второй или третий элемент из подобного списка — крах неминуем. {.task_hint} ```haskell {.task_answer} 23 ``` ## Для любопытных Haskell — не первый язык с ленивой стратегией вычислений. Открою вам исторический факт: у языка Haskell был предшественник, язык программирования с красивым женским именем [Miranda](https://en.wikipedia.org/wiki/Miranda_(programming_language)). Лень и чистая функциональность пришли в Haskell именно из Miranda, и лишь в этих двух языках ленивая стратегия вычисления аргументов используется по умолчанию. На сегодняшний день, насколько мне известно, язык Miranda мёртв. Впрочем, как сугубо исследовательский язык он, может быть, кем-то и используется. Что же касается проблемы space leak, то к счастью, существуют способы обнаружения функций, шибко прожорливых до памяти. В самом деле, представьте себе большой проект, тысячи функций, и что-то кушает гигабайты памяти. Как найти виновного? Этот процесс называют ещё «space leak профилированием». Рассказывать об этом здесь я не стану, материал довольно объёмный. Но для особо любопытных привожу ссылку на неплохую англоязычную статью по теме: [Chasing a Space Leak in Shake](http://neilmitchell.blogspot.am/2013/02/chasing-space-leak-in-shake.html). И ещё вспомним вот это: ``` square x = x * x / \ / \ / \ square $ 2 + 2 = (2 + 2) * (2 + 2) = 16 вычисляем и что, опять вычисляем?! ``` Внимательный читатель удивится, мол, неужели выражение `2 + 2` вычисляется дважды?! Ведь это нерационально. Конечно нерационально, поэтому в действительности оно будет вычислено единожды. В Haskell есть особый механизм «шаринга» (англ. sharing), позволяющий избежать напрасной работы. И если у нас есть несколько одинаковых выражений, вычисление оного происходит один раз, результат же сохраняется и потом просто подставляется в нужные места. Например: ```haskell main :: IO () main = let x = sin 2 in print x * x ``` Если бы не sharing-механизм, функция `sin` была бы применена к `2` дважды. К счастью, значение синуса будет вычислено единожды и тут же сохранено, чтобы потом просто встать на места тех двух `x`.