From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,3498dd887729ed19 X-Google-Attributes: gid103376,public From: dewar@merv.cs.nyu.edu (Robert Dewar) Subject: Re: Garbage Collection in Ada Date: 1996/10/19 Message-ID: #1/1 X-Deja-AN: 190609637 references: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> <199610132138291604607@dialup101-6-14.swipnet.se> <1996Oct13.194807.1@eisner> <199610181934142408603@dialup101-3-15.swipnet.se> organization: New York University newsgroups: comp.lang.ada Date: 1996-10-19T00:00:00+00:00 List-Id: Lars asks I don't have the expertise needed to confirm or refute your statements. It seems to me that for a conservative collector to falsely retain a block of memory there has to be a bitpattern somewhere in the root set (stack, globals, registers, currently allocated blocks,(?)) that can be interpreted as (1) a pointer to one of the currently allocated blocks that is (2) unreachable from the root set (no longer any user pointers to it) (3) not yet reused by the collector. - How large is the probability that this occurs? very hard to tell, but a program that relies on this not happening is inherently unreliable. - How large is the probability that this state persists? unknown - How large fraction of allocated memory will typically be falsely retained? unknown - Is the set of retained blocks growing over time or will it level out at some point in time? If so where? could grow over time certainly - other? other than the small possibility of freeing in-use blocks, and the consequent necessity to make sure you know what your compiler is doing and what your program is doing, I don't see any. How likely is it that Quicksort will crash due to stack overrun? This has zero probability in a properly written version. Only incompetent student implementations of Quicksort could fail with a stack overrun that was data dependent. You should know the technique (anyone should), you simply sort the small half first. This is an absolutely standard divide and conquer trick for keeping stack usage to logN. How likely that a Skiplist will behave in a non optimal fashion? Any program depending on it NOT so behaving has a bug How likely that a binary tree turns linear? Any program depending on this has chosen a wrong data structure! How likely that a compiler has a bug that will make your program fail one way or another? Well possible, but data dependent bugs are somewhat rarer, but certainly this is possible in a non-certified program. How much RAM is wasted because one makes redundant copies of a datastructures just to know when to release RAM without GC instead of sharing the datastructure with GC? Again, a program that depends on this without proper analysis has a bug and many, many other similar hazards that a program is exposed to. Well programs can be "exposed" to many problems caused by incompetent engineering decisions. I would say that relying on a conservative garbage collector NOT to get unlucky is something that you can afford to do in one-off programs that don't need to be reliable, and perhaps even in typical PC software (so what if the word processor crashes once a week - that seems to be what people expect anyway). But, as in my original point, I don't see that many high reliability programs could rely on conservative GC for correctness, though possibly they could rely on it for average case performance requirements. P.S. does lack of expertise mean you have no experience with conservative collectors? For someone with no experience, you sure are an enthusiast :-) I will admit I have no experience with them either, because I have never had occasion to need or want unreliable garbage collection in any program I have written. I have OFTEN relied on reliable garbage collection, and consider this a very valuable feature for a very large range of programs.