Am Samstag 16 Januar 2010 18:53:33 schrieb Will Ness: > Daniel Fischer <daniel.is.fischer <at> web.de> writes: > > 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, ... > > > > > > > > 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 > > That should've been > > mergeSP (a,b) p = first(a++) . second(`merge`snd p) $ spMerge b (fst > p) > > and > > mergeSP (a,b) p = first(a++) $ spMerge b (fst p) (snd p) > > > The code fragments you've posted are essentially > > > mergeSP (a,b) p = let res = case p of (c,_) -> > case spMerge b c of (# x,y #) -> > (x,y) > in > (# (++) a (case res of (bc,_)-> bc) , > case res of (_,b') -> > case p of (_,d) -> merge b' d #) > > and > > mergeSP (a,b) p = let res = case p of (c,d) -> > case spMerge b c d of (# x,y #) -> > (x,y) > in > (# (++) a (case res of (bc,_)-> bc) , > case res of (_,b') -> b' #) > > > This looks like Haskell to me, with many detailes explicitely written > out, probaly serving as immediate input to the compiler - not its > output. So it can't say to us much about how this is actually > implemented on the lower level. (?)
It's 'core', the intermediate language GHC uses and does its transformations upon. It's more or less a slimmed down version of Haskell. That came from -ddump-simpl, thus it's the output of the simplifier, after numerous transformation/optimisation passes. I think that is then fairly directly translated to assembly (via Cmm), the STG to STG and Cmm passes do not much optimisation anymore (I may be wrong, what know I about the compiler. However, I've found that the -ddump-simpl output corresponds well to the actual behaviour whenever I look.). I find that much more redable than the -fext-core output (http://www.haskell.org/ghc/docs/6.12.1/html/users_guide/ext-core.html "GHC can dump its optimized intermediate code (said to be in “Core” format) to a file as a side-effect of compilation."), which says the same, only more verbose and less readable. Of course, if I could read assembly, that would exactly reveal what happens. > > Your theory would certainly hold if the translation was done one-to-one > without any further code rearrangements. But it could've been further > re-arranged by the compiler at some later stage (is there one?) into an > equivalent of, e.g. > > > mergeSP (a,b) p = let (bc,b') = case p of (c,_) -> > case spMerge b c of (x,y) -> > (x,y) > in > (# (++) a bc , > case p of (_,d) -> merge b' d #) > > > and further, > > > mergeSP (a,b) p = let (c,d) = case p of (x,y) -> (x,y) > (bc,b') = case spMerge b c of (x,y) -> > (x,y) > in > (# (++) a bc , merge b' d #) > > > could it? This would take hold on /d/ and /c/ at the same time, right? It would. But AFAICT, after the simplifier is done, no such rearrangements occur anymore. > > What is that code that you've shown exactly? At which stage is it > produced and is it subject to any further manipulation? I'm no GHC expert either, so I don't know what it does when exactly. But after parsing and desugaring, there come a few iterations of the simplifier, intermingled with specialising, demand-analysis, CSE, let- floating, worker-wrapper-split, ... . At the end of all that, the Tidy Core is generated (part of which I posted). What happens from then on, well ... > I apologise if > these are obvious questions, I don't know anything about GHC. I also > don't know what (# x,y #) means? Unboxed tuple (pair in this case). That means, have the components for themselves, don't wrap them in a (,) constructor. > > One thing seems certain - we should not hold explicit references to same > entities in different parts of our code, to avoid space leaks with more > confidence. Except when it's good to share ;) > To make code look as much tail-recursive as possible, so to speak. Tail recursion isn't really important (for GHC at least, I think for lazy languages in general), due to different evaluation models (cf. http://www.haskell.org/pipermail/haskell-cafe/2009-March/058607.html and the thread starting with http://www.haskell.org/pipermail/haskell-cafe/2007-May/025570.html). > > Does that make sense? In general, yes. > > Anyway that was a very educational (for me) and fruitful discussion, and > I greatly appreciate your help, and fixing and improving of the code. > > Thanks! You're welcome. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe