Path: utzoo!utgpu!news-server.csri.toronto.edu!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: What is Objective C? Message-ID: Date: 14 Sep 90 15:08:45 GMT References: <3864@bingvaxu.cc.binghamton.edu> <77500056@m.cs.uiuc.edu> <1990Sep12.074154.657@tukki.jyu.fi> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 108 Nntp-Posting-Host: odin In-reply-to: sakkinen@tukki.jyu.fi's message of 12 Sep 90 07:41:54 GMT On 12 Sep 90 07:41:54 GMT, sakkinen@tukki.jyu.fi (Markku Sakkinen) said: sakkinen> In article sakkinen> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: pcg> On 4 Sep 90 22:36:00 GMT, johnson@m.cs.uiuc.edu said: ... johnson> Although I agreed with most of what Paul Chisholm said, I johnson> disagree with this statement. My experience with C++ is that johnson> memory management takes a lot of CPU time. We use reference johnson> counting, and have to lock objects before changing their johnson> reference count (we are using a multiprocessor). pcg> For example, this is *not* necessary in many cases. Since you pcg> *must* eventually invoke a garbage collector to reclaim cycles, you pcg> can just accept imprecise reference counting, that is counting that pcg> misses some count decrements. Or you can use reference count logs, pcg> etc... sakkinen> Perhaps you didn't notice that Prof. Johnson wrote specifically sakkinen> about C++. I did, uhh, I did. sakkinen> Because of pointer arithmetic, it is not *possible* to use sakkinen> garbage collection safely with C++ (or any C-based language). Or perhaps you misinterpret the C/C++ language -- pointer arithmetic is only allowed within an array. As such it is exactly equivalent to array indexing in other languages. Indeed in C/C++ array indexing and pointer arithmetic are *exactly* equivalent. Any other use of pointer arithmetic is outside the language. Therefore legal C/C++ programs do not special problems because of pointer arithmetic. The problem with C/C++ and collection, which is worked around by conservative storage reclamation, is that since you do not have in general type and size information available at runtime, the reclaimer does not know which words contain pointers and how long objects are. This has nothing to do with pointer arithmetic. sakkinen> (I have read Boehm's article in Software - Practice and sakkinen> Experience, but the reason for his success seemed to be that sakkinen> those large pieces of existing C software that he experienced sakkinen> with were amazingly constrained and well-behaving in their use sakkinen> of pointers.) The reason for his success is that, in the absence of type and size information, he only reclaims store only when he is absolutely sure that it is garbage -- every word that looks like containing a pointer into the heap (even if in fact it only contains an integer or even a piece of string whose binary value could be interpreted as an address into the heap) is treated like one, and will protect the relevant store from being reclaimed. This is absolutely safe, even if it will miss some garbage -- but then reference counting will also miss some garbage (cycles). Note that conservative collectors require a BIBOP like memory allocator to get around the other problem, not knowing an object's length, and this is admittedly un unavoidable disadvantage because a BIBOP style allocator may have a larger working set than otherwise. If we are to speak about actual, and not just _legal_ C/C++ programs, *some* programs do things that are illegal (far fewer than is commonly thought of), but those same C++ programs will not fail under conservative garbage collection, they will just accumulate more unreclaimed garbage, and on average not much of it. The state of the art seems to be that even if clever reference counting and sliding compaction are competitive with garbage collection, the facts that you still need a collector alongside reference counting to reclaim cycles, and that a copying collector can be tuned to optimally pack objects for maximum locality of reference, mean that _in general_ a copying compacting incremental collector will be simpler and perform better. Also, _even for C/C++_ there is no need to use simple reference counting -- maybe Johnson is indeed using all the nice tricks (mostly discovered or used by the Xerox people for their DORADO implementation) to make it a much lower overhead technique than is commonly thought of. Or maybe not, and he is using reference counting as illustrated in most C++ books. Either way, I think that he should not be doing his own storage reclamation at all, reference counting or garbage collection or whatever, not any more than he should be doing his own storage allocation, first fit or cartesian trees or BIBOP or whatever, unless he is doing research on *this* subject, or has some *very* special requirements. Otherwise he had better rely on some system programmer having done the proper thing in some library. This system programmer will have had the difficult task of making some design choice after reading the abundant literature on the issue, and here we have some serious problems. My own reckoning is that it is hard to beat Baker's incremental collector or one of its derivatives, unless one has very particular requirements (e.g. OS kernel), in which case one should ponder things very carefully. For example in some cases manual storage reclamation *may* be workable and efficient, just as manual storage allocation may be, usually those where reference counting or garbage collection are not necessary, because the reclaimability of an object is implicit in the overall data structure in which it is linked (e.g. if it is a tree or a forest of trees). -- 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