Cliff Hacks Things.

Saturday, March 17, 2007

Cocoa Bindings: @sum is O(n), even if you're nice to it.

My last post was very positive toward Cocoa Bindings. A week later, you might say the honeymoon is over.

They still do most of what I need, don't get me wrong -- it's the performance. In profiles, whenever Cesta starts using an entire core on my MackBook Pro, Bindings is responsible for 80-90% of it. (The harder stuff, like capturing, decoding, and constraint-checking a loaded ethernet link, is 2% or less.)

I'm working on isolating each part of the problem, but here's a tidbit for today -- not from Bindings specifically, but from the Key-Value Coding system on which they're built (thanks for the correction, Scott). (Update: I Sharked my way to some of the other Bindings issues in my next post.)

The performance of @sum may surprise you. Specifically, the @sum function is O(n) for the total size of your array, even if you distribute incremental updates using KVO.

This will come as no surprise if you're familiar with how KVC is implemented, but for those of us (me) hoping for a free ride, it's a bit of a downer.

The backstory:

I wanted a nice label on Cesta's summary view showing the number of bytes captured. Lazy as I am, I decided to use Bindings: I created an NSTextField and bound it to the aggregate property "@sum.capturedSize" on my Capture Events NSArrayController.

Now, I put a lot of work into distributing only incremental updates when new packets are captured. My code diligently calls willChange:valuesAtIndexes:forKey and didChange:valuesAtIndexes:forKey with only the changed packets, so that observers don't have to reevaluate the whole array each time. Hell, I even maintain separate state for each thread so that nobody sees new packets before they've received willChange:.

In short, I expected that any observer update that doesn't rely on all the data (like @max would) would be, at worst, O(n) for the number of changes.

I was incorrect, as my debug traces show. @sum is calling capturedSize on every packet, every time.

This is one of three hotspots that cause Cesta's screen refreshes to be O(n) to the number of events captured. The fix? Drop the aggregate function and bind to a scalar property. It's nearly trivial, but I'll include the code here for completeness.

First, we add an ivar for the property, and a getter/setter pair:

@interface CSCaptureDocument : NSDocument {
uint64_t _bytesCaptured;
- (uint64_t)bytesCaptured;
- (void)setBytesCaptured: (uint64_t)bytes;

Then, we add the code for that getter and setter. I won't post it here; there's a button to generate it.

Then, we hook into the packet delivery code:

- (void)frameSource: (CSFrameSource *)source receivedFrame: (CSFrame *)frame
[_capture appendCaptureEvent: frame];
[self setBytesCaptured: _bytesCaptured + [frame capturedSize]];

Then we simply re-bind the "Bytes Captured:" label to the bytesCaptured property of the document, rather than an aggregate property on the NSArrayController. Voila -- instant 15% performance savings.

(Edit: as Scott points out in the comments, this behavior makes sense for @sum since there's nowhere to store the accumulator. I've updated some of the text above to clarify that I'm not attacking @sum here, just pointing out my own very inappropriate use of it -- just in case someone else does the same thing and goes Googling for an explanation.)

Labels: , , ,


  • Hi Cliffe. I accidentally found your blog. Yay for synchronicity.

    The @sum thing is actually part of the Key-Value Coding protocol, not Cocoa Bindings. All the view knows is that the source of its data changed and it requests the new value using whatever key path it was given. If that key path contains @sum, KVC has to run through and add everything up.

    From a design perspective, it's not clear to me where KVC would do the "bookkeeping" to keep track of the current value and simply add to it. However, I think a Core Data app *might* use SQLite to do the calculation, so maybe that's something to experiment with.

    That is, you might be able to construct an NSPredicate which contains "@sum"as a component. This should work even for just an in-memory Core Data store. Maybe that's more work than you want, but it's worth checking out the predicates programming guide:

    Search for "@sum" in the document.

    By Blogger Unknown, at 6:49 PM  

  • Scott,

    You're right -- this is KVC. (Though there seem to be cases where @sum and @count don't work when applied to multi-value KVC properties, but do when those properties are fronted by an NSArrayController...but I'm probably screwing it up.)

    I can't blame @sum for being O(n), but for my application, replacing it with a simple aggregation-controller is a big win.

    I've actually modularized the aggregation controller; I'll edit the post with a pointer in a bit.

    By Blogger Cliff L. Biffle, at 12:14 AM  

  • Oops, forgot to respond to one part there:

    Unfortunately, I'm not using Core Data. I migrated Cesta over to Bindings because its interface is a textbook master-detail arrangement (I very nearly just copied the ADC samples); its storage requirements, however, aren't particularly well-suited to SQLite (and require the ability to work with many gigabytes of data, ruling out the binary format). Granted, my knowledge of SQLite is from mid-2006; perhaps it's gotten better at storing large blobs.

    I drool over Core Data frequently, and would love to find an excuse to use it. Perhaps that'll be my next leap.

    By Blogger Cliff L. Biffle, at 12:46 AM  

  • Have you filed an enhancement request in Radar about this behavior?

    By Blogger Peter Hosey, at 5:11 PM  

  • Peter,

    I haven't. That this is even the right thing for @sum to do is arguable...I think it is, but I'm open to being persuaded.

    I do see a way to store the accumulator without having to swizzle it into the bound class, but I'd have to prototype it before I'm confident about it.

    Every radar I've ever filed has been tersely closed as duplicate or simply never updated, so I admit that I wonder if it's worth my time. :-) Better to post it here, where others can learn from my mistakes.

    By Blogger Cliff L. Biffle, at 8:43 PM  

  • I would like to ask, what programming language you use in this post?
    my Blog: Susu Kambing & Susu Kambing

    By Anonymous Anonymous, at 4:19 PM  

  • I like this website its a master peace ! Glad I found this on google . Interesting, will come back here again. 야한동영상

    Also feel free to visit may webpage check this link

    By Blogger yadongbizz, at 7:01 AM  

  • I’m impressed, I must say. Rarely do I come across a blog that’s both equally educative and interesting, and let me tell you, you’ve hit the nail on the head 일본야동

    Also feel free to visit may webpage check this link

    By Blogger yadongbizz, at 7:01 AM  

  • I’m truly enjoying the design and layout of your website. It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. 한국야동닷컴

    Also feel free to visit may webpage check this link

    By Blogger yadongbizz, at 7:01 AM  

  • I read this article fully regarding the resemblance of most recent and preceding technologies, it’s amazing article. 국산야동

    Also feel free to visit may webpage check this link

    By Blogger yadongbizz, at 7:02 AM  

  • Thanks for the marvelous posting! I certainly enjoyed reading it, you’re a great author. I will ensure that I bookmark your blog and may come back from now on. I want to encourage you to continue your great writing, have a nice day! 중국야동넷

    Also feel free to visit may webpage check this link

    By Blogger yadongbizz, at 7:02 AM  

  • Students should always look for the best Java assignment help and conduct extensive research on them. Read the feedback from customers and learn about the experts who work with them. If a Java assignment help online has positive and reliable user evaluations, you should only use their services. A dubious Java assignment help website won't have any reviews and won't reveal any information about the specialists who work on the projects. Customers' money is taken by these companies, and they are entirely cut off.

    By Blogger Kaylee Brown, at 3:45 AM  

  • You've truly inspired me and I am delighted to have access to this special site today. A wonderful and inspiring effort in your article. Thank you very much for sharing helpful post. uduth school of community health admission 2023

    By Blogger Essien, at 8:09 AM  

Post a Comment

<< Home