Re: Static Garbage Collection

Vincent Belliard <vincent@famillebelliard.fr>
26 May 2009 22:09:26 GMT

          From comp.compilers

Related articles
Static Garbage Collection ott@mirix.org (Matthias-Christian Ott) (2009-05-25)
Re: Static Garbage Collection dot@dotat.at (Tony Finch) (2009-05-26)
Re: Static Garbage Collection gneuner2@comcast.net (George Neuner) (2009-05-25)
Re: Static Garbage Collection torbenm@pc-003.diku.dk (2009-05-26)
Re: Static Garbage Collection mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2009-05-26)
Re: Static Garbage Collection stock@esa.informatik.tu-darmstadt.de (Florian Stock) (2009-05-26)
Re: Static Garbage Collection ott@mirix.org (Matthias-Christian Ott) (2009-05-26)
Re: Static Garbage Collection vincent@famillebelliard.fr (Vincent Belliard) (2009-05-26)
Re: Static Garbage Collection DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-05-29)
Re: Static Garbage Collection armelasselin@hotmail.com (Armel) (2009-05-29)
Re: Static Garbage Collection marcov@stack.nl (Marco van de Voort) (2009-05-30)
Re: Static Garbage Collection vincent@famillebelliard.fr (Vincent Belliard) (2009-05-31)
Re: Static Garbage Collection armelasselin@hotmail.com (Armel) (2009-06-01)
| List of all articles for this month |

From: Vincent Belliard <vincent@famillebelliard.fr>
Newsgroups: comp.compilers
Date: 26 May 2009 22:09:26 GMT
Organization: les newsgroups par Orange
References: 09-05-120
Keywords: GC
Posted-Date: 28 May 2009 17:38:29 EDT

Le Mon, 25 May 2009 21:28:01 +0200, Matthias-Christian Ott a C)critB :


> Hi,
> today I stumbled upon a very intresting problem on garbage collection:
>
> Suppose we have a goto-free, pointer-less, static strongly typed
> programming language without any binary libraries (so all source code is
> available at compile time).
>
> Then we could construct the control flow graph for the entire programme.
>
> Couldn't we than statically (of course depending on conditions during
> runtime) determine the locations for the appropriate malloc() and free()
> calls, depending on if a referenced object is no longer used?
>
> The result would be same as if you manually managed you memory, so you
> would have no runtime overhead garbage collection, just for the tests of
> the user input, because we can predict everything that does not depend
> on user input at compile time.
>
> Regards,
> Matthias-Christian
> [This feels like it's equivalent to the halting problem which is known
> to be insoluble in the general case, albeit often soluble in specific
> instances. -John]


If you have a tree structure for your objects, it's obvious : you just
have to count reference on objects and then delete objects when the count
reach 0.


If you have a graph structure, it's quite difficult. If you have a loop
with your objects, you won't be able to delete it even if it's not
referenced anymore.


One way to solve the problem is to qualify references.
You can have mandatory references (from a local, a global or an argument).
You can have tree references (with such a reference you can only define
tree structure : only one tree reference on one object and no loops).
Then you can have share references (i.e. all the others references).


With this definitions, an object can be deleted only if there is no
mandatory nor tree references on it. If there is no mandatory nor tree
references then you have you cases :
- there is no share references on the object then you can delete it.
- there is at least one share reference left then you must check if you
can delete the object. For this case, it's a garbage collector problem.


With qualified references, you can reduce the needs for a garbage
collector but you still have a need for it.



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.