Re: Garbage collector vs variable lifetime

FROM : John Engelhart
DATE : Mon Jun 09 19:24:20 2008

On Jun 9, 2008, at 6:51 AM, Chris Hanson wrote:

> On Jun 9, 2008, at 12:56 AM, John Engelhart wrote:
>

>> The semantics are preserved and identical results are calculated 
>> (the 'meaning' is the same).  The semantics do not require square() 
>> to literally be called each time.

>
> Yes, that is very clear, because the compiler can have full 
> knowledge that
>

>> In the same sense, there is no requirement that a message literally 
>> be sent each time it appears in the source code as long as it can 
>> be shown that the results would be identical.

>
> This is where you're incorrect.  A message MUST be sent, literally, 
> each time it appears in the source code.  Under the Objective-C 
> semantics it CANNOT be shown at compile time that the results of 
> "the same" message send will be identical.


Yes, and "under the semantics of ANSI C it CANNOT be show at compile 
time that the results of the same C library function call in 
succession will be identical".

The const and pure attributes tell the compiler 'but in this case, 
despite what the rules strictly say, I'm saying that it doesn't apply 
in this particular case.'  By adding the attribute to a functions 
prototype, you take responsibility for the problems it may cause if at 
some later point this turns out to not be true, like say linking to a 
different version of a C library.

This isn't rocket science.  There ARE risks to overriding the 
conservative, guaranteed to work defaults.  You CAN break things, even 
when this feature is limited to just plain C.  If a newer version of a 
library invalidates the requirements of the attributes as they were 
declared for its prototype, yes, you're probably going to have some 
serious breakage.  And yet the last time you fired up the compiler, it 
cranked out code that could, just maybe, break with some future 
version of libSystem.

>
> For an extreme example, you can replace method definitions at run-
> time.  This is done in real, production code; it's not hypothetical.


You've missed an important point: "as long as it can be shown that the 
results would be identical.".  If you change things in such a way that 
the results would no longer be identical, then yes, a message would 
have to be sent each time.

Strictly speaking, under Objective-C semantics, it CANNOT be shown 
that a message to an object will return a result of the type indicated 
by its compile time prototype.  Or that the argument types accepted 
indicated by the prototype remain the same as those that are 
ultimately accepted at run time.

If I declare a method

-(id)mySuperMethod __attribute((const));

And then you choose to swap out the code for my method that violates 
the prototypes attribute, why is this the fault of 
__attribute((const))?  I, the author of mySuperMethod have certified 
via my prototype that __attribute((const)) applies to the code that I 
wrote, and it returns a type of id.  You can not just swap and swizzle 
things without any regard for the original prototype.  Otherwise I'm 
free to swizzle in a chunk of code that returns a double and complain 
that it's not my fault.

>

>> The run time dynamic dispatch nature of objc makes such 'inter-
>> message dispatch optimizations' much, much harder, especially at 
>> compile time.  Ultimately, though, they are fundamentally the same 
>> in terms of optimization.

>
> No, really, they aren't.  They are fundamentally different because 
> you cannot know, from one Planck-time tick of the Universe's clock 
> to the next, whether such an optimization is possible.  (I hope you 
> don't mind if I also indulge in a bit of hyperbole...)
>
> For example, a whole-program JIT optimizer could theoretically 
> generate some code that inlines a message dispatch, or even 
> eliminates it entirely, but it can't change the semantics of the 
> surrounding code based on the fact that it has done so.  (Which is 
> what eliminating the second [data self]; would do.)  Essentially, it 
> must preserve knowledge that an invocation of [self data] MIGHT be 
> present at that effective location, because it MIGHT actually have 
> to invoke it after all if a method is swizzled, a category is 
> loaded, and so on.


Such a theoretical JIT compiler would have all the information 
required to successfully determine if removing the sending of the 
message 'self' to object 'data' would alter the meaning of the code.

If the JIT compiler can successfully reason that the whole process of 
dispatching the 'self' message to 'data' results in no side effects 
and alters no global state, then it follows it can remove the 
statement without changing the meaning (the semantics) of the code.

If it can be shown that removing a line of code can not possibly alter 
the meaning, effects, global state, or results of code in question, 
then by definition the JIT compiler can remove '[data self]' without 
altering the semantics of what was written since it has proven that 
executing that line of code or not executing that line of code can not 
have any effect what so ever.

Consider the case of '[data release]; [data release];'  There is 
absolutely no plausible way (w/o GC) that the compiler or JIT would 
reach the conclusion that it could send the release message any more 
or less than the two times specified.

The simple statement '[data self];' on the other hand, it's easily 
conceivable that the compiler or JIT could reason the statement away. 
The result isn't even saved off in to a variable, or used in the 
comparison of anything.

Can you at least provide an example which at least demonstrates this 
alleged 'semantically completely different' behavior using the 
following example?

@interface MyObject : NSObject { int startInt; }
-(int)start;
-(MyObject)myFunkyMethod __attribute((const));
@end

@implementation MyObject
-(int)start { return(startInt); }
-(MyObject)myFunkyMethod { return(self); }
@end

-(int)doWork:(int)work with:(MyObject)obj
{
  int r = [obj start];
  for(int x=0; x<10; x++) { r += work; }
  [obj myFunkyMethod];
  [obj myFunkyMethod];
  return(r);
}

If your assertion is true, it should be a simple matter to show how 
changing the number of times myFunkMethod is dispatched (including 
removing it entirely) alters 'the semantics' of the code which results 
in a change in the value returned by doWork.

For reference: http://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Function-Attributes.html#Function-Attributes

const

Many functions do not examine any values except their arguments, and 
have no effects except the return value. Basically this is just 
slightly more strict class than the pure attribute below, since 
function is not allowed to read global memory.
Note that a function that has pointer arguments and examines the data 
pointed to must not be declared const. Likewise, a function that calls 
a non-const function usually must not be const. It does not make sense 
for a const function to return void.


>

>>> If I write
>>>
>>> - (void)doSomething:(NSArray *)array {
>>>  NSUInteger count1 = [array count];
>>>  NSUInteger count2 = [array count];
>>>  NSLog(@"%u", count1);
>>>  NSLog(@"%u", count2);
>>> }
>>>
>>> the compiler can't collapse those into a single invocation of -
>>> count.  After all, it could be passed a subclass of NSArray for 
>>> whom -count has side-effects.  Think about a "thread-safe 
>>> array" (as bad as the concept might be) for example.

>>
>> Well, in the case of your example, you have a bug: You have 
>> statically typed the class to NSArray, not your subclass.

>
> This is not a bug.  This is fundamental to how object-oriented 
> programming works!  You should always be able to pass an instance of 
> a subclass wherever an instance of the superclass is expected.


You're mistaken.  You have statically typed the object.  Consider the 
following:

@interface MySuperArray : NSArray
-(NSRange)count;
@end

If we use your example of -(void)doSomething:(NSArray *)array; and 
send it an object of class MySuperArray, you're going to get some 
surprising results.  Again, this is 100% legitimate, nothing weird 
going on.  There is no 'but you're returning a different type than the 
parent class and that's illegal!'  No, it's perfectly legal, and will 
compile without any warnings.  It highlights the fact that not all 
subclasses of NSArray are necessarily equal to the base class.

Switching to -(void)doSomething:(id)array;, as it should be if you are 
going to be sending object types other than just NSArray, THEN the 
compiler will let you know that you might be in for some trouble:

test.m: In function 'foo':
test.m:51: warning: multiple methods named '-count' found
/System/Library/Frameworks/Foundation.framework/Headers/NSArray.h:15: 
warning: using '-(NSUInteger)count'
test.m:11: warning: also found '-(NSRange)count'

This lets you know that there are classes that may return a result of 
a different type than the one you're expecting.

Consider the fact that all the methods for init* and various 
convenience init + autorelease all declare their return types as (id), 
and not the base class.  +(id)array and +(NSArray *)array mean two 
different things.  By declaring the method as +(NSArray *)array, you 
are declaring that only objects of the class NSArray will be returned 
by the +array method, which is obviously not true.  The same applies 
to your method: By declaring it as (NSArray *)array, you are 
specifying that only NSArray class objects are to be accepted.

Just as '+(NSArray *)array' does not mean "and any possible 
subclasses", neither should your prototype of "-(void)doSomething:
(NSArray *)array". The declaration '+(NSArray *)array' obviously means 
'Only of class NSArray' and is the reason why it's not declared as 
such because +array may return an object of a different class, even 
though that class is a subclass of NSArray.

Consider your statement "You should always be able to pass an instance 
of a subclass wherever an instance of the superclass is expected." in 
the context of '-(void)doSomething:(NSObject *)array'  NSArray is a 
subclass of NSObject.  Nobody interprets this to mean 'NSObject or any 
of its subclasses'.

>> If one applies the 'attribute only applies to the class it was 
>> specified for' rule:
>>
>> By statically typing the class to NSArray, you have certified to 
>> the compiler that no other object type will be received as an 
>> argument.  When you passed it an object of a different type, even a 
>> subclass, you broke your promise to the compiler.

>
> This is simply wrong.


You're encouraged to read the section "Enabling Static Behavior - 
Static Typing" in the Objective-C manual.  This is what allows for 
subclasses to return different types for the same method.  By 
statically typing a declaration as NSArray, you've told the compiler 
that the object is a NSArray (only) class object, and only the methods 
for NSArray apply.  If the compiler thought you meant 'This is an 
object of NSArray class or any of its known subclasses, and only 
methods for the NSArray class and any of its known subclasses apply' 
then you would get a warning in the case where there exists the 
possibility of different return types for the same message, like in 
the example above.  The fact that you don't seems to be a pretty clear 
indication that at least the compiler thinks that you've communicated 
your intention that 'only objects of the NSArray class need apply, no 
subclasses.'  The manual leans this way too.  The fact that object 
instantiation methods return 'id' and not the base class are further 
evidence that this is indeed the case.

You also can't send messages declared in a subclass of NSArray to a 
'NSArray *array;' object without getting a warning.  Again, further 
evidence that the compiler believes that only the explicitly named 
class is applicable, and not 'any and all subclasses'.

As soon as the method declaration is changed to -(void)doSomething:
(id)array, then the compiler steps in and warns you that all might not 
be well in the land of -count.  Again, further evidence that the 
compiler thinks you mean something very different than what you're 
claiming is the case with '(NSArray *)'.  If your interpretation were 
correct then the compiler would be obligated to inform you of 
potential subclass return type mismatches.

The evidence would seem to lean in favor of my interpretation.