Garbage Collection woes...

FROM : John Engelhart
DATE : Fri Jun 27 21:31:55 2008

A few days ago, I decided to give leopards GC system another crack. 
The experience was pretty much the same as all my other experiences 
have been with Leopards GC system (several days wasted).  I learned 
two important things that I thought I would share:

Lesson #1:  If you have any interest in performance, you must avoid, 
at all costs, "writing" to a __strong pointer.  I thought I was being 
quite careful about which pointers were __strong and which were 
getting touched in the critical path, which should have been none. 
However, once I flipped GC on, micro benchmarks results went right 
through the floor, an order of magnitude worse.  The problem was the 
following innocent statement:

-(BOOL)doSomething:(id)obj error:(NSError **)error
{
  if(error != NULL) { *error = NULL; } // Make sure we clear the 
error object
}

It's sort of ambiguous as to what should be returned by the indirect 
error pointer on the condition of success.  I could think of several 
neat ideas if the expected behavior were defined up front, even 
requiring the caller to initialize the pointer to a default NSError 
singleton and allowing errors to accumulate in a stack like fashion. 
Alas, the only clearly defined behavior is that one failure, a NSError 
object is indirectly returned.

I prefer the "Initialize your environment to a known state."  Leave 
it up to the optimizer to figure out if such an initialization is in 
fact useless because, one way or another, some path is guaranteed to 
set it later on without depending on its initial value.

Now, typically, the passed in error pointer itself lives on the 
stack.  The compiler can't tell where the pointer really lives, and so 
it must "assume the worst"[1] an insert a write barrier, even if such 
a write barrier is pointless because it's protecting an update to a 
location that ultimately lives on the stack.

[1] This is an important point in the next GC lesson learned.

So.... the way to 'fix' this is to do something like:

  if((error != NULL) && (*error != NULL)) { *error = NULL; }

This will at least only incur a write barrier penalty only when it 
needs to.

The write barrier penalty is substantial.  I benchmarked a tight loop 
that called a function that did nothing but the naive clearing of the 
value.  The result (on a 1.5GHz G4) was that it was 2429.55% (or, over 
24 times) slower with -fobjc-gc enabled.  So, best to avoid updating a 
__strong pointer at any and all costs.

Lesson #2:  Since there is so little documentation about the GC 
system, this involves a lot of speculation, but I think it summarizes 
what's really going on.  This all started with an effort to keep a 
__weak reference to a passed in string that was used to initialize an 
element in a cache.  When the cache was checked, if that weak 
reference was NULL, then the cache line is invalid and should be 
cleared.  The cache consisted of a global array of elements, selection 
was done via KEY_STRING_HASH % CACHE_SIZE, and everything was under a 
mutex lock.  An approximation of the cache is:

typedef struct {
  NSString *aString;
  __weak NSString *aWeakString;
  NSInteger anInteger;
} MYStructType;

MYStructType globalStructTypeArray[42]; // <-- Global!

Simple, right?  That's how it always starts out...  The first problem 
encountered was:

[<email_removed>] /tmp% gcc -o Global_GC Global_GC.m -framework 
Foundation -fobjc-gc
Global_GC.m:14: warning: __weak attribute cannot be specified on a 
field declaration

(The attached file contains the full example demonstrating the problem.)

I'm not really sure what this means, and I don't recall reading 
anything in the documentation that would suggest anything is amiss.  I 
never actually managed to figure out what, if any, problem this causes 
because it quickly became apparent that there was a much bigger 
problem that needed dealing with:

The pointer to 'aString' in the above (or any of my other __strong 
pointers in my actual code) were clearly not being treated as 
__strong, and the GC system was reclaiming them causing all sorts of 
fun and random crashes.

The documentation states: The initial root set of objects is comprised 
of global variables, stack variables, and objects with external 
references. These objects are never considered as garbage.

And thus began yet another exciting adventure with the GC system that 
caused me to waste several days.  In all honesty, I've probably sunk 
about 3 weeks worth of 10 hour days in to tracking down "problems" 
like this whenever I've tried to use the GC system.  At this point, 
I've probably spent more time dealing with memory allocation problems 
due to the GC system than I've spent dealing with memory allocation 
problems in the last 20 years.

I spent several hours digging through the assembly output, and even 
(once again) plunging in to the gcc source to try to figure out what 
was going on.  Using dtrace to catch all calls to objc_assign*, it was 
obvious that the GC system was performing a write barrier to update 
the global array, and that things 'worked' for awhile after the write 
barrier was done and then the GC system reclaimed the memory.

After wasting an awful lot of time verifying that there were no race 
conditions and that the write barriers were actually being done, I was 
sort of stumped.  I never even considered the possibility that the 
global variable(s) weren't roots, the GC documentation seemed pretty 
clear on that.  But it would explain a lot of things (values are 
pointers stored to the global array):

(gdb) info gc-roots 0x1012090
Number of roots: 0
(gdb) info gc-roots 0x1012030
Number of roots: 0

.... Right.

Putting the pieces together, it became obvious what was really going 
on.  The two commented out lines in the example that update the global 
variable are the key to the mystery and make everything work as 
expected.

It turns out that when the documentation says that "root set of 
objects is comprised of global variables", it's true, but probably not 
in the way that you think it is.

It would 'seem' that global variables are only __strong when the 
compiler can reason that you're referring to a global variable 
directly. In this particular case, that would be:

globalStructTypeArray[23].aString = newString;

They are not strong when you refer to them indirectly (even though 
write barriers are clearly being performed), such as:

update(&globalStructTypeArray[23], newString);

update(MYStructType *aStructType, NSString *string) {
  aStructType->aString = string;
}

Looking at the assembly output, the reason becomes clear:

The write barrier used by the first, direct reference is 
objc_assign_global, while the write barrier used by the indirect 
reference in update is objc_assign_strongCast.

This is probably an important point that you should consider if you're 
depending on global variables being truly __strong.  No doubt someone 
here will explain that this isn't a bug, it's just that you shouldn't 
reference a global variable via a pointer (this is sarcastic for the 
challenged).

I'll leave you to ponder the implications of the above.  The next nut 
to crack after that one is:  __weak pointers must be read via a 
wrapper function (objc_read_weak), and you can't tell if the pointer 
passed in is actually a __weak reference to, say, a NSString, then do 
you have to assume the worst that every pointer passed in may 
potentially be __weak and therefore for safety must be wrapped in a 
call to objc_read_weak()?  Talk amongst yourselves.

Since I can't arrange for my code to always use the GC variable 
directly, and I don't have an answer wrt/ to the "always assume 
__weak" question, I've pretty much abandoned GC for this particular use.

Compile the attached with and without GC.  Also try it with and 
without the global variable references commented out.  The great thing 
about GC bugs is that they occasionally don't cause problems, so you 
may need to run it more than once.