Jak zmniejszyć zużycie pamięci w aplikacji Haskell?

Jestem nowy w programowaniu funkcyjnym, a teraz uczyć się Haskell. Jako ćwiczenie postanowiłem wdrożyć metodę Eulera dla równania dyfuzji liniowej 1D. Podczas gdy poniższy kod działa poprawnie, nie jestem zadowolony z jego wydajności. Chodzi mi o zużycie pamięci. Uważam, że jest to związane z leniwą oceną, ale nie mogę dowiedzieć się, jak mogę zmniejszyć zużycie pamięci.

Idea algorytmu jest naprawdę prosta, aby było jasne w kategoriach imperatywnych: to przyjmuje 'tablicę' i do każdego wewnętrznego punktu dodaje wartość, która jest obliczana jako kombinacja wartości w samym punkcie i w jego sąsiadach. Punkty graniczne są szczególnymi przypadkami.

Więc to jest mój moduł 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

I prosty główny.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

Dla porównania napisałem również czystą implementację C.

Teraz, jeśli spróbuję uruchomić implementację Haskella dla wystarczająco dużego rozmiaru tablicy n, mieć:

$ time ./eulerhs 200000
100000.00000000112

real    0m3.552s
user    0m3.304s
sys     0m0.128s

$ time ./eulerc 200000
100000

real    0m0.088s
user    0m0.048s
sys     0m0.008s

EDIT: to porównanie nie jest naprawdę fair, ponieważ wersja Haskell jest skompilowane z profilowanymi flagami i C nie jest. Jeśli skompiluję oba programy z -O2 i obie bez profilowania flagi, mogę zwiększyć n. W tym case time ./eulerhs 1000000 zajmuje 0m2.236S, podczas gdy time ./eulerc 1000000 zajmuje tylko 0M0. 293s. Tak więc problem nadal pozostaje ze wszystkimi optymalizacje i bez profilowanie, to tylko przesunięcie.

[[18]}chciałbym również zauważyć, że pamięć przydział programu Haskell wydaje się rosnąć w linii z n. To chyba OK.

Ale najgorsze są wymagania dotyczące pamięci. Moja wersja Haskell wymaga ponad 100MB (moje oszacowanie minimum w C to 4MB ). Myślę, że to może być źródłem problemu. Zgodnie z raportem profilowania program spędza 85% czasu w GC i

        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

Byłem / align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center / Zdecydowałem, że jest to spowodowane jego leniwą oceną (jeśli jego kawałki pozostaną w pamięci do końca stepEuler).

Próbowałem tej zmiany w Main.hs:

   let un = u0 `seq` stepEuler 0.5 u0

Ale nie zauważyłem żadnej różnicy. Nie mam pojęcia, jak zmniejszyć zużycie pamięci w stepEuler. Moje pytania to:

1. czy w Haskell istnieje sposób na tworzenie list / składanie list ściśle? W tym przypadku nie ma korzyści, aby utrzymać go leniwy.
2. Jak mogę zmniejszyć ogólne zużycie pamięci w tym przypadku? Przypuszczam, że muszę zrobić coś ścisłego, ale nie wiem, co. Innymi słowy, jeśli muszę umieścić jakieś seqS i grzywkę, gdzie i dlaczego?
3. i wreszcie, najważniejsze, jaka jest najlepsza strategia identyfikacji tak kosztownych konstrukcji?

Czytałem rozdział na temat profilowania i optymalizacji wrealnym świecie Haskell , ale pozostaje niejasne, jak dokładnie mogę zdecydować, co powinno być surowe, a co nie.

Proszę wybacz mi taki długi post.

EDIT2: zgodnie z sugestią A. Rex w komentarzach, próbowałem uruchomić oba programy w valgrind. I to jest to, co Obserwowałem. Dla programu Haskell (n=200000) znaleziono:

Malloc / free: 33 allocs, 30 frees, 84,109 bajtów przydzielonych. ... sprawdzono 55 712 980 bajtów.

I dla programu C (po małej poprawce):

Malloc / free: 2 allocs, 2 frees, 3,200,000 bajtów przydzielonych.

Wygląda więc na to, że podczas gdy Haskell przydzielanie znacznie mniejszych bloków pamięci, robi to często, a ze względu na opóźnienie w wywóz śmieci, gromadzą się i pozostaną w pamięci. Więc mam kolejne pytanie:

• czy można uniknąć wielu małe przydziały w Haskell? Zasadniczo, aby zadeklarować, że muszę przetwarzaj całą strukturę danych a nie tylko jego fragmenty na żądanie.