[Haskell-cafe] Re: FASTER primes
daniel.is.fischer at web.de
Thu Jan 14 06:02:37 EST 2010
Am Donnerstag 14 Januar 2010 08:25:48 schrieb Will Ness:
> 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)
> > where
> > (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.
No, the problem is that d itself is gotten hold of too late, it is
accessed only indirectly via the pair, so we keep an unnecessary reference
to c via d.
> 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.
The second variant is clear about not needing the _pair_ anymore once
spMerge is entered. Thus d doesn't reference c anymore.
> Just a theory. :)
> Does that make sense?
More information about the Haskell-Cafe