pallas@red-dwarf.Sun.COM (Joseph Pallas) (09/18/90)
In <PCG.90Sep14160845@odin.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: >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 [have] special [GC] problems >because of pointer arithmetic. Well, it depends. The designer of a conservative GC system has to make a critical decision about interior pointers. (Interior pointers are pointers into the middle of an object, such as C/C++ programmers use frequently.) The decision is whether to treat interior pointers as valid or not. The tradeoff is this: In C/C++, well-behaved correct programs can have live data to which the ONLY pointers are interior pointers. These programs are rare, although they are perfectly legal. But honoring all interior pointers can reduce the effectiveness of conservative GC dramatically. I'll quote without permission here from David Chase, who worked on the Olivetti Modula-3 compiler: Now, with conservative collection (speaking loosely) one plays a statistical game. The larger an object is, the more likely that some integer out there will happen to look like a pointer into it. In this case [a large hash table], there was ALWAYS some integer resembling a pointer, and thus the hash table was never collected, nor was anything referenced from the hash table. So, to do conservative collection in C/C++, you can either restrict the set of legal programs to exclude those that use interior pointers without keeping around base pointers, or you can take the risk that your conservative collector will leak. The severity of the leak will depend on the programs, of course. Some will leak badly, and some may not leak at all. So, one way or the other, pointer arithmetic in legal C/C++ programs make conservative GC less reliable. joe