Я новичок в функциональном программировании, и теперь изучаю Haskell. В качестве упражнения я решил реализовать явный метод Эйлера для одномерного уравнения линейной диффузии. Хотя приведенный ниже код работает правильно, я не доволен его производительностью. На самом деле меня беспокоит потребление памяти. Я считаю, что это связано с отложенной оценкой, но не могу понять, как я могу уменьшить использование памяти.
Идея алгоритма очень проста, чтобы прояснить это в императивных терминах: он берет «массив», и к каждой внутренней точке он добавляет значение, которое вычисляется как комбинация значений в самой точке и у соседей. Граничные точки - это особые случаи.
Итак, это мой модуль Euler1D.hs:
module Euler1D
( stepEuler
, makeu0
) where
-- impose zero flux condition
zeroflux :: (Floating a) => a -> [a] -> [a]
zeroflux mu (boundary:inner:xs) = [boundary+mu*2*(inner-boundary)]
-- one step of integration
stepEuler :: (Floating a) => a -> [a] -> [a]
stepEuler mu u@(x:xs) = (applyBC . (diffused mu)) u
where
diffused mu (left:x:[]) = [] -- ignore outer points
diffused mu (left:x:right:xs) = -- integrate inner points
(x+mu*(left+right-2*x)) : diffused mu (x:right:xs)
applyBC inner = (lbc u') ++ inner ++ (rbc u') -- boundary conditions
where u' = [head u] ++ inner ++ [last u]
lbc = zeroflux mu -- left boundary
rbc = (zeroflux mu) . reverse -- right boundary
-- initial condition
makeu0 :: Int -> [Double]
makeu0 n = [ ((^2) . sin . (pi*) . xi) x | x <- [0..n]]
where xi x = fromIntegral x / fromIntegral n
И простой Main.hs:
module Main where
import System ( getArgs )
import Euler1D
main = do
args <- getArgs
let n = read $ head args :: Int
let u0 = makeu0 n
let un = stepEuler 0.5 u0
putStrLn $ show $ sum un
Для сравнения я также написал реализацию на чистом C .
Теперь, если я попытаюсь запустить реализацию Haskell для достаточно большого размера массива n, у меня будет:
$ time ./eulerhs 200000
100000.00000000112
real 0m3.552s
user 0m3.304s
sys 0m0.128s
Для сравнения, версия C быстрее почти на два порядка:
$ time ./eulerc 200000
100000
real 0m0.088s
user 0m0.048s
sys 0m0.008s
EDIT : Это сравнение не совсем справедливо, потому что версия на Haskell
скомпилирован с флагами профилирования и C
не является. Если я скомпилирую обе программы
с -O2 и оба без профилирования
Флаги я могу увеличить n. В этом
дело time ./eulerhs 1000000 берет
0m2.236s, в то время как time ./eulerc
1000000 занимает всего 0m0.293s. Итак
проблема все еще остается со всеми
оптимизации и без профилирования,
это только смещение.
Я хотел бы также отметить, что память
выделение программы на Haskell
кажется линейным с n.
Это, наверное, нормально.
Но худшее - это требования к памяти. Моя версия на Haskell требует свыше 100 МБ (моя оценка минимального значения в C составляет 4MB ). Я думаю, что это может быть источником проблемы. Согласно отчету о профилировании программа проводит 85% времени в GC и
total time = 0.36 secs (18 ticks @ 20 ms)
total alloc = 116,835,180 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
makeu0 Euler1D 61.1 34.9
stepEuler Euler1D 33.3 59.6
CAF:sum Main 5.6 5.5
Я был удивлен, увидев, что makeu0 стоит , поэтому дорого. Я решил, что это из-за его ленивой оценки (если его громкие звуки остаются в памяти до конца stepEuler).
Я попробовал это изменение в Main.hs:
let un = u0 `seq` stepEuler 0.5 u0
но не заметил никакой разницы. Я понятия не имею, как уменьшить использование памяти в stepEuler. Итак, мои вопросы:
- Есть ли в Haskell способ строго составлять списки / выполнять их списки? В этом случае нет смысла держать его ленивым.
- Как я могу уменьшить общее использование памяти в этом случае? Я полагаю, я должен сделать что-то строгое, но не вижу, что. Другими словами, если я должен поставить некоторые
seq и удары, где и почему?
- И, наконец, самое важное, какова лучшая стратегия для выявления таких дорогостоящих конструкций?
Я прочитал главу о профилировании и оптимизации в Real World Haskell , но остается неясным, как именно я могу решить, что должно быть строгим, а что нет.
Пожалуйста, прости меня за такой длинный пост.
EDIT2 : Как было предложено А. Рексом в комментариях, я попытался запустить оба
программы в валгринде. И это то, что
Я заметил. Для программы на Haskell
(n = 200000) найдено:
malloc / free: 33 выделяет, 30 освобождает, выделено 84 109 байтов.
...
проверено 55 712 980 байт.
И для программы на C (после небольшого исправления):
malloc / free: 2 ассигнования, 2 освобождения, 3 200 000 байтов.
Итак, похоже, что пока Хаскелл
выделяет гораздо меньшие блоки памяти,
это происходит часто и из-за задержки в
сбор мусора, они накапливаются
и остаться в памяти. Так что я
другой вопрос:
- Можно ли избежать многих
небольшие ассигнования в Haskell?
В основном, чтобы заявить, что мне нужно
обрабатывать всю структуру данных
а не только его фрагменты на
спрос.