[Haskell-cafe] Please help me spot where space leak occur.

[Olexander Kozlov]

Greetings Haskell community,

I stuck with a space leak problem in simple task. I have a function
described with a list of pairs:

   type Fn a b = [(a, b)]

mapping values from a to b. And I have a composition operation which accepts
two functions and returns
theirs composition:

   compose :: Eq b => Fn a b -> Fn b c -> Fn a c

Finding composition of 1,000,000 functions takes about 240M with the
following implementation:

type Fn a b = [(a, b)]

lkup :: Eq a => a -> Fn a b -> b
lkup x ((a, b) : abs) = if x /= a then lkup x abs else b

compose :: Eq b => Fn a b -> Fn b c -> Fn a c

compose ((a, b) : abs) bcs = (a, lkup b bcs) : compose abs bcs
compose [] _ = []

fldl :: (a -> b -> a) -> a -> [b] -> a

fldl f z (x:xs) = fldl f (f z x) xs
fldl _ z [] = z

fna = [(1, 2), (2, 3), (3, 1)]
fni = [(1, 1), (2, 2), (3, 3)]

test = fldl compose fni (replicate 1000000 fna)

main = print test

I build with:

   ghc --make -prof -auto-all -caf-all -fforce-recomp -rtsopts Test.hs

Profile results:

   Test.exe +RTS -K50M -p -RTS

total time  =        0.34 secs   (17 ticks @ 20 ms)
total alloc = 240,003,820 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

compose                        Main                  58.8   80.0
lkup                           Main                  35.3    0.0
test                           Main                   5.9   11.7
fldl                           Main                   0.0    8.3

After reading 'High-Performance Haskell' by Johan Tibell I tried to made my
compose function strict:

compose :: Eq b => Fn a b -> Fn b c -> Fn a c

compose ((a, b) : abs) bcs = let c = lkup b bcs in c `seq` (a, c) : compose
abs bcs
compose [] _ = []

and memory consuption reduced down to 180M. Good achievement but still too
much!

Profile results:

   Test.exe +RTS -K50M -p -RTS

total time  =        0.24 secs   (12 ticks @ 20 ms)
total alloc = 180,003,820 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

compose                        Main                  83.3   73.3
lkup                           Main                   8.3    0.0
fldl                           Main                   8.3   11.1
test                           Main                   0.0   15.6

I tried to make fldl strict as well:

fldl :: (a -> b -> a) -> a -> [b] -> a

fldl f z (x:xs) = let z' = f z x in z' `seq` fldl f z' xs
fldl _ z [] = z

and end up with 160M of total allocations.

Profile results:

   Test.exe +RTS -K32M -p -RTS

total time  =        0.30 secs   (15 ticks @ 20 ms)
total alloc = 160,003,820 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

compose                        Main                  46.7   82.5
lkup                           Main                  40.0    0.0
test                           Main                   6.7   17.5
fldl                           Main                   6.7    0.0

Please help me spot where space leak occur, I see no other places for space
leaks. I'll appreciate any help.

(I intentionally wrote my own implementations of lookup and foldl to have
direct control on them.)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110721/6f49ca0f/attachment.htm>