last day (15 days later) » 

6:15 PM
1
A: How does the GHC garbage collector / runtime know that it can create an array `inplace'

dfeuerThis explanation is probably a lie, especially because I'm making it up as I go, but that shouldn't be a problem. The essential mistake you're making is assuming that a value is live if a variable bound to it is in scope in a live expression. This is simply wrong. A value bound to a variable is ...

 
So would you say that the difference in memory usage is happening because of something that the runtime does? Also, does your description require that the runtime know which values are mentioned in an expression? Or perhaps it's the compiler that does these optimizations?
 
@pdexter, please see my edit.
@pdexter, and no, it doesn't actually have the expressions at runtime. But GHC compiles the program into a language for an abstract machine called the Spineless Tagless G-Machine that essentially does that. The STG code is then compiled down further in the code generation stage, and I don't know anything about how that works, but it gets rid of all the abstract stuff and makes machine code. But as I understand it, that's a relatively straightforward process, compared to other optimization processes.
 
Thank you, this is the answer I've been looking for (assuming it's correct :)) So the compilation stage handles this and the GC is as naive as expected (meaning it's not getting any extra information, and the optimization is happening 100% at the compilation stage). I understand well what arrays actually are in Haskell and the basics of GC. I just wanted to know where this optimization takes place. As expected, the GC cannot know whether something is mentioned further in the expression unless the compiler feeds it information (which it sounds like it's not).
Can you type the STG bit up as an actual answer?
 
@pdexter, I don't really understand what you're saying. I know my explanation is a bit muddled; I'll try to explain it a bit better. If you want to know about STG, you'll have to read the paper about it. The essential problem with your understanding was the essential problem with mine until I sat down to work through it. From an "interpreter" perspective, the trick is to stop thinking about an expression as something that exists in its entirety until fully evaluated. That's an artifact of a simplistic representation. As an expression is reduced, parts of it can go away.
 
All the answers are describing why the garbage collector can collect it, and what lists are, and what garbage collection means. What I'm actually wondering is where this optimization takes place. Because it obviously cannot happen purely with that code and a GC. A GC cannot know what expressions come in the future, or what values are live in the coming part of an expression. I know of the STG and have skimmed the literature. If this optimization is happening because of what the Haskell compiles to on the STG then that is what I wanted to know. From here I will look at the STG output from GHC
More concretely: a GC cannot possibly know what values will be referenced in the future. So either (a) it is receiving extra information from the compiler or (b) the compiler itself is optimizing this (which is how it sounds). If the answer is (b), then maybe it is the phases of the compiler dealing with the STG?
 
6:15 PM
@pdexter, I have tried to expand the explanation. I don't know if I succeeded.
Yes?
You called?
 
Your description makes perfect sense. Thank you for typing this up. However what if countup was defined as

countup m n = let ls = [1..10000000]
in [1]:[2]:ls:[ls]

Then, at some point printnow will be `ls` and whatprint' will be a lazy cons list, when whatprint is set to whatprint', how does it know it cannot GC `ls`
It is not allowed to peak under the cons cell, and it cannot know what values are live in the rest of the expression because that would violate (probably..?) the halting problem
 
Okay, I guess that was a little imprecise. Consider printNow and whatPrint' part of the root set too.
It can't always look deep into the list, but it doesn't need to.
It can stop as soon as it reaches a thunk.
It doesn't need to evaluate the thunk; it just looks at what the thunk points to.
 
So what if the second ls was actually two cons cells after the first one? Or, what if the thunk was created due to some branching condition where it couldn't know until runtime where it would point?
I have a seminar now, I will be back soon. But my general thought is that all of this is taken care of by some layer in the compilation process. Which makes all of these things explicit. In that, Haskell doesn't care about this but, for example, the STG code does. So it probably uses some liveness analysis? I'm not too knowledgeable on compilers but this is just what I think must happen
 
6:30 PM
The runtime, unlike your program, can tell the difference between a thunk and a non-thunk.
 
Right, but it can't know what values will be pointed to later in the execution, right? Maybe I'm confusing the runtime vs code, hmmm
 
There is indeed liveness analysis, but that gives something on top of the basic evaluation model. The basic evaluation model is sufficient for these cases.
 
Right, but these are pretty simple, I'm imaging where it can't know what a thunk will point to
 
As I understand it. Yeah, think about code-as-data, and you'll probably be thinking in the right direction.
No.
It doesn't know where the thunk will point to.
It knows what the thunk does point to.
The GC scans it for pointers.
 
hm, alright
 
6:33 PM
Of course, there are probably optimizations to obviate that sometimes, but you don't need to consider that for this.
Have fun at your seminar.
 
 
1 hour later…
7:49 PM
thanks for everything :)
 

last day (15 days later) »