Accidentally Quadratic KVO
Here’s an interesting instance of quadratic complexity: adding and removing KVO observers on an object (FB11644022). A graph of its performance as I scale the number of observations is so perfect it could probably feel right at home in an algorithmic complexity textbook!
It’s probably not surprising in the least that observers are stored internally in a set of hash tables. But when you add observations on an object, part of the lookup process calls for computing a hash value over all the observers. This would be O(n) on each KVO update except Foundation caches this hash value whenever the observers change, so lookups are O(1). This is good, except this just hoists the (one-time) O(n) calculation on each update of the observers, because adding and removing observers causes a full rehash.
[…]
By the way, if you’re interested in how KVO is implemented, you can reverse Foundation like I did…or find out after some searching that someone has basically decompiled the entire thing[…]
Ventura fixes an issue (FB9876193) where KVO rehashing would trigger 300-1400 autoreleases per operation while rebucketing, leading to a performance cliff where we’d see hundreds of millions of pending
NSKeyValueObservationInforeleases.
1 Comment RSS · Twitter
Long time ago, I worked on a Software that heavily used KVO for a large graph of objects.
It was sluggish as hell, and I had to reimplement a thin KVO proxy for objects with a large numbers of observers.
The proxy was the only object observing change using KVO, and it was forwarding change notifications to a pool of objects it manage directly.
I never investigate the root cause though.
