Compiler writers will love this language
Eric
better designed if experienced compiler writers were there right from
the beginning when Mr/Mrs Language Designer were designing their new
language. If Mr/Mrs LD decided to have feature A, the compiler writer
would say "oh no, that would affect the grammar in such and such a way
- which is not fun to implement". If Mr/Mrs LD decided to have
semantics B, the compiler writer would say "that's no problemo, bring
it on".... After lengthy negotiations a cool language is produced and
its reasonably easy to implement.
So here we are. Imagine for a moment that I am a language designer and
*you* are my faithful compiler writer. I am all excited about a
language X that I am going to design and many ideas are coming my way.
However seeing that I am a polite and considerate language designer, I
am going to consult you and seek your advice on certain aspects of X,
so as to make your life easier when it comes to implementation. While
I may not end up granting all your requests, am still interested in
hearing them.
So then, according to your experience, what are your guidelines? The
kind of answers am looking for are in this form:
*if you decide to have _____ then make sure you have/dont have ____
due to the way they interact when mixed together
* you can include feature _____, its useful and easy to implement
* keep in mind that ____ is harder to implement than ____ but they do
the same/similar thing
* stay away from ____ its not worth the trouble unless you need ____
* look at the grammar for language _____ , its easier/harder to
implement because it does/doesn't have _____
* grammars which have/dont have _____ or are like ____ are good/bad
because I can/can't do ____
* ensure your semantics for feature A are like ____ because of _____
* language ___ does ____ in this way, but it would be better to do it
like ____ because then we would implement it using _____
* _____ is better kept in the language because then I can do ____ to
optimize
* but _____ should go in libraries rather than the language because of
_____
you know, that sort of thing. You don't have to fill in the blanks to
the *exact* sentences above - feel free to answer the way you see fit.
I'd appreciate it if you could:
* give examples of languages I can refer to with respect to your
recommendations
* state which languages you've been involved in implementing and in
which year
* give reasons for your recommendations where possible
* point me to an papers/books that deal with what affects the
implementability of programming languages
* address any or all things in the categories: syntax, semantics,
code generation, optimization, memory management, run-time
environments (and whatever else you want)
It's like having an opportunity to create a language that you'll
*love* to implement, so fire away! Many thanks in advance :)
Cheers, E.
Ps: I am interested in programming language design and compiler
writing. I know more about the former than the latter, hence this
post. I am also reading the classic text: "Compilers: Principles,
Tools and Techniques" by Aho, Sethi and Ullman.
Torben Ægidius Mogensen
> So then, according to your experience, what are your guidelines? The
> kind of answers am looking for are in this form:
>
> *if you decide to have _____ then make sure you have/dont have ____
> due to the way they interact when mixed together
Don't mix unspecified evaluation order with unrestricted side-effects,
such that the result of a computation may depend on the (unknown)
evaluation order.
If you have pointers with less-than comparison and arithmetic (adding
offsets to pointers or subtract pointers to find a distance), make it
illegal (or at least undefined) to compare/subtract two pointers that
are not derived on the same base pointer (i.e, pointers into the same
array or struct).
> * you can include feature _____, its useful and easy to implement
Many things come to mind. Look at SML for a lot of features that are
nice and (relatively) easy to implement, e.g., higher order functions,
inductive data types with pattern matching, polymorphism, type
inference, a good module system, etc.
> * keep in mind that ____ is harder to implement than ____ but they do
> the same/similar thing
OO with dynamic dispatch is harder to implement than polymorphism
combined with type-classes (as in Haskell), but the latter is just as
useful (maybe more).
> * stay away from ____ its not worth the trouble unless you need ____
Mutual inheritance (unless static).
> * look at the grammar for language _____ , its easier/harder to
> implement because it does/doesn't have _____
Symbol-table dependent parsing, i.e., completely different paring
depending on whether a symbol is a type name, a variable name or a
class name. C++ is the prime horror story here, with so many
context-dependent rules that no parser for C++ is strictky conforming
to the standard.
> * language ___ does ____ in this way, but it would be better to do it
> like ____ because then we would implement it using _____
Many languages implicitly assume that all pointers can be null
pointers. It is better to distinguish this through the type, so you
can avoid testing for null pointers when the type ensures it can't
happen. Ideally, you would have subtyping, so a non-null pointer can
be passed to a function that expects a possibly-null pointer.
> * _____ is better kept in the language because then I can do ____ to
> optimize
Memory allocation, because I have free choice of GC or similar.
> * but _____ should go in libraries rather than the language because of
> _____
i/o, because there are so many variants of how it is done.
> Ps: I am interested in programming language design and compiler
> writing. I know more about the former than the latter, hence this
> post. I am also reading the classic text: "Compilers: Principles,
> Tools and Techniques" by Aho, Sethi and Ullman.
That book is good, but a bit dated. I propose that you supplement
this with a more modern text. Good choices are
- Andrew Appels "Modern Compiler Implementation in ML/C/Java" (3
books, mainly differing in which language is used to describe
implementation details)
- "Modern Compiler Design" by Grune, Bal, Jacos and Langendoen.
Alas, I know of no good book covering language design. Most modern
langauges have articles by the designers, presenting the reason behind
some of the design choices. These are a good place to start. You
should also read John Hughes' article "Why Functional Programming
Matters".
Torben Mogensen
VBDis
>However seeing that I am a polite and considerate language designer, I
>am going to consult you and seek your advice on certain aspects of X,
>so as to make your life easier when it comes to implementation.
What kind of language do you have in mind? If it is a general programming
language, what does it make different from already existing languages?
What's the difference between "designing" a language, and writing down its
grammar?
IMO the designer of a language should study existing languages first,
and reUSE existing designs, before trying to reINVENT the wheel.
DoDi
Eric
> , ericm...@email.com (Eric) schreibt:
>
> >However seeing that I am a polite and considerate language designer, I
> >am going to consult you and seek your advice on certain aspects of X,
> >so as to make your life easier when it comes to implementation.
>
> What kind of language do you have in mind? If it is a general programming
> language, what does it make different from already existing languages?
I am thinking of a general purpose, multi-paradigm programming
language. Your second question "what makes it different from existing
languages?" is an interesting one, but unfortunately it cannot be
answered fully within this space because
1) there is loads I can say and
2) I dunno if the comp.compilers folks would agree that this is the
right place to give the details.
If I was to say one thing about it, I think it would be that it gives
greater accessibility to power - power to clearly and quickly express
solutions to problems that often need to be solved in pairs.
> What's the difference between "designing" a language, and writing
> down its grammar?
Hmm. To me, "designing" a language, is thinking about problems that
need to be solved and then crafting a tool (ie the language) that is
suited to solving those problems. Writing down the grammar is indeed
part of the design (because you have to ask "how do I want the syntax
to look like?") but I would class that as being more about "language
specification" ie (formally) describing the design on paper.
>
> IMO the designer of a language should study existing languages first,
> and reUSE existing designs, before trying to reINVENT the wheel.
That's solid advice and indeed, I believe we get new ("good")
languages because someone studied existing languages and found them to
come up short. I think for two possibly similar languages X and Y,
there is a general sentence that says "Y was created because X
did/didn't do A, B and C".
Unfortunately a lot of the time language designers adopt existing
designs without questioning them and we have age old design mistakes
continually propagating into new languages. You will tend to find that
if a language designer created a language Y, and they were previously
experienced with language X, many of the faults in Y can be traced
back to X. One of the biggest things robbing us of great new advances
in language design is the fact that we use language X for so long,
that all its faults become transparent to us and propagate to the new
languages we later design.
For instance, take C and C++. Backward compatability is an important
goal and sometimes inevitable evil, but why was is it *so* important
when it came to C++?
Admittedly, that's where C++'s greatest strengths and weeknesses lie,
but I have always wondered what the world would be like if Mr.
Stroustrup had loosened up a little bit on the backward compatability
goal :)
Cheers, E.
[Language design is on-topic insofar as it affects compiler design and
implementations. But don't argume about where the semicolon goes.
-John]
Eric
> ericm...@email.com (Eric) writes:
>
> > *if you decide to have _____ then make sure you have/dont have ____
> > due to the way they interact when mixed together
>
> Don't mix unspecified evaluation order with unrestricted side-effects,
> such that the result of a computation may depend on the (unknown)
> evaluation order.
I have often wondered how specifying evaluation order impacts
implementation. The arguments I have heard for it are:
- it allows consistency between different compilers hence allowing
code portability between compilers
- it allows one to take advantage of evaluation order in expressions
The second one sounds dubious at first but thinking about it, we
always rely on our code executing from top to bottom and write the
code so its dependant on that execution order. So then, is it
unresonable to specify that evaluation order is left-to-right (or
vice-versa)? If so, what are the arguments for leaving the order
undefined? (I have heard something related to efficiency and register
allocation during procedure invocations, but no explanation was
given).
> If you have pointers with less-than comparison and arithmetic
> (adding offsets to pointers or subtract pointers to find a
> distance), make it illegal (or at least undefined) to
> compare/subtract two pointers that are not derived on the same base
> pointer (i.e, pointers into the same array or struct).
I think illegal is more like it. If that were allowed, won't the result
*always* point to somewhere that's statically unknown and hence
impossible to prove as legally/safely addressable?
> > * you can include feature _____, its useful and easy to implement
>
> Many things come to mind. Look at SML for a lot of features that are
> nice and (relatively) easy to implement, e.g., higher order functions,
> inductive data types with pattern matching, polymorphism, type
> inference, a good module system, etc.
I haven't had a chance to look at SML yet, but will do soon.
Meanwhile, I am familiar with the above features except "higher order
functions" and "inductive data types". This page:
http://www.dcs.ed.ac.uk/home/stg/NOTES/node31.html
says that higher order functions are "Functions which take functions
as an argument...". Is that similar to function pointers in C/C++
where functions are called by address instead of by name?. On the same
vein, are closures related to this in any way?
> > * keep in mind that ____ is harder to implement than ____ but they do
> > the same/similar thing
>
> OO with dynamic dispatch is harder to implement than polymorphism
> combined with type-classes (as in Haskell), but the latter is just as
> useful (maybe more).
OOP terms seem to have loads of meanings nowadays. When I hear about
"dynamic dispatch" in OOP, I think about how polymorphic invocations
are implemented by using tables of function addresses (eg C++ virtual
tables). It also makes me think about something I have heard being
called "multi-methods". It involves function overloading with
overload resolution occuring at run-time, based on the actual type of
all arguments to the function (this feature strikes me as being harder
to implement than static overload resolution, or atleast harder to
implement efficiently.) Are any of what I have mentioned, what you
mean when you speak of "OO with dynamic dispatch"?
> > * stay away from ____ its not worth the trouble unless you need ____
>
> Mutual inheritance (unless static).
Again, this is a new one to me. Is it about having a class A inherit
from B which inherits from A? If so (due to the circular reference)
how would constructors work in this scenario? What would "static" mean
in this context and how does it help?
> > * look at the grammar for language _____ , its easier/harder to
> > implement because it does/doesn't have _____
>
> Symbol-table dependent parsing, i.e., completely different paring
> depending on whether a symbol is a type name, a variable name or a
> class name. C++ is the prime horror story here, with so many
> context-dependent rules that no parser for C++ is strictky conforming
> to the standard.
I have encountered this one while writing simple parsers. It's a lot
harder to write a parser if each symbol's meaning cannot be resolved
without look-ahead or back-tracking. It's a bit of a trade-off between
having a smaller language (in terms of number of symbols) or a simpler
parser. Languages with fewer symbols will tend to overload many of
them (eg the "static" keyword in C++) and its the symbol overloading
that results in context-sensitive meanings, which in turn make parsing
difficult. Having more *unique* symbols reduces the need to overload
the meanings of symbols, so parsers are simplified because they can
resolve the symbol's meaning without looking at the context of its
occurence. One of the hard parts of language design, is coming up with
good keywords the meaning's of which can easily be guessed at.
> > * language ___ does ____ in this way, but it would be better to do it
> > like ____ because then we would implement it using _____
>
> Many languages implicitly assume that all pointers can be null
> pointers. It is better to distinguish this through the type, so you
> can avoid testing for null pointers when the type ensures it can't
> happen. Ideally, you would have subtyping, so a non-null pointer can
> be passed to a function that expects a possibly-null pointer.
I am having difficulty imagining a type which is implemented using
pointers and ensures that null cant occur. This would imply that for a
variable of such a type, memory would be allocated and then never
released. Memory deallocation is what leads to null pointers and if
the type ensures that you cant have null pointers then it is
implicitly saying you cant deallocate the memory for variables of that
type. Unless ofcourse the language:
1) allowed paramater passing by constant reference (like in C++) and
2) ensured that all pointer parameters were non-null on entry to a
function
then inside a function, we know that the user cant assign a null value
to the pointer (because of rule 1 above) and that the pointer cant be
null to begin with (because of rule 2) so we can remove all null
testing code at each point where the pointer is dereferenced. To do
this for local variables, the language would allow "run-time
constants" where a variable is initialised once (at run time) and
cannot be assigned to from that point on.
Also, on the subject of pointers, I have always been bothered by the
disparity between value types (ie those with value semantics like
int,float etc) and reference types (those with reference semantics
like object variables in OOP).
In Visual Basic for instance, if I dont initialise an integer
variable, its initialised to zero for me and I can use it without
getting some exception thrown (unless ofcourse I divide by zero).
However, with an object variable, if I use it before initialisation, I
get an null reference exception thrown at me. My question is, why dont
I just get an object in its default state (ie the one that would
result after the default constructor has run), ready for use just like
I do with the integer variable? Using lazy initialisation, the
language could leave the reference as null, up until the point I try
to use it. This way I dont have to litter my code with null pointer
testing or "try...catch...end try" blocks. Plus, if I want to
interpret the "nullness" of an object variable to mean something, I
can still test for null and act accordingly. This scheme would
eliminate a lot of error checking code hence allowing code to be
clearer, be written faster, be compiled faster and be smaller.
<snip good recommendation to keep memory management in the language
and I/O in the libraries>
<snip recommendation on good books which I will look at in due course>
> Alas, I know of no good book covering language design. Most modern
> langauges have articles by the designers, presenting the reason behind
> some of the design choices. These are a good place to start. You
> should also read John Hughes' article "Why Functional Programming
> Matters".
I only know of one book on language design and its online too (the
link may break over two lines):
"http://www.awprofessional.com/catalog/product.asp?
product_id={92E30B39-5D91-45F9-9919-D202BE6341F9}"
Thats the Addison Wesley link, but if you Google for "Advanced
Programming Language Design" by Raphael Finkel, you'll find somewhere
to download the PDF files for it.
I also tend to look for language critiques, coding style guides, any
papers with the words "traps and pitfalls", papers that say "X sucks"
where X is the language under fire, and one of the most resourceful of
places: these news groups themselves (especially the language advocacy
groups).
> Torben Mogensen
Thanks Torben, your recommendations have given me plenty to think
about.
Cheers, E.
Mark Alexander Wotton
>
> I am having difficulty imagining a type which is implemented using
> pointers and ensures that null cant occur. This would imply that for a
> variable of such a type, memory would be allocated and then never
> released.
Either that, or only released when all references to it have passed
out of scope. This is how many modern garbage-collected language
implementations work.
mrak
VBDis
>Hmm. To me, "designing" a language, is thinking about problems that
>need to be solved and then crafting a tool (ie the language) that is
>suited to solving those problems.
If I understand you correctly, then you care more about features than
about grammars. In this case you'd have to concentrate on the
algorithms which are useful in the area of interest, what data
structures are used by these algorithms, and how and which algorithms
can work together. These considerations almost go into the design of
objects (data types and structures) and a library of procedures and a
runtime system, not into the design of an compiler.
As to the runtime system, this can be more or less efficient. But IMO
this is a more a matter of optimization than of design. I'm not a
compiler writer myself, so I can give only some obvious hints, as to
consider the order (complexity) of the required algorithms. Some
keywords just come into mind, like OO, polymorphism, indirection,
globals, aliasing, and memory management. I'll not dig deeper into
these topics now, as long as I'm not sure whether they are of concern
to you. Only some general statements:
Object Orientation IMO is good, even if invisible to the user of a
language. Every data type with multiple members should become an
object, with related methods, so that it's clear to the user,
compiler, and to all procedures, how the information in such an object
can be accessed, interpreted and modified. Here I consider OO as a
design technique, with no implications on the concrete implementation.
Polymorphism and indirection is okay, as long as the objects
themselves are unambigous, so that it's possible to invoke their
methods without much guessing about the exact type of a given
object. Calling method X of interface Y of an object is not a very
complex operation, as long as the type of the interface(s) and the
pertaining methods are obvious from any given object.
IMO it's a good idea to force the user to explicitly define all
required interfaces of his objects, not only for the sake of a good
runtime behaviour, but also for a good application design. Allow for
compile time checks wherever possible, every check at compile time
prevents checks and errors at runtime.
Memory management can be implemented with or without garbage
collection, and with implicit or explicit initialization and
finalization of local objects. I'll leave it to more experienced
contributors to discuss these points, as well as the problems with
global variables and aliasing.
DoDi
Gene Wirchenko
[snip]
>I have often wondered how specifying evaluation order impacts
>implementation. The arguments I have heard for it are:
>
>- it allows consistency between different compilers hence allowing
>code portability between compilers
>
>- it allows one to take advantage of evaluation order in expressions
>
>The second one sounds dubious at first but thinking about it, we
>always rely on our code executing from top to bottom and write the
>code so its dependant on that execution order. So then, is it
>unresonable to specify that evaluation order is left-to-right (or
>vice-versa)? If so, what are the arguments for leaving the order
>undefined? (I have heard something related to efficiency and register
>allocation during procedure invocations, but no explanation was
>given).
Reversing that, you can take advantage of evaluation order. It
might be possible to optimise out constants by reordering evaluation:
#define OFFSET1 5
#define OFFSET2 15
...
... someint + OFFSET1 + OFFSET2 ...
The natural order for most programmers appears to be variable
followed by constant(s).
[snipped previous]
Sincerely,
Gene Wirchenko
Marco van de Voort
> structures are used by these algorithms, and how and which algorithms
> can work together. These considerations almost go into the design of
> objects (data types and structures) and a library of procedures and a
> runtime system, not into the design of an compiler.
I don't think that you can seperate compiler and runtime design.
Choices in compiler design affect the runtime library, but problems in
the runtime library can result in moving functionality back to the
compiler.
Eric
This scheme (reference-counting) is used in VB6 for instance. VB7 (and
every other .NET language?) uses generational, mark-and-sweep GC (hope
that's the right term for it). When I read its description, it sounded
like a rather elaborate scheme and one that would need a good deal of
implementation effort. I prefer plain vanilla automatic
reference-counting. Its deterministic (hence useful in real-time
systems), simple to explain and understand, and a lot easier to
implement and get right.
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 :)
> mrak
Cheers, E.
Eric
I see, if I define the order to be left-to-righ (or vice versa), the
compiler can perform "constant folding" and convert the above as
follows:
someint + 5 + 15 --> someint + 20
If programmers stuck to such ordering of constants and variables, the
compiler doesnt need much effort to do the above optimisation.
However, I would imagine that a compiler doing any kind of reordering
in the first place, could handle something like this:
OFFSET1 + someint + OFFSET2
just as easily, no? I'm still doing my A B C's of compiler writing so
I haven't gotten there yet, but I do know an extra degree of
"intelligence" is required on the compiler's part to handle that one.
It has to "figure out" that addition is commutative and hence my
version of the expression is equivalent to your version of the
expression. This means it can safely reorder the terms of the
expression and "fold" the constants into the single value "20", then
add that to someint.
Cheers, E.
Eric
> ericm...@email.com (Eric) schreibt:
>
> >Hmm. To me, "designing" a language, is thinking about problems that
> >need to be solved and then crafting a tool (ie the language) that is
> >suited to solving those problems.
>
> If I understand you correctly, then you care more about features than
> about grammars. In this case you'd have to concentrate on the
> algorithms which are useful in the area of interest, what data
> structures are used by these algorithms, and how and which algorithms
> can work together. These considerations almost go into the design of
> objects (data types and structures) and a library of procedures and a
> runtime system, not into the design of an compiler.
You could say am more feature-oriented than grammar-oriented, but its
hard to separate the two. For every problem the language has to solve,
there is a feature designed specifically to address that problem. And
for every feature, there must be a grammar to define what is a valid
way to express/use that feature in code. I have tried to keep
implementation issues in mind and when choosing/designing features, I
only accept those for which I can come up with a brief and verbal
description of an implementation algorithm.
Its also interesting that you mention designing libraries of objects
and procedures. I have been exploring the issues behind designing
standard libraries and consider the design of these libraries to be as
important as the design of the language itself. Its unfortunate that a
recent trend seems to assume that "big library" is a synonym for
"good/useful library". It sure does make for good advertising when you
can say "the xyz framework consists of over 200 classes...". In fact I
have a theory. We generally (all?) know the statement that our
programs spend 90% of their time executing only 10% of the code. From
this I have derived the fact that only about 25% of any interface is
absolutely crucial and will be used on a regular basis. Try this. Pick
any module/class in a library of your choice. Look through your code
that uses that library, and count the number of procedures and or
fields that you use. Now compare that to the total number of elements
in the entire interface. Try it with your cellular phone feature set,
your car dashboard items, the peripheral ports of your computer, your
favourite word processor etc...only about 25% of the interfaces for
those things are useful. (For a good programming example, if you have
Microsoft's .NET, look at the "System.Windows.Forms.Control" class.
How many of the 150+ elements of that class' interface will you use?)
> As to the runtime system, this can be more or less efficient. But IMO
> this is a more a matter of optimization than of design. I'm not a
> compiler writer myself, so I can give only some obvious hints, as to
> consider the order (complexity) of the required algorithms. Some
> keywords just come into mind, like OO, polymorphism, indirection,
> globals, aliasing, and memory management. I'll not dig deeper into
> these topics now, as long as I'm not sure whether they are of concern
> to you. Only some general statements:
Interesting. I have always thought that the best optimisation is
having a good solid design. Well, am a speed junkie - I love a program
that works and responds without undue delay. IMO, its especially
important to design the run-time system to be as efficient as
possible, simply because EVERY program written using it will suffer if
it isn't efficient - whether that's important for the program or not.
I find it a bit self-defeating to design things poorly, then work so
hard to create optimising compilers. Out of the things you've
mentioned above, I have noticed that the way a language is designed to
handle memory usage and management contributes greatly to its
performance levels.
> Object Orientation IMO is good, even if invisible to the user of a
> language. Every data type with multiple members should become an
> object, with related methods, so that it's clear to the user,
> compiler, and to all procedures, how the information in such an object
> can be accessed, interpreted and modified. Here I consider OO as a
> design technique, with no implications on the concrete implementation.
There are some places where OO shines and other places where it should
be avoided like the plague. For instance, I know of several data types
that have multiple members, but should not be implemented as
objects....This is a sensitive topic however and is usually the cause
of large debates, so suffice it to say that I consider OO a useful
enough paradigm to include in a language, and at the same time, a weak
enough paradigm that needs to be supplemented with other paradigms eg
procedural.
> Polymorphism and indirection is okay, as long as the objects
> themselves are unambigous, so that it's possible to invoke their
> methods without much guessing about the exact type of a given
> object. Calling method X of interface Y of an object is not a very
> complex operation, as long as the type of the interface(s) and the
> pertaining methods are obvious from any given object.
Polymorphism, be it via simple function pointers or the higher level
mechanism provided by OOP, is a powerful and useful concept to have.
However this is also another feature where great care is needed and
there are some rather interesting pitfalls that can occur (below is my
favourite one in VB7):
Module MyModule
Class Parent
Public Overridable Sub p1()
Console.Write("Parent.p1")
End Sub
Public Sub p2()
'blah blah
p1()
'blah blah
End Sub
End Class
Class Child
Inherits Parent
Public Overrides Sub p1()
Console.Write("Child.p1")
MyBase.p2()
End Sub
End Class
Sub Main()
Dim p As Parent
Dim c As Child
p = New Parent()
p.p1() 'OK
p.p2() 'OK
p = New Child()
p.p1() 'stack overflow
p.p2() 'stack overflow
c = New Child()
c.p1() 'stack overflow
c.p2() 'stack overflow
End Sub
End Module
The culprit is in the procedure p1() defined in the Child class. The
statement "MyBase.p2()" calls Parent.p2(). In the Parent class, p2()
calls Parent.p1(). However Parent.p1() is polymorphic so if we have an
instance of Child, the version called is the p1() defined in the Child
class. So Child.p1() calls Parent.p2() which indirectly calls
Child.p1() which calls Parent.p2() which calls.....yep, on and on
until there's no more stack space. Whats "lovely" about this pitfall,
is that the code is perfectly innocent and it fails randomly depending
on whether you have an instance of the Parent class or the Child
class. Its an excercise in masochism to try and find the problem if
the two classes were written separately and the code for the Parent
class isn't available.
> IMO it's a good idea to force the user to explicitly define all
> required interfaces of his objects, not only for the sake of a good
> runtime behaviour, but also for a good application design. Allow for
> compile time checks wherever possible, every check at compile time
> prevents checks and errors at runtime.
I am not sure if I understand you correctly there and could do with a
clarification. Is there any language that allows one to implicitly
define the interfaces to objects?
> Memory management can be implemented with or without garbage
> collection, and with implicit or explicit initialization and
> finalization of local objects. I'll leave it to more experienced
> contributors to discuss these points, as well as the problems with
> global variables and aliasing.
I am not sure how global variables affect implementation (although I
do know their effect on a program's design...you know, the usual
argument against tight coupling) but I know aliasing to be a trouble
maker for optimisers. I think (corrections are welcome) it's to do
with being unable to safely place aliased variables into registers.
> DoDi
Thanks for your comments DoDi.
Cheers, E.
Torben Ægidius Mogensen
> tor...@diku.dk (Torben Ægidius Mogensen) wrote:
> > Don't mix unspecified evaluation order with unrestricted side-effects,
> > such that the result of a computation may depend on the (unknown)
> > evaluation order.
>
> I have often wondered how specifying evaluation order impacts
> implementation. The arguments I have heard for it are:
>
> - it allows consistency between different compilers hence allowing
> code portability between compilers
>
> - it allows one to take advantage of evaluation order in expressions
>
> The second one sounds dubious at first but thinking about it, we
> always rely on our code executing from top to bottom and write the
> code so its dependant on that execution order. So then, is it
> unresonable to specify that evaluation order is left-to-right (or
> vice-versa)? If so, what are the arguments for leaving the order
> undefined? (I have heard something related to efficiency and register
> allocation during procedure invocations, but no explanation was
> given).
The advantage of leaving the order unspecified (when the semantics are
unaffected by the evealuation order) is that the compiler can optimize
the evaluation order. This can (as you say) allow the compiler to use
fewer registers or schedule instructions more efficiently,.
On a modest scale, unspecified evaluation order can apply to small
local side-effect-free expressions or it can extend so data-dependence
is the only things that determines evaluation order. The latter
allows even function calls to be executed in arbitrary order, or even
interleaved or in parallel. Haskell is an example of a language with
this feature.
> > If you have pointers with less-than comparison and arithmetic
> > (adding offsets to pointers or subtract pointers to find a
> > distance), make it illegal (or at least undefined) to
> > compare/subtract two pointers that are not derived on the same base
> > pointer (i.e, pointers into the same array or struct).
>
> I think illegal is more like it. If that were allowed, won't the result
> *always* point to somewhere that's statically unknown and hence
> impossible to prove as legally/safely addressable?
That is more or less the point. The C standard states that the
behaviour of the above is unspecified, but neither the compiler nor
the runtime system flags occurences of this. Hence, many C programs
rely on a specific compilers behaviour in these cases. Ideally,
potential occurrences of the behaviour should be caught at
compile-time, but in practice some cases must be left for runtime
checking.
> http://www.dcs.ed.ac.uk/home/stg/NOTES/node31.html
>
> says that higher order functions are "Functions which take functions
> as an argument...". Is that similar to function pointers in C/C++
> where functions are called by address instead of by name?. On the same
> vein, are closures related to this in any way?
Functions in C/C++ are all declared globally, so a function parameter
is only a code pointer. If you have locally declared function (as in
Pascal), a function parameter needs also to include an environment
pointer. This pair is called a "thunk" or "closure". In Pascal,
functions can't be returned out of their dynamic scope, so thunks can
be stack allocated. In true functional languages, there is no limit
to where functional values can be passed, returned or stored, so
thunks sometimes need to be heap allocated. Many implementations
always heap-allocated thunks, so they don't have to do global analysis
to figure out if it is safe to stack-allocate.
> > > * keep in mind that ____ is harder to implement than ____ but they do
> > > the same/similar thing
> >
> > OO with dynamic dispatch is harder to implement than polymorphism
> > combined with type-classes (as in Haskell), but the latter is just as
> > useful (maybe more).
>
> OOP terms seem to have loads of meanings nowadays. When I hear about
> "dynamic dispatch" in OOP, I think about how polymorphic invocations
> are implemented by using tables of function addresses (eg C++ virtual
> tables). It also makes me think about something I have heard being
> called "multi-methods". It involves function overloading with
> overload resolution occuring at run-time, based on the actual type of
> all arguments to the function (this feature strikes me as being harder
> to implement than static overload resolution, or atleast harder to
> implement efficiently.) Are any of what I have mentioned, what you
> mean when you speak of "OO with dynamic dispatch"?
Dynamic dispatch is when the actual method called isn't known until
run-time, so it has to be done via a virtual table (or similar
mechanism). This is easy and fairly efficient for single inheritance,
but (without whole-program analysis) it isn't for mutual inheritance.
If the method can be determined at compile-time, there is no problem,
though.
> > > * stay away from ____ its not worth the trouble unless you need ____
> >
> > Mutual inheritance (unless static).
> > Mutual inheritance (unless static).
>
> Again, this is a new one to me.
I meant _multiple_ inheritance. Sorry about the slip.
Static means that the methods can be identified at compile-time (see
above).
> > > * look at the grammar for language _____ , its easier/harder to
> > > implement because it does/doesn't have _____
> >
> > Symbol-table dependent parsing, i.e., completely different paring
> > depending on whether a symbol is a type name, a variable name or a
> > class name. C++ is the prime horror story here, with so many
> > context-dependent rules that no parser for C++ is strictky conforming
> > to the standard.
>
> I have encountered this one while writing simple parsers. It's a lot
> harder to write a parser if each symbol's meaning cannot be resolved
> without look-ahead or back-tracking. It's a bit of a trade-off between
> having a smaller language (in terms of number of symbols) or a simpler
> parser. Languages with fewer symbols will tend to overload many of
> them (eg the "static" keyword in C++) and its the symbol overloading
> that results in context-sensitive meanings, which in turn make parsing
> difficult. Having more *unique* symbols reduces the need to overload
> the meanings of symbols, so parsers are simplified because they can
> resolve the symbol's meaning without looking at the context of its
> occurence. One of the hard parts of language design, is coming up with
> good keywords the meaning's of which can easily be guessed at.
It is not just about overloading keywords or symbols. This is usually
not that difficult to handle in the grammar, nor too difficult to
understand for a human. The problem is if a piece of text should be
parsed completely differently if an indentifier is a type name, a
variable name, a class name, or other. C++ has this problem in
abundance and needs so complex disambiguation rules that no C++
compiler (to my knowledge) implements the C++ standard precisely.
> > Many languages implicitly assume that all pointers can be null
> > pointers. It is better to distinguish this through the type, so you
> > can avoid testing for null pointers when the type ensures it can't
> > happen. Ideally, you would have subtyping, so a non-null pointer can
> > be passed to a function that expects a possibly-null pointer.
>
> I am having difficulty imagining a type which is implemented using
> pointers and ensures that null cant occur. This would imply that for a
> variable of such a type, memory would be allocated and then never
> released. Memory deallocation is what leads to null pointers and if
> the type ensures that you cant have null pointers then it is
> implicitly saying you cant deallocate the memory for variables of that
> type.
You need to initialize every pointer variable on creation, either by
allocating an object to them or by copying the value of another
pointer variable. And you need to make sure that the variable that
holds the pointer is no longer accessible after you deallocate the
object it points to. This is the case if you use garbage collection
for deallocation, but other mechanisms can also be used.
Many languages (e.g., SML) have pointers that can never be null. But
it is also possible to have both nullable and non-nullable pointer
types in a language.
> Also, on the subject of pointers, I have always been bothered by the
> disparity between value types (ie those with value semantics like
> int,float etc) and reference types (those with reference semantics
> like object variables in OOP).
> In Visual Basic for instance, if I dont initialise an integer
> variable, its initialised to zero for me and I can use it without
> getting some exception thrown (unless ofcourse I divide by zero).
> However, with an object variable, if I use it before initialisation, I
> get an null reference exception thrown at me. My question is, why dont
> I just get an object in its default state (ie the one that would
> result after the default constructor has run), ready for use just like
> I do with the integer variable?
That is, essentially, what happens in a language like SML: A pointer
variable is forced to be initialized at creation.
> Using lazy initialisation, the language could leave the reference as
> null, up until the point I try to use it.
Lazy initialization is more complicated and requires run-time testing.
> This way I dont have to litter my code with null pointer
> testing or "try...catch...end try" blocks. Plus, if I want to
> interpret the "nullness" of an object variable to mean something, I
> can still test for null and act accordingly. This scheme would
> eliminate a lot of error checking code hence allowing code to be
> clearer, be written faster, be compiled faster and be smaller.
My point of having explicit distinction (by type) between pointer than
can be null and pointers that can't is essentially to avoid having to
check for null at runtime and avoiding null-cases in unit testing or
verification.
Torben Mogensen
Mikael 'Zayenz' Lagerkvist
> Alas, I know of no good book covering language design.
I'd like to recommend Michael L. Scott: Programming Language
Pragmatics. It's a clear and readable book focusing on programming
language principles with descriptions of implementations and design
criterions.
Mikael Lagerkvist
--
Student, Royal Institute of Technology
Stockholm, Sweden
~
Mark Alexander Wotton
>> out of scope. This is how many modern garbage-collected language
>> implementations work.
>
> This scheme (reference-counting) is used in VB6 for instance.
Reference counting and mark-and-sweep are just ways of implementing the basic
idea of deallocating when references are out of scope.
> VB7 (and every other .NET language?) uses generational,
> mark-and-sweep GC (hope that's the right term for it). When I read
> its description, it sounded like a rather elaborate scheme and one
> that would need a good deal of implementation effort. I prefer plain
> vanilla automatic reference-counting. Its deterministic (hence
> useful in real-time systems), simple to explain and understand, and
> a lot easier to implement and get right.
You do have the problem with reference-counting that it doesn't cope
very well with two-way links. Generational collection is nice partly
because it's complete (all unused allocations are reclaimed), and also
because it takes advantage of common memory use patterns: it's
optimised for the case of new objects pointing to old objects, which
is the usual case.
> 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.
mrak
Tony Finch
>
>I admit, reference-counting has its problems and I have been toying
>around with an idea for what I call "compile-time reference-counting".
Have a look at the papers about region-based memory management that
you can find at http://www.it-c.dk/research/mlkit/papers.html
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
Lex Spoon
> mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
>> On 5 Jun 2003 23:22:01 -0400, Eric posted:
>> >
>> > I am having difficulty imagining a type which is implemented using
>> > pointers and ensures that null cant occur. This would imply that for a
>> > variable of such a type, memory would be allocated and then never
>> > released.
>>
>> Either that, or only released when all references to it have passed
>> out of scope. This is how many modern garbage-collected language
>> implementations work.
>
> This scheme (reference-counting) is used in VB6 for instance. VB7 (and
> every other .NET language?) uses generational, mark-and-sweep GC (hope
> that's the right term for it). When I read its description, it sounded
> like a rather elaborate scheme and one that would need a good deal of
> implementation effort. I prefer plain vanilla automatic
> reference-counting. Its deterministic (hence useful in real-time
> systems), simple to explain and understand, and a lot easier to
> implement and get right.
Incidentally, generalized garbage collectors (I don't know the right
term, either) have been in use for at least 20-30 years, and have been
very well studied. Personally, I use two garbage collected languages
every day (Smalltalk and Emacs Lisp) and I have used several others,
and I have yet to run into a GC implementation bug. They doen't seem
to be so hard to implement so long as you are *very* careful about
your invariants.
In fact, garbage collectors can be modular. The main requirement is
that the GC module is able to trace data structures through memory at
runtime, which typically requires extra run-time information tagged
onto both objects and stack frames. The simplest implementation of
this requires one word of overhead per object or frame, but there are
lots of tricks available for lowering this overhead. Like most other
parts of a compiler, people tinker and tune for some amount of time
and then force themselves to leave it alone and actually use the
thing. :)
Finally, please consider that reference counting collectors will
surprise the user when they fail, and will require weird tweaks by the
user when they do fail. A generalized garbage collector is much
nicer.
> 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 :)
Be sure to look up existing work. I'm certain that people have worked
on this kind of thing. Be aware that it won't work for everything;
for example, objects that are saved out into the heap will be awfully
hard to deal with automatically. But you can surely get rid of a lot
of the intermediate increments and decrements in the way you seem to
be thinking about.
Lex
[Garbage collectors don't go back 20 or 40 years, they go back at least as
far as early versions of Lisp around 1960. I think it's safe to say that
any new garbage collection trick someone comes up with is almost certain
to have been discovered and analyzed before. -John]
Peter "Firefly" Lund
> Instead, using these rules, the compiler can analyse code at compile
> time and statically work out the life-time of an object.
Region analysis, ML Kit.
http://www.it-c.dk/research/mlkit/
http://www.comp.nus.edu.sg/~cs6202/slides/12-regions.4.pdf
It has also been done for Java and Prolog.
http://citeseer.nj.nec.com/319724.html
http://www.diku.dk/topps/bibliography/1998.html#D-395
Then there is the Cyclone language from AT&T/Cornell which also
uses regions.
http://www.research.att.com/projects/cyclone/
-Peter
John R. Strohm
> On 20 Jun 2003 00:02:55 -0400, Eric posted:
> > mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
> >>
> >> Either that, or only released when all references to it have passed
> >> out of scope. This is how many modern garbage-collected language
> >> implementations work.
> >
> > This scheme (reference-counting) is used in VB6 for instance.
>
> Reference counting and mark-and-sweep are just ways of implementing
> the basic idea of deallocating when references are out of scope.
The problem with reference-counting GC has been known for close to twenty
years that I personally know of. From the well-known "AI Koans":
One day a student came to Moon and said: "I understand how to make a better
garbage collector. We must keep a reference count of the pointers to each
cons."
Moon patiently told the student the following story:
"One day a student came to Moon and said: `I understand
how to make a better garbage collector...
[Pure reference-count garbage collectors have problems with circular
structures that point to themselves.]
Note that a doubly-linked list falls into this category...
Joachim Durchholz
> mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
>
>>On 5 Jun 2003 23:22:01 -0400, Eric posted:
>>
>>out of scope. This is how many modern garbage-collected language
>>implementations work.
>
> This scheme (reference-counting) is used in VB6 for instance.
No, garbage-collected languages don't use reference counting.
> VB7 (and
> every other .NET language?)
AFAIK, .net uses automatic garbage collection.
> uses generational, mark-and-sweep GC (hope
> that's the right term for it).
Correct but somewhat overspecific: there are non-generational
mark-and-sweep collectors.
> When I read its description, it sounded
> like a rather elaborate scheme and one that would need a good deal of
> implementation effort.
That's true. Writing a good garbage collector takes several
person-months or person-years.
> I prefer plain vanilla automatic
> reference-counting. Its deterministic (hence useful in real-time
> systems),
The counterargument runs as follows:
Garbage collections becomes important exactly at the point when it's
becoming difficult to statically determine which parts of some data
structure become inaccessible.
In other words, there will be some code that manipulates pointers, where
static analysis won't reveal whether the block of memory pointed to
before the change just lost its last reference.
The problem is that the time needed to remove the link to that block
becomes statically unpredictable: it will either be the relatively cheap
decrement of a reference count, or it will be the much more
time-consuming process of adding the block to the list of free blocks,
potentially merging it with neighbouring free blocks, and updating lots
of background data structures that do heap management. Even worse:
freeing the block means decrementing the reference counts of all blocks
that the block-being-released referred to, creating an avalanche of
block releases that may affect all blocks where static analysis doesn't
determine that they stay accessible. That's not even viable for soft
real-time, let alone hard real-time!
There are techniques around this. For example, one can delay the actual
freeing of a block whenever there is time. This trades real-time latency
for some bookkeeping and noticeably more memory consumption (since
inaccessible data is not being freed at the earliest opportunity).
The next interesting point on the spectrum is already incremental
garbage collection. It's just like stop-the-world mark-and-sweep
collection, it just interleaves the execution of the garbage collection
and normal program execution. Since garbage collection is a separate
process, it can be deferred to "quiet times" (i.e. when not servicing
time-critical requests) just like delayed-freeing reference counting.
Reference counting is optimal for predicting memory usage (since no data
will be kept beyond necessity), but bad for predicting latency times.
Garbage collection is not very good for predicting memory usage, but
excellent for predicting latency times: assigning to a pointer is just
the usual write-to-memory, and garbage collection is just a background
process.
> simple to explain and understand, and a lot easier to
> implement and get right.
That's very correct. If you don't have a working garbage collector and
don't have the budget for writing one, use reference counting.
However, most of the time you have the Boehm-Demers-Weiser collector.
It's written in C and will run on practically any hardware that can run C.
> I admit, reference-counting has its problems
Yes, there are two serious problems here:
1) Reference counting cannot handle cycles. All solutions that I know
reintroduce mark-and-sweep at some scale, and I doubt it's even possible
to avoid it.
2) Reference counting is horribly expensive. Every single assignment to
a pointer incurs two memory writes: one to decrement the reference count
of the block that it previously referred to, and one to increment the
reference count it's going to refer to after the change.
If the hardware architecture has an on-CPU data cache, things are even
worse: you dirty two memory locations that are most likely not in the
cache line. Pointer writes require /triple/ the required memory
bandwidth compared to simply assigning to the reference in memory! In an
SMP environment, this also increases the chance that two CPUs must
engage in (time-consuming) cache coherency protocols when they wish to
modify data in the same cache line.
Finally, CPUs are favoring read accesses over write accesses. Adding a
write access is always more expensive than adding a read access.
There are ways to reduce the efficiency impact of reference counting,
but the net result of optimizing reference counting will give something
just as complicated as a good incremental garbage collector...
> 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.
There is research in that area available. Keywords to look for are
"liveness analysis", and/or "regional (garbage collection|liveness
analysis)". You'll also find a lot of people who are much more
knowledgeable than myself in news:comp.lang.functional.
Hope this helps,
Jo
Gene Wirchenko
>On 20 Jun 2003 00:02:55 -0400, Eric posted:
>> mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
[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?
if branch: yes, else branch: no.
Your code would make sense to me if the return values were
switched. Is that what you meant, or am I missing something?
>You may be able to find some decent heuristics, but I suspect it's a lot
>harder than it looks.
It does have that feel to me, too.
Sincerely,
Gene Wirchenko
Eric
> On 20 Jun 2003 00:02:55 -0400, Eric posted:
> > mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
> >>
> >> Either that, or only released when all references to it have passed
> >> out of scope. This is how many modern garbage-collected language
> >> implementations work.
> >
> > This scheme (reference-counting) is used in VB6 for instance.
>
> Reference counting and mark-and-sweep are just ways of implementing the basic
> idea of deallocating when references are out of scope.
Just out of curiosity, are these the only major automatic memory
management techniques out there?
> > VB7 (and every other .NET language?) uses generational,
> > mark-and-sweep GC (hope that's the right term for it). When I read
> > its description, it sounded like a rather elaborate scheme and one
> > that would need a good deal of implementation effort. I prefer plain
> > vanilla automatic reference-counting. Its deterministic (hence
> > useful in real-time systems), simple to explain and understand, and
> > a lot easier to implement and get right.
>
> You do have the problem with reference-counting that it doesn't cope
> very well with two-way links.
This problem really bugs, because the standard library is going to be
full of data structures the utilise two way links (eg. doubly linked
lists). Is there a general solution (other than using a completely
different scheme like mark-and-sweep) for this? One of the reasons I
really fancy reference-counting is its low overhead, but I suspect
that with a few adjustments to the algorithm, one can add in logic
that will detect circular links during deallocation. Its seems to be a
general graph traversal/tracing problem, where one wants to know "have
I visited this node before?" and if the answer is "yes" then we know a
circular link exists somewhere and act accordingly inorder to
deallocate the objects involved.
> Generational collection is nice partly
> because it's complete (all unused allocations are reclaimed)
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?
> and also
> because it takes advantage of common memory use patterns: it's
> optimised for the case of new objects pointing to old objects, which
> is the usual case.
Thanks for that point. Up until now I had always wondered why in the
world someone would choose generational GC. It is more complex to
implement, requires a completely separate entity (the collector), it
is harder to explain and understand conceptually, plus its unideal for
use in real-time environments. What other advantages are there for
this scheme? (other than the ones mentioned above) and in the long
run, are they worth the disadvantages?
> > 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"
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:
Dim f As Foo, g as Foo
Set f = New Foo
g = f
(at this point, the compiler statically knows that the instance of Foo
is being referred to twice)
Set f = Nothing 'null out the reference
(at this point, the compiler statically knows that the instance of Foo
is being referred to once because f has been set to Nothing)
g = New Foo
(now the compiler statically knows there are no more references to
that first instance of Foo, so it generates code to deallocate it.)
The rule I mentioned above is important and needed because it allows
the compiler to "see" every point at which references are set or
removed. This partly breaks down when you have conditional execution
because the compiler cannot know at compile-time whether the code will
execute (and hence adjus the reference count) or not. Eg if the above
code had been:
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.
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!!)
> mrak
You know, i have been calling you "mrak" all this time, is that
correct or just a typo for "Mark"? In any case, thanx for your
comments.
Cheers,E.
Dobes Vandermeer
>
> ericm...@email.com (Eric) writes:
>
> > mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
> >> On 5 Jun 2003 23:22:01 -0400, Eric posted:
> >> >
> >> > I am having difficulty imagining a type which is implemented using
> >> > pointers and ensures that null cant occur. This would imply that for a
> >> > variable of such a type, memory would be allocated and then never
> >> > released.
> >>
> >> Either that, or only released when all references to it have passed
> >> out of scope. This is how many modern garbage-collected language
> >> implementations work.
> >
> > 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 :)
>
> Be sure to look up existing work. I'm certain that people have worked
> on this kind of thing.
I've been looking around for something similar, the most I've found is
this paper:
Ran Shaham, Eran Yahav, Elliot K. Kolodner, and Mooly Sagiv,
Establishing Local Temporal Heap Safety Properties with Applications to
Compile-Time Memory Management. To appear in the 10th Annual
International Static Analysis Symposium (SAS '03) San Diego, California,
USA, June 2003.
Available from the author's web page at
http://www.math.tau.ac.il/~ransh/ (direct:
http://www.math.tau.ac.il/~rans/sas03-safety-mm.pdf )
This paper has some references, but its
Of course, if you think about it a little, you might expect that each
conditional test (in the run-time code) will follow the format:
for each live possible referencor X of Y:
if Y is referenced by X, Y is still alive, otherwise Y can be freed.
The problem lies in determination of the list of referencors.
For data structures that are globally accessible, you might be able to
calloect a list of possible referencors for a given object by just
annotating each function input/output with escape information.
For local variables, you can pass along information about which objects
that will be checked by the called functions are (or are not) referenced
further up, and you'll only get into real trouble with recursive
functions, where the size of this information is possibly unbounded (and
possibly difficult to determine before they are called).
Brute force would eventually produce a program that runs with very good
memory use, even if it was very very slow. Once you have it working you
can starting improving.
Everything starts to crumble as soon as you consider adding threads to
the model, though. How can you account for the state of other threads
in your tests? Every idea so far falls apart -- suddenly you have to
have this referencing information stored globally somewhere -- maybe
with the object? Maybe reduced to a simple counter for performance?
Sigh....
If I had time I would implement the non-threaded version and see how bad
the performance really is... if its less than 100 times as slow, it
would be a useful tool for measuring the real memory overhead of GC. I
think you could even adapt the algorithms to ignore variables which can
never be used again, which is as close to optimal memory usage as you
can get. (I suppose with optimal memory usage you would predict which
objects _will_ never be used again -- which requires foreknowledge of
the external inputs that affect the program's behavior).
Nick Maclaren
|>
|> The problem with reference-counting GC has been known for close to twenty
|> years that I personally know of. From the well-known "AI Koans":
I have known about it for nearly 40, and am no specialist! My guess
is that it dates from the days of early LISP, at the latest.
|> One day a student came to Moon and said: "I understand how to make a better
|> garbage collector. We must keep a reference count of the pointers to each
|> cons."
|> Moon patiently told the student the following story:
|>
|> "One day a student came to Moon and said: `I understand
|> how to make a better garbage collector...
|>
|> [Pure reference-count garbage collectors have problems with circular
|> structures that point to themselves.]
|>
|> Note that a doubly-linked list falls into this category...
Yes. But it IS a better garbage collector, in the case when such
references are not a problem. Take, for example, the following
language design:
Object ownership is strictly hierarchical (DAG, not tree - let's
not be unreasonably restrictive), and hard links (i.e. counted
references) exist within the ownership model.
The language allows the spawning of independent threads, with
some half-sane semantics. The point about this is only that,
without it, you can do static garbage collection and don't need
even reference counting.
Unrestricted pointers are soft links, constrained to be
relative to a specific object. EITHER their scope is such so that
the object's life must be longer than theirs (e.g. Algol 68) OR
they are specified in such a way that a soft link reference can
fail ("Object no longer exists").
The advantages of such a language for software engineering over
most current ones are legion - you can do some serious reasoning
and checking of memory resource usage, for a start. And you can
use reference counting garbage collection :-)
Regards,
Nick Maclaren.
Joachim Durchholz
>>Reference counting and mark-and-sweep are just ways of implementing the basic
>>idea of deallocating when references are out of scope.
>
> Just out of curiosity, are these the only major automatic memory
> management techniques out there?
From a distance, yes.
There are countless variations on both themes.
Reference counting often has various degrees of delaying the actual
deallocation (to keep reference count decrease times predictable).
Another common technique is avoiding having to install a reference
counter in the first place. I.e. there are approaches that try to
identify memory blocks that don't ever make it out of the scope where
they were created, and don't let them enter the garbage collection
mechanism in the first place. Actually this technique is applicable
to both reference counting and mark-and-sweep.
Mark-and-sweep variations include:
1) Incremental collection. Both mark and sweep phase are somehow
integrated into the program. Some schemes do "a little bit of work" on
every call to malloc(), others run as a coroutine or in a separate process.
2) Generational collection. This tries to exploit the assumption that
data that has lived for a long time is unlikely to vanish in the next
cycle of garbage collection, and not garbage collected. Every so often
the older generation(s) are collected as well. The usefulness of this
approach isn't generally accepted AFAIK, but most incremental collectors
are generational as well anyway.
3) Copying collectors. The simplest version of this is having two heaps.
Live blocks are "marked" by copying them from heap 1 to heap 2. When all
live blocks are copied, the garbage is summarily collected by declaring
heap 1 to be a huge free block, and the next cycle starts by reversing
the roles of heap 1 and heap 2. (The "treadmill" scheme splits this into
more sub-heaps, and only one heap being copied from, so that the
overhead shrinks from 50% to as low as your space-time trade-off dictates.)
Interesting variations exist for heaps that are fragmented into
separate areas with unreliable communication (i.e. if data is
distributed over networked computers). Last time I looked, there was
no reliable algorithm that was had better than O(N^2) performance for
N nodes. In other words, that's an area where lots of scientific kudos
can be gained :-)
> This problem really bugs, because the standard library is going to be
> full of data structures the utilise two way links (eg. doubly linked
> lists). Is there a general solution (other than using a completely
> different scheme like mark-and-sweep) for this?
There is: use two types of pointers, normal and weak. Normal pointers
keep the referred-to block alive, weak pointers don't. (For example,
in a doubly-linked list, the back pointers are usually made weak.)
The downside is that it's sometimes not easy to determine which pointer
should be made weak. Besides, weak pointers may become dangling at any time.
> One of the reasons I really fancy reference-counting is its low
> overhead,
Let me repeat: reference counting does NOT have low overhead. Every
single assignment to a pointer adds two (!) memory writes. Unless your
data structures are relatively static, this will have a serious
performance impact!
A good incremental garbage collector will have a 5-10% overhead.
Reference counting is usually in the same domain.
There's a simple experiment, easy to do in C++. Write a
reference-counting smart pointer class, and a variant that's just normal
pointers. (Make sure that the normal-pointer variant of the class is
always fully inlined by the compiler, i.e. check the assembly output
that assignments to a pointer don't go through a subroutine call.) Run
your software with reference counting, then with normal pointers and
with the the Boehm-Demers-Weiser collector installed. For comparison
purposes, run the software with no garbage collection at all (i.e. with
normal pointers and no garbage collector), just to see how much overhead
garbage collection takes in general. (Make sure you have enough memory
to run your program when it never deallocates...)
I'm pretty sure that the difference between having no GC and any GC is
more than the difference between reference-counting GC and
mark-and-sweep GC :-)
> but I suspect that with a few adjustments to the algorithm, one can
> add in logic that will detect circular links during deallocation.
If you do that, you have a "hybrid" collector. It has been done
several times. Research conclusions were that hybrid collectors are
neither simpler nor faster than normal mark-and-sweep collectors.
> Its seems to be a general graph traversal/tracing problem, where one
> wants to know "have I visited this node before?" and if the answer
> is "yes" then we know a circular link exists somewhere and act
> accordingly inorder to deallocate the objects involved.
That's exactly the mark phase of a mark-and-sweep collector :-)
>>Generational collection is nice partly
>>because it's complete (all unused allocations are reclaimed)
>
> How, by the way, does generational collection deal with circular
> references?
Just like any other mark-and-sweep collector. Generational collection
simply considers all blocks of older generations to be alive without
actually checking them. In other words, it cuts down on checking time
and pays by keeping blocks alive that have become unreachable. (This
is why generational algorithms check older generations every once in a
while, to get rid of the accumulated cruft.)
> Could the algorithm used be adapted for use in reference
> counting, to form a sort of new hybrid scheme?
Yes, but it would probably not be worth the work. Generational
collection is there to reduce the marking work; however, in a hybrid
scheme, the mark-and-sweep phase would only serve to clean up the
remnants that accidentally formed cycles.
> [mark-and-sweep is] unideal for use in real-time environments.
The reverse is true. With reference counting, every single assignment to
a pointer may remove the last reference to a potentially large set of
blocks. This makes reasoning over the cost of a pointer assignment
non-local.
For mark-and-sweep GC, all you have to do is to set aside enough time to
do the garbage collection. You still have a global number to compute,
namely an upper bound on the number of blocks that get allocated and/or
unreachable, but you do that computation once, not for every point in
the code where a pointer is modified.
Even better, mark-and-sweep is error-tolerant. You have a memory
requirement; add a bit more memory, and unexpected "spikes" in memory
usage will not matter since the additional memory will be collected
anyway (and if the time for GC isn't enough, the accumulated garbage
will still be deallocated in the GC run AFTER the incomplete run). Of
course, the unexpected memory usage should be monitored and analyzed,
and the error in the memory consumption calculations should be
corrected. But the chances for device failure will be reduced, and
/that's/ a Good Thing.
>>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).
But that's the entire point!
As long as you don't have if/end if, you can do all memory usage
calculations at compile time.
With if/end if, things get interesting in the first place...
Regards,
Jo
Mark Alexander Wotton
>> very well with two-way links.
>
> This problem really bugs, because the standard library is going to be
> full of data structures the utilise two way links (eg. doubly linked
> lists). Is there a general solution (other than using a completely
> different scheme like mark-and-sweep) for this? One of the reasons I
> really fancy reference-counting is its low overhead, but I suspect
> that with a few adjustments to the algorithm, one can add in logic
> that will detect circular links during deallocation. Its seems to be a
> general graph traversal/tracing problem, where one wants to know "have
> I visited this node before?" and if the answer is "yes" then we know a
> circular link exists somewhere and act accordingly inorder to
> deallocate the objects involved.
As soon as you've done graph traversal, though, you've got the same
overhead as mark and sweep. The appeal of reference counting (apart
from simplicity) is that it's got a constant overhead (modulo the case
discussed where a freed object sets off a chain of deallocation). To
be honest, I'm not even convinced that reference counting does have
low overhead. If A points to B, and is then changed to point to C,
then I have three memory accesses instead of 1: I have to decrement
B's counter and increment C's, as well as the actual write to A.
(Idle thought: seeing as the only way to create circular references is
through mutable references in a strict language, or tying the knot in
a lazy one, perhaps reference counting would be useful for a strict
purely functional language.)
>> Generational collection is nice partly
>> because it's complete (all unused allocations are reclaimed)
>
> 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?
My understanding is that generational collection is essentially an
optimisation on mark and sweep, which has no problems with circular
references.
>> mrak
>
> You know, i have been calling you "mrak" all this time, is that
> correct or just a typo for "Mark"? In any case, thanx for your
> comments.
It's a deliberate tyop. My real name is Mark.
Mrak
--
realise your life was only bait for a bigger fish
-- aesop rock
Nick Maclaren
|> Eric wrote:
|> > mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
|> >
|> >>out of scope. This is how many modern garbage-collected language
|> >>implementations work.
|> >
|> > This scheme (reference-counting) is used in VB6 for instance.
|>
|> No, garbage-collected languages don't use reference counting.
Eh? Few if any "garbage-collected languages" specify the method they
use, or even whether the garbage is ever collected. It is one of the
great faults of their design, because it makes it much, much harder to
write reliable portable code.
|> > VB7 (and
|> > every other .NET language?)
|>
|> AFAIK, .net uses automatic garbage collection.
Reference counting IS a form of automatic garbage collection. Not a
very powerful one, as you point out, but it is still one.
Regards,
Nick Maclaren.
Basile STARYNKEVITCH
Joachim> Eric wrote:
>> mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote
>>
>>> On 5 Jun 2003 23:22:01 -0400, Eric posted:
>>>
>>> Either that, or only released when all references to it have
>>> passed out of scope. This is how many modern garbage-collected
>>> language implementations work.
Modern GC are usually *not* reference-counters based! But some crude
language implementations do happen to have poor garbage collectors,
sometimes only reference-counting based (which works poorly for
reference cycles and costs a lot).
>> This scheme (reference-counting) is used in VB6 for instance.
Joachim> No, garbage-collected languages don't use reference
Joachim> counting.
Sorry to be picky, but reference counting actually is a (crude) method
of garbage collection (and language implementations have GC, not the
language themselves!) Of course, I do think that most of the time,
better ways of garbage collection exist, in particular generational
copying GC (which can even be used in C, provided you agree to follow
strict coding constraints - see http://freshmeat.net/projects/qish for
an example of such a GC).
Ref counting does have it uses, notably in distributed GC (where they
are used in addition of better, locally working, GCs).
See for example Jones&Lins' book on GC for more.
Regards.
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net
aliases: basile<at>tunes<dot>org = bstarynk<at>nerim<dot>net
8, rue de la Faïencerie, 92340 Bourg La Reine, France
Lex Spoon
management, but a couple of comments got under my skin. For the
record:
>> This scheme (reference-counting) is used in VB6 for instance.
>
> No, garbage-collected languages don't use reference counting.
Garbage collection is actually a general term that includes reference
counting. Note that no garbage collector is perfect, due to the
Infinite Employment Theorem for Compiler Writers. Good garbage
collection is as much of an optimization as, say, good register
allocation.
> > When I read its description, it sounded
>> like a rather elaborate scheme and one that would need a good deal of
>> implementation effort.
>
> That's true. Writing a good garbage collector takes several
> person-months or person-years.
Not necessarily. If nothing else, you can hook into the Boehm-Weiser
collector to get started:
> That's very correct. If you don't have a working garbage collector and
> don't have the budget for writing one, use reference counting.
> However, most of the time you have the Boehm-Demers-Weiser collector.
> It's written in C and will run on practically any hardware that can run C.
Also, the entire Squeak VM took only person-months to implement (I
don't know the exact time frame), and the garbage collector was just
one part of it.
Lex
Rodney M. Bates
> One of the reasons I
> really fancy reference-counting is its low overhead, but I suspect
> that with a few adjustments to the algorithm, one can add in logic
> that will detect circular links during deallocation.
Actually, as I recall, reference counting has much higher overhead
than all forms periodic tracing GC. Intuitively, it's because it has
to keep track of referenceability all the time, whereas the periodic
collectors can forget about it for a time, then recompute what is
referenceable only occasionally.
Reference counting can operate right down to zero "headroom", i.e.
available space, whereas the others generally need a certain amount of
headroom.
Short of resorting to some kind of hybrid with a tracing algorithm,
I don't believe anyone has ever fixed the cyclic graph problem with
reference-counting.
With this much interest in the subject, you should get the book:
http://www.cs.kent.ac.uk/people/staff/rej/gc.html
http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html
It's a good summary of the massive number of published papers on GC,
and would answer a lot of these questions.
--
Rodney M. Bates
Mark Alexander Wotton
>>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?
>
> if branch: yes, else branch: no.
>
> Your code would make sense to me if the return values were
> switched. Is that what you meant, or am I missing something?
The idea is that you can't statically determine whether or not you branch.
If you could, you'd have solved the halting problem.
x represents a (program,input) pair, and halts(x) tells you whether the
program given ever stops with the given input. Now I think about it a bit
harder, I've made it needlessly subtle: I'm using x in two ways, as the
program to be tested _and_ the object to be freed.
To be a bit more verbose:
Object foo(Program p, Input i, Object x, Object y) {
if (halts (p,i)) {
return x;
} else {
return y;
}
}
and also assuming that there are no other references to the objects x and y.
mrak
Dobes Vandermeer
> > > around with an idea for what I call "compile-time
> >
> > Be sure to look up existing work. I'm certain that people have worked
> > on this kind of thing.
>
> I've been looking around for something similar, the most I've found is
> this paper:
>
> Ran Shaham, Eran Yahav, Elliot K. Kolodner, and Mooly Sagiv,
> Establishing Local Temporal Heap Safety Properties with Applications to
> Compile-Time Memory Management. To appear in the 10th Annual
> International Static Analysis Symposium (SAS '03) San Diego, California,
> USA, June 2003.
>
> Available from the author's web page at
> http://www.math.tau.ac.il/~ransh/ (direct:
> http://www.math.tau.ac.il/~rans/sas03-safety-mm.pdf )
Well, here are some more:
Simon B. Jones and M. White. Is compile time garbage collection worth the
effort. In Peyton Jones et al. Simon L. Peyton Jones, G. Hutton, and C. K.
Hols, editors. Third Annual Glasgow Workshop on Functional Programming.
Springer-Verlag, 1991, pages 172-176
Couldn't find this one
Simon B. Jones and Andrew S. Tyas. The implementer's dilemma: A mathematical
model of compile-time garbage collection. In Sixth Annual Glasgow Workshop
on Functional Programming, Workshops in Computer Science. Springer-Verlag,
1993, pages 139-144
file://ftp.cs.stir.ac.uk/pub/tr/cs/1994/TR118.ps.Z
Simon B. Jones. An experiment in compile time garbage collection. Technical
Report 84, Programming Methodology Group, Göteborg University and Chalmers
University of Technology, January 1995
file://ftp.cs.stir.ac.uk/pub/tr/cs/1994/TR127.ps.Z
Thomas P. Jensen and Torben Mogensen. A backwards analysis for compile-time
garbage collection. In Neil D. Jones, editor, ESOP'90 3rd European Symposium
on Programming, Copenhagen, Denmark, May 1990. (Lecture Notes in Computer
Science, vol. 432), pages 227-239. Springer-Verlag, 1990
Couldn't find this one online
Compile-time garbage collection by sharing analysis. In ACM Func. Prog.
Langs. and Comp. Arch. (FPCA), 1989, pages 54-74. (not complete)
Available from acm.org
So far none of them account for threads -- you can augment them to support
global variables by annotating each function with the global variables that
it (and its callees) uses and modifies and treating those as part of the
parameters/returns of the function.
C
> mwo...@cse.unsw.edu.au (Mark Alexander Wotton) wrote in message news:<03-0...@comp.compilers>...
[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
Nick Maclaren
|> Eric wrote:
|> > One of the reasons I
|> > really fancy reference-counting is its low overhead, but I suspect
|> > that with a few adjustments to the algorithm, one can add in logic
|> > that will detect circular links during deallocation.
|>
|> Actually, as I recall, reference counting has much higher overhead
|> than all forms periodic tracing GC. Intuitively, it's because it has
|> to keep track of referenceability all the time, whereas the periodic
|> collectors can forget about it for a time, then recompute what is
|> referenceable only occasionally.
That is deceptive, and many of the books on garbage collection
approach propaganda on the issue. I agree with Lex Spoon here.
Reference counting is very cheap for some purposes. For example,
there are many where allocation and setting up permanent pointers is
rare, but known temporary (scope checked) pointers are common. For
example, many data structures in operating systems - and they often
use reference counting as the primary method.
Secondarily, it ignores the software engineering aspects, and even
simple debugging. If you are to enable any useful debugging of memory
allocation, you virtually have to maintain enough state that reference
counting comes for free. But who provides facilities for debugging
applications in the field any longer?
|> Reference counting can operate right down to zero "headroom", i.e.
|> available space, whereas the others generally need a certain amount of
|> headroom.
Generally, yes. There are forms of reference counting that can't,
of course.
|> Short of resorting to some kind of hybrid with a tracing algorithm,
|> I don't believe anyone has ever fixed the cyclic graph problem with
|> reference-counting.
As it is theoretically impossible to fix, that seems likely :-)
Regards,
Nick Maclaren.
Joachim Durchholz
> (Idle thought: seeing as the only way to create circular references is
> through mutable references in a strict language, or tying the knot in
> a lazy one, perhaps reference counting would be useful for a strict
> purely functional language.)
AFAIK, all such languages use mark-and-sweep collectors.
I'm not sure about the exact reasons. I could imagine that it's just
a case of "reference counting is beneath contempt", or a case of
"mark-and-sweep was measured to be just as fast as reference
counting", or simply "we want to avoid the analysis overhead of
assigning ownership to objects when writing our run-time system".
Regards,
Jo
VBDis
>for each live possible referencor X of Y:
> if Y is referenced by X, Y is still alive, otherwise Y can be freed.
>
>The problem lies in determination of the list of referencors.
Not only in the list of referencors, but more annoying in the list of
"live" referencors! You'll immediately end up in an infinite loop for
circular references between X and Y.
IMO this representation of the algorithm only describes the viepoint
of the referenced object Y, whereas the implementation should use an
different and non-recursive algorithm. In practice it must be possible
to create a complete list of all referencors, regardless of their
liveness, without recursion. This list will be finite and can be
constructed by a linear or at least delimited traversal of all
involved memory areas (static, heap, stack, threads...). Note that in
a delimited stack no unbounded recursion can occur, every recursive
invocation of a subroutine adds 1 linear entry to the stack.
In the following determination of the liveness state of every object
recursion must be prevented. IMO it's obvious that it's easier to
determine whether an object is certainly alive, than whether it's
certainly dead. Then we can start with a number of certainly alive
objects (from references in static variables or in the stack), and
propagate that alive state to all referenced objects. Even if this
propagation is recursive, an infinite recursion can be prevented when
the state of an object is updated prior to the propagation into all
it's referenced objects. Then a recursion can occur only for not yet
marked objects, whose number is continuously decreasing. Without such
an immediate state change infinite recursion can occur, when the state
of the same referencors is evaluated over and over again, in case of
circular references.
There is only one question, which I cannot answer, but probably others
can do:
How to determine the existence of references in a stack, which are not
bound to (local) variables?
This can occur e.g. during the evaluation of f(a(), b()), where the
results of a() and b() can reside in arbitrary locations in the stack,
before f() is invoked.
DoDi
Lex Spoon
> optimisation on mark and sweep, which has no problems with circular
> references.
The topic is fascinating but let's try to get our terminology straight.
"garbage collection" is simply "automatic memory management". It's a
general term. To contrast, malloc/free are "manual memory
management".
"reference counting" is garbage collection where you keep track of how
many references there are to an object, and then you free objects when
there are no more references. This approach has problems with cycles.
"mark and sweep" is where you do a graph traversal starting at certain
"root" objects (including things like the current register set), and
then follow object references. Free everything that you did not
reach. This approach has problems with fragmentation.
Additionally, "stop and copy" has not been mentioned yet, perhaps
because it would seem really strange to people in this group. In stop
and copy, the basic approach is to have two separate banks of memory.
You are always working within one of those banks. When you do a
garbage collection, you copy all the live data from one bank to the
other, updating pointers as you go, and compacting all the objects so
that they are next to each other. You still do the "sweep" part of
mark and sweep, but not the marking. This approach has a lot of
memory overhead, but it avoids memory fragmentation.
Finally, "generational" collection means that you have multiple
sections of memory which are collected one at a time. Objects start
out in the newest generation, and gradually move back to older
generations if they survive long enough. Most objects do not, and
most objects which do, live for a very long time -- thus you can
usually just collect within the newest "eden" generation and thus save
a lot of time. The main trick is that you have to keep track of
pointers from older generations into newer generations. This
typically requires a "write barrier".
There are massive flame wars about which kind of garbage collector is
the best. Further, "the best" depends on the particular application,
a lot of times. Finally, garbage collectors are extremely amenable to
tweaking, and people do so....
Phew. Here are two links with more info:
http://www.iecc.com/gclist/GC-faq.html
http://dmoz.org/Computers/Programming/Memory_Management/
Also, there is a garbage collection mailing list, for anyone who
really wants to get into it. It has quite low traffic.
Lex
Mark Alexander Wotton
On 4 Jul 2003 00:11:39 -0400, C posted:
>
> 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.]
No, you're in an even more constrained system. If you have code that
could do anything that can't be scrutinised by your compiler, you
really are stuffed.
The halting problem objection is based on knowing everything that can
possibly be statically known about your program, and _still_ not being
able to determine which branch will be taken.
> 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.
Better to state this the other way round, I think. A program to decide
if something is undecidable is itself undecidable. You can certainly
choose safe subsets, where it's easy to show that the compile-time
scheme is ok: just because you can't do something in every single
special case is no reason to give up on it in i general.
> [Ewwww: who ever designed that syntax should have nasty
> things done to them involving custard,
You can do nasty things with custard?
My education has been sorely lacking.
mrak
Dobes Vandermeer
>
> 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
There are plenty of papers comparing time & memory overhead -- IIRC
the tracing (mark-and-sweep) collectors tend to use a larger heap
because they keep unreachable garbage around for longer, whereas a
counting collector will deallocate objects as soon as they are
unreachable (if it deallocates them at all); its a tradeoff of space
versus time overhead really.
> > 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.
See:
Generational Cyclic Reference Counting
Rafael D. Lins
http://citeseer.nj.nec.com/lins92generational.html
Concurrent Cycle Collection in Reference Counted Systems
David F. Bacon, V.T. Rajan
http://citeseer.nj.nec.com/383143.html
and you can follow a trail of references from there.
Mark Alexander Wotton
> >>> passed out of scope. This is how many modern garbage-collected
> >>> language implementations work.
>
> Modern GC are usually *not* reference-counters based! But some crude
> language implementations do happen to have poor garbage collectors,
> sometimes only reference-counting based (which works poorly for
> reference cycles and costs a lot).
Sorry, I was being imprecise. From ten thousand feet up, the idea of garbage
collection is to deallocate memory that is no longer referenced, ie
out of scope. Whether you do it immediately (reference counting) or later is
an implementation issue.
mrak
Eric
> structures that point to themselves.]
I notice here, that you refer to "pure" reference-count GC, implying
that some GC's are "hybrid" and combine reference-counting and some
other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
work? any papers on the subject?
> Note that a doubly-linked list falls into this category...
Cheers, E.
[I think I've seen descriptions of GC that use reference counts in places
where they're known to be safe, other kinds elsewhere. -John]
Nick Maclaren
>> [Pure reference-count garbage collectors have problems with circular
>> structures that point to themselves.]
>
>I notice here, that you refer to "pure" reference-count GC, implying
>that some GC's are "hybrid" and combine reference-counting and some
>other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
>work? any papers on the subject?
Gug. There certainly were some, but I last looked decades ago. One
approach was to use reference counters for objects that contain no
potential for backpointers, and fancier methods for those that do.
For example, arrays of plain data - even sparse arrays - are safe, and
many applications have ten of those for every structure that isn't
safe.
>> Note that a doubly-linked list falls into this category...
I can't remember whether anyone has said so, but it doesn't if the
list type is known to the language. It does only if the type is
built up from plain pointers.
>[I think I've seen descriptions of GC that use reference counts in places
>where they're known to be safe, other kinds elsewhere. -John]
Yes, I remember that, too.
Regards,
Nick Maclaren.
Tony Finch
>
>Sorry, I was being imprecise. From ten thousand feet up, the idea of garbage
>collection is to deallocate memory that is no longer referenced, ie
>out of scope. Whether you do it immediately (reference counting) or later is
>an implementation issue.
Note that there is at least one automatic memory management system
(compile-time region analysis) that can free memory which is still
referenced but which will never be used. A simple example of this is
that you only need the spine of a list to calculate its length, so if
that is all you are going to do to the list then its elements can be
freed early even though they are still referenced.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
Stephen J. Bevan
The OCS implementation of Opal <http://uebb.cs.tu-berlin.de/~opal/>
uses reference counting. I remember reading an explanation of why
this was done sometime in the 90s, but right now all I can find is
<http://uebb.cs.tu-berlin.de/~opal/ocs/doc/html/hcguide.html> which
contains :-
OCS uses an enhanced lazy reference counting approach to memory
management which results in a residual garbage collector, that is,
the garbage collector is compiled online into the code.
Stefan Monnier
> approach propaganda on the issue. I agree with Lex Spoon here.
Probably because tracing GC has generally been criticized for its slowness,
so there's a lot of understandable defensiveness.
The fact that both ref-count and tracing GC are still in widespread use
after more than 40 years of competition is a strong indication that there's
no clear winner.
> |> Short of resorting to some kind of hybrid with a tracing algorithm,
> |> I don't believe anyone has ever fixed the cyclic graph problem with
> |> reference-counting.
> As it is theoretically impossible to fix, that seems likely :-)
I don't know what counts as a hybrid, but I think the paper below
is not using any kind of "tracing GC" technology:
http://www.research.ibm.com/people/d/dfb/papers/Bacon03Pure.pdf
Other possible approaches to dealing with cycles can be found in works
on distributed GC.
Stefan
Stefan Monnier
> a case of "reference counting is beneath contempt", or a case of
> "mark-and-sweep was measured to be just as fast as reference
> counting", or simply "we want to avoid the analysis overhead of
> assigning ownership to objects when writing our run-time system".
I guess it's the cost of the counter-per-object (such languages tend to use
a lot of very small objects, such as cons cells). Of course there are ways
to work around that as well, but a simple GC is pretty easy to code up.
Stefan
Hans Aberg
>|> I don't believe anyone has ever fixed the cyclic graph problem with
>|> reference-counting.
>
>As it is theoretically impossible to fix, that seems likely :-)
It is not impossible to make versions (but not pure ref count) that can
trace cyclicity in some circumstances:
I thought of a variation building on Tarjan's strongly connected
components (SCC) algorithm:
http://www1.ics.uci.edu/~eppstein/161/960220.html#sca
This works so that the objects are numbered consecutively as they are
created. A cycle can then be detected if it points to another object with
(depending on the setup) higher/lower number, which can be used to adjust
the ref count so that deletion takes place appropriately also in cycles
(which initially must have some external ref pointing at them). A problem
arises though if, after an initial setup of references have been achieved,
they are relocated dynamically, creating new cycles. That is hard to track
down. But if that does not happen, one can make a version building on this
SCC algorithm to remove the cycles as well (or so I remember).
If one should get around this dynamically created cycles problem, perhaps
one ends up on essentially a tracing algorithm.
Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <remove...@member.ams.org>
* Home Page: <http://www.math.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
Lars Duening
> I notice here, that you refer to "pure" reference-count GC, implying
> that some GC's are "hybrid" and combine reference-counting and some
> other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
> work? any papers on the subject?
One way of doing this is to use reference counting as usual, but in
addition you keep track of all allocated memory. Every once in a while
you run a mark&sweep GC in the traditional way, using your list of
allocated memory to identify unreferenced memory blocks, and
recalculating the reference counts as you trace the referenced blocks.
Other hybrids are possible and limited only by your imagination (and the
application's requirements).
RL...@oxfam.org.pe
> that some GC's are "hybrid" and combine reference-counting and some
> other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
> work? any papers on the subject?
You might find the following interesting (and also its bibliography):
Wise, David S., Stop-and-copy and One-bit Reference Counting
<http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR360>
Dobes Vandermeer
>
> Dobes Vandermeer <do...@dobesland.com> schreibt:
>
> >for each live possible referencor X of Y:
> > if Y is referenced by X, Y is still alive, otherwise Y can be freed.
> >
> >The problem lies in determination of the list of referencors.
>
> Not only in the list of referencors, but more annoying in the list of
> "live" referencors! You'll immediately end up in an infinite loop for
> circular references between X and Y.
I think that at runtime we'd want to avoid recursively making liveness
determinations. After any given use of a reference, that use is
either the last use of that reference (and the reference is dead) or
it is not. If the reference is dead, an implementation could set it
to NULL to indicate it's deadness.
If your list of possible references is a list of expressions
(following pointers from the root) then circular references between X
and Y can be handled because the circular reference becomes
inaccessible at the same instant as Y becomes garbage.
What I worry about, is if your object is possibly "somewhere" in a
given (possibly very large) array - you'd have to scan the entire
array in order to be sure it wasn't. Or even worse, if an object is
"somewhere" in a doubly-linked list, you'd need a way to avoid
searching head->next->prev->next->prev->next etc. which is the same
problem in a different part of the system.
> IMO this representation of the algorithm only describes the viepoint
> of the referenced object Y, whereas the implementation should use an
> different and non-recursive algorithm.
> In practice it must be possible
> to create a complete list of all referencors, regardless of their
> liveness, without recursion.
Consider applying a precise static alias analysis which can produce
"alias" and "may-alias" (alias is short for references the same object")
sets for a given reference. When the last use of a given reference is
reached, the "may-alias" set is the set of possible referencors to
scan. We can look to the alias analysis literature for efficient
implementations with varying degrees of precision, some of which may be
adapted to produce these sets.
> This list will be finite and can be
> constructed by a linear or at least delimited traversal of all
> involved memory areas (static, heap, stack, threads...). Note that in
> a delimited stack no unbounded recursion can occur, every recursive
> invocation of a subroutine adds 1 linear entry to the stack.
If you're talking about a traversal at runtime, then we're getting
further away from being compile-time GC.
Nevertheless, using the compiler to reduce the tracable/freeable set of
objects might be useful by itself in place of generations.
> In the following determination of the liveness state of every object
> recursion must be prevented. IMO it's obvious that it's easier to
> determine whether an object is certainly alive, than whether it's
> certainly dead. Then we can start with a number of certainly alive
> objects (from references in static variables or in the stack), and
> propagate that alive state to all referenced objects. Even if this
> propagation is recursive, an infinite recursion can be prevented when
> the state of an object is updated prior to the propagation into all
> it's referenced objects. Then a recursion can occur only for not yet
> marked objects, whose number is continuously decreasing. Without such
> an immediate state change infinite recursion can occur, when the state
> of the same referencors is evaluated over and over again, in case of
> circular references.
I think you're talking about a standard mark-sweep tracing collector --
or maybe you're making fun?
> There is only one question, which I cannot answer, but probably others
> can do:
>
> How to determine the existence of references in a stack, which are not
> bound to (local) variables?
>
> This can occur e.g. during the evaluation of f(a(), b()), where the
> results of a() and b() can reside in arbitrary locations in the stack,
> before f() is invoked.
As part of compiling, everything becomes identifiable directly .. but if
you want to translate from one source language to another, you could
move them into their own statement and store them in a uniquely-named
temporary variable.
CU
Dobes
Joachim Durchholz
> In the following determination of the liveness state of every object
> recursion must be prevented. IMO it's obvious that it's easier to
> determine whether an object is certainly alive, than whether it's
> certainly dead. Then we can start with a number of certainly alive
> objects (from references in static variables or in the stack), and
> propagate that alive state to all referenced objects. Even if this
> propagation is recursive, an infinite recursion can be prevented when
> the state of an object is updated prior to the propagation into all
> it's referenced objects. Then a recursion can occur only for not yet
> marked objects, whose number is continuously decreasing. Without such
> an immediate state change infinite recursion can occur, when the state
> of the same referencors is evaluated over and over again, in case of
> circular references.
You have just accurately described the "mark" phase of a mark-and-sweep
collector :-)
In a nutshell, the mark phase is like this:
1. Start with a set of "root" objects. (Usually, these will be all
objects referenced from memory registers, from local variables on the
stack, and a "global" object that keeps references to all global data
that's permanently available). Put these objects on a "todo" list.
2. While the "todo" list is not empty:
2a. Mark the first object as "alive" and remove it from the list.
2b. Put all referenced-to objects on the "todo" list,
unless they are already marked "alive" or already on the
"todo" list.
> There is only one question, which I cannot answer, but probably others
> can do:
>
> How to determine the existence of references in a stack, which are not
> bound to (local) variables?
Traditionally, compilers provide enough information to the garbage
collector to identify pointers on the stack. Additionally, they
provide the same information for memory blocks on the heap.
Collectors like Boehm-Demers-Weiser don't get that information and work
with heuristics: if some bit pattern looks like it could be a pointer,
the block that may be referenced by that object is considered alive.
This works well if the virtual address space is larger than the actual
heap size in use, since the probability of misinterpreting an arbitrary
integer as a pointer is low.
If you know that the program doesn't use pointers "into" a memory block,
the collector can identify pointers even more precisely.
The docs claim that a typical program will overlook less than 1% of dead
blocks in the latter case.
> This can occur e.g. during the evaluation of f(a(), b()), where the
> results of a() and b() can reside in arbitrary locations in the stack,
> before f() is invoked.
It's not an arbitrary location, it's the slots for intermediate
results. These are usually found between the local variables of the
current routine and top-of-stack.
Regards,
Jo
Dennis Ritchie
[ ... ]
In the matter of GC--
> >[I think I've seen descriptions of GC that use reference counts in places
> >where they're known to be safe, other kinds elsewhere. -John]
>
> Yes, I remember that, too.
Limbo, http://www.vitanuova.com/inferno/papers/limbo.html ,
the programming language for Inferno, mostly uses reference
counts for GC. The original version forbade creating references
that could be cyclical, and offers an explicit guarantee that things are
freed at last in-scope reference; in the Inferno implementation, for example,
a subwindow automatically disappears when its last handle is assigned
to or moves out of scope. Similarly for communication channels
and other system resources.
This was done by disallowing assignments to references that could
(directly or indirectly) lead back to the same type of object
containing the reference.
A slightly later version relaxed the rule by permitting reference
objects to be declared "cyclical". At the same time, a backup marking
GC was installed, but reference counting usually suffices.
Dennis
Tony Finch
>I notice here, that you refer to "pure" reference-count GC, implying
>that some GC's are "hybrid" and combine reference-counting and some
>other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
>work? any papers on the subject?
Try using Google or CiteSeer.
http://www.cs.kent.ac.uk/people/staff/rej/gc.html#Bibliography
Dobes Vandermeer
>
> > [Pure reference-count garbage collectors have problems with circular
> > structures that point to themselves.]
>
> I notice here, that you refer to "pure" reference-count GC, implying
> that some GC's are "hybrid" and combine reference-counting and some
> other scheme (supposeddly mark-and-sweep). How would such a hybrid GC
> work? any papers on the subject?
There are different reasons for hybrids:
- Two languages (e.g. Java & Objective-C) using different memory
management strategies. In this case, the GC takes a single for itself
when there are references to a refcounted object within the GC, and
releases the reference when there aren't any more. The refcounted
client creates a temporary GC root when it first refs a GC managed
object, and deletes the root when its refcount falls to zero.
- Reference counting to reduce memory usage of mark-and-sweep. When a
refcount falls to zero, the object is definitely freeable, so you can
free objects earlier than the GC would, if you'd rather use less memory
and you don't mind extra memory accesses, cpu cycles, synchronization,
etc..
- Mark-and-sweep to collect cycles. The mark and sweep runs
occasionally to collect any cycles that might have come up. This is
potentially identical in implementation to the previous bullet, but
running less often.,
- Cycle hunting - when a refcount falls to any value other than zero,
you can scan the graph rooted at that object to see if all of its
references are cyclic. This is usually deferred: a list of released
objects is kept, and periodically checked for cycles. This might be
more efficient than the previous bullet because it only has to scan
objects which were unreferenced but not deleted, but there isn't any
guarantee that it is (some apps may modify a lot of references without
causing objects to become unreachable, and to arbitrarily large data
structures), and you have to account for the overhead of the write
barrier (each pointer write potentially has to update the scanning list
as well as the reference count). This idea hasn't been generating many
papers in the last decade or two, but its get all the same variations as
mark-and-sweep (generational, concurrent, whatever).
You could, of course, combine regions with reference-counts garbage
collection as well to eliminate cycles, as long as the cycles aren't
stored in a place where the regions wont free them.
CU
Dobes
ikhnos
> created. A cycle can then be detected if it points to another object with
> (depending on the setup) higher/lower number, which can be used to adjust
> the ref count so that deletion takes place appropriately also in cycles
> (which initially must have some external ref pointing at them). A problem
> arises though if, after an initial setup of references have been achieved,
> they are relocated dynamically, creating new cycles. That is hard to track
> down. But if that does not happen, one can make a version building on this
> SCC algorithm to remove the cycles as well (or so I remember).
This is interesting.
Leaving aside the SCC stuff, if I may (I haven't given this a great
deal of thought, but it seems that this is effectively adding
mark-n-sweep GC to supplement the ref-count system, which I gather
from this thread is a well known technique), what I interpret this as
(and correct me if I'm wrong) is:
If P acquires a reference to a newer object Q, then Q's ref-count is
incremented. If P acquires a reference to an older object Q, then Q's
ref-count is NOT incremented.
This makes the objects-and-references graph acyclic, overcoming the
cyclic-reference problem.
I suspect that there MUST be problems with this, although I don't see
them, because it doesn't "feel" like a new idea, and if it worked,
then no-one would be talking about the cyclic-reference problem.
So: Question: What are the problems?
VBDis
>The docs claim that a typical program will overlook less than 1% of dead
>blocks in the latter case.
Fine, but what about overlooking live references? ;-)
>> This can occur e.g. during the evaluation of f(a(), b()), where the
>> results of a() and b() can reside in arbitrary locations in the stack,
>> before f() is invoked.
>
>It's not an arbitrary location, it's the slots for intermediate
>results. These are usually found between the local variables of the
>current routine and top-of-stack.
And that's just a location which deserves detailed description. Consider that
the stack can have any number of layouts (scopes), during execution of a
subroutine. Every evaluation, which pushes intermediate references onto the
stack, will deserve an according description of the current stack layout. The
marker then will have to examine the current address within the subroutine
code, and use it to fetch the according stack description from a list of all
those descriptions. Those stack descriptions also will have to include the
local variables, which may be overlaid for parallel blocks of code.
DoDi
Joachim Durchholz
> Joachim Durchholz <joachim....@web.de> schreibt:
>>The docs claim that a typical program will overlook less than 1% of dead
>>blocks in the latter case.
>
> Fine, but what about overlooking live references? ;-)
Live references are never overlooked. This is what the "conservative"
bit in the Boehm-Demers-Weiser documentation means: it prefers to err
on the conservative side and misidentify a nonpointer as a pointer
(rather than erring in the reverse direction).
There is one exception: if the application mangled pointers, the
garbage collector will indeed overlook live blocks. (For example,
there's a linear-list implementation where the forth and back pointers
are xor-ed together. Scanning through such a list means taking the
address of the first block, xoring it with its "link" field to get the
address of the next block, and so on - or, alternatively, start with
the last block and go back. However, *any* garbage collector will have
difficulties dealing with such constructions, and these aren't very
much in vogue anymore - you need this kind of trick only if you have
to squeeze serious data into a one-digit number of kilobytes.)
>>>This can occur e.g. during the evaluation of f(a(), b()), where the
>>>results of a() and b() can reside in arbitrary locations in the stack,
>>>before f() is invoked.
>>
>>It's not an arbitrary location, it's the slots for intermediate
>>results. These are usually found between the local variables of the
>>current routine and top-of-stack.
>
> And that's just a location which deserves detailed description. Consider that
> the stack can have any number of layouts (scopes), during execution of a
> subroutine. Every evaluation, which pushes intermediate references onto the
> stack, will deserve an according description of the current stack layout. The
> marker then will have to examine the current address within the subroutine
> code, and use it to fetch the according stack description from a list of all
> those descriptions.
Hmm... right, the intermediate result stack may have a mixture of
pointer and nonpointer data.
I'm not sure how this is handled. I could imagine various techniques,
like having bitmaps for every conceivable instruction pointer value, or
interleaving bitmaps and result values on the stack. Or reserving enough
space on the stack to store the bitmap for the maximum size of the
intermediate values stack (for a single expression, this is the maximum
nesting depth of the call as written in the source code, which is easy
to compute for a compiler). Or one could store pointer data on a
different stack than nonpointer data (with all the complications that a
two-stack scheme entails).
> Those stack descriptions also will have to include the
> local variables,
For this case, the same techniques as for distinguishing pointers from
nonpointers in a heap block would apply.
> which may be overlaid for parallel blocks of code.
The compiler could overlay pointers with pointers and nonpointers with
nonpointers, this would eliminate the problem.
If stack space is really at a premium, the compiler could insert
statements to switch stack layout indicators when entering a block that
uses a new layout. However, the machine instructions will most likely
take up more static code space than stack space saved; I could imagine
this in cases where a routine is known to be heavily recursive, or in an
embedded microprocessor with limited RAM and large ROM. On a desktop
CPU, I'd just use a single stack layout for each routine and ignore the
waste of space...
Regards,
Jo
Dobes Vandermeer
>> This works so that the objects are numbered consecutively as they
>> are created. A cycle can then be detected if it points to another
>> object with (depending on the setup) higher/lower number, which can
>> be used to adjust the ref count so that deletion takes place
>> appropriately also in cycles (which initially must have some
>> external ref pointing at them). A problem arises though if, after
>> an initial setup of references have been achieved, they are
>> relocated dynamically, creating new cycles. That is hard to track
>> down. But if that does not happen, one can make a version building
>> one this SCC algorithm to remove the cycles as well (or so I
>> remember).
> This is interesting.
>
> If P acquires a reference to a newer object Q, then Q's ref-count is
> incremented. If P acquires a reference to an older object Q, then Q's
> ref-count is NOT incremented.
>
> This makes the objects-and-references graph acyclic, overcoming the
> cyclic-reference problem.
>
> So: Question: What are the problems?
Well, what if you only have references from younger/older objects?
e.g. only younger objects
InputStream i = socket.getInputStream();
DataInputStream d = new DataInputStream(i);
If you only retain younger objects, "i" won't be ref'd and might be deleted
too soon.
or:
ArrayList a1 = new ArrayList();
ArrayList a2 = new ArrayList();
a1.add(a2);
If you only retain older objects, than a2 hasn't been ref'd, and will
be deleted once the scope falls away...
In languages without assignment, objects can't take pointers to
anything newer than them -- once they are created they stay the same.
Nevertheless, you can't create cycles in these language so reference
counting is already just fine. Typically, however, copying collectors
are more efficient for these languages; they don't need to run
destructors, they allocate short-lived objects like crazy, and so bulk
freeing of memory is a big win.
CU
Dobes
Nick Maclaren
|> nm...@cus.cam.ac.uk (Nick Maclaren) wrote:
|>
|> >|> I don't believe anyone has ever fixed the cyclic graph problem with
|> >|> reference-counting.
|> >
|> >As it is theoretically impossible to fix, that seems likely :-)
|>
|> It is not impossible to make versions (but not pure ref count) that can
|> trace cyclicity in some circumstances:
Yes, indeed. The theoretical impossibility is for the general case,
as usual.
|> If one should get around this dynamically created cycles problem, perhaps
|> one ends up on essentially a tracing algorithm.
It could well be. The papers I have seen 'solve' the problem have
handled only the static case.
Regards,
Nick Maclaren.