Re: Adding more and more key/value observers is much too slow - workaround needed.
On Aug 12, 2009, at 11:15 AM, Andy Lee wrote:
On Aug 12, 2009, at 11:37 AM, Christopher Kane wrote:
Don't pass the observer as the context: argument; pretty much
anything else is better.
Out of curiosity -- why would this affect performance and why is
this a bad idea (other than performance)? Isn't the context:
treated as an opaque pointer by KVO?
--Andy
Well, as anyone can see from sampling the test program, a lot of time
is being spent in hash table management, and as I can tell through
experience, there are a lot of probe collisions happening. You are
adding many observers into the KVO subsystem, and perhaps KVO is
keeping hash tables of these registrations.
[modelObject addObserver:observer
forKeyPath:@"title"
options:NSKeyValueObservingOptionNew |
NSKeyValueObservingOptionOld
context:observer];
Now here is where we enter the realm of the hypothetical. Suppose
that the hashing is based on some combination of the observer, key
path, options, and context, which would be reasonable. Suppose (and I
checked and this isn't the case, but this is easy to understand), that
the hash code computation goes something like this:
NSUInteger computeHash(...args...) {
return (NSUInteger)((uintptr_t)observer - (uintptr_t)context +
[keyPath hash] - (uintptr_t)options);
}
Now, the keyPath and the options are the same for every registration,
so they aren't contributing anything [in the test program] to make the
hash codes for each registration different. If the observer and
context are the same, obviously in my contrived example, they are
cancelling each other out. Thus my -hash would always return the same
value for all the registrations, which is terrible for hash table
performance.
Now I can see that what is going on is not actually full degenerate
linear probing, so the interaction between observer and context must
be more subtle in the computation of any hash code. How did I know
that context being the observer was the issue? Try it! Just changing
it to NULL makes an enormous difference. So there must be some sort
of interaction there. In this contrived example, the observers and
modelObjects are likely to be fairly linearly allocated from out of
the heap, and probably all pretty close together, which might be one
effect, and so the bit pattern of the "contexts", which can only be
used as a raw pointer/integer value in any hash code computation,
would be relatively similar.
However, using the address of static data would be better than NULL,
to avoid the likelihood of collisions with other possible KVO
registrants on that object.
I don't know any reason for not passing observer as the context: other
than it seems to avoid this performance corner-case. In the context
(no pun intended) of the observeValueForKeyPath:... method, of course,
you don't *need* to pass observer as the context because the observer
is already "self".
Chris Kane
Cocoa Frameworks, Apple
Passing NULL (just, for example) flattens the curve quite a bit.
If you have nothing better to pass in, put this in your code and
pass the address of it:
static char _xyzzy_ = 0;
Chris Kane
Cocoa Frameworks, Apple
On Aug 3, 2009, at 6:51 AM, Andreas Känner wrote:
Hi,
If you add more and more key/value observers with
addObserver:forKeyPath:options:context: this call takes longer and
longer in a non-linear way.
I posted a bug report today (ID: 7112953) but maybe someone
already has a workaround. Here is my sample code:
#include
@interface ModelObject : NSObject
{
NSString* title;
}
@property (readwrite, copy) NSString* title;
@end
@implementation ModelObject
@synthesize title;
@end
@interface Observer : NSObject
{}
@end
@implementation Observer
@end
void addObservers(NSUInteger count)
{
// Create model objects and observers:
NSMutableArray* modelObjects = [NSMutableArray
arrayWithCapacity:count];
NSMutableArray* observers = [NSMutableArray
arrayWithCapacity:count];
for(NSUInteger i=0; i options:NSKeyValueObservingOptionNew |
NSKeyValueObservingOptionOld
context:observer];
}
NSLog(@"time to add %d observers: %f s", count, -[startDate
timeIntervalSinceNow]);
}
int main (int argc, const char * argv[])
{
NSAutoreleasePool* pool = [NSAutoreleasePool new];
addObservers(10);
addObservers(100);
addObservers(1000);
addObservers(1);
[pool release];
}
In my test case an observer does always observe only one object
and each observed object is only observed by one observer. I think
this is a common use case.
I have results for Snow Leopard too, but I think I'm not allowed
to post them on this mailing list. Here are the results for Leopard:
I tested this with different build settings (with/withou
Re: Adding more and more key/value observers is much too slow - workaround needed.
On Aug 12, 2009, at 11:37 AM, Christopher Kane wrote:
Don't pass the observer as the context: argument; pretty much
anything else is better.
Out of curiosity -- why would this affect performance and why is this
a bad idea (other than performance)? Isn't the context: treated as an
opaque pointer by KVO?
--Andy
Passing NULL (just, for example) flattens the curve quite a bit.
If you have nothing better to pass in, put this in your code and
pass the address of it:
static char _xyzzy_ = 0;
Chris Kane
Cocoa Frameworks, Apple
On Aug 3, 2009, at 6:51 AM, Andreas Känner wrote:
Hi,
If you add more and more key/value observers with
addObserver:forKeyPath:options:context: this call takes longer and
longer in a non-linear way.
I posted a bug report today (ID: 7112953) but maybe someone already
has a workaround. Here is my sample code:
#include
@interface ModelObject : NSObject
{
NSString* title;
}
@property (readwrite, copy) NSString* title;
@end
@implementation ModelObject
@synthesize title;
@end
@interface Observer : NSObject
{}
@end
@implementation Observer
@end
void addObservers(NSUInteger count)
{
// Create model objects and observers:
NSMutableArray* modelObjects = [NSMutableArray
arrayWithCapacity:count];
NSMutableArray* observers = [NSMutableArray
arrayWithCapacity:count];
for(NSUInteger i=0; i options:NSKeyValueObservingOptionNew |
NSKeyValueObservingOptionOld
context:observer];
}
NSLog(@"time to add %d observers: %f s", count, -[startDate
timeIntervalSinceNow]);
}
int main (int argc, const char * argv[])
{
NSAutoreleasePool* pool = [NSAutoreleasePool new];
addObservers(10);
addObservers(100);
addObservers(1000);
addObservers(1);
[pool release];
}
In my test case an observer does always observe only one object and
each observed object is only observed by one observer. I think this
is a common use case.
I have results for Snow Leopard too, but I think I'm not allowed to
post them on this mailing list. Here are the results for Leopard:
I tested this with different build settings (with/without GC and
32/64bit)
Machine: iMac 2.4 GHz Intel Core 2 Duo
Leopard (10.5.7/9J61):
32Bit:
With GC:
time to add10 observers: 0.001008 s
time to add 100 observers: 0.001796 s
time to add 1000 observers: 0.174864 s
time to add 1 observers: 10.746330 s
Without GC:
time to add10 observers: 0.000920 s
time to add 100 observers: 0.000956 s
time to add 1000 observers: 0.056894 s
time to add 1 observers: 4.615175 s
64Bit:
With GC:
time to add10 observers: 0.001340 s
time to add 100 observers: 0.001533 s
time to add 1000 observers: 0.125700 s
time to add 1 observers: 7.545702 s
Without GC:
time to add10 observers: 0.001058 s
time to add 100 observers: 0.000831 s
time to add 1000 observers: 0.053189 s
time to add 1 observers: 4.006754 s
Notes:
If you know a workaround for this bottleneck please drop me an email.
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/ckane%40apple.com
This email sent to ck...@apple.com
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/aglee%40mac.com
This email sent to ag...@mac.com
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
Re: Adding more and more key/value observers is much too slow - workaround needed.
Don't pass the observer as the context: argument; pretty much anything
else is better. Passing NULL (just, for example) flattens the curve
quite a bit. If you have nothing better to pass in, put this in your
code and pass the address of it:
static char _xyzzy_ = 0;
Chris Kane
Cocoa Frameworks, Apple
On Aug 3, 2009, at 6:51 AM, Andreas Känner wrote:
Hi,
If you add more and more key/value observers with
addObserver:forKeyPath:options:context: this call takes longer and
longer in a non-linear way.
I posted a bug report today (ID: 7112953) but maybe someone already
has a workaround. Here is my sample code:
#include
@interface ModelObject : NSObject
{
NSString* title;
}
@property (readwrite, copy) NSString* title;
@end
@implementation ModelObject
@synthesize title;
@end
@interface Observer : NSObject
{}
@end
@implementation Observer
@end
void addObservers(NSUInteger count)
{
// Create model objects and observers:
NSMutableArray* modelObjects = [NSMutableArray
arrayWithCapacity:count];
NSMutableArray* observers = [NSMutableArray
arrayWithCapacity:count];
for(NSUInteger i=0; i options:NSKeyValueObservingOptionNew |
NSKeyValueObservingOptionOld
context:observer];
}
NSLog(@"time to add %d observers: %f s", count, -[startDate
timeIntervalSinceNow]);
}
int main (int argc, const char * argv[])
{
NSAutoreleasePool* pool = [NSAutoreleasePool new];
addObservers(10);
addObservers(100);
addObservers(1000);
addObservers(1);
[pool release];
}
In my test case an observer does always observe only one object and
each observed object is only observed by one observer. I think this
is a common use case.
I have results for Snow Leopard too, but I think I'm not allowed to
post them on this mailing list. Here are the results for Leopard:
I tested this with different build settings (with/without GC and
32/64bit)
Machine: iMac 2.4 GHz Intel Core 2 Duo
Leopard (10.5.7/9J61):
32Bit:
With GC:
time to add10 observers: 0.001008 s
time to add 100 observers: 0.001796 s
time to add 1000 observers: 0.174864 s
time to add 1 observers: 10.746330 s
Without GC:
time to add10 observers: 0.000920 s
time to add 100 observers: 0.000956 s
time to add 1000 observers: 0.056894 s
time to add 1 observers: 4.615175 s
64Bit:
With GC:
time to add10 observers: 0.001340 s
time to add 100 observers: 0.001533 s
time to add 1000 observers: 0.125700 s
time to add 1 observers: 7.545702 s
Without GC:
time to add10 observers: 0.001058 s
time to add 100 observers: 0.000831 s
time to add 1000 observers: 0.053189 s
time to add 1 observers: 4.006754 s
Notes:
If you know a workaround for this bottleneck please drop me an email.
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/ckane%40apple.com
This email sent to ck...@apple.com
___
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
