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: Hans-Juergen Boehm Subject: Re: Garbage Collection in Ada Date: 1996/10/17 Message-ID: <32666C4A.41C6@mti.sgi.com>#1/1 X-Deja-AN: 190101383 references: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> <199610162305033003135@dialup100-4-3.swipnet.se> <3265BD97.41C6@mti.sgi.com> cc: boehm content-type: text/plain; charset=us-ascii organization: Silicon Graphics Inc., Mountain View, CA mime-version: 1.0 newsgroups: comp.lang.ada x-mailer: Mozilla 2.0S (X11; I; IRIX 6.2 IP22) Date: 1996-10-17T00:00:00+00:00 List-Id: Robert A Duff wrote: > > In article <3265BD97.41C6@mti.sgi.com>, > Hans-Juergen Boehm wrote: > >For systems I've seen it does inhibit some optimizations, ar least to > >the extent that proper use of a conservative collector inhibits > >optimizations. Especially in multithreaded systems, there must be a > >recognizable pointer to every accessible object at every program point > >at which a GC might occur. Often this is between every pair of > >instructions. In a nonconservative system you could generate > >arbitrarily complex tables to allow reconstruction of those pointers. > > I would think it would be simpler and more efficient to represent this > information as executable code. That is, the compiler generates a > procedure for each type, and for each stack frame, that knows how to > find all the pointers. It could take the PC as a parameter, so it could > deal with optimizations where, for example, register R1 contains a > pointer sometimes, and an integer other times. > That seems to be the consensus. Whether or not it's right probably depends on the context. There appear to be systems around that lose performance by generating code instead of tables. There are at least 2 reasons it may be undesirable: 1. Code size. Even generating traversal procedures for user-defined data structures is not free. (The SRC Modula 3 implementation does this, so it should even be possible to quantify the effect.) Things get much worse if you have to generate a traversal procedure for every client procedure frame, and if the result of that procedure depends on the PC value. Even table sizes for code with limited GC interruption points are nontrivial (see the paper by Diwan, Moss, and Hudson in PLDI 92). I would guess that generating such code for really arbitrary interruption points with full optimization would more than double code size. (Actually this is impossible in a few odd cases. See the above paper.) 2. Too much procedure call overhead, especially for structures composed of many small user-defined types. How much of an issue this is depends on the details of the compilation system. But it's usually easier to optimize tables with whole program information than code. Since table interpretation can be cheap, this may dominate. > Anyway, I don't understand why you would want a conservative collector, > unless you're dealing with an uncooperative language/compiler (like C). > If the language "requires" gc, then there's every opportunity to have a > well-defined interface between generated code and gc, so why be > conservative? > There are several reasons to go with a collector that acts conservatively by default, but can make use of type information: 1. C intercallability. 2. The compiler-collector interface is much simpler, at least for the fall-back case. You might get code compiled by one compiler to link against code compiled by another. 3. You can scan the top stack frame conservatively. Then you only need to have pointer location information at call sites, potentially reducing table (or traversal code) size substantially. 4. You don'y have to get the type information right for hand-coded routines in the runtime. In my experience, this is a significant source of persistent GC bugs. It also makes it easier to debug other type descriptor problems. -- Standard disclaimer ... Hans-Juergen Boehm boehm@mti.sgi.com