On Apr 1, 2005, at 10:33 PM, Jean-François Brouillet wrote:
A virtual machine isn't required at all for garbage collection. Lisp
systems have been compiling straight to machine code for decades, and
also implementing garbage collection for decades.
Having a virtual machine can make implementing garbage collection
easier because it may allow you to make some simplifying assumptions
that you otherwise might not be able to make.
It is also to be pointed out that the simplest form of garbage
collection, reference counting, which is at the heart of Cocoa,
only got a bad rep because people tend to confuse use-of and
references-to, and hence create the dreaded "uncollectable islands".
The ease of creating retain cycles in cyclic data structures, where it
then becomes impossible to free any of the objects participating in the
retain cycle, is just one disadvantage of reference counting compared
to AGC systems and just one reason why it has become a bad reputation
over the years.
Reference counting, especially the way it is implemented in Cocoa, has
the additional problem that it makes the transfer of object ownership
much more expensive in terms of consumed CPU cycles compared to an AGC.
Transferring object ownership in Cocoa requires two method calls: one
-retain plus a -release or -autorelease call. We not only pay the price
for two method calls, we also pay the price for taking a lock two times
and above that even the price for two hash table lookups, because the
retain counts are actually stored in a global hash table - not in the
objects themselves. Transferring object ownership in an AGC based
system is either just a simple pointer assignment and nothing else, if
it is a full stop collector, or requires the overhead of a single write
barrier, if its a generational collector. A write barrier is, however,
much simpler, implementation wise, than for example the -retain method
is.
One of the biggest advantages of an AGC is that it allows very fast
object allocations, simply because the allocator does not have to do as
much book-keeping as a standard allocator like malloc has to do. The
best example in this regard is a copying collector. Allocating memory
in such a system is as simple as atomically incrementing a single
pointer. But even the allocator of a generational collector is still
much simpler and faster than malloc could ever be.
Speed of allocation is obviously very important for an object
orientated language like ObjC. This is especially true for objects
which are used for a very short amount of time - aka temporary objects.
OO languages, however, have the tendency to generate a lot of such
objects. That is why for example the concept of generational GCs was
developed. Those AGCs take advantage of the fact that the vast majority
of objects typically created in an OO language are very short-lived.
The interested read can find a lot of info about generational GC and
AGC in general in this book: "Garbage Collection. Algorithms for
Automatic Dynamic Memory Management" by Jones Lins.
Recently Cocoa has gained new technologies like bindings or KVO, and
increased the prominence of others like KVC. All those technologies
have one thing in common: they have a tendency to create a lot of
temporary objects. For example, KVC must allocate an NSNumber object if
you call -valueForKey: on an accessor which returns an integer. Also
take into account that parsing key paths does not come for free and
likely requires the creation of additional temporary objects
(sub-strings in this case). Its obvious that all those technologies
could profit a lot from memory allocation overhead which is as low as
possible.
Finally, reference counting also suffers from the problem of
unpredictable time behavior. At the time when you call -release on an
object, you can not know how long it will take for the release
operation. You may be lucky and the object is still in use by someone
else, and thus the release operation will take maybe just a single
microsecond. However, you may have bad luck and the release leads to
the deallocation of a large object graph which may take multiple
milliseconds. Cocoa's autorelease pools make the situation even worse
in this regard, because such a pool can easily collect large numbers of
objects either by directly referencing them (leaf objects) or by
indirectly referencing them (object graphs). Emptying an autorelease
pool with many many objects in it can easily take a few dozen
milliseconds or even one or two seconds - a time span that is
definitely noticeable to the users of an app, if the deallocation
happens on the main thread and thus blocks the UI.
A modern AGC does not suffer from this problem because of two things:
the collector can run on its own thread and needs to stop the
application only for a brief amount of time in order to run its
scanning phase, and the time spent on scanning can be exactly
controlled by the application.
So in short, reference counting has the disadvantages of retain cycles,
high object ownership transfer cost, high object allocation cost and
unpredictable time behavior. AGC on the other side has the advantages
of being able to automatically deal correctly with cyclic data
structures, low object ownership transfer cost, low object allocation
cost and predictable time behavior.
Naturally, AGC does not come for free. First and foremost implementing
a good and efficient AGC is by far not a trivial task and much much
harder than implementing a simple reference counting scheme. It also
has the tendency of increasing the working set size of an application.
Finally, because of the necessary scanning, it tends to thrash the CPU
caches. However, the latter is also true for reference counting when an
object graph gets deallocated.
I personally would highly welcome it if Apple would add AGC to ObjC.
Honestly, while it may have been cool (well actually often a
requirement) to have precise control over every single memory
allocation and free operation in your application in 1985, it is simply
boring and totally uninteresting in 2005. Note, I'm only talking of
application development - not stuff like real time or other low-level
software. But even in those areas are AGCs quite common today. Hell,
even the 3D renderer I'm currently working on implements its own mark &
sweep garbage collector in order to drastically cut down on the memory
management overhead that malloc() caused in the original
implementation...
However, there is one thing that would be an absolute requirement for
me if AGC should ever be added to ObjC: it absolutely _must_ be
integrated into the language level. A library only solution would be
ignored by me.
The fundamental problem with AGCs that operate on the library level
only is that they don't have any exact information about the objects
used by the application. Therefor, they are forced to spend a lot of
time trying to figure out whether a particular word in the address
space is a pointer to a live object or just some random integer.
Further, there is also no guarantee that the collector will not mistake
a real pointer for an integer and thus leak an object. While such
conservative collectors are certainly a way to add AGC to a language as
an afterthought, the price that must be paid by its user is very high
and often unacceptably high.
If on the other side AGC is part of the language definition and thus an
integral part of the language, then its possible to implement an AGC
that is both highly efficient and correct. The advantage in this case
is that the language definition can simply disallow certain problematic
situations that would make life for the collector unnecessarily harder.
In the case of ObjC it would make sense to make only pointers with the
type tag `id' or a type tag which corresponds to a class name
collectible by default. All other pointers would not be collectable.
This rule would ensure enough backward compatibility to C. Further,
only pointers which point to the start of a live memory block should be
considered by the collector, internal pointers simply be ignored. Hell,
I would even go so far as completely disallowing any kind of pointer
arithmetic on object pointers. Just call them references and the case
is closed ;)
Another important aspect of making AGC part of the language level is
that it makes it possible for the compiler to analyze the source level
program and optimize the program so that the generated code plays well
with the collector and does not fight against it. For example, a
compiler can automatically generate the necessary write barrier calls
for a generational collector.
Anyway, as far as I can tell there are still a-lot of prejudice
floating around when it comes to AGC vs. reference counting. However,
it shall be (finally) mentioned that every single Cocoa application and
in fact all ObjC applications which you can run on Mac OS X today, are
already using an AGC under the hood.
Have you ever wondered how its possible that Apple's runtime can
maintain a per class method cache and be thread safe at the same time
without having to take a lock in the message dispatcher ?
Short answer: by taking advantage of an AGC.
Long answer: Every class has a method cache into which the message
dispatcher enters the selector and entry point of a method the first
time that particular method gets called. Now, over time the method
cache fills up because its size after all is not infinite. The easiest
way to implement the method cache reallocation would be to simply take
a lock in the message dispatcher for every method invocation, so that
when we need to expand the method cache, we can do it atomically
without disturbing any other threads which might currently look for a
method in the method cache we want to replace. However, that would add
significant overhead to every single method call.
The alternative is to simply allocate a new cache, copy over the old
cache contents, and then finally, abandoning the old cache. However,
leaking caches is not a good way to make new friends, so the abandoned
caches must be freed up at some point in time - and this is where AGC
comes into play. The runtime's cache collector checks from time to time
every thread in the app if it is still using an abandoned method cache.
If so the cache is left alive. Otherwise it is freed. The first one who
finds out how exactly the collector determines that a cache is still in
use by a thread will get a nice big smile from the cute goldfishes
swimming in the pond under my office window :)
This doesn't have to be that way, and, if my memory serves me well,
David Stess's Portable Objective C (POC) uses reference counting
*automatically, at the language level, under the hood* and doesn't
create cycles.
The POC compiler is not able to generate code which would automatically
break retain cycles at runtime. You can fake it somewhat however by
declaring weak pointers as void* pointers. While there do exist
reference counting implementations that are able to detect the presence
of retain cycles at runtime, they are significantly more complex than a
standard reference counting implementation is. They basically add a
scanner similar to the scanner you can find in a mark & sweep collector
on top of the reference counting primitives.
However, once you go down that routine you might just as well go the
whole way and implement a real mark & sweep collector. Its really not
much more work.
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
