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/21 Message-ID: <326BE660.41C6@mti.sgi.com>#1/1 X-Deja-AN: 191024762 references: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> 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-21T00:00:00+00:00 List-Id: I will argue yet again that there is no fundamental difference in reliability between conservative collection and a general purpose vendor-supplied nonmoving memory allocator with explicit deallocation. To guarantee that your program doesn't run out of memory, you would have to prove that a certain amount of memory suffices. I'm not an expert on Ada implementations, but in C this is impossible for many reasons: 1. The worst-case memory requirements of ANY general purpose malloc implementation are quite bad. This is a mathematical theorem. The only way to limit this is to restrict object sizes. 2. Many vendor malloc implementations have even worse worst-case behaviour, sometimes much worse. 3. Vendors rarely specify the allocation algorithm. So it's not possible to tune for the algorithm even in nonportable code. 4. Independent of fragmentation issues, language standards don't sprcify padding, allocator overhead, etc. Random corrections/observations: - I know of no commercial system vendors that include a conservative GC. There are many third-party language implementations that include a GC that's at least partially conservative (e.g. SRC Modula-3, NAG Fortran 90, Sun's Java, Sather, ...) - I don't believe it's realistically possible for a C compiler to exclusive-or the pointer location into the pointer value (or to use self-relative pointers). Copying pointer-containing unions becomes essentially impossible. (This is irrelevant to the discussion, but ...) - "Virtual origins" work fine with a conservative GC, so long as you also keep the naive pointer representation. This is likely to be cheap (at most one extra store). - The latest draft of the C++ standard requires new and delete to be replaceable. (This is also irrelevant, I think ...) - There are a number of measurements of accidentally retained memory by conservative GC. It's usually smaller than fragmentation losses, which aren't very big either. That says nothing about worst-case bounds. -- Standard disclaimer ... Hans-Juergen Boehm boehm@mti.sgi.com