Re: Storage management, was Compiler writers will love this language

ericmuttta@email.com (Eric) wrote in message news:03-07-023...
> mwotton@cse.unsw.edu.au (Mark Alexander Wotton) wrote in message news:03-06-106...


[snip]


> I really fancy reference-counting is its low overhead,


Sorry to throw a spanner in your works but reference-counting has a
_higher_ overhead than mark-and-sweep, just ref-counting spreads this
overhead through out the entire programme where mark-and-sweep bunches
the overhead together in a large cluster (which may be observed as a
short pause in the application during a mark/sweep cycle.) A pause,
such as this, is obviously not desireable for interactive tasks, but
is no problem for batch jobs (where through-put is more important than
responsiveness.) That is why I use a mark/sweep GC in my compiler,
the overhead is less plus there is only need for 1 bit in the
structure for the mark, instead of 4 bytes for a reference (which
should reduce cache overhead.)


[snip]


> How, by the way, does generational collection deal with circular
> references? Could the algorithm used be adapted for use in reference
> counting, to form a sort of new hybrid scheme?


I seem to remember reading a paper discussing an algorithm to solve
the circluar reference problem, I cannot seem to find the paper right
now (was it Lester92?), citeseer.com should help for anyone interested.


[snip]


> > > I admit, reference-counting has its problems and I have been toying
> > > around with an idea for what I call "compile-time
> > > reference-counting". Basically, I am looking for a set of rules,
> > > that will allow the compiler to figure out when to release memory
> > > for an object, *without* having to allocate memory space for a
> > > reference counter value. Instead, using these rules, the compiler
> > > can analyse code at compile time and statically work out the
> > > life-time of an object. Its a bit wishy washy at the moment but if
> > > its at all possible, I will write a paper on it :)
> >
> > It smells a bit undecidable to me. At least for the complete case, I think
> > this reduces to the halting problem.
> >
> > Object foo(Object x, Object y) {
> > if (halts(x)) {
> > return y;
> > } else {
> return x;
> > }
> > }
> >
> > When do you release x's memory?
> >
> > You may be able to find some decent heuristics, but I suspect it's a lot
> > harder than it looks.
>
> The scheme as it stands now actually seems to work fine, when you do
> not have any conditional statements (eg If..End If statements). One
> rule that I came up with that allows this is "references can only be
> 'nulled out' or reassigned to another instance, in the scope of their
> declaration"


I am working on a similar scheme, however you get this problem
when someone does something like...


Wombat * externalProcedureUnknownToCompiler ( Wombat * );


Wombat * undecidable ( void ) {
    Wombat * w = new Wombat;
    return externalProcedureUnknownToCompiler();
}


Now did the externalProcedureUnknownToCompiler() return
a new Wombat variable or a copy of the reference to the
Wombat it was passed? Plus has the nasty external callee
squirreled away another copy of the reference somewhere?
Both of these problems are clearly undecidable at
compile time (due to lack of information.)


[I guess the above is a variant of the Halting problem.]


On the otherhand, you could solve the problem above by
having a different procedure stack unwind code for
the condition that returns y and that which returns x.


So there is no reason to discard your "compile-time
reference-counting" (I say that because I have
independently arrived at a similar scheme - I do not
doubt may others has as well.) Just make the
compiler clever enough to be able to spot when
something is undecidable (and use a run time GC
scheme) and when to use the normal scheme.


My idea selects wether the object should be
allocated on the stack or on the heap based on
wether the references to the object instance
outlives the procedure's scope (and autocalls
destructors on deallocation or procdure return.)


> Sub Blah
> Dim f As New Foo
> ...
> Call BarProc(f)
> ...
> End Sub
>
> with that rule, the compiler knows that the only scope in which the
> reference "f" can become null, is within procedure Blah. Within
> BarProc, "f" can be manipulated as desired, but BarProc is not allowed
> to set "f" to null or reassign it to refer to another instance.
> Then using static analysis, object life time can be worked out:


I guess cloning 'f' is acceptable, plus calling another similarly
restricted procedure with 'f' should be allowed and also you may
reduce the restriction to allow extra references to be creates
_provided_ that those references do not continue after the
subroutine has completed.


[
This is similar to the 'in' condition in my language, other
conditions are 'out', 'in out', 'new' and reference. With 'in'
the restrictions listed above are mandated plus the data within
the object is considered constant - therefore static checking
is possible. ('out' indicates a return, 'new' is similar to out
except it allocates a new object only when none is supplied.)
'in out' is similar to 'in' but indicates the parameter's
reference may be modified or stored by the procedure and
reference allows storage or data modification, though the
actual reference must remain unaltered. All of these
restrictions may be checked at compile time.
]


[snip]


> Dim f As Foo, g as Foo
>
> Set f = New Foo
>
> g = f
>
> If Something = True
> Set f = Nothing
> End If
>
> g = New Foo
>
> the compiler cant statically tell whether "f" was actually Nulled out,
> so after the "If" block, it doesnt know whether the refence count is 1
> or 2. Extra code would be needed to work that out, but then we might
> as well go back to the run-time reference counting scheme if we are
> going to add some overhead.


Not needed, just dupilcate the code after the 'If' adding
a deallocation for the 'True' condition. Or solve your
problem using code movement, a good optimiser should do
something like this...


[...]
        g = New Foo // code moved as
                                                // 1. g not used
                                                // 2. no procedure called
                                                // or procedure called
                                                // which meets 1.
        If Something = True
            Set f = Nothing
            // implicit call : deallocate 'f'
        End If


[Ewwww: who ever designed that syntax should have nasty
things done to them involving custard, even Lisp is
easier to type.]




> Well, as I said, its still a bit wishy washy but its showing signs of
> potential. If it ever works then it could really help save on memory
> use (eg if one would normally use a 4 byte (32bit) reference counter,
> and you had a collection of 1,000,000 objects, with this scheme you'd
> save 4MB!!)


Not to mention all the calls to malloc() it you can avoid
heap allocations and allocate on the stack!


[snip]


C 2003/7/3

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