Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!mcsun!ukc!edcastle!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.object Subject: Re: C++ and garbage collection (long, but interesting :->) Message-ID: Date: 23 Sep 90 01:07:38 GMT References: <1990Sep16.090226.11051@tukki.jyu.fi> <1990Sep18.131307.984@tukki.jyu.fi> <142839@sun.Eng.Sun.COM> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 185 Nntp-Posting-Host: teachb In-reply-to: pallas@red-dwarf.Eng.Sun.COM's message of 21 Sep 90 00:48:10 GMT On 21 Sep 90 00:48:10 GMT, pallas@red-dwarf.Eng.Sun.COM (Joseph Pallas) said: pallas> In pcg@cs.aber.ac.uk pallas> (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. pcg> It merely excludes all erroneous programs, i.e. all those that pcg> violate the interface contract with the storage manager. pallas> This is a novel interpretation, I should say. The C++ language pallas> most definitely does not include such a constraint in the pallas> language definition. I am sorry, but I cannot understand your comment. The definition was not specific in any way to C++. As understood in academic circles, the garbage collection problem is: given a memory snapshot with recognizable pointers and object boundaries, and a list of root pointers, identify all objects reachable from that list, and reclaim all the others. In this context the language definition here is irrelevant; what is relevant, I am fairly tired here of repeating it, is the language implementation. Can we have a faithful and efficient language implementation (for any given language X) such that conservative g.c. is possible? For Pascal and C, definitely yes. But for obscure details that can turn up yet, this is also possible for C++. Again: a conservative g.c. storage reclaimer cannot work with a language implementation that uses a format for pointers different from that for which the storage manager has been written. This is not, as I understand it, a constraint. It is simply a condition for the implementation to work at all, i.e. not to be erroneous. Using a conservative g.c. would be a 'constraint' if it required changes in the language definition, not just respect of its interface contract from the other components of the implementation. 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. 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++). pcg> Well, in that case you cannot use that pointer as operand to operator pcg> delete either, so if you are doing manual storage reclamation your pcg> object has become unreclaimable -- unless you keep around a pointer to pcg> the 'E*', in which case no problem arises under any reclamation policy. pallas> This is a substantial constraint you are suggesting: automatic storage pallas> reclamation that works correctly only if the program can be pallas> transformed, by just the addition of delete operations, into one that pallas> correctly reclaims all garbage with manual storage reclamation. We pallas> seem to agree that the set of such programs is smaller than the set of pallas> valid/legal programs. Again this seems very obscure to me -- you seem to be suggesting that a program that does not reclaim storage, either totally or partially, is valid and legal. It may be true in the sense that a program that does no storage reclamation gives the same results as one that does (modulo destructors, that is) -- storage consumption after all is part of pragmatics, not semantics, so it may seem you have a point. Incidentally I am quite disappointed that nobody so far has raised the thorniest problem with C++ and automatic storage reclamation, especially conservative g.c., which is indeed destructors. The problem however we are discussing is *reclamation*, not just semantics, in the sense that we have already granted that pragmatics *are* relevant to our discussion, because we want to do reclamation. Sakkinen has explicitly stated that we are not interested in the null reclaimer. We are interested in comparing a manual reclamation policy with one based on a conservative g.c., I have so far presumed. So the question is whether conservative g.c. can be implemented in such a way that it will indeed identify and *reclaim* as much non in use storage, and no in-use storage, without altering a program's behaviour, as would a manual reclaimer, or better. But even assuming that leaving storage unreclaimed is not a mistake, programmers can always disable the storage reclaimer for a critical section, just as they can refrain from deallocating manually an object if still holding pointers to its members. Nobody *forces* you to always have the collector enabled either. It is true that refraining from calling operator delete is not the same as calling say 'DontReclaim()' (or 'DontReclaim(object)' for a more selective disabling), but consider that these are pretty marginal cases on one hand, and on the other that in general the program texts that are designed for different storage management policies need not be the same, as long as they are equivalent (just for the sake of example, if the storage allocation policy changes, so may the number of arguments to operator new -- for example we may add to each call a binary value to select fast/slow storage). Typically the program logic that depends on the details of the interface contract to the storage manager will, in well written programs, be relegated to some low level module. This will be particularly important in the case of manual storage reclamation. pcg> It would be 'in-use' as long as the resulting pointer did not have pcg> a different *format* (I very carefully wrote that) from that pcg> returned by the storage allocator and returned by the storage pcg> deallocator; in your example the format is not changed, just the pcg> value of the pointer is. pallas> No, you did not very carefully write that. I did, I did. You quoted me: pcg> address *as if* returned by the storage allocator I think I also used *format* explicitly in some other of my excessively long articles. pallas> What you very carefully wrote (above) was that the address of pallas> the object (i.e., the VALUE, not just the format) appears in a pallas> pointer in storage. I do not understand you again here. Of course a pointer, which must be in the same format as that of pointers to objects returned by the allocator, must contain a value. Which value is irrelevant -- I have even allowed explicitly illegal addresses, addresses to members of a composite object, obtained with any form of arithmetic on pointers, etc... Or maybe I did assume here that it was understood that 'object' in general also denotes an object that is part (member or inherited) of another object, as in the example by Sakkinen. This is why the *as if* above -- a pointer to an object part of another object will not be actually one of those returned by the storage collector, but one derived by pointer arithmetic from one of those, but as long as it looks *as if* it had been returned by the storage allocator (i.e. it has the same format), the value of a pointer word is irrelevant. pallas> You seem to be assuming your conservative collector honors all pallas> interior pointers. But that is not what you are writing. I am sorry I did not make myself understood here -- as I have repeated to exhaustion, if you use a BIBOP style storage allocator, a pointer to the middle of a composite object trivially implies the pointer to the beginning of the (whole) object, and will protect the entire object. It is true however that in general, i.e. without a BIBOP style storage allocator, or the use of type tables, a pointer to an object that is part of another is not equivalent, storage reclamation wise, to a pointer to the whole composite object in which it sits. pcg> Note that the conservative reclaimer will do one better than even pcg> a manual one using free(3) or operator delete would, because if pcg> these were used either one would have to reclaim all of the pcg> structure, ... or could not reclaim the structure even if the pcg> reference ... were lost .... pallas> Now you're not making sense. Either you honor interior pointers pallas> or you don't. If you do, your collector cannot reclaim anything pallas> in this example. If you don't, your above claims are pallas> invalidated. Which is it? I do not understand again what you are writing. I am quite tired in effect, so that maybe why. I will try to express myself better, maybe this will help: Sakkinen proposed an example in which a composite object is protected only by a pointer to an object part of it. The composite object *cannot* be reclaimed manually, because a pointer to one of its parts cannot be used with operator delete, because it has the wrong type (if nothing else). A conservative g.c. (that cooperates with a BIBOP style storage allocator) will not reclaim the composite object as long as a pointer to an object that is part of it is still around; when no such pointers remain, the entire composite object will be reclaimed. This looks to me an improvement, and a safe one as to that, over manual reclamation. As I said, it takes a sophisticated storage reclaimer, manual or automatic, and a type table at runtime, to be able to reclaim only the unreachable subojects of a composite object, leaving the reachable subobjects alone. operator delete is not even allowed to do it, because it must be presented with a pointer with the same type and value as one returned by a call to operator new. -- 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