Пытаюсь разобраться в том, как программы на Хаскелле используют память и наткнулся на вот такой непонятный эффект. Есть такая простая программа:
sum1 :: Integer -> Integer -> Integer -> Integer
sum1 a b acc -- | a `seq` b `seq` False = undefined
| a < b = sum1 (a+1) b (acc+a)
| otherwise = acc
main = print $ (sum1 0 1000000 0)
Если выполнять её как она написана (с закомментированной строчкой), то она выполняется за O(1) памяти, всего выделяя за время работы O(N). Хотя, казалось бы, она должна использовать O(N) памяти, поскольку функция sum1 нестрогая по acc, и, следовательно, должна создать цепочку недовычисленных сумм (как foldl). Но это ладно, может анализатор строгости работает.
Непонятное происходит, если строчку с seq раскомментировать. По-моему, функция как была строгой по a и b, так и остается. Хвостовая рекурсия тоже остается. Ан нет, происходит переполнение стека. Как так?
Если Integer заменить на Int, то получается все нормально — работает за O(1), выделяя тоже O(1) в обоих случаях. Тут все понятно.
Здравствуйте, Vintik_69, Вы писали:
V_>Непонятное происходит, если строчку с seq раскомментировать. По-моему, функция как была строгой по a и b, так и остается. Хвостовая рекурсия тоже остается. Ан нет, происходит переполнение стека. Как так? V_>Если Integer заменить на Int, то получается все нормально — работает за O(1), выделяя тоже O(1) в обоих случаях. Тут все понятно. V_>Разъясните, что тут происходит?
Ваши наблюдения у меня не подтверждаются. Как вы ставили экперименты — какая реализация Haskell, компилировали ли с оптимизацией, etc?
Здравствуйте, palm mute, Вы писали:
PM>Ваши наблюдения у меня не подтверждаются. Как вы ставили экперименты — какая реализация Haskell, компилировали ли с оптимизацией, etc?
Версия у меня GHC 6.8.2. Действительно, это странное поведение проявляется только если компилировать с -O2, c -O все нормально. Интересно, почему так? Вроде в мануале написано что -O2 не применяет никаких опасных оптимизаций.
Здравствуйте, Vintik_69, Вы писали:
PM>>Ваши наблюдения у меня не подтверждаются. Как вы ставили экперименты — какая реализация Haskell, компилировали ли с оптимизацией, etc? V_>Версия у меня GHC 6.8.2. Действительно, это странное поведение проявляется только если компилировать с -O2, c -O все нормально. Интересно, почему так? Вроде в мануале написано что -O2 не применяет никаких опасных оптимизаций.
Для начала disclaimer: я плохо разбираюсь в вопросах оптимизации Haskell.
Опять же, наблюдения не подтверждаются.
Я тестировал следующий код:
sum1 :: TYPE -> TYPE -> TYPE -> TYPE
sum1 a b acc
#ifdef SEQ
| a `seq` b `seq` False = undefined
#endif
| a < b = sum1 (a+1) b (acc+a)
| otherwise = acc
main = print $ (sum1 0 10000000 0)
Следующим скриптом:
#!/bin/bash
function run
{
echo =============== $*
rm -f sumint
touch sumint.hs
ghc -cpp sumint.hs -o sumint $* # add -ddump-simpl to view core
time ./sumint
}
run -O -DSEQ -DTYPE="Int"
run -O -DSEQ -DTYPE="Integer"
run -O -DTYPE="Int"
run -O -DTYPE="Integer"
run -O2 -DSEQ -DTYPE="Int"
run -O2 -DSEQ -DTYPE="Integer"
run -O2 -DTYPE="Int"
run -O2 -DTYPE="Integer"
GHC 6.8.3, система — Ubuntu 7.10.
Все варианты завершаются (переполнения стека нет), разницы между -O и -O2 нет, поведение от наличия "a `seq` b `seq` False = undefined" тоже не зависит (что ожидаемо — функция строга по a и b). Что интересно, GHC генерирует разный core в зависимости от наличия seq, с seq core страшный и разобраться я в нем не могу — надо бы спросить в cafe.
Переполнение стека происходит в единственном случае — если компилировать без оптимизации или запускать в интерпретируемом режиме. Причина известна — strictness analyzer работает только при включенных флагах оптимизации, потому вычисление аккумулятора надолго откладывается с последующим крахом при форсировании (точно так же, как в случае печально известной функции foldl).
Как вы оценивали потребление памяти? С помощью флага +s в ghci? Цифра, которую ghci покажет в этом случае, полезна только для оценки нагрузки на сборщик мусора — при увеличении верхнего предела цикла она будет расти, но реально утечки памяти нет. Здесь различаются случаи Int и Integer — в случае Int оптимизатор достаточно умен, чтобы не боксировать аргументы функции sum1, потому она компилируется в цикл, переменные должны попадать в регистры. С Integer печальнее — без боксирования не обойтись.
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, Vintik_69, Вы писали:
PM>Опять же, наблюдения не подтверждаются. PM>Я тестировал следующий код:
У меня все подтверждается с вашим кодом. Видимо, дело в версии Хаскелла — у меня 6.8.2. Глючит версия с seq и O2.
PM>Как вы оценивали потребление памяти?
Оценивал с помощью опции +RTS -s. Получаются такие результаты:
=============== -O -DSEQ -DTYPE=Integer
49999995000000
real 0m0.533s
user 0m0.514s
sys 0m0.008s
320,031,832 bytes allocated in the heap
40,960 bytes maximum residency (1 sample(s))
=============== -O -DTYPE=Integer
49999995000000
real 0m0.571s
user 0m0.547s
sys 0m0.010s
320,031,832 bytes allocated in the heap
40,960 bytes maximum residency (1 sample(s))
=============== -O2 -DSEQ -DTYPE=Integer
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.
real 0m21.179s
user 0m20.134s
sys 0m0.542s
753,882,456 bytes allocated in the heap
268,029,952 bytes maximum residency (9 sample(s))
=============== -O2 -DTYPE=Integer
49999995000000
real 0m0.552s
user 0m0.534s
sys 0m0.008s
320,031,832 bytes allocated in the heap
40,960 bytes maximum residency (1 sample(s))
V_>Непонятное происходит, если строчку с seq раскомментировать. По-моему, функция как была строгой по a и b, так и остается. Хвостовая рекурсия тоже остается. Ан нет, происходит переполнение стека. Как так?
Судя по всему, глюк.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Есть код, к сожалению, не очень простой (с использованием Yampa), смысл которого вкратце следующий. Грубо говоря, SF' a b :: DTime -> a -> (SF' a b, b), — это функция состояния системы, которая на вход получает шаг времени (dt), входное значение (которое может остутствовать), и выдает функцию состояния системы и выход через время dt.
Функция embed :: SF a b -> (a, [(DTime, Maybe a)]) -> [ b] берет систему в начальном состоянии и входные значения с метками времени и вычисляет набор выходных значений системы в эти моменты времени. Вопрос в том, что если убрать выделенный жирным фрагмент с seq, то она начинает работать быстрее, хотя очевидно, что a и b все равно вычисляются, так как это вход и выход системы. Спрашивается, как это может быть?
embed :: SF a b -> (a, [(DTime, Maybe a)]) -> [ b]
embed sf0 (a0, dtas) = b0 : loop a0 sf dtas
where
(sf, b0) = (sfTF sf0) a0
loop _ _ [] = []
loop a_prev sf ((dt, ma) : dtas) =
b : (a `seq` b `seq` (loop a sf' dtas))
where
a = maybe a_prev id ma
(sf', b) = (sfTF' sf) dt a
main = print $ sum $ embed' returnA inp
where-- Это просто входы через равные промежутки времени
inp = deltaEncode 1 [(1::Int)..10000000]
Здравствуйте, Vintik_69, Вы писали:
V_>[haskell]sum1 :: Integer -> Integer -> Integer -> Integer V_>sum1 a b acc -- | a `seq` b `seq` False = undefined V_> | a < b = sum1 (a+1) b (acc+a) V_> | otherwise = acc
если раскомментировать первую строчку, то фнукция становится нестрогой, поскольку undefined — (единственное) используемое в ней нестрогое значение/функция
а вообще олучше обратиться в англоязычную эху, это уже похожде на тонкие эффекты компилятора
