Haskell: как обнаружить «ленивые утечки памяти»

Question

После нескольких часов отладки я понял, что очень простой пример игрушки неэффективен из-за отсутствия ! в выражении return $ 1 + x (спасибо, duplode! ... но почему gh c не оптимизирует который??). Я также понял это, потому что я сравнивал его с кодом Python, который был быстрее, но я не всегда буду писать код Python для тестирования моего кода ...

Итак, вот мой вопрос: есть ли способ автоматически обнаруживать эти «ленивые утечки памяти», которые без реальной причины замедляют работу программы? Я по-прежнему не умею оптимизировать код Haskell, и, скорее всего, я забуду !, даже если у вас есть опыт.

Я знаю:

• +RTS -s, но я не уверен, как это интерпретировать: например, просмотр 79MB памяти для простой программы кажется мне огромным, но, возможно, это не то, что требует моя текущая программа ... а для более крупных программ невозможно просто обнаружить «ленивые утечки» таким образом, я полагаю, поскольку я понятия не имею, какой объем памяти должна занять моя программа.
• команда cabal v2-run --enable-profiling mysatsolvers -- +RTS -p, но кажется, что включение Profiler убивает некоторые оптимизации, сделанные GH C, и поэтому эти значения трудно использовать для реального теста. И все же мне непонятно, как найти утечки из этого вывода.

Не могли бы вы, например, объяснить мне, как я могу найти «ленивые утечки» в такой игрушечной программе?

{-# LANGUAGE DerivingVia, FlexibleInstances, ScopedTypeVariables #-}
module Main where

--- It depends on the transformers, containers, and base packages.
--- Optimisation seems to be important or the NoLog case will be way to long.
--- $ ghc -O Main.hs

import qualified Data.Map.Strict as MapStrict
import Data.Functor.Identity

import qualified Control.Monad as CM
import qualified Control.Monad.State.Strict as State
import qualified Data.Time as Time

-- Create a class that allows me to use the function "myTell"
-- that adds a number in the writer (either the LogEntry
-- or StupidLogEntry one)
class Monad m => LogFunctionCalls m where
  myTell :: String -> Int -> m ()

---------- Logging disabled ----------
--- (No logging at all gives the same time so I don't put here)
newtype NoLog a = NoLog { unNoLog :: a }
  deriving (Functor, Applicative, Monad) via Identity

instance LogFunctionCalls NoLog where
  myTell _ _ = pure ()

---------- Logging with Map ----------
-- When logging, associate a number to each name.
newtype LogEntryMap = LogEntryMap (MapStrict.Map String Int)
  deriving (Eq, Show)

instance LogFunctionCalls (State.State LogEntryMap) where
  myTell namefunction n = State.modify' $
    \(LogEntryMap m) ->
      LogEntryMap $ MapStrict.insertWith (+) namefunction n m

---------- Logging with Int ----------
-- Don't use any Map to avoid inefficiency of Map
newtype LogEntryInt = LogEntryInt Int
  deriving (Eq, Show)

instance LogFunctionCalls (State.State LogEntryInt) where
  myTell namefunction n = State.modify' $
    \(LogEntryInt m) -> LogEntryInt $! m + n

---------- Function to compute ----------
countNumberCalls :: (LogFunctionCalls m) => Int -> m Int
countNumberCalls 0 = return 0
countNumberCalls n = do
  myTell "countNumberCalls" 1
  x <- countNumberCalls $! n - 1
  return $ 1 + x

main :: IO ()
main = do
  let www = 15000000
  putStrLn $ "Let's start!"
  --- Logging disabled
  t0 <- Time.getCurrentTime
  let n = unNoLog $ countNumberCalls www
  putStrLn $ "Logging disabled: " ++ (show n)
  t1 <- Time.getCurrentTime
  print (Time.diffUTCTime t1 t0)
  -- Logging with Map
  let (n, LogEntryMap log) = State.runState (countNumberCalls www) (LogEntryMap MapStrict.empty)
  putStrLn $ "Logging with Map: " ++ (show n)
  putStrLn $ (show $ log)
  t2 <- Time.getCurrentTime
  print (Time.diffUTCTime t2 t1)
  -- Logging with Int
  let (n, LogEntryInt log) = State.runState (countNumberCalls www) (LogEntryInt 0)
  putStrLn $ "Logging with Int: " ++ (show n)
  putStrLn $ (show $ log)
  t3 <- Time.getCurrentTime
  print (Time.diffUTCTime t3 t2)

Answer 1

Основной метод обнаружения утечек памяти - это профилирование кучи. В частности, вы ожидаете неожиданного увеличения объема резидентной (в основном кучи) памяти, либо максимальной резидентности в выводе статистики +RTS -s, либо, что более надежно, характеристики c Форма «пирамиды» с течением времени в выводе профиля кучи, созданном с помощью флагов +RTS -h<x> и инструмента hp2ps.

Если я запустил вашу игрушечную программу с помощью +RTS -s, я увижу:

   3,281,896,520 bytes allocated in the heap
   3,383,195,568 bytes copied during GC
     599,346,304 bytes maximum residency (17 sample(s))
       5,706,584 bytes maximum slop
             571 MB total memory in use (0 MB lost due to fragmentation)

Первую строку вообще можно игнорировать. Haskell программы обычно выделяют примерно постоянный объем памяти в секунду во время выполнения, и эта скорость выделения либо почти равна нулю (для некоторых необычных программ), либо 0,5–2,0 гигабайта в секунду. Эта программа работала в течение 4 секунд и выделила 3,8 гигабайта, что не является необычным.

Байты, скопированные во время G C, и максимальное время хранения вызывают беспокойство. Предполагая, что у вас есть программа, которую вы ожидаете запускать в постоянном пространстве (т. Е. Нет постоянно растущей структуры данных, все содержимое которой необходимо), правильно функционирующая программа Haskell обычно не требует копирования большого количества данных во время сборки мусора и будет имеют тенденцию иметь максимальную резидентность, которая составляет небольшую часть от общего объема выделенных байтов (например, 100 килобайт, а не полгигабайта), и это не будет существенно расти с количеством «итераций» того, что вы тестируете.

Вы можете быстро создать профиль кучи с течением времени, не включая формальное профилирование. Если вы компилируете с флагом GH C -rtsopts, вы можете использовать:

./Toy +RTS -hT

, а затем отобразить результат графически с помощью инструмента hp2ps:

hp2ps -c -e8in Toy.hp
evince Toy.ps &

Это вид пирамиды - это красный флаг:

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

В стороне, ось x находится в «секундах MUT» (секундах работы «мутатора», что исключает сборку мусора ), поэтому это меньше, чем реальное время выполнения в 4 секунды. На самом деле это еще один красный флаг. Программа Haskell, которая тратит половину своего времени на сбор мусора, вероятно, работает некорректно.

Чтобы получить более подробную информацию о том, что вызывает эту пирамиду кучи, вам нужно скомпилировать с включенным профилированием. Профилирование может привести к замедлению работы программы, но обычно не меняет применяемые оптимизации. Однако флаг -fprof-auto (и связанные с ним флаги), который автоматически вставляет центры затрат, могут вызвать большие изменения производительности (вмешиваясь во встраивание и т. Д. c.). К сожалению, флаг cabal --enable-profiling включает профилирование (флаг компилятора -prof) и флаг -fprof-auto-top, который автоматически генерирует центры затрат для функций верхнего уровня, поэтому для вашего игрушечного примера это существенно изменится поведение вашего первого тестового примера (увеличение времени выполнения с 0,4 до 5 секунд, даже без флагов +RTS). Это может быть проблемой, с которой вы сталкиваетесь с профилированием, влияющим на ваши результаты. Вам не нужны какие-либо центры затрат для нескольких дополнительных видов профилей кучи, поэтому вы можете добавить флаг клики --profiling-detail=none, чтобы отключить его, и тогда ваша профилированная программа должна работать с синхронизацией немного медленнее, но в целом аналогичной производительности непрофилированной версия.

Я не использую Cabal, но компилирую со следующим (что должно быть эквивалентом --enable-profiling --profiling-detail=none):

ghc -O2 -rtsopts -prof Toy.hs    # no -fprof-auto...

Я могу запустить вашу программу с профилированием по данным введите:

./Toy +RTS -hy

Если я посмотрю на график профиля кучи:

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

Если я У меня действительно проблемы с сужением, и я чувствую себя как технический специалист, я также могу запустить профиль кучи путем закрытия (флаг -hd). Это говорит мне, что виноваты Main.sat_s7mQ и Main.sat_s7kP для двух пирамид соответственно. Это выглядит очень загадочно, но это имена функций в "STG", низкоуровневом промежуточном представлении моей программы, созданном компилятором.

Если я перекомпилирую с теми же флагами, но добавлю -fforce-recomp -ddump-stg -dsuppress-all:

ghc -O2 -rtsopts -prof -fforce-recomp -ddump-stg -dsuppress-all Toy.hs

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

Если я поискать в STG первого виновника, я нахожу определение:

sat_s7mQ =
    CCCS \u []
        case ww2_s7mL of {
          I# y_s7mO ->
              case +# [1# y_s7mO] of sat_s7mP {
                __DEFAULT -> I# [sat_s7mP];
              };
        };

Да, это все очень технически, но это STG-язык для выражения 1 + y, которое поможет мне сосредоточиться на виноват.

Если вы не говорите STG, вы можете попробовать ввести несколько центров затрат. Например, я пробовал профилировать только вашего второго тестового примера с помощью -fprof-auto (флаг Кабала --profiling-detail=all-functions). Выходные данные профиля в Toy.prof не являются , что полезно для утечек памяти, потому что он имеет дело с общим распределением вместо активного (т.е. резидентного, а не сборщика мусора) выделения с течением времени, но вы можете создать профиль кучи по МВЗ, запустив:

./Toy +RTS -hc

В этом случае он относит все к одному МВЗ, а именно (315)countNumberCalls. «315» - это номер центра затрат, который вы можете посмотреть во вводе Toy.prof, чтобы найти точные строки исходного кода, если это не ясно из названия. В любом случае, это, по крайней мере, помогает сузить проблему до countNumberCalls.

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

countNumberCalls :: (LogFunctionCalls m) => Int -> m Int
countNumberCalls 0 = return 0
countNumberCalls n = do
  {-# SCC "mytell_call" #-} myTell "countNumberCalls" 1
  x <- {-# SCC "recursive_call" #-} countNumberCalls $! n - 1
  {-# SCC "return_statment" #-} return $ {-# SCC "one_plus_x" #-} 1 + x

Это фактически приписывает все «recursive_call», так что это не так уж и полезно.

Но это не так. Фактически у вас есть две утечки памяти - куча утечек x <- countNumberCalls $! n - 1, потому что x не принудительно, и стек утечек 1 + x. Вы можете включить расширение BangPatterns и написать:

!x <- countNumebrCalls $1 n - 1

, и это фактически устранит одну из утечек памяти, увеличив скорость второго случая с 2,5 до 1,0 секунды и снизив максимальную резидентность с 460 мегабайт. до 95 мегабайт (а байты, скопированные во время G C, с 1,5 гигабайта до 73 килобайт!). Однако профиль кучи будет показывать линейно растущий стек, учитывающий почти всю эту резидентную память. Поскольку стек не так хорошо отслеживается, как куча, его будет труднее отследить.

Некоторые дополнительные примечания:

Несмотря на то, что флаги +RTS -h<x> в основном предназначены для профилирования кучи ( и обсуждаются как параметры «профилирования кучи» в документации GH C), они могут технически сообщать о других способах использования резидентной памяти, помимо кучи, включая состояние каждого потока, которое включает объекты состояния потока и стек. По умолчанию при запуске профилированного двоичного файла (скомпилированного с -prof) флаги +RTS -h<x> делают не отчет о состоянии каждого потока, включая стек, но вы можете добавить флаг -xt , чтобы добавить его, как в +RTS -hc -xt. Из-за вероятной непреднамеренной оплошности в непрофилированном двоичном файле флаг +RTS -hT (единственный доступный флаг -h<x>) включает стек даже без флага -xt. Из-за ошибки компилятора флаг -hT не работает в профилированных двоичных файлах для GH C 8.6.x и более ранних версий, но он работает в GH C 8.8.x и для эта версия, +RTS -hT, включает стек для непрофилированных двоичных файлов, но исключает его для профилированных двоичных файлов, если вы также не укажете -xt. Вот почему в приведенных выше примерах «Стек» отображается только при запуске профиля кучи на непрофилированном двоичном файле. Вы можете добавить флаг -xt, чтобы увидеть его для всех других профилей кучи. Обратите внимание, что этот «СТЕК» является фактическим использованием стека, а не объектами в куче, которые каким-то образом связаны со стеком.

Черные дыры в первую очередь являются механизмом для поддержки параллелизма. Когда поток начинает оценивать преобразователь, он делает его «черными дырами» (т. Е. Отмечает его как черную дыру), так что, если другой поток приходит и хочет оценить тот же преобразователь, он ждет оценки вместо того, чтобы пытаться повторить попытку. оценивать его параллельно (что дублирует усилия работающего потока). Он также используется в среде выполнения без потоков, отчасти потому, что он может обнаруживать бесконечные циклы (если поток встречает собственную черную дыру), но также по некоторым более важным причинам, которые я не могу вспомнить. Для профилирования кучи -hT, -hd и -hy объекты кучи, которые были заблокированы таким образом, будут помечены как «BLACKHOLE». Ограниченная частота дискретизации в профилях выше может сделать ее немного неясной, но в вашей программе происходит то, что большая серия из Int преобразователей выстраивается в цепочку, и когда значение, наконец, принудительно устанавливается, они превращаются в длинная цепочка BLACKHOLE с, каждое из которых представляет вычисление, которое было инициировано и ожидает следующего вычисления в цепочке.

Answer 2

Вы спрашиваете

return $ 1 + x [...] но почему gh c не оптимизирует это ??

Ответ заключается в том, что строгая оценка семантика и ленивое вычисление несколько различаются, поэтому использование GH C optimize может сломать вашу программу.

Разница заключается в обработке неопределенных значений. Любая попытка оценить undefined вызывает исключение. В GHCi:

Prelude> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:1 in interactive:Ghci1

Если у меня есть выражение, содержащее undefined, происходит то же самое:

Prelude> 2 + undefined
*** Exception: Prelude.undefined [...]

Однако, если оценка никогда не достигает значения undefined, тогда все в порядке:

Prelude> True || undefined
True

Haskell использует «нестрогую семантику» и «ленивую оценку». Технически нестрогая семантика является частью определения Haskell, а ленивое вычисление - это механизм реализации в GH C, но вы можете рассматривать их как синонимы. Когда вы определяете переменную, значение не вычисляется немедленно, поэтому, если вы никогда не используете переменную, у вас нет проблем:

Prelude> let b = undefined
Prelude> b
*** Exception: Prelude.undefined

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

Теперь рассмотрим ваш огромный стек неоцененных 1+ вызовов. GH C не имеет возможности узнать заранее, собираетесь ли вы когда-либо использовать результат (см. Ниже), а также не имеет возможности узнать, есть ли где-то скрывающееся исключение. Как программист вы, возможно, знаете, что существует исключение, и не смотрите внимательно на результат, полагаясь на нестрогую семантику Haskell. Если GH C преждевременно оценивает и получает исключение, ваша программа выйдет из строя, хотя этого не должно быть.

На самом деле компилятор GH C включает часть оптимизации, называемую Demand Analyzer ( его раньше называли анализатором строгости), который ищет возможности для оптимизации именно так, как вы хотите. Однако у него есть ограничения, потому что он может оптимизировать вычисления только тогда, когда он может доказать , что результат будет оценен.

Еще одна проблема заключается в том, что вы использовали монаду State . На самом деле это бывает в двух вариантах; Ленивый и строгий. Вариант Strict принудительно устанавливает состояние при записи, а вариант Lazy (по умолчанию) - нет.

Answer 3

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

• Компилировать и запускать со стеком ограниченного размера, используя +RTS -K10K для ограничьте стек до 10 КБ.
• Изучите код, который нарушает ограничение стека, используя +RTS -xc для получения трассировки стека.

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