Как уменьшить использование памяти в приложении Haskell?

Я новичок в функциональном программировании, а теперь изучаю 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 [email protected](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 и оба без профилирования flags, я могу увеличить n. В этом дело time ./eulerhs 1000000 принимает 0m2.236s, тогда как time ./eulerc 1000000 принимает только 0m0.293s. Итак проблема все еще остается оптимизации и без профилирования, это только смещение.

Я хотел бы также отметить, что память выделение программы Haskell кажется, растет линейно с n. Вероятно, это нормально.

Но хуже всего - требования к памяти. Для моей версии Haskell требуется более 100 МБ (моя оценка минимального минимума в C 4 МБ). Я думаю, что это может быть источником проблемы. Согласно отчету профилирования программа тратит 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 и bangs, где и почему?
• И, наконец, самое главное, что является лучшей стратегией для определения таких дорогостоящих конструкций?

Я прочитал главу о профилировании и оптимизации в Real World Haskell, но остается неясным, как именно я могу решить, что должно быть строгим и что нет.

Пожалуйста, простите мне такой длинный пост.

EDIT2: Как было предложено А. Рексом в комментариях, я попытался запустить оба программы в valgrind. И это то, что Я заметил. Для программы Haskell (n= 200000) он нашел:

malloc/free: 33 allocs, 30 frees, выделено 84109 байт.   ...   проверено 55 712 980 байт.

И для программы C (после небольшого исправления):

malloc/free: 2 allocs, 2 frees, выделено 3 200 000 байт.

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

• Можно ли избежать многих небольшие ассигнования в Haskell? В принципе, заявить, что мне нужно обрабатывать всю структуру данных а не только его фрагменты на спрос.