Luke Palmer wrote:
On Dec 28, 2007 9:35 AM, Jules Bean <[EMAIL PROTECTED]> wrote:
In particular, adding sharing can stop something being GCed, which can
convert an algorithm which runs in linear time and constant space to one
which runs in linear space (and therefore, perhaps, quadratic time).
I've heard of this before, but can you give an example?
Sure:
foo (length (build_big_list 1 2 3)) (build_big_list 1 2 3)
Here, "foo" is a function which operates on a list, but needs to know
the length of the list for some reason.
As written, build_big_list is called twice. This is potentially a waste
of time, but it *does* mean that if the big list is very very big
(larger than available memory) but build_big_list is a good producer, it
can be produced and GCed in constant space - as long as length is a good
consumer (which it is) and as long as foo is (can't tell without seeing
the definition, obviously!)
So, you can do a two-pass algorithm in two-passes, but in constant space.
Now, if we automatically share those two, we get something like this:
let l = build_big_list 1 2 3 in foo (length l) l
which *looks* like an optimisation, but the shared 'l' will be kept
around. The length will be calculated first (assuming foo uses the
length, that is) and then the entire list kept in memory while foo
processes it.
Of course, it's hard to see this kind of problem with the simple x@(Just
y) case we were talking about, but if your function calls itself
recursively then it can.
Jules
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
