[Haskell-cafe] Re: FASTER primes
will_n48 at yahoo.com
Thu Jan 14 02:25:48 EST 2010
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> Am Mittwoch 13 Januar 2010 10:43:42 schrieb Heinrich Apfelmus:
> > I wonder whether it's really the liveness of pair in
> > mergeSP (a,b) pair
> > = let sm = spMerge b (fst pair)
> > in (a ++ fst sm, merge (snd sm) (snd pair))
> > that is responsible for the space leak, for chances are that Sparud's
> > technique applies and pair is properly disposed of. Rather, it could
> > be that we need the stronger property that forcing the second component
> > will evaluate the first to NF.
> I think that is responsible. At least that's how I understand the core:
> mergeSP (a,b) ~(c,d) = (a ++ bc, merge b' d)
> (bc, b') = spMerge b c
> spMerge ...
That is equivalent to
first (a++) . second (`merge`d) $ spMerge b c
and Daniel's fix is equivalent to
first (a++) $ spMerge b c d
Now, when compiler sees the first variant, it probably treats spMerge as
opaque. I.e. although in reality spMerge only contributes to the
first "channel" while it is progressively instantiated, and (`merge`d) will
only be called upon when spMerge's final clause is reached, that is (most
likely) not known to the compiler at this stage. When looking at just the first
expression itself, it has to assume that spMerge may contribute to both
channels (parts of a pair) while working, and so can't know _when_ /d/ will get
called upon to contribute to the data, as it is consumed finally at access.
So /d/ is gotten hold of prematurely, _before_ going into spMerge.
The second variant passes the responsibility for actually accessing its inputs
to spMerge itself, and _it_ is clear about needing /d/ only in the very end.
Just a theory. :)
Does that make sense?
More information about the Haskell-Cafe