Re: Static Garbage Collection

On Mon, 25 May 2009 21:28:01 +0200, Matthias-Christian Ott
<ott@mirix.org> wrote:


>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.


Google "region based memory management".


>[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]


It's not quite that bad. The best you can do with some allocations is
approximate their lifetimes ... so any solution would necessarily be
equivalent to a conservative GC. The major difference is that
deallocations can throw away a whole heap at a time so the amortized
cost of operation is less than GC.


George

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