Alastair David Reid wrote:
Executive summary: David's program has an incredibly subtle space leak in it (or I'm being incredibly dumb). I encourage the honchos (and would be honchos) to have a look. Users of other compilers might give it a shot too.
David Bakin wrote:
Why is there a space leak in foo1 but not in foo2?
The reason that foo1 "leaks" space is because the middle of v grows faster than its head. So taking elements from v causes its in-memory footprint to grow. To see why this is the case, evaluate foo1 by hand:
-- This has a space leak, e.g., when reducing (length (foo1 1000000)) foo1 m = take m v where v = 1 : flatten (map triple v) triple x = [x,x,x]
Focusing on just v for now, and letting f = flatten for notation purposes, we have (1) v = 1 : f (map triple v) (2) = { unwrap v } 1 : f (map triple (1 : f (map triple v))) (3) = { eval map } 1 : f (triple 1 : map triple (f (map triple v))) (4) = { eval triple } 1 : f ([1,1,1] : map triple (f (map triple v))) (5) = { eval f (= flatten = foldr (++) []) } 1 : 1 : 1 : 1 : f (map triple (f (map triple v)))) In order to expose elements 2-4 of v, we had to evaluate v to the extent that the overall expression held in memory *grew*. Notice how in (1) we had a single (f (map triple ...)) expression in the tail of v but in (5) there are two such expressions, nested. Continuing further, if we want to expose the 5th-7th elements of v, we have to expand the expression yet even more. Noticing that the (f (map triple v)) subexpression in (5) is identical to the tail of (1), we can apply the same expansion that we derived in (1)-(5) to yield (6) = { repeat (1)-(5) for f (map triple v) in (5) } 1 : 1 : 1 : 1 : f (map triple (1 : 1 : 1 : f (map triple ( f (map triple v))))))) (7) = { eval map } 1 : 1 : 1 : 1 : f (triple 1 : map triple ( f (map triple ( f (map triple v)))))))) (8) = { eval triple } 1 : 1 : 1 : 1 : f ([1,1,1] : map triple ( f (map triple ( f (map triple v)))))))) (9) = { eval f } 1 : 1 : 1 : 1 : 1 : 1 : 1 : f (map triple ( f (map triple ( f (map triple v))))))))) Notice how in (9) we have three nested (f (map triple (...))) expressions in the tail of v whereas in (5) we had only two and in (1) we had but one? Now you can see why foo1 has a space "leak": In order to take the Nth element of v, v's definition must be expanded to the point where there are 1+(N+1)/3 (f (map triple (...))) subexpressions in the tail of v *that will never be reached*. In other words, v's "middle" grows faster than its head, ensuring that take will never consume the tail. Taking elements from the head only makes the middle grow larger. The more your take, the larger it grows. So the problem isn't Hugs but rather the definition of v, which grows faster than it can be consumed. Cheers, Tom