Xref: utzoo comp.object:1817 comp.lang.c++:9601 Path: utzoo!attcan!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.object,comp.lang.c++ Subject: Re: C++ and garbage collection (long, but interesting :->) Message-ID: Date: 19 Sep 90 12:20:24 GMT References: <1990Sep16.090226.11051@tukki.jyu.fi> <1990Sep18.131307.984@tukki.jyu.fi> Sender: pcg@aber-cs.UUCP Followup-To: comp.object Organization: Coleg Prifysgol Cymru Lines: 231 Nntp-Posting-Host: teacha In-reply-to: sakkinen@tukki.jyu.fi's message of 18 Sep 90 13:13:07 GMT [ I have added comp.lang.c++ to the newsgroup list, because this is is discussion mostly on C++ implementation, not on general OO implementation, but I have ensured that followups are to comp.object to avoid fragmenting the thread across two newsgroups ] On 18 Sep 90 13:13:07 GMT, sakkinen@tukki.jyu.fi (Markku Sakkinen) said: sakkinen> In article sakkinen> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: pcg> The definition of "in use" being that its address as if returned by the pcg> storage allocator appears in one or more pointers in storage. If you are pcg> using any other definition of "in use" you are making your own rules, pcg> and we are no longer speaking of storage allocation or reclamation as is pcg> described in the current academic literature on the subject. sakkinen> Aha, we have been playing with different rules. This I seemed to understand. Unfortunately your rules are somewhat questionable; your arguments are based on the assumption that the programmer and the storage reclaimer may use a different definition of 'in-use', by using different notions of pointer. Under such an assumption then you show that storage reclamation is not safe. This is not an interesting result :-). sakkinen> I thought we were talking about the applicability of GC to sakkinen> _general_ C++ programmes. You in contrast are intending only sakkinen> code that obeys certain additional constraints. The idea that programmer and storage reclaimer use the same notion of 'in-use' and thus of pointer is not an additional constraint, under any commonly accepted interpretation of the word. sakkinen> I have no objection to the statement that "GC is applicable to sakkinen> C++ programmes as far as they obey rules that make them sakkinen> susceptible to GC." The correct wording is "Storage reclamation of any sort is only possible in C++, as in any language, as far as C++ programmes agree with the storage reclaimer on what is a pointer". sakkinen> The constraint that you suggest above seems extremely severe sakkinen> for C++. It does not seem so to me; it merely excludes all erroneous programs, i.e. all those that violate the interface contract with the storage manager. The interface contract on operator delete, the C++ manual storage reclaimer, is even more severe, as in: sakkinen> For instance, suppose we have a case of multiple inheritance sakkinen> where class D is some other base class than the first, of class E. Nitpicking: well, it could be *any* base class -- there is no reason for which MI has to be implemented by strict prefixing. The problem is valid in general. sakkinen> If we now create an object by 'new E' and cast the resulting pointer sakkinen> to the type 'D*', it will no more point to the same address that sakkinen> the allocator returned (at least in some implementations of C++). Well, in that case you cannot use that pointer as operand to operator delete either, so if you are doing manual storage reclamation your object has become unreclaimable -- unless you keep around a pointer to the 'E*', in which case no problem arises under any reclamation policy. C++ (like most any language I can remember) has a rule that says that you can only apply operator delete to the same pointer, in value *and* type, that was returned by some call to operator new. A (conservative or not) garbage collector need not be that restrictive. sakkinen> This is legal, sound, and commonplace C++ usage, but according sakkinen> to your rule the object would no more be "in use". It would be 'in-use' as long as the resulting pointer did not have a different *format* (I very carefully wrote that) from that returned by the storage allocator and returned by the storage deallocator; in your example the format is not changed, just the value of the pointer is. For example, this is virtually exactly equivalent to have a pointer to a structure member, or an array element, in C, as in: struct s { int a,b,c; }; int *ip; s *s1 = (struct s *) malloc(sizeof (struct s)); ip = (int *) &s->b; s1 = 0; Well, after this, a conservative garbage collector will *not* reclaim the relevant storage area. The storage for fields 'a' and 'c' will be wasted of course, but this is nearly unavoidable, without type information and a very sophisticated reclaimer. Note that the conservative reclaimer will do one better than even a manual one using free(3) or operator delete would, because if these were used either one would have to reclaim all of the structure, thus making '*ip' meaningless, or could not reclaim the structure even if the reference to 's1->b' were lost, because free((void *) ip); ip = 0; would of course be illegal (by the rule mentioned above that you can only deallocate an object with the same pointer that was returned by a call to the storage allocator). Let's switch to C++ and consider your example class C { ... }; class D { ... }; class E : C,D { ... }; E *e = new (E); D *d = (D *) d; Now, as in the example above, if you lose the pointer contained in 'e', the object allocated by operator new is unreclaimable, because you cannot write e = 0; delete d; Of course you can write e = 0; delete (E *) d; but here you are making use of information that you have not given to the compiler. By contrast a conservative g.c. that uses a BIBOP style storage allocator will correctly not reclaim that space as in e = 0; Reclaim() because 'd' still protect the entire object, but will effciently reclaim the space when no longer protected by either 'e' or 'd' as in: e = 0; d = 0; Reclaim(); Knowing this, I did not say that the conservative storage reclaimer would only work with pointers returned by the allocator, but with pointers *of the same format*, which is weaker than the equivalent interface contract on manual storage reclamation. In other words, in similar situations, the conservative g.c. will safely reclaim *more* space than manual reclamation. Even illegal pointers are allowed (i.e. those denoting an invalid address), as long as they have the same format as those returned by the allocator component of the storage manager. pcg> Even free(3) will fail if you pass it an encrypted or XOR-ed or pcg> otherwise encoded form of a pointer. sakkinen> (Since we are speaking about C++, we should refer to the sakkinen> 'delete' operator instead of the 'free' function, which is sakkinen> unknown to C++ standards unless it has surfaced in Release sakkinen> 2.1.) Ahhh. Here then we merely need to make the storage reclaimer understand the format of pointers accepted by operator delete -- if you are using an underlying storage reclaimer that cannot accept all pointer formats that the programmer can supply to operator delete, you are using the wrong reclaimer. It is an interesting question whether it is always possible to implement C++ in such a way that all pointer formats used by the implementation can be fairly easily identified as such by examining a snapshot of memory, without using type information. In other words: can C++ be implemented without modification in such a way that the interface contract with the storage manager allows for conservative garbage collection? This is certainly true for C, and almost any other language I can remember. I think it is also true for C++, because all pointers in it must point either to the beginning or within a valid object (or array thereof, except for the harmless end-of-array exception), and a BIBOP style storage allocator means that one has no problem with pointers to the middle of an object (like in your example above). I think that the only problem seems to be with pure based or relative pointers; but probably this is not a problem, because while a based or relative pointer is essentially undetectable in a memory snapshot, it is not meaningful if there is no absolute pointer to the whole object somewhere, and this absolute pointer will protect the object. sakkinen> Certainly, but 'delete' does not require that you have sakkinen> preserved the pointer exactly in its original form, without sakkinen> interruption, all the time from 'new'. That's the difference! Here you seem to say that with manual storage reclamation the programmer can temporarily change the format of a pointer and leave the corresponding object "unprotected", because reclamation will only be triggered manually. Well, an automatic storage reclaimer need not be triggered at unexpected times -- indeed any decent automatic storage reclaimer offers you the option either to be only activated explicitly or to defer its invocation till the end of a critical region, if you are temporarily violating the interface contract with it. pcg> It is *much* safer for application programmers to leave reclamation in pcg> the hands of a purpose built reclaimer, than to try to design their own pcg> reclamation policy and algorithm, and even system programmers, that know pcg> the problems, find manual storage reclamation difficult to get right. sakkinen> I agree, but my conclusion is: programmers should prefer sakkinen> cleaner OO languages that make things like this possible, and sakkinen> not C++. I beg to differ inasmuch C++ is involved -- the advantages of cleaner languages than C++ may be: 1) they are simpler to understand and use than C++, as you have so often demonstrated. 2) they usually do not require a conservative storage reclaimer, so that they can reclaim all garbage. Automatic storage reclamation is *possible* and *safe* in C++, even if less efficient than in language that provides type information to the storage manager. But again, as to this: the loss of space to garbage is often minimal, and I know of languages where, even if possible, the implementation does not bother to provide type tables to the storage manager, and uses conservative g.c. instead. -- Piercarlo "Peter" Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk