Re: Instance Variable access
Re: Instance Variable access
- Subject: Re: Instance Variable access
- From: Andy Lee <email@hidden>
- Date: Mon, 10 May 2004 11:03:37 -0400
On May 10, 2004, at 7:34 AM, Allan Odgaard wrote:
On 10. May 2004, at 4:39, Andy Lee wrote:
Like the current use of hashing ;)
Sort of, but with the reminder that hash values per se are not used
for looking up a class's implementation of a method. The
method-lookup table uses a unique lookup key -- a SEL -- and not a
hash value, which is not guaranteed to be unique for all method
names.
I was thinking of "(uint32_t)selector % ARRAY_SIZE" as hash-value --
if you do not "modulo" it, then the table needs to be as big as the
highest SEL-value, and since these are unique, that could result in
some rather large arrays, pr. class.
Yes, I got that -- the hash function being modulo, or even if it
wasn't, "%" could be thought of as shorthand for the actual function.
My point was that there are other ways to do lookup besides a hash
table. Hash tables are most useful for one-to-many associations.
Going from a SEL to a function pointer is a one-to-one association, so
I thought something faster could maybe be used. But if hash tables are
in fact used, I guess this was a vain hope; in practice, maybe a
well-chosen ARRAY_SIZE and a fast, sufficiently random hash function
(like, say, modulo) make the hash table best. The naive alternative
that came to mind was a sorted array with binary search, but I can
imagine a hash table beating that. In any case, I shouldn't try to
argue a "maybe" against what is done in practice by people who actually
know what they're doing.
[...] I figured the class loader could go through the names of all
the methods in the class being loaded, generate new SELs as necessary
for method names we haven't seen before, and update the method-lookup
tables (the big ones I was talking about) for all classes that are
affected.
Okay -- you are correct about the first part, but it doesn't update
the tables. I think the main reason for this is, that since the table
is a hash, we want as few values as possible in the array, to minimize
the chance of clashes.
Even if it weren't a hash, it would have non-constant search time, so
smaller would be faster. I was thinking that maybe a fully populated
table could pay for itself by not having a clash or cache updates to
worry about, but given the numbers we're talking about I believe I was
wrong. I can see how just-in-time updates of a hash table would be the
best solution.
Another reason could have to do with performance, e.g. if I add an
NSString category, it needs to update tables for all classes being or
inheriting from NSString.
I would lump that case together with class-loading and +poseAsClass: --
they're one-time operations that are almost always done at application
launch. I wouldn't have considered these to be performance issues.
The worst scenario I can think of would be loading a category of
NSObject while the application is running; you'd have to update the
method-lookup tables of practically every class. If it's an app with
user interaction, there would be an ugly time lag. Given the fact
that, as you point out, only a fraction of the methods will be used,
just-in-time makes sense.
Okay, thanks again!
--Andy
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.