Что такое космическая утечка?
Я нашел вики-страницу на haskell о космических утечках, которая утверждает, что перечисляет примеры реальных утечек, которых нет. Это действительно не говорит, что является космической утечкой; это просто ссылки на страницу для утечек памяти.
Что такое космическая утечка?
2 ответа
Как отмечено в ответе @Rasko, утечка пространства относится к ситуации, когда программа или конкретное вычисление использует больше (обычно намного больше) памяти, чем это необходимо для вычисления и / или ожидается программистом.
Программы на Haskell, как правило, особенно восприимчивы к утечкам пространства, в основном из-за ленивой модели оценки (иногда сложной из-за того, как IO взаимодействует с этой моделью) и крайне абстрактной природы языка, которая может затруднить программисту точное определение того, как вероятно, будет выполнено конкретное вычисление.
Это помогает рассмотреть конкретный пример. Эта программа на Haskell:
main = print $ sum [1..1000000000]
идиоматический способ суммировать первый миллиард целых чисел. Составлено с -O2он работает в течение нескольких секунд в постоянной памяти (несколько мегабайт, в основном это накладные расходы времени выполнения).
Теперь любой программист может ожидать, что программа суммирует первый миллиард целых чисел, которые должны выполняться без потери памяти, но на самом деле немного удивительно, что эта версия на Haskell хорошо себя ведет. В конце концов, если читать буквально, он формирует список из миллиарда целых чисел, прежде чем их суммировать, поэтому он должен требовать, по крайней мере, несколько гигабайт (только для хранения миллиарда целых чисел, не говоря уже о накладных расходах связанного списка на Haskell).
Однако ленивая оценка гарантирует, что список генерируется только по мере необходимости, и, что не менее важно, оптимизации, выполняемые компилятором, гарантируют, что по мере добавления элементов списка к сумме накопления программа распознает, что они больше не нужны, и позволяет им собирать мусор вместо того, чтобы хранить их до конца вычислений. Таким образом, в любой момент вычислений в памяти необходимо хранить только скользящее "окно" в середине списка - более ранние элементы отбрасываются, а более поздние элементы еще не вычисляются лениво. (На самом деле, оптимизация идет дальше, чем это: список даже не создается, но это далеко не очевидно для программиста.)
Оооочень... Программисты на Haskell привыкли к мысли, что перебрасывание гигантских (или даже бесконечных) структур данных будет "просто работать" с вычислениями автоматически, используя только необходимую им память.
Но небольшое изменение в программе, например, печать длины списка в качестве доказательства всей тяжелой работы, которую мы делаем:
main = let vals = [1..1000000000]
in print (sum vals, length vals)
внезапно приводит к тому, что использование пространства увеличивается до десятков гигабайт (или, в случае с моим ноутбуком, до 13 гигабайт, прежде чем он начинает безнадежно обмениваться, и я его убиваю).
Это космическая утечка. Вычисление суммы и длины этого списка - это, очевидно, вещи, которые можно сделать в постоянном пространстве с использованием представления "скользящего окна" в списке, но вышеприведенная программа использует гораздо больше памяти, чем необходимо. Причина в том, что, как только список получил имя vals который используется в двух местах, компилятор больше не позволяет немедленно удалять "используемые" элементы. Если sum vals сначала оценивается, список генерируется и суммируется, но весь гигантский список сохраняется до length vals можно оценить.
В качестве более практического примера вы можете написать простую программу для подсчета слов и символов в файле:
main = do txt <- getContents
print (length txt, length (words txt))
Это отлично работает на небольших тестовых файлах размером до пары мегабайт, но заметно замедляет работу на 10-мегабайтном файле, и если вы попытаетесь запустить его на 100-мегабайтном файле, он медленно, но верно начнет сжимать всю доступную память. Опять же, проблема в том, что - хотя содержимое файла лениво читается в txt -- так как txt используется дважды, все содержимое считывается в память как Haskell String type (неэффективное представление больших блоков текста в памяти), когда, скажем, length txt оценивается, и ни одна из этой памяти не может быть освобождена до length (words txt) также был вычислен.
Обратите внимание, что:
main = do txt <- getContents
print $ length txt
а также:
main = do txt <- getContents
print $ length (words txt)
оба работают быстро в постоянном пространстве даже на больших файлах.
Как примечание, исправление вышеупомянутой утечки пространства обычно включает в себя переписывание вычислений, чтобы символы и слова подсчитывались за один проход содержимого, поэтому компилятор может определить, что содержимое файла, который уже был обработан, не нужно хранится в памяти до конца вычислений. Одним из возможных решений является:
{-# LANGUAGE BangPatterns #-}
import Data.List
import Data.Char
charsWords :: String -> (Int, Int)
charsWords str = let (_, chrs, wrds) = foldl' step (False, 0, 0) str
in (chrs, wrds)
where step (inWord, cs, ws) c =
let !cs' = succ cs
!ws' = if not inWord && inWord' then succ ws else ws
!inWord' = not (isSpace c)
in (inWord', cs', ws')
main = do txt <- getContents
print $ charsWords txt
Сложность этого решения (использование взрыва (!) шаблоны и явная складка вместо length а также words) иллюстрирует, насколько серьезными могут быть утечки пространства, особенно для новых программистов на Haskell. И совсем не очевидно, что использование foldl' вместо foldl не имеет значения (но используя foldr или же foldr' будет катастрофа!), что челка до cs' а также ws' имеют решающее значение, чтобы избежать космической утечки, но что взрыв до inWord' нет (хотя это немного улучшает производительность) и т. д.
Утечка пространства происходит, когда компьютерная программа использует больше памяти, чем необходимо. В отличие от утечек памяти, когда утечка памяти никогда не освобождается, память, используемая утечкой пространства, освобождается, но позже, чем ожидалось. * Источник