Timeline for Is garbage collection needed for implementing safe closures?
Current License: CC BY-SA 3.0
42 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 21, 2013 at 17:28 | vote | accept | Giorgio | ||
| Mar 11, 2013 at 9:19 | comment | added | SK-logic | @MasonWheeler, not all the GC-based systems provide finalisation semantics (and functional ones should never do it). Also, allocator response timing is deterministic. Memory profile is deterministic on a given time scale. Your example is irrelevant, since you cannot allocate memory if there is no free space (which triggers premature GC generations swap). I can give you an equally stupid counter-example with your link-counting pseudo-GC: if you accidentally free a root of a large tree, cleaning it up will stop the world for an unpredictable amount of time. Mathematica does it all the time. | |
| S Mar 10, 2013 at 20:37 | history | notice removed | yannis | ||
| S Mar 10, 2013 at 20:37 | history | unlocked | yannis | ||
| S Mar 10, 2013 at 20:37 | history | notice added | yannis | Comments only | |
| S Mar 10, 2013 at 20:37 | history | locked | yannis | ||
| Mar 10, 2013 at 19:29 | comment | added | Giorgio | @Mason Wheeler, SK-logic: This is a very interesting discussion but I think it would be better to move ti somewhere else. What about opening a chat room? | |
| Mar 10, 2013 at 19:21 | comment | added | Mason Wheeler | Also, if an object needing finalization falls out of use, and then the program shuts down, will it be finalized? If the collector does not run in the interim, no finalization takes place. This shows that the correctness of a garbage-collection system is non-deterministic. | |
| Mar 10, 2013 at 19:20 | comment | added | Mason Wheeler | @SK-logic: That is still not deterministic memory behavior. Imagine I allocate something large, requiring 100 MB of memory. Then, sometime soon after I finish using it, I need another 100 MB of memory. If my allocation was deterministic, I am guaranteed that the previous 100 is no longer in use, and I can reuse it. Under a GC scheme, the question of whether I can reuse the previous 100 MB or end up allocating another 100 (even though there's 100 MB of unused memory sitting around) depends on whether a GC pass has been run in the meantime. This shows that memory usage is non-deterministic. | |
| Mar 10, 2013 at 19:07 | comment | added | SK-logic | @MasonWheeler, start with reading on limitations of region inference. Say, here: en.wikipedia.org/wiki/Region-based_memory_management | |
| Mar 10, 2013 at 19:07 | comment | added | SK-logic | @MasonWheeler, your definitions are vague. The fact that all the unused objects are guaranteed to be eliminated every n seconds renders memory behaviour definitely deterministic. | |
| Mar 10, 2013 at 17:43 | comment | added | Giorgio | @Mason Wheeler: Closures are just values, in general it is not possible to predict how they will be moved around at runtime. In this sense, they are nothing special, the same would be valid for a string, a list, and so on. | |
| Mar 10, 2013 at 17:33 | comment | added | Mason Wheeler | Also, you seem a bit confused as to the meaning of "deterministic" in this context. It does not mean "hard realtime;" it means "strict cause-and-effect." Or, more specifically, it means "an object is freed immediately after it is no longer needed, and not at some point in the future that is determined by some external factor not related to whatever caused the object to no longer be needed." | |
| Mar 10, 2013 at 17:29 | comment | added | Mason Wheeler | @SK-logic: Again with the non-answers. You can't claim that it's pointless to discuss something because I "fail to understand" the very point that I'm asking you to prove. A closure's lifetime being unpredictable is not a fundamental axiom. Now either you can back up your claims, or you should stop making them to people with experience that contradicts them. | |
| Mar 10, 2013 at 17:24 | comment | added | SK-logic | @MasonWheeler, as for semantics, it makes no sense to discuss it with you, sorry. Your understanding of even basic lambda calculus is patchy at most. If you fail to understand that lifetime of a closure is in general unpredictable, and there is no way to determine it statically, there is no point to discuss it any further. | |
| Mar 10, 2013 at 17:22 | comment | added | SK-logic | @MasonWheeler, stop-and-copy do indeed guarantee that an unlinked object will be collected. It also guarantee compactification, it guarantee a deterministic GC timing and therefore used in hard realtime. | |
| Mar 10, 2013 at 14:57 | comment | added | Giorgio | @Mason Wheeler: I looked at the question you cited and I agree it would have been helpful to have a more concrete example. However (beware, I do not have much experience working with closures) I think there are some closure idioms that you would like to use in practice but for which you need a more general notion of closures (like in SML and, e,g., without the restrictions of Delphi). But this is outside the scope of this question: whatever notion of closures one language introduces, I wanted to understand what is needed to make those closures safe (no undefined behaviour on invocation). | |
| Mar 10, 2013 at 14:34 | comment | added | Mason Wheeler | Also, what specifically can "real closure semantics" do that Delphi's closures cannot? You've been asked about this before, and your response was a bunch of mystical mumbo-jumbo and non-explanatory non-answers. Is there a real, quantifiable, explainable difference? | |
| Mar 10, 2013 at 14:10 | comment | added | Mason Wheeler | @SK-logic: For the same reason as any other automatic GC system is non-deterministic: there is no deterministic relationship between an object no longer being needed and it getting cleaned up. Like other GC systems, stop-and-copy does not even guarantee that any given object will ever be collected. (It also wastes half of your memory and address space, which is kind of silly.) | |
| Mar 10, 2013 at 11:00 | comment | added | SK-logic | @MasonWheeler, mind explaining, why, for example, stop-and-copy is "non-dererministic"? | |
| Mar 10, 2013 at 10:58 | comment | added | SK-logic | It depends on why do you want closures in the first place. If you want to implement, say, a full lambda calculus semantics, you definitely need GC, period. There is no other way around. If you want something which distantly resembles closures, but does not follow the exact semantics of such (like in C++, Delphi, whatever) - do whatever you want, use region analysis, use fully manual memory management. | |
| Mar 9, 2013 at 15:09 | comment | added | Mason Wheeler | @gbjbaanb: Argh, and now it's too late to edit that. But yeah, that's what I meant. | |
| Mar 9, 2013 at 15:05 | comment | added | gbjbaanb | @MasonWheeler you'll want to proof-read that last comment. GC is non-deterministic :) It can have some issues with not removing objects who are still "in use", the nature of a GC will encourage circumstances where this will occur. | |
| Mar 9, 2013 at 14:45 | answer | added | Matthieu M. | timeline score: 9 | |
| Mar 9, 2013 at 13:39 | comment | added | Mason Wheeler | @Jorg: There's a very important difference between GC and reference counting: reference counting is non-deterministic, with no guarantee that any given object will even be freed at all, whereas reference counting is deterministic. | |
| Mar 9, 2013 at 11:03 | answer | added | barjak | timeline score: 14 | |
| Mar 9, 2013 at 10:36 | history | edited | Giorgio | CC BY-SA 3.0 | Added an extra example and extended explanation. |
| Mar 9, 2013 at 10:30 | history | edited | Giorgio | CC BY-SA 3.0 | Added an extra example. |
| Mar 9, 2013 at 8:22 | answer | added | user102008 | timeline score: 7 | |
| Mar 9, 2013 at 3:07 | comment | added | Jörg W Mittag | @btilly: There are also algorithms which, instead of having two completely separate GCs like CPython has for example, combine (aspects of) refcounting and tracing into a single GC algorithm. | |
| Mar 9, 2013 at 2:52 | comment | added | Jörg W Mittag | @btilly: What does "true" garbage collection mean? Refcounting is just another way of implementing GC. Tracing is more popular, probably because of the difficulties of collecting cycles with refcounting. (Usually, you end up with a separate tracing GC anyway, so why bother implementing two GCs if you can get by with one.) But there are other ways of dealing with cycles. 1) Just forbid them. 2) Just ignore them. (If you're doing an implementation for quick one-off scripts, why not?) 3) Try to explicitly detect them. (It turns out that having the refcount available can speed that up.) | |
| Mar 9, 2013 at 2:16 | comment | added | btilly | @JörgWMittag I've seen people draw a distinction between reference counting and true garbage collection. In particular do cycles get collected? | |
| Mar 9, 2013 at 1:33 | history | tweeted | twitter.com/#!/StackProgrammer/status/310201708032688128 | ||
| Mar 9, 2013 at 1:13 | comment | added | Jörg W Mittag | @btilly: Refcounting is just one of many different implementation strategies for a garbage collector. It doesn't really matter how the GC is implemented for the purpose of this question. | |
| Mar 9, 2013 at 1:05 | comment | added | btilly | Do you count reference counting as garbage collection? A number of languages, including Perl, implement reasonably complete closures and use reference counting under the hood. | |
| Mar 9, 2013 at 0:25 | answer | added | Mason Wheeler | timeline score: 6 | |
| Mar 9, 2013 at 0:16 | comment | added | Giorgio | @Robert Harvey: I did not interpret it in this way (that you implied garbage collection was the only possibility). I am curious to understand what the possible alternatives are. | |
| Mar 9, 2013 at 0:11 | comment | added | Robert Harvey | My statement didn't imply that garbage collection was the only possible mechanism for tracking closed-over variables. But it is reasonable to conclude that garbage collection is a convenient, and probably reliable, method for tracking such variables. | |
| Mar 9, 2013 at 0:10 | comment | added | Giorgio | @delnan: In other words, C++ does not guarantee that I can safely call all the closures I create. Can it be that this is connected with the lack of garbage collection? | |
| Mar 9, 2013 at 0:06 | comment | added | Giorgio | So having safe closures are only possible with garbage collection (and in this case, by using garbage collection properly)? | |
| Mar 9, 2013 at 0:04 | comment | added | Robert Harvey | Any variables that are closed-over should be protected from garbage collection, and any variables that are not closed over should be eligible for garbage collection. It follows that any mechanism that can reliably track whether or not a variable is closed over can also reliably reclaim the memory that variable occupies. | |
| Mar 9, 2013 at 0:00 | history | asked | Giorgio | CC BY-SA 3.0 |