Ленивость в бою

В уроке 08 ленивость была моделью вычислений: граф из thunk-ов, две глубины готовности, sharing. Красивая теория. Сегодня она становится тем, чем бывает в проде: иногда честным преимуществом, а иногда утечкой памяти, из-за которой сервис падает по OOM на третьи сутки работы. Разберём, как thunk-и копятся, какими рычагами их прибивают (seq, deepseq, bang-паттерны, строгие поля), во что физически компилируется ленивость в куче GHC, как снять и прочитать профиль памяти и как вообще отлаживать то, чего на экране не видно.

Идея

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

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

Space leak это не ошибка в логике. Тесты зелёные, ответ верный. Сломан профиль памяти: программа держит разросшийся граф thunk-ов вместо компактного значения. Самое коварное в том, что на маленьких входах всё работает, а на проде с реальным объёмом данных сервис тихо распухает. Поэтому ленивость в бою это в первую очередь умение такие места видеть и измерять, а уже потом чинить.

Утечка крупным планом

Канонический пример из урока 05 в одну строку: foldl (+) 0 [1 .. n] строит аккумулятор как (((0 + 1) + 2) + 3) + ..., гигантский отложенный thunk, и держит его в куче целиком до конца списка. Лечится foldl' или строгим аккумулятором. Это ты уже умеешь. Но в реальном коде утечка редко так очевидна. Посмотрим на три места, где она прячется лучше.

Ловушка пары: WHNF это не до конца

Среднее арифметическое одним проходом. Кажется, что foldl' тут спасёт, ведь он строгий.

import Data.List (foldl')

-- всё равно течёт
meanLazy :: [Double] -> Double
meanLazy xs =
  let (total, count) = foldl' step (0, 0) xs
   in total / count
  where
    step (s, c) x = (s + x, c + 1)

foldl' форсирует аккумулятор на каждом шаге, но только до WHNF, до внешнего конструктора. А внешний конструктор пары это (,). То есть foldl' доводит аккумулятор до (_, _) и останавливается, а оба компонента s + x и c + 1 внутри остаются thunk-ами и копятся как ни в чём не бывало. Получаем две горки вместо одной. Урок 08 предупреждал об этом, теперь видим во всей красе: лозунг “foldl' строгий” опасен, если не помнить, до какой глубины он строгий.

Лечение это форсировать сами компоненты, а не только конструктор пары:

{-# LANGUAGE BangPatterns #-}

meanStrict :: [Double] -> Double
meanStrict xs =
  let (total, count) = foldl' step (0, 0) xs
   in total / count
  where
    step (!s, !c) x = (s + x, c + 1)

Bang-паттерны на !s и !c форсируют поля до WHNF при каждом заходе. Теперь в куче лежат два числа, а не две цепочки сложений. Запомни диагностику: строгость до внешнего конструктора не означает строгость внутри. Для пары, записи, Maybe, любого составного типа надо думать на уровень глубже.

Ленивая Map: thunk застрял в значении

Подсчёт частот. Классика, и классическая же течь.

import qualified Data.Map.Lazy as Map
import Data.List (foldl')

-- течёт: значения это отложенные (+)
counts :: [String] -> Map.Map String Int
counts = foldl' (\m w -> Map.insertWith (+) w 1 m) Map.empty

Здесь foldl' честно строгий, и сама Map на каждом шаге доводится до WHNF. Но insertWith (+) из Data.Map.Lazy кладёт в значение отложенное old + 1, не считая его. Встретили слово сто раз, и в ячейке лежит башня из ста вложенных (+), которая досчитается, только когда карту распечатают. Структура карты компактна, а вот её значения текут.

Лечение одно слово в импорте:

import qualified Data.Map.Strict as Map
-- всё остальное без изменений

Data.Map.Strict форсирует значения до WHNF при вставке, и old + 1 считается на месте. Тот же API, та же сложность, ноль thunk-ов в значениях. Правило на будущее: любой накопитель в Map (счётчики, агрегаты) это Data.Map.Strict, а Data.Map.Lazy бери осознанно, когда значение реально дорогое и может не понадобиться. Подробнее про устройство Map и выбор контейнера в уроке 33.

Рентген через :sprint

Прежде чем чинить, утечку надо увидеть. Самый дешёвый микроскоп это :sprint в ghci из урока 08: он печатает значение, не форсируя его, и показывает невычисленные части как _.

ghci> import qualified Data.Map.Strict as MS
ghci> import qualified Data.Map.Lazy as ML
ghci> let lazy = ML.insertWith (+) "a" 1 (ML.singleton "a" 10)
ghci> :sprint lazy
lazy = fromList [("a",_)]
ghci> let strict = MS.insertWith (+) "a" 1 (MS.singleton "a" 10)
ghci> :sprint strict
strict = fromList [("a",11)]

Вот она, разница, прямо на ладони. У ленивой карты значение _, отложенный thunk. У строгой там уже 11. Когда подозреваешь утечку в накопителе, :sprint это первое, что стоит сделать: если видишь _ там, где ждёшь готовое значение, ты нашёл копящийся thunk. В большой программе так не походишь, для неё есть профайлер ниже, но в ghci на сжатом примере :sprint ставит диагноз за секунды.

Лестница строгости

Рычаг форсирования из урока 08 был один (seq), но он ступенчатый, и теперь нужна вся лестница. Снизу вверх, по глубине.

seq доводит первый аргумент до WHNF, до внешнего конструктора, и возвращает второй. $! это то же самое в форме применения: f $! x форсирует x до WHNF, потом применяет f. Bang-паттерн !x это синтаксический сахар для seq в сопоставлении. Все трое останавливаются на внешнем конструкторе. Для Int, Double, любого простого значения этого хватает: их WHNF и есть готовое значение. Для составных типов, как мы только что видели на паре, нет.

Когда нужно прогнать до самого дна, до NF, в дело идёт верхняя ступенька, пакет deepseq.

import Control.DeepSeq (deepseq, force, NFData, rnf)

deepseq это seq до упора: форсирует первый аргумент до NF рекурсивно и возвращает второй. force x это тот же deepseq, направленный на само значение: то же x, но при первом же касании оно посчитается целиком. А f $!! x это $! для глубокой строгости. Работает всё это через класс NFData, и для своих типов его не пишут руками, а выводят:

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveAnyClass #-}

import GHC.Generics (Generic)
import Control.DeepSeq (NFData)

data Stats = Stats
  { total :: Double
  , count :: Int
  , maxSeen :: Double
  }
  deriving stock (Show, Generic)
  deriving anyclass NFData

Две строки deriving подряд это не опечатка, а первое появление стратегий вывода. До сих пор (вспомни урок 07) мы писали просто deriving (Eq, Ord, Show) и не спрашивали, откуда компилятор берёт код. На самом деле способов несколько, и с расширением DerivingStrategies ты говоришь, какой именно нужен. Их четыре:

• stock это встроенные деривации GHC, ровно та механическая генерация из структуры типа, что и в уроке 07: Eq, Ord, Show, Functor, а ещё Generic. Тут компилятор сам знает, как написать инстанс.
• anyclass (расширение DeriveAnyClass) даёт пустое тело инстанса, а методы берутся из умолчаний самого класса. Именно так выводится NFData: его rnf определён один раз поверх Generic, поэтому твоему типу хватает deriving stock Generic рядом, а сам NFData получается даром.
• newtype (GeneralizedNewtypeDeriving) переиспользует инстанс обёрнутого типа. Понадобится в уроке 39, когда newtype App будет наследовать способности у ReaderT.
• via (DerivingVia) выводит инстанс через выбранный тип-представитель: «веди себя как вот этот тип».

Почему вообще выбирать руками: для одного класса могут подойти сразу две стратегии, и без явного слова GHC не знает, что ты имел в виду. Например, Generic и встроен в stock, и формально подходит под anyclass. Пара deriving stock (Show, Generic) против deriving anyclass NFData снимает двусмысленность и заодно документирует намерение: первое компилятор строит из структуры, второе это пустышка поверх Generic. Поэтому в проде ты почти всегда увидишь deriving с явной стратегией, а не голый список классов.

Теперь force someStats или acc \deepseq` next` прогонят запись до дна.

Важная оговорка, чтобы не натворить нового зла. deepseq не бесплатен: он обходит всю структуру целиком при каждом вызове. Поставить force на каждый чих это не “сделать быстро”, а добавить лишний полный проход и иногда испортить ровно ту ленивость, что держит бесконечные структуры (force по бесконечному списку зависнет навсегда). Правило: форсируй точечно и до нужной глубины. Чаще всего лекарство это bang-паттерн на аккумуляторе или Data.Map.Strict, а deepseq достают, когда в аккумуляторе сидит составная структура, которую seq не дотягивает до дна. Самый частый честный случай для force это граница: значение возвращают из чистого кода в IO (или отправляют в другой поток), и нужно, чтобы вся работа случилась здесь, а не утекла отложенным thunk-ом в неожиданное место. Про эту границу подробнее в уроке 35.