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;
@end

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.)