This is obviously not an initializing store because we can not prove,
given our static knowledge about the above method, that it is an
initializing store.
So obviously there will be no "initializing stores" unless you make
even more radical changes to the language (stores into registers and
the stack don't have to be checked via the write-barrier).
Okay, if its really necessary to describe everything in detail, then
lets do it.
So, first of all, what is an initializing store ?
An initializing store is the first write operation to a storage
location.
How can a compiler for a statically typed language detect whether a
particular store is initializing or not ?
The compiler assigns storage to variables. It knows at any time what
variable is stored where and what type it has. It knows for example
that the first write to a particular local memory location or register
in the context of a function / method is initializing. It can further
take advantage of the static type information it has in order to see
that for example writing an object pointer to storage location 4, which
is currently holding an integer, is an initializing store. Without the
static type information, we would not be able to detect this. The
storage location 4, could after all already contain an object pointer.
But why would a compiler store an object pointer in a storage location
that is currently holding an integer ?
It can do this if it has determined that the life time of the integer
variable and the life time of the object pointer don't overlap and if
it knows that both require the same amount of storage and if the
alignment requirements of the object pointer are not violated. The
advantage of using memory locations for more than one variable is that
it helps to reduce memory consumption. This applies even more to the
register file of a CPU.
Why are we even bothering about the concept of an initializing store ?
Because it can help us to make a decision whether we really need to
emit a write barrier for a store operation or not.
Is the above statement specific to a particular programming language ?
No. When, how and why we need a write barrier is dependent on both the
language definition and the particular AGC implementation.
How does an AGC work in principle ?
An AGC works in principle by detecting for every object in your
application whether there still exists at least one pointer that points
to it. If there is no pointer that points to a particular object, then
that object is considered garbage and can be reclaimed by the AGC at
any time. Naturally the sooner it gets reclaimed the better.
How is an AGC able to find all the pointers to all the objects in my
app ?
An AGC starts with the pointers in the root set. It then follows those
pointers to the objects to which they point. Then it follows the
pointers in those objects and so on. The root set usually contains the
CPU registers, stack and global variables. The act of finding pointers
to life objects is usually called scanning.
How does a generational AGC work ?
A generational collector takes advantage of the fact that most objects
created in OO languages tend to die young. Thus, the heap is divided up
into two or more sub-heaps where every generation is assigned to one
heap. Freshly created objects are put into the first generation
(generation 0) heap. The reason why a generational AGC can be faster
than a non-generational one is because the scanning can be split up so
that it works on a per generation basis and thus needs to scan only a
fraction of the heap at a time. Objects in the generation 0 heap are
scanned the most frequent. Objects in other generations less frequent.
What is the root set of a generational AGC ?
The union of the default root set and the remembered set. The default
root set may include CPU registers, stack and globals. However, there
is no requirement that a particular implementation must define the
default root set that way. Further, the root set may be split up among
the various generations. I.e. there is one default root set for
generation 0 and another one for generation 1.
What is the remembered set ?
A set of pointers to objects. A problem in generational GC is that a
generation 0 object may not be directly or indirectly referenced by the
default root set. The only reference to it may exist in one of the
generation 1 objects. Thus, if the AGC would only scan the objects
directly reachable by the default root set for generation 0, it may
mistake a life object for a dead one. Thus, somehow we must add all
those pointers that may point from generation 1 to generation 0 objects
to the root set. That set of added pointers is the remembered set.
How can we detect such inter-generational pointers ?
For example, by employing a write barrier. In principle, we add a write
barrier at all places in our program where such an inter-generational
pointer may get assigned to a storage location.
What exactly does a write barrier do ?
What exactly it does depends on the particular implementation of a
particular AGC. However, typically, a write barrier takes the address
of the storage location into which an inter-generational pointer may
get stored and adds it to a pointer table. That pointer table is then
used by the AGC in its scanning phase.
Is it always necessary to go through a write barrier for every pointer
store ?
In general no. However, when exactly it is possible to optimize away a
write barrier depends on the language definition and the particular AGC
implementation. In most cases it turns out that going through a write
barrier is not necessary if the storage location is already part of the
default root set or if the storage location does not yet contain a
valid object pointer.
The first case does not require any work by the compiler because it is
the job of the AGC implementor to define what the default root set is.
I.e. it may contain the CPU registers and stack, but not global
variables. Generating a write barrier would in that case not be
necessary for stores into registers or stack locations. But it would be
necessary for globals.
The second case requires work by the compiler. Namely the determination
if a particular object pointer store is an initializing store or not.
In general, a write barrier is necessary for object pointer stores
which are valid object pointers, inter-generational pointers and are
initializing stores. Its not necessary otherwise.
Is a write barrier responsible for trapping each and every store to a
particular storage location or just the first one ?
As described so far, its in principle only necessary to trap the first
one. Remember, the job of a write barrier is to extend the root set.
Once a storage location which holds an object pointer was added to the
root set, its available to the collector. Whether the object pointer
value stored in that storage location changes or not is in principle
not interesting to the scanner. However, it is certainly a good idea to
remove a particular storage location from the remembered set, once we
know that it can no longer hold valid object pointers.
Why are you so vague in your description of how a write barrier works ?
Simply because the way that a write barrier is implemented and the
question when exactly it needs to be called, dependents on how exactly
a generational AGC is implemented. It may store pointers in tables, it
may set bits in a bitmap, it may store pointers in a variable size or
fixed size queue, etc. Further, it may need to trap stores to fields in
heap allocated objects, it may need to trap stores to objects living on
the stack, it may need to trap stores to objects cached in particular
registers, etc. Finally, when a write barrier call is necessary or not
necessary depends on how the default root set is defined.
How can a language specification make the life of an AGC easier ?
By defining the language in such a way that it either forbids
problematic operations altogether, or in that it does not guarantee the
semantic validity of operations which would negatively interfere with
the AGC.
What does that mean ? (give an example)
Take internal pointers. They are problematic because they can make it
hard for an AGC to decide to which object it points. Now, the language
specification can either say: "internal pointers are forbidden and
there is no way in the language to create one" or it can say: "internal
pointers are allowed, but their semantic with regard to objects is
undefined".
The latter options sounds familiar to me, can you tell me why ?
It is probably familiar to you because it is a common theme in C, C++
and ObjC. The syntax of those languages allow you to write a lot of
code that compiles, but, according to the language specification, has
no guaranteed semantic meaning.
How can a compiler make the life of an AGC easier ?
A compiler can gather static information at compile time about the
program it compiles and make it available to the AGC at runtime. I.e. a
compiler can collect the declaration information of every class it saw
in the source and make that, object layout, information available to
the AGC.
Why should a compiler even bother to collect information for an AGC ?
Because it allows the AGC to do its work faster and because it helps to
reduce the likeliness of page faults and cache misses while the AGC is
scanning the object heap. An AGC which does not have any information
about which object has a pointer to another object must scan all words
in the object heap. Further, it must analyze every word it picks up
from the object heap and show that this word does indeed point to
another object. Then and only then can it interpret that word as an
object pointer. Obviously, this technique wastes a lot CPU cycles in
picking up and analyzing words which turn out to be everything but an
object pointer.
Isn't that what a conservative collector like the Boehm GC does ?
Yes. However, the Boehm GC allows it's user to set object layout
information for objects stored in the heap. It still has to figure out
the hard way if a particular CPU register or stack location contains an
object pointer or not.
Can't a compiler make such layout information available to an AGC for
register and stack locations ?
A compiler for a statically typed language - yes. Whether it is worth
the effort, again, depends on the particular language, AGC and
platform.
Everything clear now ?
Regards,
Dietmar Planitzer
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Objc-language mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden
