Re: objective-c: dynamic inheritance and s-arrays [was: how slow] ?

[Marko Mikulicic]

Malmberg wrote:

> > But this means that a cached lookup needs to walk through the inheritance graph.
> > IC-s cache the target where the method is effectively found so no cycles are
> > lost traversing the inheritance graph.
>
> I think you've misunderstood the s-arrays. The s-array for a class
> includes all methods for that class, including ones that have been eg.
> inherited.

uh ?

Erick M. Buck wrote:

>As long as the instance variable layout does not change, dynamically
>changing the super class of an existing class is one pointer operation.
>Each class object has a "superclass" variable.  The message cache tables are
>per-class (At least in my runtime and Apple's runtime) so changing a
>superclass automatically changes the method cache with no extra effort.

Perhaps something changed in the runtime. but which way ?

> >   I've made some simplified testing and it turns out that for a 10 deep
> > inheritance there is a 6% difference between calling the root and the child
> > (the test method returns the incremented argument). In this case IC are ~2.3
> > times faster than cached lookup.
>
> In obj-c? That shouldn't be possible, but I'll check.

It's only 6%, possibily a mistake (althrouh I executed the test 20 times for 40 
secs run each). I'd expect something more for a walkthrough.

But then poseAs: (dynamic inheritance) has to rebuild the whole s-array.

Is there more than one developed runtimes implementations around (for gnustep, I 
mean)?

> >  What is the relationship between lookup speed and the number of methods in
> > that class ?
>
> The lookup time is constant (for all valid selectors with
> implementations after the first call to a method in that class, at
> least).

Ok. as one would expect from sparse arrays.

> > Why sends to "super" are not directly called, if dynamic inheritance is not used
> > ? (A compiler flag perhaps?)
> > Is this related to dynamic loading of classes ?
>
> Dynamic loading of categories and poseAs: (I suppose that would qualify
> as dynamic inheritance) would break, but it should be possible to add a
> compiler flag to do it.

I heard of some problems with poseAs:. Someone said that it works only if you 
call it when no instance of that class is alive. (or at least NeXT runtime did 
so) Is this just a bug or an implementation feature ?
 If so, it does not really qualify as dynamic inheritance. And also if the 
s-array conains the flattened method table, it must be rebuilded if the parent 
changes, so it can't really be used for fast dynamic inheritance (required by 
some applications of DI), but of course it can be acceptable for slowly changing
reparenting.

> > Perhaps super sends are a good place for ICs (you get 99.99% hits)
>
> 100% until you use poseAs:, in which case you'd get 0% hits for that
> class.

poseAs could update the cache.
Or you could update on every miss, since the misses are so rare.

> > Do you think that the increase in code size due to PICs, and its presence in the
> > icache, could lead to performance loss comparable to the gain (~2 times) in
> > message sends ? (the performance loss can show up somewhere else, that's my 
> > worry)
>
> I don't know, and I wouldn't want to try to find out. Things like that
> are very tricky to measure.

I'm not asking you to do it. I was only courious about your feeling about that.
We cannot know everything, we must speculate with far less data than stricly 
required.
 When I'll have more time I will implement two level outline (thread-safness 
mostly) PICs and we will see how the impact on overall performances is, just for 
curiosity.

Marko