Cocoa with Love

Designing a view with Bindings (UITableView on the Mac)

2010-03-10T21:23:00.001-08:00

Bindings are one of the best ways of connecting your view and model on the Mac but due to the layers of abstraction involved — and the fact that they don't exist on other platforms — bindings can seem foreign and confusing. In this post, I'll show a complex view that is traditionally implemented without bindings (the iPhone's UITableView) and show how it might be redesigned for the Mac with bindings.

The aim

I'm going to show the design of ColumnView, a Mac NSView subclass which operates in a similar manner to the iPhone's UITableView.

Specifically, the ColumnView will lay out RowViews (a proper NSView subclass instead of cells like NSTableView arranges). The rows are grouped in sections (sections may have a header and may be independently sorted). The rows can have different heights and be different classes.

I'm not aiming to make this a fully-fledged UITableView recreation — it won't support significant interactivity, animation or editing modes, although all these things could be added to the design (it is designed to be a flexible foundation, even if all features aren't present).

The aim of this design is to show that the entire structure and configuration of the ColumnView can be done with one binding. The UITableViewDataSource/UITableViewDelegate, normally required for a UITableView, can all be replaced by this single binding.

I won't be looking at bindings in Interface Builder in this post. I realize that is how most people configure bindings but to keep the number of topics down, I'm going to limit discussion to bindings configured in code.

Background: controller heavy implementations

Traditionally, Model-View-Controller would work like this:

Model — sends notifications when it changes but otherwise keeps to itself
Controller — receives model notifications and actively changes views in response
View — passive and simply shows information the controller shoves at it

This works well but the controller ends up being huge because it contains all the logic of responding to changes, configuring the view, plus all of the interactivity work that may be required by the views.

A number of larger views, including the iPhone's UITableView and the Mac's NSTableView (without bindings) operate on a delegate model which breaks the controller up slightly:

Model — (as before) sends notifications when it changes but otherwise keeps to itself
Controller — pushes new data to the delegate and notifies the view that it needs an update
View — determines areas needing an update and asks the delegate how to display those areas
View delegate — tells the view how to update based on data from the controller

A view delegate is really just a controller but since it is invoked by the view, it allows the view to control when data is loaded and changes are made (the view can control lazy load order).

Ultimately though, this second case can still involve a lot of code to configure the view and provide it with data. The potential advantage of breaking the controller into two pieces (the controller and the view delegate) is normally lost since both are frequently implemented in the same class.

Bindings: a reusable controller

The controller heavy nature of the above approaches can be burdensome as you need to rewrite the controller every single time — it is entirely specific to the mode and view that it joins.

Cocoa Bindings are a way of eliminating implementation specific controller code — the entire controller layer can be handled with reusable controllers and observations and configurations specified in data, not code.

Cocoa Bindings purpose in one sentence: If you can simplify your design so that all a controller needs to do is copy data from the model to the view, then the controller's role can be replaced by a simple, reusable "binding" object and all that remains is to configure that binding object with data.

The bindings structure is then:

Model — (as before) sends notifications when it changes but otherwise keeps to itself

KVO interface/controller — the interface that the model exposes must be Key Value Observing compliant. This interface may be part of the Model, or it can be a lightweight wrapper around the model, or a generic controller like NSArrayController.

Key Value Binding — ensures that data from the KVO controller is pushed to an object with exposed bindings. May pass the data through an NSValueTransformer before pushing to the exposed binding. A binding may also contain an options dictionary which tells the view how to handle data it receives.
View — determines areas needing an update and asks the delegate how to display those areas

Exposed binding — any Key Value Coding compliant property on the view but may also have options and other metadata to support Interface Builder and configuration.

While I've included more layers in this description, most of the time, you'll only deal with two: the model and the view.

The "Key Value Binding" layer is entirely automatic — in fact, unless you're hacking or looking closely at the stack, you won't actually see the classes that handle this layer. It will "just happen".

The "KVO interface/controller" and "Exposed binding" may or may not be automatic. Many model classes will be KVO compatible already, although others may require a shallow layer to improve their compatibility.

The real work for bindings, is in designing views to be fully configurable through bindings alone.

Terminology: I've already mentioned KVC and KVO. These technologies are fundamental to how bindings work. If you don't have great familiarity with these terms, you can read the Apple programming guide to Key Value Coding and Key Value Observing. You could also read my earlier post on 5 key-value coding approaches in Cocoa but note that bindings require proper NSKeyValueCoding compatible KVC.

Implicit bindings support

In some situations, you might be able to connect a model and view with a binding with no cooperation from either the model or the view. This will be the case if your model is already KVO compliant and your view can be totally configured by piping this KVO data directly into KVC properties on the view.

For example, if your model has a text property that is only ever changed through its setText: method and you want to display that property in a text field, you can connect the two with:

[someTextField bind:@"stringValue" toObject:myModelObject withKeyPath:@"text" options:nil];

Bindings will do the rest.

As soon as the binding is established, the binding will set the stringValue property of the someTextField to the value of the text property from the myModelObject. Every time the text is set using the setText: method, an automatic Key Value Observing notification will be detected by the binding and it will keep the text field in sync.

Normally though, bindings are used in situations where the view explicitly supports them. For example, with NSTextField, you would normally use NSValueBinding instead of @"stringValue". Ultimately, the NSTextField will map NSValueBinding onto the same @"stringValue" property but the supported binding guarantees compliance (and also supports other options like implicit conversion from NSNumber to NSString).

Adapting a delegate/dataSource view for use with bindings

Most views require a redesign so that they can be completely configured through Key Value Coding compliant properties. The reason for this is that the view must be completely configurable through KVC compliant properties to work with bindings.

In adapting UITableView for the Mac, I'll need to make such a redesign since UITableView does not expose the KVC properties we would require.

Looking at the situation before bindings

To achieve the features I want, a UITableView would require its dataSource to implement the following methods:

– tableView:cellForRowAtIndexPath:
– numberOfSectionsInTableView:
– tableView:numberOfRowsInSection:
– tableView:titleForHeaderInSection:

and the delegate would need to implement:

– tableView:heightForRowAtIndexPath:
– tableView:viewForHeaderInSection:

None of these methods set KVC properties so they all need to go.

Recategorizing delegate and controller methods as properties

We need to rethink what the table displays as data that we can set.

Ultimately, a UITableView contains two tiers of data: the section and the row. For each of the UITableView dataSource and delegate methods, we can consider the returned value as either a property of a section, row (or the array containing them).

tableView:cellForRowAtIndexPath: — Row property
numberOfSectionsInTableView: — Property of the sections array
tableView:numberOfRowsInSection: — Property of the rows array within a section
tableView:titleForHeaderInSection: — Section property
tableView:heightForRowAtIndexPath: — Row property
tableView:viewForHeaderInSection: — Section property

ColumnView, ColumnSection and RowView binding interfaces

Structure of data used for the bindings

The bindings design for the ColumnView then comes directly from this categorization.

At the top level we need to bind the ColumnView to an array of sections. Each section must have a row array property.

Each "section" is not an object of any specific class — it can be any object from your model. To make it work, the ColumnView must also know the key path from the section to its content. This key path can be set by using a binding option when a binding is established for the sectionsArray. It is this type of key path traversal that allows the view to traverse model data whose structure it doesn't necessarily know.

The only tricky point is the tableView:cellForRowAtIndexPath: method. While the "cellForRowAtIndexPath" could be considered a property, the rows and sections here a model objects and having "view" properties on model objects is a bad idea.

I've opted instead to use the row's class as the property instead of a fully realized view. The ColumnView will then construct the view from this class. Further, this class does not need to come from the model object — other means of setting the row's class will exist that are unrelated to the model object involved.

Class structure to follow the data structure

To break the implementation down into manageable components, the design will use three classes:

ColumnView — does all of the layout and manages the array of sections
ColumnSection — manages the array of rows in each section and stores header information
RowView — mostly a drawing class but does report the height for the row, given its data

ColumnView

The only binding for the ColumnView is the ColumnViewSectionArrayBinding which sets the sectionsArray property (ColumnViewSectionArrayBinding is a globally defined string with the value @"sectionsArray").

Along with this binding, the ColumnView has the following additional properties that can be set in the ColumnViewSectionArrayBinding options:

sectionContentKey —A key path (relative to the section object) where the rows array can be found (if not present, it is assumed that the section is the rows array).
sectionClassKey — A key path (relative to the section object) where the default class to use for all rows in the section can be found (if not present the default RowView class is used). This property is overridden by the rowClassKey.
rowClassKey — A key path (relative to the row object) where the class for the row can be found (if not present, it is assume the section is the rows array).
rowDisplayKey — A key path (relative to the row object) where a separate object used for display is found (if not present, the row object is used directly for display).
headerDataKey — A key path (relative to the section object) where the object for the header is found (if not present, no header is shown for the section).
headerClassKey — A key path (relative to the section object) where the class for the header row is found (if not present, the default RowView class is used).

While you can set these properties directly on the ColumnView, it is expected that they will be passed in the options dictionary and picked up in the implementation of bind:toObject:withKeyPath:options: on the ColumnView.

ColumnSection

The ColumnSection is a simple data class to manage data associated with a section. It looks like this:

@interface ColumnSection : NSObject
{
    NSArrayController *rowDataArrayController;
    NSString *rowClassKey;
    NSString *rowDisplayKey;
    
    Class defaultClass;
    
    id headerData;
    Class headerClass;
}

All of these properties are set by the ColumnView using the properties it extracts from the sectionsArray by following the key paths options from the binding.

The array of row data is set by binding the NSContentArrayBinding of the rowDataArrayController instead of setting it directly as an NSArray property. This is done so that the ColumnSection can sort the array independent of the original data and so that the selection and other controller features of the NSArrayController could be used if desired.

RowView

The RowView has no bindings of its own — it doesn't bindings since its data is passed to it by the ColumnView which gets it from the ColumnSection.

Following the path of setting the data

To see how these bindings work to change the table, I'll explain what happens at each step.

1. The sectionsArray property is set by the binding

Immediately after you establish a binding, the bindings will set the value of the underlying property to be the same as the model object to which it is bound.

- (void)setSectionsArray:(NSArray *)newSectionsArray;

When the sectionsArray is set by the ColumnViewSectionArrayBinding, the ColumnView's setSectionsArray: method is invoked where it constructs a ColumnSection object for each section.

2. The constructed array of ColumnSections is set as the columnSections array

- (void)setColumnSections:(NSArray *)newColumnSections;

The final step in the setter for sectionsArray sets the columnSections property of the ColumnView using the constructed array of ColumnSections objects.

This method observes the rowDataArrayController's arrangedObjects (in case a row in the section changes) and triggers a reload of the view.

If you wanted to bypass bindings for the sections (to use static, manually created sections), you could create and configure the ColumnSection objects yourself and set them using this method.

3. Reload the view

The ColumnView then accesses the properties on the ColumnSection objects to populate the table. Only rows and headers that are visible are constructed, positioned and displayed.

I show this code next time with the implementation of the ColumnView.

End result

The end result of a class designed this way is that configuring the ColumnView is done with a single statement. For the screenshot I showed at the top, the ColumnView is configured with data from the ABAddressBook with a single statement:

[columnView
    bind:ColumnViewSectionArrayBinding
    toObject:[[AddressBookDataController sharedController] groupsController]
    withKeyPath:@"arrangedObjects"
    options:
        [NSDictionary dictionaryWithObjectsAndKeys:
            @"members", ColumnViewSectionContentKeyOption,
            kABGroupNameProperty, ColumnViewSectionHeaderDataKeyOption,
            @"Last", ColumnSectionRowDisplayKeyOption,
        nil]];

This selects the arranged groups from the AddressBookDataController and uses them as sections. The title of each section is the group name, the content is the group's members and the object used for display is the lastname of the group member.

This one statement replaces the 6 dataSource and delegate method implementations that UITableView requires for the same functionality. If you create an IBPlugin for the view, you can configure all of this in Interface Builder and reduce the lines of code to zero.

Obviously, I'm going through a small controller here: the AddressBookDataController. This is because the ABAddressBook does not send KVO notifications when groups or their contents change and further, ABGroups are not KVC compliant for their members method. This controller is to address these problems, sort the groups by name and handle a situation where no groups exist. This work is not really bindings related and would be required in some form if the ColumnView were configured another way.

To be continued...

Matt, I can't help but notice you haven't shared the complete implementation of the ColumnView class.

Well spotted, voice in my head. I wanted to focus on bindings and how to redesign an interface to work with them. I've already run way past the time I was going to spend on this. In my next post, I'll share more about the implementation and let you see all the code.

Load from NIB or construct views in code: which is faster?

2010-03-01T21:54:00.001-08:00

You don't have to look far to find people suggesting that constructing views in code will increase the speed of your program. Since interface performance is a serious concern in iPhone development, I thought I'd look at the performance speed in creating complex iPhone UITableViewCells in code versus loading them from a NIB file.

Introduction

The sample program this time is pretty simple: an iPhone application that can load a table containing 20 rows (sized so that they will all fit onscreen), each row containing 20 fully-configured UILabels, a backgroundView and a selectedBackgroundView.

All timing is done on the construct/load only. Adding cells to the table, configuring the cell for its row and drawing to the screen (all of which is identical in either load from NIB or construct in code cases) is not included as part of the timing results.

The dark line across the right-hand side of each cell is just the word "placeholder" written 19 times on top of itself by the labels added to the cell.

You can download the sample project: NibOrNot.zip

Creating the cell in code

The construction of the cell in code looks like this:

cell = [[[UITableViewCell alloc]
	initWithFrame:CGRectZero reuseIdentifier:CellIdentifier] autorelease];
cell.backgroundView = [[[UIView alloc] initWithFrame:CGRectZero] autorelease];
cell.backgroundView.backgroundColor = [UIColor colorWithWhite:0.95 alpha:1.0];

cell.selectedBackgroundView = [[[UIView alloc] initWithFrame:CGRectZero] autorelease];
cell.selectedBackgroundView.backgroundColor = [UIColor colorWithWhite:0.85 alpha:1.0];

UILabel *firstLabel =
	[[[UILabel alloc] initWithFrame:CGRectMake(5, 0, 60, 20)] autorelease];
firstLabel.tag = 1;
firstLabel.font = [UIFont boldSystemFontOfSize:14];
firstLabel.shadowOffset = CGSizeMake(1,1);
firstLabel.textColor = [UIColor colorWithRed:0.0 green:0.2 blue:0.5 alpha:1.0];
firstLabel.backgroundColor = [UIColor clearColor];
firstLabel.text = @"placeholder";
firstLabel.autoresizingMask = UIViewAutoresizingFlexibleLeftMargin;
firstLabel.adjustsFontSizeToFitWidth = YES;
firstLabel.minimumFontSize = 10;
firstLabel.baselineAdjustment = UIBaselineAdjustmentAlignCenters;
firstLabel.lineBreakMode = UILineBreakModeTailTruncation;
firstLabel.baselineAdjustment = UIBaselineAdjustmentAlignCenters;
firstLabel.highlightedTextColor = [UIColor clearColor];

[cell addSubview:firstLabel];

//
// Plus the construction of a further 19 labels...
//

In this case, the next 19 labels could all be created in a loop (since they're all identical) but I wanted to code to reflect a proper view where each subview is distinct and has many properties uniquely applied — so a basic loop is not necessarily appropriate.

Loading the NIB

There are many different ways to load a UITableViewCell (loading just the contentView, constructing a UITableViewCell subclass and having it load the NIB, etc). I've gone for the quick and easy approach: loading the UITableViewCell from the NIB in its entirety, passing my UITableViewController as the owner.

[[NSBundle mainBundle] loadNibNamed:@"Cell" owner:self options:nil];
cell = loadedCell;
loadedCell = nil;

It may be hard to see how the loadNibNamed:owner:options: method is connected to the other two lines. In this code, loadedCell is an IBOutlet on self. When the NIB is loaded, it sets the loadedCell value to be equal to the loaded cell (this is configured in the NIB file). After loading, I copy the loadedCell into a local variable named cell (which is later configured and returned) and set the instance variable on the class back to nil (because we no longer need this pointer after returning it).

Simulator results

The first 10 results from the simulator look like this:

Generated in code	Loaded from NIB
Generated cell in 0.00153798 seconds	Loaded cell in 0.00184 seconds
Generated cell in 0.00138998 seconds	Loaded cell in 0.00168097 seconds
Generated cell in 0.00138199 seconds	Loaded cell in 0.00168198 seconds
Generated cell in 0.00139898 seconds	Loaded cell in 0.001706 seconds
Generated cell in 0.00167602 seconds	Loaded cell in 0.001697 seconds
Generated cell in 0.00235301 seconds	Loaded cell in 0.00171804 seconds
Generated cell in 0.00137097 seconds	Loaded cell in 0.002105 seconds
Generated cell in 0.00138301 seconds	Loaded cell in 0.00173801 seconds
Generated cell in 0.00140399 seconds	Loaded cell in 0.00171405 seconds
Generated cell in 0.00137198 seconds	Loaded cell in 0.001692 seconds

Constructing in code is generally about 20% faster — although at 1 millisecond per construction in the simulator, it doesn't really matter.

Device results

The first 10 results running on my iPhone 3G look like this:

Generated in code	Loaded from NIB
Generated cell in 0.113011 seconds	Loaded cell in 0.131085 seconds
Generated cell in 0.114312 seconds	Loaded cell in 0.097244 seconds
Generated cell in 0.101614 seconds	Loaded cell in 0.08413 seconds
Generated cell in 0.105022 seconds	Loaded cell in 0.081331 seconds
Generated cell in 0.10087 seconds	Loaded cell in 0.093407 seconds
Generated cell in 0.105968 seconds	Loaded cell in 0.083472 seconds
Generated cell in 0.100045 seconds	Loaded cell in 0.091788 seconds
Generated cell in 0.105458 seconds	Loaded cell in 0.083763 seconds
Generated cell in 0.098836 seconds	Loaded cell in 0.08714 seconds
Generated cell in 0.102028 seconds	Loaded cell in 0.109811 seconds

The construction in code is about 15% faster on the first construction but by the third cell, loading from the NIB file is 17% faster.

Running some CPU sampling in Instruments, I was able to work out that adjustsFontSizeToFitWidth was the critical factor here: it appears that Interface Builder precalculates the correct size based on the placeholder string, whereas the constructed code is forced to do this at runtime, causing its performance to suffer.

Turning off adjustsFontSizeToFitWidth in both the generated code and the loaded code (replaced the label.adjustsFontSizeToFitWidth = YES with label.adjustsFontSizeToFitWidth = NO and switched Cell.xib to Cell2.xib), gave the following results:

Generated in code	Loaded from NIB
Generated cell in 0.085553 seconds	Loaded cell in 0.095012 seconds
Generated cell in 0.077257 seconds	Loaded cell in 0.087141 seconds
Generated cell in 0.084639 seconds	Loaded cell in 0.082693 seconds
Generated cell in 0.079142 seconds	Loaded cell in 0.098218 seconds
Generated cell in 0.078286 seconds	Loaded cell in 0.082136 seconds
Generated cell in 0.087895 seconds	Loaded cell in 0.087088 seconds
Generated cell in 0.0792 seconds	Loaded cell in 0.082335 seconds
Generated cell in 0.084037 seconds	Loaded cell in 0.082358 seconds
Generated cell in 0.076416 seconds	Loaded cell in 0.08714 seconds
Generated cell in 0.078426 seconds	Loaded cell in 0.084312 seconds

This now swings the performance advantage back to handwritten code by 7%.

Conclusion

You can download the sample project: NibOrNot.zip

Don't assume that NIB files are always slower than generating views in code — it is not always true. While in general, generating user interface views in code appears to be 5-10% faster than loading from a NIB, the reality is that this difference is small enough that it doesn't matter and there are certainly some views that load faster from a NIB than from code.

This doesn't mean that construction speed is unimportant on the iPhone; it clearly is. I was able to create a (slightly contrived) view that took nearly two seconds to load (unacceptably slow). However, saving 10% by moving from NIBs to creating views in code will never fix the problem (1.8 seconds is still too slow). In this case, flattening the view hierarchy (using a single custom view to draw what multiple subviews used to draw), or removing text fields entirely, is the best way to improve performance. This type of redesign can improve performance by a factor of 10 or more.

The conclusion to be drawn is that when choosing to use a NIB file or not, you should use whatever you're most comfortable with and whatever will keep your code maintenance costs low. Don't be concerned that one approach or the other will cause your UI performance to suffer.

StreamToMe 2.0 is out (and Cocoa With Love is 2 years old).

2010-02-26T00:35:00.001-08:00

Two different things turning two different kinds of "2". Snap.

Cocoa With Love is two years old today

I've been writing a feature article every week for two years now — haven't missed a single week yet (hope that doesn't jinx me).

To commemorate, I've put the complete list of downloadable code samples from my blog on the Projects With Love: Open Source Projects page.

StreamToMe 2.0 is out!

For those who don't know, StreamToMe is an iPhone application for streaming video and music from your Mac to your iPhone/iPod Touch. Plug your phone into your TV and you can use it to stream your Mac's music and video files to your TV. No prior conversion necessary — a huge range of codecs and formats (including AVI, WMV, MOV, MP4, FLV and more) will just play.

StreamToMe 2.0 adds:

Thumbnail previews for video files
Album artwork for music files (including while playing)
Artist and title metadata display
Subtitle rendering (including SRT and SSA files, MKV embedded SSA tracks and MOV text tracks)
Multiple audio tracks
Continuous and random play modes
Sort options including folder flattening (so you can view the full hierarchy of your iTunes collection as a single flat collection)
Preliminary support for EyeTV streams
Persistent playback — if you quit or are interrupted by a phone call during playback, you can continue from where you were.

And more!

StreamToMe is available to purchase from the iTunes App Store:

Download StreamToMe 2.0 from the AppStore now

Free upgrade for existing customers. Lucky them! Don't forget to update ServeToMe to enable some of the newer features.

Windows XP support for ServeToMe is coming soon (I'm hoping by the end of March).

Here's a few screenshots of the new version of StreamToMe in action:

Resolving a path containing a mixture of aliases and symlinks

2010-02-21T20:27:00.001-08:00

Resolving symlinks in a path is very easy in Cocoa (it can be done in a single statement) but aliases require more work. Additionally the commands for resolving symlinks and aliases are incompatible with each other — meaning that you can resolve a path containing symlinks or aliases but not a mixture of the two. In this post, I present a category on NSString that will allow you to resolve a path containing any combination of symlinks or aliases as simply as resolving symlinks alone.

Introduction

When Apple introduced alias files in System 7, they were the only way of referencing another file in the filesystem. Sure, other operating systems already had symlinks but there was little likelihood of the two needing to interact since System 7 had almost no interoperability with Unix filesystems (despite the existence of A/UX).

Alias files are a great way of referencing other files because they can continue to track their target if it moves. Aliases store both the path of their target and the inode plus volume identifier of their target. This means that they won't break if the file at their target path moves, unlike a symlink which will break if the target moves (since a symlink is just a path). In fact, symlinks will often break if the symlink file itself moves since symlinks are normally relative paths.

Aliases do have some annoying traits. In their current incarnation, they insist on storing the thumbnail and metadata of data of their target, resulting in a file which may be hundreds of kilobytes (or more) of entirely redundant data — especially annoying if you have thousands of aliases. Despite this, they are normally a good, general-purpose way of linking files in the filesystem.

As a "user-exposed" feature (unlike symlinks which are largely hidden from novice users) they are also common. It's unfortunate then that they're so annoying to deal with in Cocoa.

Resolving aliases

Resolving a symlink is easy:

NSString *resolvedPath = [path stringByResolvingSymlinksInPath];

Theoretically, you only need one command to resolve an alias:

OSErr err = FSResolveAliasFile(
    &fsRef, resolveAliasChains, &targetIsFolder, &wasAliased);

Unfortunately, the FSRef here is a campy 1990's throwback (the 90's are now two decades ago) and in Cocoa programming, you rarely have or want an FSRef for a file. This means that you need to convert your NSString to an FSRef and then convert the result back to an NSString when you're done.

Apple's Low Level File Management Topics include an approach for resolving an alias from an NSString path which demonstrates this procedure. While I use an implementation derived from this in my solution, Apple's original implementation suffers from the following problems:

The CFURLGetFSRef function used to convert a CFURL into an FSRef will fail if the path contains an alias at anywhere other than the last path component.
While CFURLGetFSRef will follow symlinks in the URL to create the FSRef, no part of this code will actually return a resolved symlink, so that part will require a separate step.
The function FSResolveAliasFile will present a user dialog if the alias points to a volume which is not mounted. While potentially desirable in a user application, this is undesirable in all other cases.

This final point is not too difficult — we'll replace FSResolveAliasFile with FSResolveAliasFileWithMountFlags which allows us to disable the user dialog using the flags. But the remaining two points will require a little more work to address.

As a further comment about usage of FSResolveAliasFileWithMountFlags: aliases that point to other aliases are exceedingly rare (if you try to create an alias to an alias in the Finder, the Finder will make the second alias point directly to the target) so I pass false for resolveAliasChains to optimize for the unchained case and handle the unusual case of chained aliases at a different level in the code.

Breaking it down into solvable components

We can resolve paths that contain any number of symlinks and we can resolve a path that contains an alias but we can't do both at once.

The solution is therefore straightforward:

break the path down into components
build the components together, iteratively resolving aliases or symlinks at each level
implement code for resolving the symlink or alias as efficiently as possible for the bottom level of this scenario

Each of these points will then be a different tier in a three level solution.

My solution will contain two requirements:

The initial path must be resolvable to an absolute path using -[NSString stringByStandardizingPath]
The path contained within a symlink file will not include any aliases or symlinks except as the final string component (no recursive parsing)

This second point is mostly a theoretical limitation since it is nearly impossible to generate a symlink with an alias or other symlink as a non-final path component (you'd have to create the symlink file manually).

Top level

The top level of the solution is simply an iteration over path components which then invokes the iterative link resolution.

// Break into components.
NSArray *pathComponents = [path pathComponents];

// First component ("/") needs no resolution; we only need to handle subsequent
// components.
NSString *resolvedPath = [pathComponents objectAtIndex:0];
pathComponents =
    [pathComponents subarrayWithRange:NSMakeRange(1, [pathComponents count] - 1)];

// Process all remaining components.
for (NSString *component in pathComponents)
{
    resolvedPath = [resolvedPath stringByAppendingPathComponent:component];
    resolvedPath = [resolvedPath stringByIterativelyResolvingSymlinkOrAlias];
    if (!resolvedPath)
    {
        return nil;
    }
}

I haven't shown the code which resolves the path to an absolute path or fails but the assumption that it begins with a "/" is valid.

Middle level

The middle level of the solution iterates over a path where only the final component could be a symlink or alias and resolves it until the result is neither an alias nor symlink.

For efficiency, this does two things in an unusual way:

I use lstat instead of -[NSFileManager attributesOfItemAtPath:error] since I only need the st_mode field, and NSFileManager invokes lstat internally anyway.
I use my own -[NSString stringByConditionallyResolvingSymlink] method instead of - [NSString stringByResolvingSymlinksInPath] since I know that only the final component requires resolution (I've already done the work for earlier components).

- (NSString *)stringByIterativelyResolvingSymlinkOrAlias
{
    NSString *path = self;
    NSString *aliasTarget = nil;
    struct stat fileInfo;
    
    // Use lstat to determine if the file is a directory or symlink
    if (lstat([[NSFileManager defaultManager]
        fileSystemRepresentationWithPath:path], &fileInfo) < 0)
    {
        return nil;
    }
    
    // While the file is a symlink or resolves as an alias, keep iterating.
    while (S_ISLNK(fileInfo.st_mode) ||
        (!S_ISDIR(fileInfo.st_mode) &&
            (aliasTarget = [path stringByConditionallyResolvingAlias]) != nil))
    {
        if (S_ISLNK(fileInfo.st_mode))
        {
            // Resolve the symlink component in the path
            NSString *symlinkPath = [path stringByConditionallyResolvingSymlink];
            if (!symlinkPath)
            {
                return nil;
            }
            path = symlinkPath;
        }
        else
        {
            // Or use the resolved alias result
            path = aliasTarget;
        }

        // Use lstat again to prepare for the next iteration
        if (lstat([[NSFileManager defaultManager]
            fileSystemRepresentationWithPath:path], &fileInfo) < 0)
        {
            path = nil;
            continue;
        }
    }
    
    return path;
}

The stringByConditionallyResolvingAlias method returns nil if the path exists but isn't an alias, allowing this function to double as both a test for whether the path is an alias as well as the resolution of that alias. I could use a similar approach to test and resolve symlinks (since I have also implemented a stringByConditionallyResolvingSymlink method) but I don't do this for aforementioned efficiency reasons: it would cause an extra fetch of the filesystem metadata which is the main bottleneck of the whole procedure.

Bottom level

The bottom level is then just the implementation of the stringByConditionallyResolvingAlias and stringByCondictionallyResolvingSymlink. The first is just a modification of Apple's code to address the issues I've already discussed — you can see the final product by downloading the code. The second method looks like this:

- (NSString *)stringByConditionallyResolvingSymlink
{
    // Get the path that the symlink points to
    NSString *symlinkPath =
        [[NSFileManager defaultManager]
            destinationOfSymbolicLinkAtPath:self
            error:NULL];
    if (!symlinkPath)
    {
        return nil;
    }
    if (![symlinkPath hasPrefix:@"/"])
    {
        // For relative path symlinks (common case), resolve the relative
        // components
        symlinkPath =
            [[self stringByDeletingLastPathComponent]
                stringByAppendingPathComponent:symlinkPath];
        symlinkPath = [symlinkPath stringByStandardizingPath];
    }
    return symlinkPath;
}

Hooray, I finally used NSFileManager in a post about files! Yes, once again it's probably just a wrapper around the C function readlink that I could invoke for myself but the fact that the NSFileManager method handles the nasty business of buffer allocation, sizing and string conversion is more than enough reason to forego the lower level function.

Conclusion

You can download NSString+SymLinksAndAliases.zip (3kb) which contains all the code discussed in this post (plus a few other related methods) as a category on NSString.

Usage of the category is as simple as importing the header and writing:

NSString *fullyResolvedPath = [somePath stringByResolvingSymlinksAndAliases];

The fullyResolvedPath will either contain the destination (as an absolute and fully resolved path) or it will be nil (if the path can't be fully resolved because it doesn't exist or can't be read for some reason).

I've tried to keep this code efficient by keeping the number of filesystem calls low. The code will certainly handle at least a few thousand alias resolutions per second on my computer but I haven't pushed it much harder than that.

Of course, if you're an iPhone programmer, all of this is a waste of time since the iPhone doesn't publicly expose FSRef (although CFURLGetFSRef exists to generate a pointer which is totally unusable). In fact, I'm not sure aliases are possible on the iPhone anyway.

The differences between Core Data and a Database

2010-02-16T00:32:00.001-08:00

The Core Data Programming Guide clearly states that Core Data is not a database but since both Core Data and a database are ways of providing searchable, persistent storage, exactly how and why they are different may not be clear. In this post, I'll look at the way Core Data works and the reasons why its features and capabilities are different to those of common SQL databases — even though an SQL database may be used as the backing store.

Introduction

Both Core Data and an SQL database provide a means of persistently storing structured data in a searchable store.

Since programmers are generally familiar with databases and since Core Data is actually backed by an SQLite database, it is understandable that Core Data is often treated and used as though it were a wrapper around SQLite.

It is important to realize that although you can use Core Data in this way (in fact, it works very well like this), that Core Data actually operates over a different domain to SQLite — meaning that it provides lots of services that SQLite doesn't but also that Core Data can't provide some of the services that SQLite can. Even for services that both technologies provide, there are different performance considerations.

Primary function of a database

The somewhat narrow description of database that I will use is: persistent and searchable storage for data in table, row, column format where the primary goal is to keep the data up-to-date on disk at all times, with a secondary goal of powerful, focussed, narrow fetching and updating capabilities.

There are lots of database implementations and many provide features far beyond this description but I'm really looking at the key components of a straightforward SQLite-style database implementation with which many programmers are familiar.

Despite many databases being called "relational" (which implies that they have a degree of support for object connectivity), SQLite and many other relational databases don't handle the mechanics of connecting objects; maintaining state (like a an object relation) between columns, rows or tables is left to the user of the database. In this sense, a database is "dumb" storage — rows have few behaviors beyond "read" and "write" and extending or customizing their behavior would involve extending the database system itself. Even when triggers are available, their programmatic capabilities are limited.

Primary function of Core Data

At its heart, Core Data is an object graph manager with lifecycle, searching and persistence features. In the case of Core Data, object graph management includes:

You can connect object A to object B and the connection at both the A and B ends is kept perpetually in sync.
If you change the connection at the A end, the B end will be updated and all changes trigger notifications (to which you can attach arbitrary code)
Deletion of objects at one end of a connection can trigger cascading deletion or nullify responses.
The other end of a connection can exist out of memory (faulted) unless the connection is actually followed at which time the connected object is loaded.

Unlike a typical database, Core Data can be used totally in-memory. While Core Data is often called a "object persistence" framework (since it is expected that you will use its persistence features), it is actually possible to use Core Data entirely in-memory without any form of persistence. Of course, once you have data, it is reasonable to want to keep that data, so persistence is treated as a major feature of the framework but it is important to know that persistence is not mandatory.

Also unlike a database, it is possible to use Core Data without any form of searching. If you allocate and connect all your objects, all you need to do is hold onto one of them and you can walk through everything without needing a fetch request. This search-less behavior is not because Core Data transparently performs a search: once data is loaded in memory, following a connection does not involve a search.

All Core Data objects are fully instantiated Objective-C objects that manage most of their own attributes, relationships and lifecycle. This also means that their properties and behaviors are implemented by methods, making them both observable and overrideable.

Databases and object graph management are not inherently exclusive

While not available by default in SQLite, the "foreign key" of MySQL, and other SQL:2003 compliant databases, can handle keeping identifiers in different tables in sync and even cascade deletion when requested. The programmatic customization abilities of overrideable objects is not available but the basics of graph management are there.

There are other object relational frameworks that work closer to Core Data's model but which try to behave as an atomic, transactional database. To update the object graph, these frameworks must:

load appropriate rows from a database
instantiate objects from these rows
make changes to the graph objects that are now in memory
commit the changes back to the database

To be properly atomic, these steps must all be performed as a single transaction (with no other reads or write to the affected rows during the transaction). While some systems might require this, it is far too slow for a general object graph system.

Core Data does not follow this model as Core Data aims to be a more general object management system — and that means that it needs far better performance and flexibility than this model would allow.

Operating in-memory versus an on-disk database

Without access to the source code, it's not entirely clear. We can only assume that the NSManagedObjectContext tracks instantiated objects in a heap or structured container of some form so that it can find them again.

This tracking structure may behave a bit like an in-memory database but it would only be for tracking the existence of instantiated objects — it is important to note that it would not itself store any data. Also note that the centralized NSManagedObjectContext and any structures it might maintain are not how you interact with instantiated NSManagedObjects — you interact with an NSManagedObject by sending messages to NSManagedObject pointers.

The reason that Core Data focuses on an in-memory representation is speed. For object graph changes that affect multiple objects, it is much faster if they are all in memory already, rather than needing to search for them again in the database.

For temporary objects (data that doesn't have to be saved to disk) Core Data can create, change and manipulate objects much faster than SQLite can since SQLite has to update indexes and update nodes in the B-tree, as well as simply allocating space and setting values. Core Data can allocate millions of objects in a few seconds, where SQLite might take a few minutes for the same number of allocations.

The tradeoff with an in-memory approach is that SQLite is still used as the backing store. Reading from disk and saving to disk involves all of SQLite's overheads plus the overhead of the Core Data to SQLite conversion process — so is invariably slower than SQLite alone.

Common database tasks that Core Data doesn't do

I've spoken about features that Core Data has that databases do not. It is important to consider some of the features that Core Data's approach lacks with respect to a database.

Core Data cannot operate on data without loading the data into memory

In SQL you can simply "DROP tableName" to delete whole tables or update every column of a table with commands like "UPDATE tableName SET key1 = value WHERE key2 = otherValue". These commands can efficiently update vast amounts of data because they only need to load small amounts of data into RAM at any given time.

Core Data doesn't work in this perpetually on-disk manner — it only works on objects in memory. Even if you only want to delete an object, it must be loaded and instantiated in RAM.

Of course, this is necessary because the object, and its potentially overridden behaviors must be loaded and invoked. There are also connections to be kept up to date with other objects.

However this constraint has implications: if you're trying to change huge numbers of objects (tens of thousands or more) you will need to consider keeping your memory footprint down. This can be done by periodically refaulting unchanged values (refreshObject:mergeChanges:) or avoiding the fetch of an object's data (setIncludesPropertyValues:NO on NSFetchRequest) or even saving the whole context and releasing all the objects you're holding.

Core Data does not handle data logic

There are a few data-related features that SQL contains, a good example being "unique" keys, that Core Data does not include.

There are a couple of technical reasons why this might be the case. Subclasses can override the getter and setter for an attribute to the point where it is unclear whether it is or is not unique. In fact, transient Core Data attributes need not even support isEqual:.

However, I suspect the distinction is actually that Core Data offers no real support for attribute behaviors at all. Core Data manages the "graph" (connections) but the data attributes are all the responsibility of the business logic in the rest of the program; convenient as it may be, it falls outside Core Data's conceptual domain.

Multi-threaded, multi-user scenarios

Core Data does not offer any amount of threading support. To be fair, SQLite is single threaded too but many other databases are multi-threaded and multi-user.

Core Data has been designed for single-user environments (running inside desktop and iPhone apps). Getting rid of threading and locking makes the framework much faster and simpler to work with in its standard usage scenarios.

However, there are still situations where you will want multiple threads reading your data. NSManagedObjects and their NSManagedObjectContext should be accessed from a single thread only. If you need another thread working on the same data, you need to save the file and reopen using a different NSManagedObjectContext in the other thread.

Summary

Database	Core Data
Primary function is storing and fetching data	Primary function is graph management (although reading and writing to disk is an important supporting feature)
Operates on data stored on disk (or minimally and incrementally loaded)	Operates on objects stored in memory (although they can be lazily loaded from disk)
Stores "dumb" data	Works with fully-fledged objects that self-manage a lot of their behavior and can be subclassed and customized for further behaviors
Can be transactional, thread-safe, multi-user	Non-transactional, single threaded, single user (unless you create an entire abstraction around Core Data which provides these things)
Can drop tables and edit data without loading into memory	Only operates in memory
Perpetually saved to disk (and often crash resilient)	Requires a save process
Can be slow to create millions of new rows	Can create millions of new objects in-memory very quickly (although saving these objects will be slow)
Offers data constraints like "unique" keys	Leaves data constraints to the business logic side of the program

Custom build rules, generated tables and faster floating point

2010-02-08T02:26:00.001-08:00

As fast as computers are, heavy use of floating point functions can still slow them down. One way around this, is to use a lookup table instead of calculating floating point values at runtime. But keeping a generated table up-to-date is annoying work. In this post, I'll show you how to create a lookup table automatically using a custom build rule, making an OpenGL animation 5 times faster in the process.

Introduction

In this post, I'm going to work with a modified version of Apple's default OpenGL ES 1.0 program. In this program, a colored square will spin in the center of the window:

Download the complete project for this post: Spinner.zip (25kb).

To artificially create a situation where this simple program is bound by CPU performance, I will calculate the location of the square thousands of times for every frame.

Initial code and performance

The initial code for updating the model matrix before drawing is:

static float transX = 3.14159265f * 0.5;
static float transY = 0.0f;
for (int i = 0; i < 2e5; i++)
{
    translateX = sinf(transX)/2.0f;
    translateY = sinf(transY)/2.0f;
    doNothingff(&translateX, &transX);
    doNothingff(&translateY, &transY);
}
transX += 0.075f;
transY += 0.075f;

glTranslatef((GLfloat)(translateX), (GLfloat)(translateY), 0.0f);

This is a very simple calculation: it translates out to the edge of the unit circle and progresses around the circle by 0.075 radians per frame.

The code loops 2e5 (i.e. 20,000) times and passes its variables by reference into a dummy function (to prevent the compiler optimizing the loop away).

On my iPhone 3G, this runs between 5 and 6 frames per second.

Faster with tables

The reason this code is slow, is the sinf() function — the iPhone simply isn't meant for heavy floating point arithmetic.

However, this code only uses 84 steps to get around the circle. We can precalculate all of those points, store them in a table and use the table instead.

static int tableIndexX = -1;
static int tableIndexY = 0;
if (tableIndexX == -1)
    tableIndexX = SinTableSize / 4;

for (int i = 0; i < 2e5; i++)
{
    translateX = SinTable[tableIndexX];
    translateY = SinTable[tableIndexY];
    doNothingif(&tableIndexX, &translateX);
    doNothingif(&tableIndexY, &translateY);
}
tableIndexX = (tableIndexX + 1) % SinTableSize;
tableIndexY = (tableIndexY + 1) % SinTableSize;

glTranslatef((GLfloat)(translateX), (GLfloat)(translateY), 0.0f);

This code is the same as the previous code except instead of calculating each point, it simply steps through an array of values.

The SinTable just looks like this:

const float SinTable[84] = 
{
    0.000000f,
    0.037365f,
    0.074521f,
    0.111260f,
    //... 80 more entries ...
};

With the change to a lookup table, the code now runs at 26-28 frames per second. A 5 times speed increase.

Using code to generate code with a build rule

If you've ever used lookup tables, you'll know that they can be annoying to maintain. If you want to change them, you need to regenerate them and then reintegrate them into your project.

With a custom build rule, the regeneration and reintegration can be done automatically.

The code that generates the SinTable looks like this:

enum
{
    ProcessName = 0,
    OutputFile,
    TableSteps,
    ArgumentCount
};

int main (int argc, const char * argv[])
{
    if (argc != ArgumentCount)
        return 1;
    
    FILE *outputFile = fopen(argv[OutputFile], "w");
    long tableSteps = strtol(argv[TableSteps], NULL, 10);
    
    fprintf(outputFile, "const float SinTable[%ld] = \n", tableSteps);
    fprintf(outputFile, "{\n");
    for (long i = 0; i < tableSteps; i++)
    {
        fprintf(outputFile, "    %ff,\n", 0.5f * sinf(i * 2.0f * 3.14159265f / tableSteps));
    }
    fprintf(outputFile, "\n};\n");
    fprintf(outputFile, "const long SinTableSize = %ld;", tableSteps);
    
    return 0;
}

I put it in a file named SinTable.gen.c then I added a custom build rule to the target (Project→Edit Active Target→Rules).

The custom build rule looks like this:

What this does is:

Takes any file that ends in .gen.c
Compiles it to a .gen file in the Derived files directory
Executes the .gen program to generate a gen.result.c file in the same directory
Tells Xcode that it produces the gen.result.c file and Xcode will then build it according to Xcode's standard C compilation rules, integrating it with the rest of the program.

Custom Build Rules versus Custom Build Phases

Many people are familiar with Custom Build Phases for running scripts during their builds. It is important to understand the differences between the two:

Custom Build Rule	Run Script Custom Build Phase
Is an arbitrary /bin/sh script	Is an arbitrary /bin/sh script
Runs once for input of a given type	Runs exactly once per build
Only runs when an input of the relevant type changes	Runs on either every build (no inputs/outputs specified) or when specifically nominated "input" files are newer than nominated "output" files.
Outputs can be automatically picked up by Xcode for further processing by other build rules	Xcode doesn't touch outputs — you must handle all processing yourself
Only visible in the Target's Settings window	Visible in the Group Tree by expanding the Target

Custom Build Rules are ideal for generating files that will be picked up by another build rule (for example, generating source code or .o files). Custom Build Phases are a better option for applying build numbers or handling the final built product.

Conclusion

Download the complete project for this post: Spinner.zip (25kb).

5 times faster, easy to implement and maintain.

Of course, lookup tables have a major limitation: they use memory. This table was only 84 entries long, so there's no real problem but if you need thousands of entries, you'll need to test to make sure you're actually gaining performance. Also, if the table is never in cache (because you're using huge amounts of memory between lookups), you're unlikely to save much time.

The point of this post though was to demonstrate build rules. This build rule keeps the lookup table up-to-date on every build and won't run unless the .gen.c file changes, so it won't recompile unnecessarily. The key strength of the build rule is that it will automatically run on all ".gen.c" files we happen to add to this target and the outputs are automatically picked up by Xcode and compiled and linked with the rest of the target.

These two points are the key advantages of Build Rules in Xcode: running on every file of a given type and integration into the build pipeline. If you only need your script to run once per build (instead of once per file) and you don't need Xcode to further handle the outputs, you can use Run Script Custom Build Phases instead.

Finding the cause of performance issues in your programs

2010-02-01T03:34:00.001-08:00

This post is a response to reader questions asking how, in my previous post on Replacing Core Data Key Paths, I knew that the biggest performance problem in my initial approach was the incremental reallocation of NSMutableSet. In this post, I'll look at basic time and memory profiling on the Mac and talk about the most common types of scenario to look for when you're trying to solve performance problems.

Introduction

In my previous post, Performance Tests: Replacing Core Data Key Paths, I presented a simple category to improve Core Data key path fetching by 25%-35% (actually the improvement was much greater at small set sizes but they rarely matter). The improvement worked by using property accessors to access the Core Data values instead of looking up the properties by string name.

However, the original "naïve" approach that I used to do this actually took more than twice as long as the original Core Data string key paths.

This week, I'll look at how I analyzed this code and how I worked out where the performance bottleneck was.

The code to analyze

The purpose of the code was to replace this:

NSSet *projectNames = [company valueForKeyPath:@"projects.name"];

with this:

NSSet *projectNames = [company.projects slowObjectValuesForProperty:@selector(name)];

But, as the "slow" in the method name reveals. The initial approach was slower — by approximately a factor of 2.

The implementation of the slowObjectValuesForProperty: method is really simple. Let's look at it:

- (NSSet *)slowObjectValuesForProperty:(SEL)propertySelector
{
    NSMutableSet *result = [NSMutableSet set];
    for (id object in self)
    {
        id value = [object performSelector:propertySelector];
        if (value)
        {
            [result addObject:value];
        }
    }
    return result;
}

The test harness that I'll be using will be the PropertyAccessors project from the Performance Tests: Replacing Core Data Key Paths post, with all tests except the "Key Path Accessor" and "slowObjectValuesForProperty: accessor" ifdef'd out.

Time profiler

The first approach you should use when your code isn't running as fast as desired is a basic time profile.

As preparation for this, you should make sure that the test will run for long enough to give useful test results. Time profiling works by suspending the program at regular intervals and reading the program's current position. This amounts to a random sampling over time. But these random samples won't be helpful unless there are enough in your time critical code. Increase your data size or put the code you're looking at in a loop and try to make it run for at least 2 seconds.

For this test, I set the NumCompanies and NumProjectsPerCompany to 100 (giving a total data size of 10,000 project names) and further set the NumTestIterations to 1000 (so this test will fetch 10 million names in total).

This gives the following test durations:

Key Path set iteration test took                4.13078 seconds.
Slow objectValuesForProperty: test took         8.83262 seconds.

By default, the Time Profiler will sample once every millisecond. If your tests cover a large amount of code, you'll need more samples — so either make your tests run longer or increase the sample frequency (Time Profiler can go as fast as 20 μs).

Build the project (but don't run it directly from Xcode). Then select the "Run→Run with Performance Tool→Time Profiler" menu. You can also use "Shark" for this but they both work in a similar way and the Time Profiler runs in Instruments which has a nicer, newer interface (although Shark can track a few lower level metrics that Instruments still lacks).

iPhone note: The Time Profiler is not available to iPhone projects. For iPhone projects, select the "CPU Sampler" in the "Run with Performance Tool" menu. The "CPU Sampler" is higher overhead and cannot sample as often or as rigorously but will normally provide similar information.

The PropertyAccessors test will self-run, so you can just watch it go. For other projects where some interactivity may be required, you'll need to interact with the program until it runs the code you want to examine. If your test has a short duration or a large amount of code, you may need to click the "i" next to the "Time Profiler" Instruments icon at the top to change the sample rate to get good coverage for your program (you'll need to rerun the test if you make this change).

Your window should look like this. If it doesn't, make sure the "Detail" view is visible (you won't need the "Extended Detail" view). Also make sure the "Call Tree" view is selected in the "Detail" view (it's the icon at the bottom of the window that looks like three horizontal lines stacked slightly askew).

Once the program finishes, uncheck the "Invert call tree" checkbox in the left column then expand the "Main Thread → start → main" elements and we'll see the most expensive steps in the main() function (which is where all the tests are run in this project).

The top item in the main() function is the fetchObjectSetForRequest: method but we're not looking at that here (it's just Core Data loading and prefaulting the entire database).

Instead, we want to know why the second item, slowObjectValuesForProperty:, takes 2.23 times longer than the third item, valueForKeyPath:.

Expanding the tree from the slowObjectValuesForProperty: method twice, we see CFBasicHashAddValue() occupies almost all of this method's time.

If we expand the valueForKeyPath: call tree 7 times, we can see the same CFBasicHashAddValue() is used to create the set here but for some reason, this function only takes 1402 milliseconds here, compared to 5996 milliseconds for the slowObjectValuesForProperty: method.

The same function, acting on the same data. But one takes 4 times longer than the other. What is the explanation?

There are two possible answers: either the slow case is suffering from poor memory caching performance, or it is acting repeatedly and is slow due to repetition.

Object allocations

Shark can measure event counts (like cache misses and memory bandwidth) if you actually think that's the cause of a problem but it's unlikely to be the problem here. In most situations where the Time Profile isn't clear cut, the best thing to try here is a object allocation analysis.

As with the Time Profile, we run the Object Allocations performance tool from "Run→Run with Performance Tool→Object Allocations" menu in Xcode.

Again, switch to the "Call Tree" view and make sure "Invert Call Tree" and "Separate by Category" are off.

Additionally, right-click (or control click) in the table header of the "Detail" view and make certain that "Count" and "Bytes" columns are both enabled.

If you navigate into "Main Thread → start → main →slowObjectValuesForProperty:", then follow the biggest allocation 4 times and you'll see that __CFBasicHashRehash is responsible for allocating almost all of this method's memory.

Similarly navigating into the valueForKeyPath: of the other test, reveals the same method 7 levels in allocates a majority of this method's memory.

However, there are three big differences between the memory performances of the __CFBasicHashRehash in each case:

The slowObjectValuesForProperty: version performs 800,000 allocations whereas the valueForKeyPath: version performs exactly 100,000 (equal to the number of tests).
The slowObjectValuesForProperty: version allocates 210.57MB whereas the valueForKeyPath: version allocates just 97.66MB.
The slowObjectValuesForProperty: version is found inside CFSetAddValue where the valueForKeyPath: version is found inside CFSetCreate.

From the first point, it would appear that the presumption that the slow version is slow because it unnecessarily repeats itself is looking accurate — it is repeatedly reallocating.

The second point also suggests that the slow method is wasting extra memory (which is probably causing mild performance penalities). On low memory systems, this would be even worse.

The third point suggests why the first two might be the case: the slow method needs to reallocate as it adds more data.

Understand what the code you're invoking does

All this helps to identify where your program is spending its time. From here, you could probably work out that allocating the NSMutableSet once, instead of repeatedly as you go, is a good idea.

Of course, you need to confirm this by applying your changes and testing. Changing this code to allocate once instead of repeatedly as it goes is easy — it takes a matter of seconds. You do need to be wary though about spending too long optimizing code on a whim. The more involved the code change, the more confident you should be that you're actually fixing a problem and not inspecting irrelevant code or making unhelpful changes.

This is where it helps to really understand the code you're playing with.

For example: the reason why moving to a single allocation with the NSMutableSet above is helpful, is not actually directly because of the allocation itself — since the biggest block of time inside slowObjectValuesForProperty: that we're trying to optimize is spent in __CFStringEqual and memcmp when you drill all the way down; it is not spent in malloc itself.

Instead, I know that whenever NSMutableSet resizes, it needs to rehash every single object back into the newly resized hash table. It is this rehashing that is hammering the __CFStringEqual and memcmp functions (since they are the functions used to hash and detect collisions in the hash table). Yes, reducing reallocations makes it faster but the biggest reason for this improvement is the nature of hashed storage: because reducing reallocations reduces the need to rehash.

As I reported in the original post, fixing this allocation so that it happens just once will speed this code up by 2.6 times but it is important to understand that the need to rehash is why this change helped — other reallocation situations may not gain as much as we have here.

Finding the best candidates for speed improvements

Generally though, allocations and reallocations are always a prime place to look. Large allocations are expensive to move around in RAM, millions of small, irregular allocations can fragment memory and every allocation normally needs to be initialized, incurring some kind of expense. Even with NSArray, which doesn't need to rehash when it reallocates, there is still a copy of the elements from the old array to the new one. The performance gain will not be as great but it is still a place to squeeze extra performance.

When optimizing, the first things to look for are:

Memory allocations. They're easy to find and easy to tweak. They don't always give the best performance improvements but they're a good first point to examine.
Iteration over large arrays to find elements. If you need to search large arrays often, you should be storing in a dictionary or other constant time access structure. Depending on the size of the array, this can be a near 100% speed improvement. i.e. never, ever search anything bigger than a trivial array.
Nested loops over medium to large data sets. Easy to find. Eliminate the nesting if you can. Although they can be hard to eliminate since you need to rethink how you access your data but you can often do something to reduce their impact. If you have 1 loop inside another, always put the smallest loop (in terms of number of elements) inside the bigger one if you can, since memory scales better to doing small packets of work huge numbers of times.
Anything non-polynomial on more than trivial data sets. Non-polynomial actions are the slowest, worst things you can do. They are occasionally required but if at all possible, think up another design. What's non-polynomial? Anything where the number of packets of work involved in processing a collection grows greater than polynomially with respect to the size of the collection (i.e. if the packets of work are "y" and the number of objects in the collection is "x", then non-polynomial means the number of packets of work exceed y=x^a for large values of x, where a is any constant). Exponential growth (i.e. y=a^x) or factorial (i.e. y=x!) are the most common kinds of non-polynomial growth. If all this is confusing, then at least know the common case: trying to find an ordering or arrangement for a set of objects by exhaustively testing every combination is non-polynomial.

You may be tempted to think that pervasive multi-threading, OpenCL, SSE vectorization or assembly optimizations are the best way to solve performance issues, since they are all "high performance" technologies and the fastest programs all use them in some combination. However, these technologies are much harder to implement than simple design improvements so they should always be something you consider once you're sure that the design can't be further improved.

Conclusion

The first rule with optimization is that you should always optimize based on evidence.

Don't begin to optimize if you can't find a bottleneck or create one with data. Optimizing without actual evidence of a bottleneck (just suspicion that there might be one in future) is called "Premature Optimization" and is normally considered a waste of time.

However, even once you know where the bottleneck is, you need to know what is causing it. If the code is small, you can just play with it to see what happens but generally you need to inspect closely. It is surprisingly easy to make the wrong guesses about what is causing performance issues and waste time changing code for no gain.

I hope I've shown you how to gather the information you need to understand simple performance problems and the types of clues you'll need to narrow down the locations in your code that can be improved.

5 key-value coding approaches in Cocoa

2010-01-25T20:51:00.001-08:00

Key-value coding (KVC) is a way of decoupling a generic action from the specific properties it may need to act upon. It is most commonly associated with the NSKeyValueCoding protocol but there are a number of other ways to achieve the same effect. In this post, I look at why key-value coding is important and show you 5 different ways — each with their own particular advantages — to implement this pattern.

Introduction

The NSKeyValueCoding protocol has been in Cocoa since Mac OS X 10.0 but it first made a real mark in Mac OS X 10.3 when user-interface bindings demonstrated their potential — allowing user-interface controls to connect to properties on objects by configuring the data, not changing the code.

While the core concepts in key-value coding exist (or can be implemented) in most programming frameworks, key-value coding is both prevalent and pervasive throughout Cocoa in a way that is uncommon, certainly among other compiled application frameworks.

Despite its prevalence, you can avoid key-value coding if you choose. However, Apple introduced it for a reason — it is a simple design pattern that can be highly beneficial to your code. To that end, I'm going to spend this post talking about what key-value coding is, how it can improve your code and different approaches you can use to achieve the effect.

What is key-value coding?

The idea behind key-value coding is pretty simple: instead of directly getting and setting specific properties on an object, key-value coding involves passing in a "key" (usually a string) and getting or setting the property associated with that key.

This may sound a lot like NSDictionary

For example:

// Set a property directly...
someObject.someProperty = someValue;

// ...or set the same property using key-value coding
[someObject setValue:someValue forKey:@"someProperty"];

Why would you want to do this? The answer is that it decouples the action of setting a value for a property from the specific property involved.

Imagine a table for editing names and addresses:

Without key-value coding, the NSTableViewDataSource method to handle an edit for one of the rows might look like this:

- (void)tableView:(NSTableView *)aTableView
    setObjectValue:(NSString *)anObject
    forTableColumn:(NSTableColumn *)aTableColumn
    row:(int)rowIndex
{
    if ([[aTableColumn identifier] isEqual:@"name"])
    {
        [[records objectAtIndex:rowIndex] setName:anObject];
    }
    else if ([[aTableColumn identifier] isEqual:@"address"])
    {
        [[records objectAtIndex:rowIndex] setAddress:anObject];
    }
}

With key-value coding, the method becomes:

- (void)tableView:(NSTableView *)aTableView
    setObjectValue:(NSString *)anObject
    forTableColumn:(NSTableColumn *)aTableColumn
    row:(int)rowIndex
{
    [[records objectAtIndex:rowIndex] setValue:anObject forKey:[aTableColumn identifier]];
}

I spoke about bindings before: this approach isn't using user-interface bindings (that would require no code at all). This is really showing a simplified way that bindings might be implemented.

This key-value coding approach is better because it doesn't have to handle the edit of each property as a separate condition. This is the essence of key-value coding.

And key-value coding remains just as efficient as the data set increases in size. A table with 1,000 columns would require the same amount of code to edit.

KVC approach 1: NSKeyValueCoding protocol

All the key-value coding that I've show so far uses the NSKeyValueCoding protocol. Actually, I call it a protocol but it is actually an "informal protocol" (a category on NSObject).

This category implements the setValue:forKey: and valueForKey: methods that you can use for setting and getting values by NSString keys.

Advantages

Finds getter and setter methods automatically and will even get or set ivars directly if a getter or setter can't be found. This means that most properties automatically support NSKeyValueCoding. Learn more about the search paths in my Key Value Information post.
Includes key paths (for traversing multiple properties).
Integrates with NSKeyValueObserving for implementing the Observer design pattern.
Offers fallbacks and ways of dealing with undefined keys.

Disadvantages

The extended search path makes this one of the slowest key-value coding approaches (see my earlier performance-related post on Replacing Core Data Key Paths).
Requires either a method or ivar on the class matching the property name that can be found by NSKeyValueCoding.
Only supports NSStrings as property keys.

KVC approach 2: Manual subsets of NSKeyValueCoding behavior

The NSKeyValueCoding protocol looks up methods by selector names and looks up ivars by name.

This is work that you can do yourself.

// Manual KVC setter method implementation
NSString *setterString = [@"set" stringByAppendingString:[someKeyString capitalizedString]];
[someObject performSelector:NSSelectorFromString(setterString) withObject:someValue];

// Manual KVC ivar setter
object_setInstanceVariable(someObject, someKeyString, someValue);

Why would you do this instead of using the NSKeyValueCoding approach? You would only use this in situations where you want to avoid methods or ivars that would ordinarily be found by NSKeyValueCoding. This approach allows you to define your own lookup path.

Advantages

More control over the lookup path than with NSKeyValueCoding.
Potentially faster than NSKeyValueCoding.
Will work for classes that don't inherit from NSObject and hence don't have NSKeyValueCoding implementations.
Manual method implementations can get and set non-object values.

Disadvantages

Less flexible than NSKeyValueCoding.
In most cases, it is more work than using NSKeyValueCoding.

KVC approach 3: Associated objects

The Objective-C 2.0 runtime (used on the iPhone and 64-bit Mac OS X apps) allows you to set any object to be associated with any other object. This allows any object in the runtime to have an arbitrary set of extra properties set by key, without support from ivars or methods on the object itself.

objc_setAssociatedObject(someObject, someKey, someValue, OBJC_ASSOCIATION_RETAIN_NONATOMIC);

The main reason why you would use this approach is that you want to set properties on an object from the outside — i.e. without the object supporting, being involved with or even knowing about the property access. Properties can be set on an object by other parts of the program for their own purposes.

Advantages

No support from the object (methods or ivars) required.
Key can be any pointer (so can the object if OBJC_ASSOCIATION_ASSIGN is used).
Potentially the fastest KVC approach.

Disadvantages

Key is a pointer, not an object, so if an object is used, it must be a pointer-unique object (i.e. won't work if you try to get and set with different allocations of the same string value).
Does not affect ivars or methods on the object. Generally this means if you want the object itself to know about the change, you must use a different approach.

KVC approach 4: selectors as keys

Key-value coding is primarily about looking up a property for a key and then acting upon the property found during lookup.

Objective-C has a lookup at its very core — the method lookup. The keys for this lookup are selectors.

objc_msgSend(someObject, someSetterSelector, someValue);

This approach is similar to manually implementing the method part of NSKeyValueCoding but rather than forming a selector string from the key and then looking up the selector string, this approach opts to use the selector as the key.

The disadvantage this approach has is that separate selectors are needed for getting and setting.

Advantages

Fastest approach that goes through methods (which is good since methods are overrideable and hence more subclass friendly).
Can get and set non-object data (although objc_msgSend_fpret and objc_msgSend_stret need to be used to get float, double and struct properties).

Disadvantages

Different keys required for getting and setting.
Selectors are not objects and are therefore can't be stored directly in Objective-C arrays and dictionaries (must use CoreFoundation or NSValue wrappers).

KVC approach 5: do it yourself

The final approach to key-value coding is to handle the implementation yourself. This is something you would do if you needed maximum flexibility (for handling unusual keys/values) or wanted to expose different key-value sets from a single object.

The easiest way to do this is to expose a getter and a setter method and simply get or set the values on a dictionary contained by the object.

- (void)setCollectionValue:(id)value forKey:(NSString *)key
{
    [collectionDictionary setObject:value forKey:key];
}

- (id)getCollectionValueForKey:(NSString *)key
{
    return [collectionDictionary objectForKey:key];
}

To handle the internal storage of the values, you could use any of the key-value storage structures in Cocoa:

NSMutableDictionary
NSMapTable
CFMutableDictionaryRef
associated objects on self or other objects (see above)

or your own storage solution.

Advantages

A single object can exposes multiple, separate collections.
Can get and set any data type supported by the underlying collection.
The most flexible approach for fallbacks and handling special cases.

Disadvantages

Must be implemented by the target class (will not work for arbitrary objects).
Doesn't interoperate with NSKeyValueObserving or any of the other NSKeyValueCoding concepts.

Conclusion

Using key-value coding is not mandatory — it is certainly possible to implement whole projects without it. However, it is one of the best code patterns for reducing repetitious code and making classes more reusable by decoupling actions from properties and data.

As you can see, there are a number of different kinds of key-value coding you can use in your program. NSKeyValueCoding is probably the most flexible, reusable and best supported throughout Cocoa, so unless you need one of the advantages of the other approaches or you want to keep your solution to a problem narrow, it is probably the best approach to use.

What is a meta-class in Objective-C?

2010-01-17T03:49:00.001-08:00

In this post, I look at one of the stranger concepts in Objective-C — the meta-class. Every class in Objective-C has its own associated meta-class but since you rarely ever use a meta-class directly, they can remain enigmatic. I'll start by looking at how to create a class at runtime. By examining the "class pair" that this creates, I'll explain what the meta-class is and also cover the more general topic of what it means for data to be an object or a class in Objective-C.

Creating a class at runtime

The following code creates a new subclass of NSError at runtime and adds one method to it:

Class newClass =
    objc_allocateClassPair([NSError class], "RuntimeErrorSubclass", 0);
class_addMethod(newClass, @selector(report), (IMP)ReportFunction, "v@:");
objc_registerClassPair(newClass);

The method added uses the function named ReportFunction as its implementation, which is defined as follows:

void ReportFunction(id self, SEL _cmd)
{
    NSLog(@"This object is %p.", self);
    NSLog(@"Class is %@, and super is %@.", [self class], [self superclass]);
    
    Class currentClass = [self class];
    for (int i = 1; i < 5; i++)
    {
        NSLog(@"Following the isa pointer %d times gives %p", i, currentClass);
        currentClass = object_getClass(currentClass);
    }

    NSLog(@"NSObject's class is %p", [NSObject class]);
    NSLog(@"NSObject's meta class is %p", object_getClass([NSObject class]));
}

On the surface, this is all pretty simple. Creating a class at runtime is just three easy steps:

Allocate storage for the "class pair" (using objc_allocateClassPair).
Add methods and ivars to the class as needed (I've added one method using class_addMethod).
Register the class so that it can be used (using objc_registerClassPair).

However, the immediate question is: what is a "class pair"? The function objc_allocateClassPair only returns one value: the class. Where is the other half of the pair?

I'm sure you've guessed that the other half of the pair is the meta-class (it's the title of this post) but to explain what that is and why you need it, I'm going to give some background on objects and classes in Objective-C.

What is needed for a data structure to be an object?

Every object has a class. This is a fundamental object-oriented concept but in Objective-C, it is also a fundamental part of the data. Any data structure which has a pointer to a class in the right location can be treated as an object.

In Objective-C, an object's class is determined by its isa pointer. The isa pointer points to the object's Class.

In fact, the basic definition of an object in Objective-C looks like this:

typedef struct objc_object {
    Class isa;
} *id;

What this says is: any structure which starts with a pointer to a Class structure can be treated as an objc_object.

The most important feature of objects in Objective-C is that you can send messages to them:

[@"stringValue"
    writeToFile:@"/file.txt" atomically:YES encoding:NSUTF8StringEncoding error:NULL];

This works because when you send a message to an Objective-C object (like the NSCFString here), the runtime follows object's isa pointer to get to the object's Class (the NSCFString class in this case). The Class then contains a list of the Methods which apply to all objects of that Class and a pointer to the superclass to look up inherited methods. The runtime looks through the list of Methods on the Class and superclasses to find one that matches the message selector (in the above case, writeToFile:atomically:encoding:error on NSString). The runtime then invokes the function (IMP) for that method.

The important point is that the Class defines the messages that you can send to an object.

What is a meta-class?

Now, as you probably already know, a Class in Objective-C is also an object. This means that you can send messages to a Class.

NSStringEncoding defaultStringEncoding = [NSString defaultStringEncoding];

In this case, defaultStringEncoding is sent to the NSString class.

This works because every Class in Objective-C is an object itself. This means that the Class structure must start with an isa pointer so that it is binary compatible with the objc_object structure I showed above and the next field in the structure must be a pointer to the superclass (or nil for base classes).

As I showed last week, there are a couple different ways that a Class can be defined, depending on the version of the runtime you are running, but yes, they all start with an isa field followed by a superclass field.

typedef struct objc_class *Class;
struct objc_class {
    Class isa;
    Class super_class;
    /* followed by runtime specific details... */
};

However, in order to let us invoke a method on a Class, the isa pointer of the Class must itself point to a Class structure and that Class structure must contain the list of Methods that we can invoke on the Class.

This leads to the definition of a meta-class: the meta-class is the class for a Class object.

Simply put:

When you send a message to an object, that message is looked up in the method list on the object's class.
When you send a message to a class, that message is looked up in the method list on the class' meta-class.

The meta-class is essential because it stores the class methods for a Class. There must be a unique meta-class for every Class because every Class has a potentially unique list of class methods.

What is the class of the meta-class?

The meta-class, like the Class before it, is also an object. This means that you can invoke methods on it too. Naturally, this means that it must also have a class.

All meta-classes use the base class' meta-class (the meta-class of the top Class in their inheritance hierarchy) as their class. This means that for all classes that descend from NSObject (most classes), the meta-class has the NSObject meta-class as its class.

Following the rule that all meta-classes use the base class' meta-class as their class, any base meta-classes will be its own class (their isa pointer points to themselves). This means that the isa pointer on the NSObject meta-class points to itself (it is an instance of itself).

Inheritance for classes and meta-classes

In the same way that the Class points to the superclass with its super_class pointer, the meta-class points to the meta-class of the Class' super_class using its own super_class pointer.

As a further quirk, the base class' meta-class sets its super_class to the base class itself.

The result of this inheritance hierarchy is that all instances, classes and meta-classes in the hierarchy inherit from the hierarchy's base class.

For all instances, classes and meta-classes in the NSObject hierarchy, this means that all NSObject instance methods are valid. For the classes and meta-classes, all NSObject class methods are also valid.

All this is pretty confusing in text. Greg Parker has put together an excellent diagram of instances, classes, meta-classes and their super classes and how they all fit together.

Experimental confirmation of this

To confirm all of this, let's look at the output of the ReportFunction I gave at the start of this post. The purpose of this function is to follow the isa pointers and log what it finds.

To run the ReportFunction, we need to create an instance of the dynamically created class and invoke the report method on it.

id instanceOfNewClass =
    [[newClass alloc] initWithDomain:@"someDomain" code:0 userInfo:nil];
[instanceOfNewClass performSelector:@selector(report)];
[instanceOfNewClass release];

Since there is no declaration of the report method, I invoke it using performSelector: so the compiler doesn't give a warning.

The ReportFunction will now traverse through the isa pointers and tell us what objects are used as the class, meta-class and class of the meta-class.

Getting the class of an object: the ReportFunction uses object_getClass to follow the isa pointers because the isa pointer is a protected member of the class (you can't directly access other object's isa pointers). The ReportFunction does not use the class method to do this because invoking the class method on a Class object does not return the meta-class, it instead returns the Class again (so [NSString class] will return the NSString class instead of the NSString meta-class).

This is the output (minus NSLog prefixes) when the program runs:

This object is 0x10010c810.
Class is RuntimeErrorSubclass, and super is NSError.
Following the isa pointer 1 times gives 0x10010c600
Following the isa pointer 2 times gives 0x10010c630
Following the isa pointer 3 times gives 0x7fff71038480
Following the isa pointer 4 times gives 0x7fff71038480
NSObject's class is 0x7fff710384a8
NSObject's meta class is 0x7fff71038480

Looking at the addresses reached by following the isa value repeatedly:

the object is address 0x10010c810.
the class is address 0x10010c600.
the meta-class is address 0x10010c630.
the meta-class's class (i.e. the NSObject meta-class) is address 0x7fff71038480.
the NSObject meta-class' class is itself.

The value of the addresses is not really important except that it shows the progress from class to meta-class to NSObject meta-class as discussed.

Conclusion

The meta-class is the class for a Class object. Every Class has its own unique meta-class (since every Class can have its own unique list of methods). This means that all Class objects are not themselves all of the same class.

The meta-class will always ensure that the Class object has all the instance and class methods of the base class in the hierarchy, plus all of the class methods in-between. For classes descended from NSObject, this means that all the NSObject instance and protocol methods are defined for all Class (and meta-class) objects.

All meta-classes themselves use the base class' meta-class (NSObject meta-class for NSObject hierarchy classes) as their class, including the base level meta-class which is the only self-defining class in the runtime.

Getting the subclasses of an Objective-C class

2010-01-11T19:35:00.001-08:00

Getting the full list of subclasses for a class is a fairly simple task but it requires some uncommon runtime functions which can make the process more difficult. In this post, I look at how a Class is defined in Objective-C and two completely different ways of working out the subclasses.

Introduction

Given the high level of reflection and introspection in the Objective-C runtime, you might expect that you would simply find a class_getSubclasses(Class parentClass) in the Objective-C Runtime API but no such function exists.

There are a few possible reasons why this function might have been omitted — dynamic class creation and loading, threading and locking concerns, historical omissions in the class_t structure, premature optimization considerations or even an attempt to deliberately guide programmers away from certain designs — but the result is that you must work out the subclasses for yourself.

Note: fetching the subclasses of a class is an unusual thing to do and is usually done as an after-the-fact change to an API you don't control or as a debug-only introspection or hack. Generally, designs where subclasses explicitly register themselves work better than trying to find subclasses at runtime. For example, in my Simple, Extensible HTTP Server, every HTTPResponseHandler must include:

+ (void)load
{
    [HTTPResponseHandler registerHandler:self];
}

which allows subclasses of HTTPResponseHandler that "opt-in" to be discovered by the parent when it is looking for a handler to handle a request.

Fetching subclasses is then used in situations where you can't include a load method like this or you can justify not wanting to do this (e.g. debug-only verification code which checks that all HTTPResponseHandlers you've written actually do register themselves).

Filter the list of all classes

The traditional definition of a class in Objective-C looks like this:

struct objc_class {
    Class isa;
    Class super_class;
    const char *name;
    long version;
    long info;
    long instance_size;
    struct objc_ivar_list *ivars;
    struct objc_method_list **methodLists;
    struct objc_cache *cache;
    struct objc_protocol_list *protocols;
};

Classes contain pointers to their superclass but contain no pointer to subclasses.

Since there is no specific function to access the subclasses, the only approach using public APIs is to get the list of all classes in the runtime and test each one to see if it is a subclass of the class in question.

If this sounds like a heavy-handed approach, you're probably right. In Mac OS X 10.6.2, there are 527 classes in Foundation alone and 1966 in the Cocoa framework. This doesn't include all the classes your project will add, plus classes in other frameworks. Of course, interrogating all of these only takes a millisecond or two but it's still not something you should do in a tight loop — if you need to repeatedly use the list of subclasses for a class, you'll want to cache it somewhere.

Fetching all the classes in the runtime is pretty simple:

int numClasses = objc_getClassList(NULL, 0);
Class *classes = NULL;

classes = malloc(sizeof(Class) * numClasses);
numClasses = objc_getClassList(classes, numClasses);

// do something with classes

free(classes);

The question is then: how do we determine which classes are actually subclasses of some parent class?

The intuitive approach would be to use the isSubclassOfClass: method:

NSMutableArray *result = [NSMutableArray array];
for (NSInteger i = 0; i < numClasses; i++)
{
    if ([classes[i] isSubclassOfClass:parentClass])
    {
        [result addObject:classes[i]];
    }
}

Unfortunately, we can't do this because when considering all classes in the runtime, the method isSubclassOfClass: may not be present on all of them (since isSubclassOfClass: is an NSObject method).

The problem here is that many of the methods that are commonly considered to be implemented by all classes, are actually implemented by NSObject or in an implementation of the NSObject protocol. Some classes, like _NSZombie_ or NSProxy don't derive from NSObject and even if they do implement the NSObject protocol, may do so in unpredictable ways (_NSZombie_ throws an exception for any method and NSProxy forwards many of these methods to its target instead of responding for itself).

So instead of invoking any methods on arbitrary classes we must use the runtime functions. We use class_getSuperclass() to find out the class' superclass and compare this to the parentClass. This gives the complete solution:

NSArray *ClassGetSubclasses(Class parentClass)
{
    int numClasses = objc_getClassList(NULL, 0);
    Class *classes = NULL;

    classes = malloc(sizeof(Class) * numClasses);
    numClasses = objc_getClassList(classes, numClasses);
    
    NSMutableArray *result = [NSMutableArray array];
    for (NSInteger i = 0; i < numClasses; i++)
    {
        Class superClass = classes[i];
        do
        {
            superClass = class_getSuperclass(superClass);
        } while(superClass && superClass != parentClass);
        
        if (superClass == nil)
        {
            continue;
        }
        
        [result addObject:classes[i]];
    }

    free(classes);
    
    return result;
}

The fast and dirty hack approach

The function I just gave is the correct approach to use in a program. But I wouldn't feel like I'd made an interesting post if I didn't also show a completely different, totally unsafe approach too.

This approach will require the Objective-C Runtime 2.0 (that's the one used in Mac OS X 64-bit and on the iPhone). In the new version of the runtime, a class actually contains a direct link to its subclasses.

From objc-runtime-new.h in Apple's opensource repository, a class is declared as follows:

typedef struct class_t {
    struct class_t *isa;
    struct class_t *superclass;
    Cache cache;
    IMP *vtable;
    class_rw_t *data;
} class_t;

with the class_rw_t struct definition:

typedef struct class_rw_t {
    uint32_t flags;
    uint32_t version;

    const class_ro_t *ro;
    
    struct method_list_t **methods;
    struct chained_property_list *properties;
    struct protocol_list_t ** protocols;

    struct class_t *firstSubclass;
    struct class_t *nextSiblingClass;
} class_rw_t;

This means that we can traverse along the firstSubclass and nextSiblingClass members to reach all of the subclasses of a parent class without needing to read every class in the runtime.

A depth-first recursive traversal then gives the full list of subclasses for a class:

typedef void *Cache;
#import "objc-runtime-new.h"

void AddSubclassesToArray(Class parentClass, NSMutableArray *subclasses)
{
    struct class_t *internalRep = (struct class_t *)parentClass;
    
    // Traverse depth first
    Class subclass = (Class)internalRep->data->firstSubclass;
    while (subclass)
    {
        [subclasses addObject:subclass];
        AddSubclassesToArray(subclass, subclasses);
    
        // Then traverse breadth-wise
        struct class_t *subclassInternalRep = (struct class_t *)subclass;
        subclass = (Class)subclassInternalRep->data->nextSiblingClass;
    }
}

However, while highly efficient compared to traversing the whole list of classes, this approach cannot be safely used. According to objc-runtime-new.m, all access to the data member of a class_t must be protected by the runtimeLock — which is inaccessible outside the runtime library itself.

Since the lock is inaccessible, it means that this approach cannot be made safe, since any thread (including threads automatically started by Cocoa) could cause you to crash.

It was a fun experiment and I hope that Apple include a function to do this safely in the future.

Conclusion

The runtime provides no simple method to access the subclasses of a class — even in the newer version of the runtime where this data is actually stored in the class' data structure.

Filtering out classes from the list of all classes presents some interesting problems due to the classes in the runtime which don't derive from NSObject. Ultimately though, once you're aware of the limitations of using the full class list, getting subclasses is fairly simple.

Even though it isn't data you normally need, it would be nice if Apple had decided to offer access to the subclass data in the new version of the runtime. It is more efficient and allows the list to be generated in sorted order if required.

Quality control in application development without unit testing

2010-01-05T17:07:00.001-08:00

In my last two posts, I've shown a Mac app with full unit tests and an iPhone app with full unit tests. The reality though is that I do not write or test code this way. In this post, I look at why so few applications are actually developed using unit tests. I'll also look at the alternate approaches — both manual and automated — that are normally used to maintain high quality and low bug rates in application development.

Introduction

I have many friends who love unit tests. They never write code without writing the unit tests first. And they love it; the thought of writing code without unit tests seems foolish and scary to them. Test-first approaches ensure that they never write anything that isn't specified and unit tested.

This post is not to dissuade these people from unit tests. If you already know that you know and love unit tests, then stick with them.

But even unit testing advocates should remember that unit tests are about code-level specification and working within certain types of development methodology — they do not attempt to catch all bugs.

This post is primarily for people who have heard of unit tests and are wondering if they are an efficient way to maintain product quality and lower bug rates.

The short answer is: no. If you simply want to lower bug counts, the best and most efficient approach is through system tests.

Difficulties of unit testing for application development

Depending on your development methodology, unit tests can serve a number of different functions. But if used purely to detect bugs then they are a very high cost approach for low return.

Unit tests don't test the overall program, only isolated units. This creates many holes (integration, timing, re-entrancy, inter-module communication) that need to be tested another way. These limitations are not unique to application development so I'll focus instead on something that is: the difficulty of isolating your units for testing.

Advocates of unit testing claim that you can follow good program design and reduce coupling and integration, making tests easy to write.

Unfortunately, in application development, that's not exactly possible.

As I noted when I was discussing iPhone application design, the code that you write in a Cocoa application is mostly controller classes — since the model and view classes are so reusable, you rarely need to write them yourself.

Controller classes are the classes which link your program together — they join model and view elements together to make your program. The entire purpose of these classes is coupling. The unit tests I wrote for the WhereIsMyMac program were approximately three times the size of the original code due to large numbers of mock objects and tricky hackery to intercept calls into the Cocoa framework — and this was a simple sample application, it could easily be much worse. Every mock object reduces the accuracy of the test by reducing the reality of the test environment and the risk of false positives or negatives in test results.

Since controller classes are so common in applications and the main role of a controller class is to join different objects together, unit testing suffers from the following serious problems in application development:

Requires huge amounts of mocking code and other fakery (time consuming).
The resulting tests are far removed from the integrated reality, making false positives and false negatives highly likely and leaving large holes that are simply not tested.

System testing methodologies for application development

The best approach for testing an application is to accept the coupled, integrated, timing dependent, environment dependent nature and test everything in place. The idea is simple: test the complete program in the exact manner (or as close as possible) in which you expect it to be used.

Tests which operate in this manner are classed as "system tests".

The reason why system tests are the most efficient and accurate form of product testing is simple: if you want to ensure low bug rates for the user, test the program in the same way that the user will use it; don't test a fake environment and don't test at levels the user can't access.

Types of system testing

There are lots of ways to system test your code. In order from most important to least important for application development:

I'm not going to give full definitions of these tests here — I'm simply going to discuss their importance to applications and related projects. Follow the links to read more about each one.

Every good application has point 2 and most have 3 and 4 as part of their regular testing methodology — sanity checks occur as part of the development methodology (run your code before you commit) and fall outside formal testing.

The important step in making system tests work is to keep them formalized. If the test is not automated, then it should be formally documented so that each of the steps is correctly run during a testing phase. A basic or ad hoc approach to any of these points doesn't count though: proper quality comes from rigorous and clearly defined testing approaches.

User interface testing

User interface testing is normally performed using testing matrices. In its simplest form, this means a document containing all user interface test cases in a table — a spreadsheet, workprocessor or TextEdit document, it doesn't really matter as long as it is documented.

The rows in the table are all steps in operating your program (selecting menu items, operating buttons, perform edit operations). Every single user interface element in the program should be tested and most should be tested multiple ways to account for different expected effects.

The columns are all environmental differences between runs. Different operating system versions, different computers, different installation settings or different builds of the application (lite, demo or full).

Each cell in the table should then contain the observed result and an indication of whether this is a success or failure according to the specification.

If you can automate the process, then great — there are software tools that will help with this on the Mac. If you can't — yes, user interface testing will get manual and tedious but ultimately, it is the only way to guarantee that the program works as expected. Most of the programs you use have simply had someone sitting in front of them, progressively clicking all the buttons and using all the controls — for every test case in every version.

You need to have the whole table documented and it needs to cover every element of the user interface. The purpose is to remind you to test everything (bad luck will ensure that failure to test a row will guarantee that it contains uncaught bugs).

API testing

In theory, user-interface testing should test everything in a user facing application. It may seem inefficient to suggest API testing (which is normally done for libraries and code modules).

There are three reasons that any substantial application would want API tests:

Human testers of user-interfaces are lazy, forget or make mistakes
API tests are automated and can be run at build-time or as part of continuous integration
You can test issues that may not be obvious during user testing (like data coherency)

For user applications though, it presents the problem that you must create an API layer that can actually be programmatically tested. The common approach is to separate the "model" of your application into a separate module with an API layer.

API testing is similar to unit testing in many respects:

it is automated
can be implemented using OCUnit or similar libraries
can be used to develop your application using test-first methodologies

The difference is that API tests do not separate the units within the module. API tests test the whole module in-place, fully integrated. This means that the API tests can be quite removed from the implementation details — which has the advantage that they can be more easily written by a separate programmer or test engineer, freeing up programming resources. API tests also aim to be optimally efficient: they only test inputs and outputs and don't care about how intermediary steps in the transformation occurs.

API tests attempt to provide a realistic environment and data but do suffer from some of the same limitations as unit tests in that some parts of the environment must be synthetic (the full application will not be present during testing).

Regression tests

After you're happy that your program is working as intended, regression tests ensure that subsequent work doesn't screw it up.

These are tests are normally used for programs that produce a file output. Their operation is basically: run the regression test and compare the output to the "known good" result which was saved previously. If the output changes unexpectedly, the test fails.

For many file producing projects (like a few major open-source projects specializing in video codecs, PDF renderers, DVD authoring packages) this is the only test they include. However, it's all that these types of project require: a good set of regression tests should have high code coverage (exercise almost all of the program) and perform most of the work of API testing too.

Regression tests can be human or automatically driven. Applescript can drive regression tests in full applications or OCUnit can be used to drive regression tests through an API layer.

Specification

As I hinted previously, there are a few roles served by unit tests that system tests handle. One is that unit tests are a form of specification for the code. You can use the tests as a way of learning what the code is supposed to do and in some cases for sketching out how future code should operate.

API testing can certainly replicate the unit testing specification at the API level; again, API tests are like an interface optimized application of unit tests.

However, I prefer the old-school approach: document your code with comments. Not with a line or two inside the method but full comment blocks on every single method documenting conditions on all parameters and the return parameters and effects of the method. Like test-first development, it is common to write comments first (specify the functionality of the method, then write it, asserting pre and post conditions if desired).

I use a customized version of Xcode's "Script Menu→HeaderDoc→Insert @method comment" to automate the creation of the comment block's formatting from the method prototype.

If the comments at the start of each method are not clear enough for documentation (think about Apple's Cocoa API documentation) then you're not doing your commenting job.

Conclusion

Unit testing an application is filled with difficulties and problems. In my development style, I consider the time cost of unit testing an application outweighs its benefits — especially since a unit tested application still requires system tests like user-interface and regression tests for proper validation.

Regardless of whether you use unit tests, formalized system testing — either automated or manual and methodical — is required to fully validate an application and ensure the lowest possible low bug rates.

The most efficient approach is to test the interface that the program exposes in the exact way that the user will use it. For user interface apps, this means user testing matrices. For applications with a lot of model code, this means API tests. For document producing applications, this means regression tests. In many cases though, a combination of all three is best.

Most of these approaches require that you be disciplined. You need to comment your code. You need to maintain user interface testing matrices. You need to refactor your model layer so it has an interface that can be tested automatically. You need to measure the code coverage of your regression tests.

I know these things are tedious. I know that no one wants to write test plans, test documents and API tests. But if you love your program and you want it to suck less, this is work that needs to be done.

A sample iPhone application with complete unit tests

2009-12-27T15:59:00.001-08:00

In this post, I present a complete Cocoa Touch iPhone application implemented with unit tests for all created code. I'll look at setting up build and debug targets and executables for both Application and Logic tests, and show you some of the differences between Application and Logic tests.

The code for this post is an iPhone version of the Mac post I presented last week.

Xcode unit testing targets for the iPhone

Like Mac unit testing, unit testing targets on the iPhone are generally divided into two types:

Logic tests — these are run in a executable that is separate from your application. The separate build can be easier to manage, faster to build and is easier to run objects in isolation since it avoids the application setup. However, you cannot test components which rely on the application (which is most user interface components). Generally, this type of test target is intended for libraries, frameworks and testing the back-end (model components of model-view-controller) of your application.
Logic tests are easily run at build-time or from the command-line, which is helpful for continuous integration or automated test processes.
Application tests — these tests let the application load first and are subsequently loaded into the existing application. This means that the full application environment is available to your tests. In many cases, controller tests and view tests need to be run as application tests since they are reliant on the full environment.
Application tests allow your application to be tested in a more realistic environment, reducing the chance that environment or integration level issues will be missed. They are normally run as a separate step (not as part of the build) and therefore may be less convenient for tests that need to be run every time.

In last week's post on Mac development, I covered the Application Tests exclusively. For the iPhone, I will cover both. The reason for this is:

iPhone Application Tests will only run on the device.

This is annoying. It means that you must have a device connected to your test machine via USB to run Application Tests and endure the slow copy-to-device and slow gdb interaction speeds. Apple could have allowed the simulator to perform the same bundle injection but they have not.

There are alternatives to this approach. You could probably run a regular iPhone application in the simulator and invoke SenTestingKit manually after your application starts. There's also Google's Toolbox for Mac has an iPhone Unit Testing approach that runs in the simulator.

But I'm going to keep to the default OCUnit approaches used in Xcode, so I'll show you how to configure both Application Tests and Logic Tests and I'll show you the sorts of tests that will run in both and which will require the full Application Test to run.

To be clear: if you want to run Logic Tests for your Mac applications, you can follow almost exactly the same approach that I present here. For Mac applications though, since you can invoke the ApplicationTests from the command line (as a post-build step or integration step) I would not normally consider the hassle of maintaining an extra build target and executable worth the effort.

iPhone project configuration

Unit testing targets

After you've created a blank project, use the "Project→New Target..." menu item to add two new "Cocoa Touch→Unit Testing Bundle" Targets to the project. These will be the ApplicationTests and LogicTests bundles.

Be wary of target memberships: When you add bundle resources and sources-to-compile to the original project, also add these to the LogicTests target but do not add them to the ApplicationTests target. Testing-specific files should be added to the LogicTests target and the ApplicationTests target but not to the original project.

As with the Mac project configuration, that's sadly not enough to make it work.

First, drag your original application's target onto the ApplicationTests and LogicTests targets to create a dependency (force the application to build before the unit tests).

Then delete the Run Script phase of the ApplicationTests testing target. It's only for logic tests and won't work for application tests.

Then edit the ApplicationTests target's settings (Right click→Get Info) and set the "Build→Linking→Bundle Loader" for all configurations to:

$(CONFIGURATION_BUILD_DIR)/WhereIsMyPhone.app/WhereIsMyPhone

where "WhereIsMyPhone" is the name of the application you're unit testing. As with the Mac setup, this step lets the testing target link against the application (the ApplicationTests target doesn't include the original source files and we don't want linker errors when compiling). Unlike the Mac setup, we don't need to set the "Unit Testing→Test Host" (since we can't run using the build-time step).

On the build configuration, also add APPLICATION_TESTS to the "GCC 4.2 - Preprocessing→Preprocessor Macros". This will let us flag certain tests for running in the ApplicationTests bundle but not the LogicTests.

It'd be nice to use the OCMock framework but the iPhone doesn't allow dynamic linking. Instead we need to take the OCMock source code from, OCMock on GitHub, take the non-test-related files and add them directly to both unit testing targets' "Compile Sources" phases. To get it to compile for the iPhone you'll need to replace isEqualTo: in OCMConstraint.m with isEqual:, the import of <objc/objc-runtime.h> in OCPartialMockObject.m with <objc/runtime.h> and the typeof in OCMArg.h with __typeof.

To ensure that the compiler will find the OCMock headers you will also need to add $SRCROOT (non-recursive) to the Project Settings ("Project→Edit Project Settings") under "Build→Search Paths→Header Search Paths" (for all Configurations).

Debugging setup for the ApplicationTests target

To run the application tests, we need to make a copy of the original iPhone application's target (Right Click→Duplicate) — give it a name like "WhereIsMyPhoneTesting" to distinguish from the original "WhereIsMyPhone" target.

Separate targets again: You will need to keep the duplicate in sync with the original. This means that all source files and resources added to the application should also be added to the testing target.

With all these separate targets, it's worth noting that you don't need to add to each target separately — when you're adding a new file to the project, you are normally given the list of targets and you select the checkboxes for the appropriate targets all at once. Don't add test files to the application and don't add application files to the ApplicationTests target and everything will work.

Drag the ApplicationTests target onto this duplicate (to make the duplicate dependent on the application testing bundle). Also drag the application testing bundle (in the Group Tree under Products named ApplicationTests.octest) to the new "WhereIsMyPhoneTesting" target's "Copy Bundle Resources" phase.

Finally, in the settings for the "WhereIsMyPhoneTesting" target, for all Configurations set the "Build→Packaging→Product Name" to something distinct from the original target (e.g. change "WhereIsMyPhone" to "WhereIsMyPhoneTesting").

iPhone application tests only work on the device.
To run the iPhone's application unit tests, you must build and install onto a device. They will not load in the simulator. Yes, this is annoying. Please request simulator support for Application Tests in future iPhone SDK releases if this bothers you.

To set breakpoints and interactively debug, you'll need to build the WhereIsMyPhoneTesting target before running the WhereIsMyPhoneTesting executable on your device. If the project contains the custom executable (from the LogicTests setup below) you may need to set the project's Executable (from the "Project→Set Active Exectuable..." menu) to WhereIsMyPhoneTesting manually.

Debugging setup for the LogicTests target

For the logic tests, we don't create another target but we do need to create a custom executable ("Project→New Custom Executable...") named "DebugLogicTests" or similar with a path relative to the Current SDK of:

Developer/usr/bin/otest

This is Apple's test harness and will handle the work of running the LogicTests bundle headlessly in the iPhone Simulator.

You also need to set the Arguments and Environment for this executable to work. Double click the DebugLogicTests item in the Executables section of the Group Tree and edit the Arguments tab to look like this:

Warning: order of arguments is important (the "-SenTest Self" must be first).

Note: If you're in a hurry, the DLYD_ROOT_PATH and DYLD_FORCE_FLAT_NAMESPACE are normally enough to get it running. The rest relate to minor configuration points that you may want or need eventually but which aren't critical — however, they may cause unexpected runtime behavior if missing.

To set breakpoints and interactively debug, you'll need to build the LogicTests target before running the DebugLogicTests executable in the simulator. Since the project contains a custom executable you may need to set the project's Executable (from the "Project→Set Active Exectuable..." menu) to DebugLogicTests first.

The project on the left is configured to run Application tests.
The project on the right is configured to run Logic tests.
Set Target and Executable to "WhereIsMyPhone" to run the application as normal.

If you have tests running at build-time that fail but the actual compile has succeeded, you can Debug without rebuilding by pressing Command-Option-Return ("Run→Debug").

The sample iPhone application

As with last week, the sample application is a recreation of my earlier post, WhereIsMyMac, this time written for the iPhone using a test-first approach to development.

With so much discussion about how to set up the Xcode project, I might keep the discussion of the tests themselves quite brief. If you want to know more about the implementation of the tests, they are almost identical to last week's — I deliberately chose this application because the implementation is very similar on the Mac and iPhone — so I encourage you to read through the writing of the tests from that post.

The only significant differences between the iPhone and Mac applications are that the Window Controller from last week is a View Controller in the iPhone version, NSTextFields are now UILabels and the UIWebView that the iPhone version contains is simpler than the WebView on the Mac, so the mainFrame access never occurs on the iPhone.

There is no application for the LogicTests

What I'll focus on this time, are the differences between the Mac and iPhone tests and implementations. Here's an example:

#ifdef APPLICATION_TESTS

- (void)testAppDelegate
{
   id appDelegate = [[UIApplication sharedApplication] delegate];
   STAssertNotNil(appDelegate, @"Cannot find the application delegate.");
}

#endif

On the Mac, this code was almost the same (NSApplication instead of UIApplication). The big difference is that I've wrapped the entire test in #ifdef APPLICATION_TESTS since the application delegate does not exist in the logic tests, we must ensure this test is only run for application tests (we added the APPLICATION_TESTS preprocessor macro to the ApplicationTests target only).

LogicTests are a different bundle

The next big difference is that the actual application code, which runs out of the mainBundle in the regular application, runs out of the LogicTests.octest bundle that otest loads in the LogicTests target. To make code that accesses the bundle work the same, independent of where it is running, all NSBundle access is handled by class.

For example, the code in WhereIsMyPhoneViewController.m that generates the HTML to send to the UIWebView fetches the structure of the HTML from a file with:

[[NSBundle bundleForClass:[self class]]
    pathForResource:@"HTMLFormatString"
    ofType:@"html"]

Previously, I would have used [NSBundle mainBundle] here but that code failed when run in the LogicTests. The [NSBundle bundleForClass:[self class]] will find the bundle that contains the class whether it is the main bundle or the LogicTests.octest bundle loaded by otest.

Many UIKit classes won't work without the UIApplication

Trying to add code to pass the tests in this project revealed that other tests would have to be conditionally excluded from LogicTests as well:

The default loadView method will fail — so the testLoadView method is #ifdef'd out.
Any attempt to alloc/init a UILabel will fail. I don't know why but because of this, all tests on the labels must be #ifdef'd.

Generally, don't expect anything from the UIKit framework to work in your Logic tests. Other frameworks will almost always work (in this application, the CoreLocation and Foundation frameworks work without issue).

Within UIKit, some elements will work — for example, UIWebView didn't have any issues in my testing. Exactly which user-interface objects will fail in the LogicTests bundle (without an actual running application) is never really clear until you try but these failures are why you still need to run the Application Tests to verify against — the Application Tests are a more authoritative result for anything in UIKit.

Conclusion

Download the complete WhereIsMyPhone-WithUnitTests.zip (85kb).

Warning: custom executables (like the DebugLogicTests executable) are user data in the project file. This means that you will not see the DebugLogicTests that I created in this project unless you create it yourself or your username happens to be "matt".

This project includes code from the OCMock framework, which is Copyright (c) 2004-2009 by Mulle Kybernetik. OCMock is covered by its own license (contained in the OCUnit/License.txt file in the download).

The code for this post is largely been a repeat of last week's post for the benefit of iPhone programmers. You can have a look at the differences for yourself but I deliberately chose this project because the iPhone and Mac implentations are so similar.

I have taken the time though to show you how you can maintain a LogicTests target (in addition to the application-wide ApplicationTests target) that can test most of your project outside the application environment — including most of the user-interface controller code. The purpose is to sidestep the "device-only" limitations of the current OCUnit testing for the iPhone but also to show how you could set up build-time unit tests for part of your application, without necessarily applying this approach to your entire project.

A sample Mac application with complete unit tests

2009-12-21T15:40:00.001-08:00

In this post, I present a complete Cocoa Mac application implemented with unit tests for all created code. I'll create the tests first and then only add the code required to make the tests pass, largely following a test-driven development (TDD) methodology.

Next week I'll show the configuration and implementation of this project as an iPhone application for the benefit of Cocoa Touch developers.

Introduction

A few days ago, I spent some time searching for a Cocoa application with source code and full unit tests but I was only able to find Apple's trivial iPhoneUnitTests sample project.

With more than four years of official support (Apple added OCUnit to the Developer Tools in 2005) and a large number of articles and blog posts by Mac programmers endorsing unit testing and offering solutions to problems within unit testing, it is surprising to me that there are so few code examples showing Cocoa applications with full unit tests.

So I decided to re-implement one of my own projects (the WhereIsMyMac application from an earlier post) with complete unit tests using a test-first approach — I'll create failing tests and only add code to the project to pass those failing tests.

I'll be cheating a bit relative to proper test-first development (since this is a re-implementation of an existing project, I already know what the final code should be) but I'll keep to the spirit of the process by only adding as much code as I need to make the tests pass.

I know people will want to see how this works on the iPhone but since this post is already large, I've deferred that implementation until next week.

Xcode unit testing targets

There are two different ways of configuring Xcode for unit testing: logic test targets and application test targets.

Logic tests — these are run in a executable that is separate from your application. The separate build can be easier to manage, faster to build and is easier to run objects in isolation since it avoids the application setup. However, you cannot test components which rely on the application (which is most user interface components). Generally, this type of test target is intended for libraries, frameworks and testing the back-end (model components of model-view-controller) of your application.
Logic tests are easily run at build-time or from the command-line, which is helpful for continuous integration or automated test processes.
Application tests — these tests let the application load first and are subsequently loaded into the existing application. This means that the full application environment is available to your tests. In many cases, controller tests and view tests need to be run as application tests since they are reliant on the full environment.
Application tests allow your application to be tested in a more realistic environment, reducing the chance that environment or integration level issues will be missed. They are normally run as a separate step (not as part of the build) and therefore may be less convenient for tests that need to be run every time.

I'll focus exclusively on the second type of testing target, since it will allow full testing of the application.

It may seem strange to talk about "unit tests" which are supposed to be run in isolation but then talk about "Application tests" which provide the environment in which to run tests. The reality is that you can only isolate user-interface unit tests from your own code — there will always be some interaction (in hidden and not controllable ways) with the application framework code. Windows, views and controls simply won't work if there's no application around them.

Mac project configuration

One of the best sources of information on configuring Xcode for Unit Tests is Chris Hanson's series on unit testing. I'll follow many of the steps that he describes and further add OCMock integration to the procedure.

After you've created a blank project, use the "Project→New Target..." menu item to add a new "Cocoa→Unit Testing Bundle" Target to the project.

Note: The testing target is a separate target. This means that you need to be careful of target membership. All application source files should be added to the application target only. Test code files should be added to the testing target only.

It'd be great if that's all that you needed but there's more.

First, drag your application's target onto the unit testing target to create a dependency (force the application to build before the unit tests).

Then edit the unit testing target's settings (Right click→Get Info) and set the "Build→Linking→Bundle Loader" for all configurations to:

$(CONFIGURATION_BUILD_DIR)/WhereIsMyMac.app/Contents/MacOS/WhereIsMyMac

where "WhereIsMyMac" is the name of the application you're unit testing. This will let the testing target link against the application (so you don't get linker errors when compiling).

Also set the "Build→Unit Testing→Test Host" to $(BUNDLE_LOADER) (this will give this property the same value as the above setting). This property lets the automated build-time script know to launch the application and inject the unit testing bundle into it to start the tests.

Logic tests note: If you want to do logic tests instead of application tests, leave the Bundle Loader and Test Host fields empty and add all files you want to test to the test target (so the test target becomes a separate, self-contained target instead of linking against the main application).

Finally, download a copy of OCMock, place the OCMock.framework in the same directory as your .xcodeproj file and set the "Build→Search Paths→Framework Search Paths" to:

"$(SDKROOT/Developer/Library/Frameworks"
"$(SRCROOT)"

Neither need to be recursive. The quotes are to handle potential spaces in your paths. The first search path will probably already exist in the settings but we add the second search path so that the OCUnit framework will be found in the project's directory.

The configuration so far will run all tests as a build step (the Cocoa Unit Testing target includes a Run Script build step that runs all the unit tests).

To allow debugging as well as build-time execution, add a new executable to the project ("Project→New Custom Executable...") with a path relative to the Build Product of:

WhereIsMyMac.app/Contents/MacOS/WhereIsMyMac

and in the custom application's settings (Right click→Get Info) on the Argument tab, set the arguments and environment variables as follows:

Most of these settings configure the application to load our test bundle into itself when it runs. The :$(SRCROOT) at the end of fallback framework path is to allow the application to find the OCUnit framework in our project directory at runtime.

Separate executable: since this test debugging executable is a separate executable, you will need to switch to the debugging executable for debugging tests and switch back when you want to run the application normally.

AppDelegate Tests

Startup integration

The application will start with the WhereIsMyMacAppDelegate and we'll use the the WhereIsMyMacAppDelegate to load the main window.

The first test is therefore to ensure that application's delegate is an instance of WhereIsMyMacAppDelegate on startup.

- (void)testAppDelegate
{
    id appDelegate = [[NSApplication sharedApplication] delegate];
    STAssertTrue([appDelegate isKindOfClass:[WhereIsMyMacAppDelegate class]],
        @"Cannot find the application delegate.");
}

This is a short and simple test but it isn't a unit test. It's actually an integration test (since it is testing the fully connected +[NSApplication sharedApplication] in place.

An ideal unit test would test the NSApplication in isolation and ensure that it creates and sets its delegate property correctly. This is infeasible since NSApplication can't be isolated so we simply accept the nature of the class and test the instance of sharedApplication that should be created on startup. Of course, unit testing NSApplication itself shouldn't be necessary but an integration test to ensure that the startup of the program leads correctly to the creation and setting of the WhereIsMyMacAppDelegate is still a good idea.

applicationDidFinishLaunching:

The next test is to ensure that applicationDidFinishLaunching: on the delegate will:

create the WhereIsMyMacWindowController and set it on the delegate
load the WhereIsMyMacWindowController's window
make the WhereIsMyMacWindowController's window the main and key window

- (void)testApplicationDidFinishLaunching
{
    WhereIsMyMacAppDelegate *appDelegate =
        [[[WhereIsMyMacAppDelegate alloc] init] autorelease];

    id mockWindow = [OCMockObject mockForClass:[NSWindow class]];
    [[mockWindow expect] makeKeyAndOrderFront:appDelegate];

    mockWindowController = [OCMockObject mockForClass:[WhereIsMyMacWindowController class]];
    [[[mockWindowController expect] andReturn:mockWindow] window];
    NSUInteger preRetainCount = [mockWindowController retainCount];

    [appDelegate applicationDidFinishLaunching:nil];
    
    [mockWindowController verify];
    [mockWindow verify];
    
    NSUInteger postRetainCount = [mockWindowController retainCount];
    STAssertEquals(postRetainCount, preRetainCount + 1, @"Window controller not retained");

    id windowController;
    object_getInstanceVariable(appDelegate, "windowController", (void **)&windowController);
    STAssertEqualObjects(windowController, mockWindowController,
        @"windowController not set on appDelegate");

    object_setInstanceVariable(appDelegate, "windowController", nil);
    mockWindowController = nil;
}

This test is a near perfectly decoupled unit test of the -[WhereIsMyMacAppDelegate applicationDidFinishLaunching:] method. However, the approaches used to decouple it from the rest of the program probably make it tricky to understand.

The first two lines create a clean WhereIsMyMacAppDelegate to test.

The second two lines create a mock NSWindow that we use to check that the window is brought to the front by makeKeyAndOrderFront:. In conjunction with the later [mockWindow verify] this will test the 3rd requirement in the list above.

The next three lines create a WhereIsMyMacWindowController that will be swapped in place of any WhereIsMyMacWindowController that the appDelegate tries to create (more on how this works in the next paragraph). The mockWindowController is told to expect window to be invoked and when it does, will return the mockWindow. In conjunction with the [mockWindowController verify], the retain count checks and the STAssertEqualObjects will verify the first two requirements in the list.

I mentioned that mockWindowController will be substituted in place of a real WhereIsMyMacWindowController any time the appDelegate tries to create a WhereIsMyMacWindowController. This works because mockWindowController is a global variable that affects the following category:

id mockWindowController = nil;

@implementation WhereIsMyMacWindowController (WhereIsMyMacAppDelegateTests)

- (id)init
{
    if (mockWindowController)
    {
        [self release];
        return mockWindowController;
    }
    
    return invokeSupersequent();
}

@end

This category overrides the -[WhereIsMyMacWindowController init] method to return the mockWindowController if it exists, otherwise the default behavior. The invokeSupersequent() comes from my old Supersequent implementation post (it's like invoking the super method but will invoke the current class' base or earlier category implementation, not just a genuine super method and is more flexible — though slower — than method swizzling).

Of course, we only want this override to return the mock object at specific times. This is why the mockWindowController must be explicitly set back to nil at the end of the method.

Notice that the category overrides init, not alloc: technically, overriding alloc would prevent any method being invoked on WhereIsMyMacWindowController (making the test perfectly decoupled from other classes) however this would mean that we'd need to invoke init on the mock object and OCClassMockObject does not let you mock any methods that it implements for itself (this includes all of the NSProxy methods plus initWithClass: and mockedClass). So instead, we override init and make the acceptable tradeoff to allow +[WhereIsMyMacWindowController alloc] to be invoked.

A related point is that OCClassMockObject can't mock retain or release. This is why manual checks on the retainCount are used instead of asking the mock object to expect a retain. If you expect autorelease to be used instead of release, you'd need to wrap the tested method invocation in an NSAutoreleasePool to flush the autorelease before testing the retainCount.

A final point about this test: it uses object_getInstanceVariable and object_setInstanceVariable to get the windowController from the appDelegate instead of the property accessor. The reason for this is that object_getInstanceVariable directly reads the value from the object without invoking any accessor methods that might have secondary effects. Some code presented elsewhere uses valueForKey: to achieve the same effect but the problem with this is that valueForKey: will use the window getter method if it exists — we want to directly test that the actual instance variable is set on the class without interference.

applicationWillTerminate:

The final tests for the WhereIsMyMacAppDelegate are for the applicationWillTerminate: method. This method should close window and release it.

- (void)testApplicationWillTerminate
{
    WhereIsMyMacAppDelegate *appDelegate =
        [[[WhereIsMyMacAppDelegate alloc] init] autorelease];
    
    id mockWindowController = [OCMockObject mockForClass:[WhereIsMyMacWindowController class]];
    [mockWindowController retain];
    object_setInstanceVariable(appDelegate, "windowController", mockWindowController);
    
    NSUInteger preRetainCount = [mockWindowController retainCount];
    [[mockWindowController expect] close];

    [appDelegate applicationWillTerminate:nil];
    
    [mockWindowController verify];

    NSUInteger postRetainCount = [mockWindowController retainCount];
    STAssertEquals(postRetainCount, preRetainCount, @"Window controller not released");

    id windowController;
    object_getInstanceVariable(appDelegate, "windowController", (void **)&windowController);
    STAssertNil(windowController, @"Window controller property not set to nil");
}

After creating an appDelegate to test, this method creates a mock WhereIsMyMacWindowController, tells it to expect a close invocation, sets it as the windowController on the appDelegate to this new mock object, invokes applicationWillTerminate: on the appDelegate, verifies that the close method was invoked, ensures that the retainCount is decremented by one and that the windowController instance variable is set to nil.

That's three failing tests. One is more of an integration test than a unit test (since it relies on the NSApplcation operating in place) but the others are genuine isolated unit tests on the WhereIsMyMacAppDelegate. The implementation to pass these tests is less interesting but you can have a look at the sample project to see how I added code to pass these tests.

Window Controller Tests

loadWindow integration

As with the application delegate, the first test is an integration test. We need to test that the loadWindow method will load the required user interface elements from files in the bundle. This is similar to Chris Hanson's "Trust by verify" approach except that I test the loading of the window separately from the windowDidLoad and window methods.

- (void)testLoadWindow
{
    [windowController loadWindow];

    WebView *webView;
    object_getInstanceVariable(windowController, "webView", (void **)&webView);
    CLLocationManager *locationManager;
    object_getInstanceVariable(windowController, "locationManager", (void **)&locationManager);
    NSTextField *locationLabel;
    object_getInstanceVariable(windowController, "locationLabel", (void **)&locationLabel);
    NSTextField *accuracyLabel;
    object_getInstanceVariable(windowController, "accuracyLabel", (void **)&accuracyLabel);
    NSButton *openInBrowserButton;
    object_getInstanceVariable(windowController, "openInBrowserButton", (void **)&openInBrowserButton);
    
    STAssertTrue([windowController isWindowLoaded], @"Window failed to load");
    STAssertNotNil(webView, @"webView ivar not set on load");
    STAssertNotNil(locationLabel, @"locationLabel ivar not set on load");
    STAssertNotNil(accuracyLabel, @"accuracyLabel ivar not set on load");
    STAssertNotNil(openInBrowserButton, @"openInBrowserButton ivar not set on load");
    STAssertEqualObjects(windowController, [openInBrowserButton target],
        @"openInBrowserButton button doesn't target window controller");
    STAssertTrue([openInBrowserButton action] == @selector(openInDefaultBrowser:),
        @"openInBrowserButton button doesn't invoke openInDefaultBrowser:");
}

The windowController is a fixture that's allocated in the setUp method. The majority of this method then gets the instance variables from the windowController after the loadWindow method is invoked and tests that the required properties are all set.

We can now test the windowDidLoad method as a separate step to the loadWindow. The windowDidLoad should create a CLLocationManager object, set the window controller as the delegate and start location updates.

windowDidLoad

- (void)testWindowDidLoad
{
    mockLocationManager = [OCMockObject mockForClass:[CLLocationManager class]];
    [[mockLocationManager expect] setDelegate:windowController];
    [[mockLocationManager expect] startUpdatingLocation];

    [windowController windowDidLoad];

    [mockLocationManager verify];
    
    object_setInstanceVariable(windowController, "locationManager", nil);
    mockLocationManager = nil;
}

This uses the same category override approach that was used in the testApplicationDidFinishLaunching method to swap in a mock CLLocationManager and ensure that the appropriate methods are invoked.

locationManager:didUpdateToLocation:fromLocation:

Next step: verify that the correct Google Maps location is loaded in the WebView's mainFrame when a given coordinate is passed to the WhereIsMyMacWindowController implementation of the -[CLLocationManagerDelegate locationManager:didUpdateToLocation:fromLocation:] method.

This test method is pretty big but the essence is that:

The web view and its main frame are mocked.
The main frame is told to expect specific a specific HTML string that's loaded from a pre-created file.
The method is then passed the exact location that should trigger that HTML string.
The mock web frame is then asked to verify that the expected HTML string was loaded.
The window's labels are also tested to ensure they receive the correct values.

- (void)testUpdateToLocation
{
    NSString *htmlString =
        [NSString 
            stringWithContentsOfFile:
                [[NSBundle bundleWithIdentifier:@"com.yourcompany.UnitTests"]
                    pathForResource:@"WebPageTestContent" ofType:@"html"]
            encoding:NSUTF8StringEncoding
            error:NULL];
    id mockWebView = [OCMockObject mockForClass:[WebView class]];
    id mockWebFrame = [OCMockObject mockForClass:[WebFrame class]];
    [[[mockWebView stub] andReturn:mockWebFrame] mainFrame];
    [[mockWebFrame expect]
        loadHTMLString:htmlString
        baseURL:nil];
    object_setInstanceVariable(windowController, "webView", mockWebView);

    NSTextField *locationLabel = [[[NSTextField alloc] init] autorelease];
    NSTextField *accuracyLabel = [[[NSTextField alloc] init] autorelease];
    object_setInstanceVariable(windowController, "locationLabel", locationLabel);
    object_setInstanceVariable(windowController, "accuracyLabel", accuracyLabel);

    CLLocationCoordinate2D coord;
    coord.longitude = 144.96326388;
    coord.latitude = -37.80996889;
    CLLocation *location =
        [[[CLLocation alloc]
            initWithCoordinate:coord
            altitude:0
            horizontalAccuracy:kCLLocationAccuracyBest
            verticalAccuracy:kCLLocationAccuracyHundredMeters
            timestamp:[NSDate date]]
        autorelease];
    
    [windowController
        locationManager:nil
        didUpdateToLocation:location
        fromLocation:nil];
    [windowController
        locationManager:nil
        didUpdateToLocation:location
        fromLocation:location];
    
    [mockWebFrame verify];
    
    STAssertEqualObjects(
        ([locationLabel stringValue]),
        ([NSString stringWithFormat:@"%f, %f", coord.latitude, coord.longitude]),
        @"Location label not set.");
    STAssertEqualObjects(
        ([accuracyLabel stringValue]),
        ([NSString stringWithFormat:@"%f", kCLLocationAccuracyBest]),
        @"Location label not set.");
}

An interesting point to notice here is that the WebPageTestContent file is loaded from a bundle that isn't the mainBundle. This is because the test resides in the UnitTests.octest bundle, not the application's bundle (which is the "main" bundle).

locationManager:didFailWithError: and openInDefaultBrowser:

I'll leave out the code for the locationManager:didFailWithError: test — it's largely the same as the previous test but with a different HTML string to load in the web view's main frame. You can see it in the downloaded project if you wish.

Similarly, openInDefaultBrowser: is just a URL, generated from the current location and sent to the shared NSWorkspace (which we mock through category overrides) so the test contains largely the same elements — so I'll omit the code for this test too. Again, check the downloaded project if you're interested.

dealloc:

All that remains is to create tests for the dealloc method to ensure that the locationManager receives a stopUpdatingLocation and a release message.

- (void)testDealloc
{
    id mockLocationManager = [OCMockObject mockForClass:[CLLocationManager class]];
    NSUInteger preRetainCount = [mockLocationManager retainCount];
    [mockLocationManager retain];
    object_setInstanceVariable(windowController, "locationManager", mockLocationManager);
    
    [[mockLocationManager expect] stopUpdatingLocation];

    [windowController dealloc];
    
    [mockLocationManager verify];

    NSUInteger postRetainCount = [mockLocationManager retainCount];
    STAssertEquals(postRetainCount, preRetainCount, @"Location manager not released");
    
    windowController = nil;
}

Notice that we have to set windowController to nil at the end. This is because invoking dealloc on the windowController fixture has deallocated it and we need to ensure that the tearDown method doesn't try to invoke release on it.

Six failing tests for the WhereIsMyMacWindowController. You can look at the downloadable project to see the code added to pass these tests.

Conclusion

Download the complete WhereIsMyMac-WithUnitTests.zip (139kb).

Warning: Custom executables (like the UnitTestWhereIsMyMac discussed in this post) are part of user data in the project file, so you will not see the UnitTestWhereIsMyMac custom executable in the downloaded project unless you create it yourself or your username happens to be "matt".

This project includes OCMock.framework, which is Copyright (c) 2004-2009 by Mulle Kybernetik. OCMock is covered by its own license (contained in the OCMock.framework/Versions/A/Resources/License.txt file).

In this post, I created a Mac project, created unit tests for all required functionality (plus two integration tests) and ultimately added code to make the project pass those tests. I've shown the configuration required for unit testing targets in Xcode and the implementation of the tests themselves, which show how to isolate units of a program (using mock objects and category overrides) for properly decoupled unit testing.

Unit tests for all created code does not mean that the project is "fully tested". There are lots of aspects associated with integration, runtime and memory behaviors, user events and the behaviors of the Cocoa frameworks that are not covered by these tests. Of course, this is the limit of "unit testing" for classes that operate in an application framework — to test these other aspects requires different kinds of tests.

Next week, I'll be presenting the same post developed for the iPhone. I apologize that this will result in two posts that almost the same but there are enough differences between the two that I couldn't squeeze both into a reasonable sized post. I also hope that by separating the posts, the result will be easier for dedicated Mac or iPhone programmers to follow.

Finally, a disclaimer: please don't consider the existence of this post as a recommendation that you should necessarily write your applications with full unit tests. It is important to look at the work involved and weigh the associated time costs and against your project's need for unit level validation. There are alternative approaches for maintaining code quality that have different associated costs and benefits which I hope to discuss and compare in a later post.

Multiple copy buffers, cursor and tab key tricks in Xcode

2009-12-12T15:21:00.001-08:00

This week, I'll show you a few keyboard related tricks for editing in Xcode, including setting up multiple copy-and-paste buffers by adjusting the key mappings, switching tabs on or off for autocomplete and other text editing quirks in Xcode like understanding why the "End" key doesn't move to the end of the line on the Mac.

Key bindings, the cursor and Emacs

Standard text editing on the Mac obeys many more keyboard commands than most casual users realize. This is because the key bindings on the Mac derive from NeXTStep which chose to implement (where possible) a large number of the Emacs key bindings.

First developed in the 1970's, Emacs was designed for keyboards that lacked cursor and forward delete keys and computers that lacked a mouse. And, like its spiritual enemy in the world of text editing, Vi, Emacs was never a program to update its key bindings to stay current.

What this means is that text editing applications that use the standard Cocoa text editor — like TextEdit.app — and other more sophisticated text editors that support the operating system's default key bindings — like Xcode — support most of the Emacs key controls for navigating and editing — like Ctrl-F and Ctrl-B for forward and backward by one character or Ctrl-A and Ctrl-E for jump to the start or end of the paragraph.

Of course, most of this is pointless to ordinary users since the standard cursor and home keys will do this in a far less cryptic way.

For those of you who still scream at Xcode when the Home key doesn't move to the start of the line or get annoyed that the cursor doesn't move when using PageUp/PageDown, here's a quick refresher:

Key or combination	Action
↑	cursor up
↓	cursor down
←	cursor left
→	cursor right
Command ←	cursor to start of line
Command →	cursor to end of line
Option ←	cursor to start of previous word
Option →	cursor to end of previous word
Control ←	cursor to start of previous camel-case component (Xcode only — otherwise it works like Command ←)
Control →	cursor to end of previous camel-case component (Xcode only — otherwise it works like Command →)
PageUp or Control ↑	scroll up one page, without moving the cursor
PageDown or Control ↓	scroll down one page, without moving the cursor
Home	scroll to top of document, without moving the cursor
End	scroll to end of document, without moving the cursor
Option-PageUp	scroll up one page, moving cursor to center of new location
Option-PageDown	scroll down one page, moving cursor to center of new location
Command ↑	move cursor to start of document
Command ↓	move cursor to end of document
Option ↑	move cursor to start of the paragraph (except in Xcode where it does nothing)
Option ↓	move cursor to end of the paragraph (except in Xcode where it does nothing)

Due to the importance of the Home/End/PageUp/PageDown keys in text editing, I have no respect for Apple's choice to start shipping keyboards without these keys by default on new computers.

I wish there was a little more sense to these bindings. There almost are a few rules — like Control, Option and Command represent small, medium and largest increments in any direction and combinations involving the cursor keys move the cursor but Home/End/PageUp/PageDown combinations just scroll without moving the cursor — but sadly there are enough violations of these rules that you must simple learn them all by rote.

The ability to scroll the document without moving the cursor when desired on the Mac is an ability that I sorely miss when I'm stuck using Visual Studio or other development environments — in these other environment, my cursor always gets stranded when I quickly glance at another point in the document, whereas on the Mac I can just tap a left or right arrow to return to where I was.

Kill and yank

A side effect of bringing Emacs key bindings into Xcode though is that a few Emacs commands that don't have common Macintosh equivalents are brought in as well.

This includes kill and yank. Kill and yank are Ctrl-K and Ctrl-Y by default.

In most respects, kill and yank work like cut and paste. Kill something and it gets stored in your kill buffer, yank and the contents of your kill buffer are inserted at the current insertion point. If you have no selection, kill will delete from the cursor to the end of the line, otherwise it will only delete the selection. There are a few differences compared to cut-and-paste: you can't yank between applications (each application has its own, non-shared kill ring) and they store pure text only (no styled text, images or other copyable data).

In their default setup, kill and yank are like a second-rate extra cut-and-paste option. But correctly configured, you can have as many separate cut buffers as you want.

Setting up kill-and-yank

The first configuration change you need to make is to set up a binding for yankAndSelect: instead of ordinary yank:. We do this because yank: will only ever insert the most recently killed text whereas yankAndSelect: allows you to cycle through all stored buffers. You can do this in the "Xcode Preferences→Key Bindings→Text Key Bindings" but I prefer to make the binding System-wide by using the "/Developer/Applications/Utilities/Property List Editor.app" to create a file at "~/Library/KeyBindings/DefaultKeyBinding.dict" that overrides the yank: command with a yankAndSelect: command.

The key string is actually caret-y, not Ctrl-Y. You may need to create the KeyBindings
directory in your Library directory as it is not there by default.

Both yank: and yankAndSelect: are standard commands on NSReponder, so this just exchanges one for another. In a totally bizarre twist of documentation, yankAndSelect: is an undocumented method (it's not in the Cocoa.h headers) that appears in the documentation where you are encouraged to used it as required.

The other step to make multiple kill buffers work is to specify how many buffers you want. By default, there is 1 but we want multiple buffers.

To do this, just add the key NSTextKillRingSize with a string or number value greater than 1 to any .plist file. For example, if you only want this behavior added to Xcode, add the line to the Xcode .plist file.

I like to add this like to my Global Preferences. To do this, type:

open ~/Library/Preferences/.GlobalPreferences.plist

in a Terminal window (the file is hidden by default in the Finder so you need to open it like this unless you've turned the display of hidden files on).

The NSTextKillRingSize setting in my .GlobalPreferences.plist file.

With these changes, you can use Control-K to copy something to a kill buffer and then Control-Y to cycle through the last 3 items stored in your kill buffers (the collection of kill buffers is called the "kill ring"). You can use any number or kill buffers but large numbers may make cycling through the complete set harder (since you can only cycle through in one direction).

The Tab key binding in Xcode

While I'm talking about key bindings, one of the biggest shocks in Xcode 3.2 for me was the fact that the Tab key is configured by default to select the next Code Sense Completion, instead of inserting a Tab character.

This meant that if I had code like this:

and I hit the Tab key to indent the second line, it wouldn't indent — instead the autocomplete field would be selected.

I found this particularly frustrating since I normally use Ctrl-/ to select autocomplete fields, making the Tab key redundant as well as interfering.

Fortunately, Xcode supports a "Insert Tab without Extra Action" that is normally bound to Option-Tab which will only ever insert a Tab character (will never perform other UI actions). By exchanging the key bindings between "Insert Tab" and "Insert Tab without Extra Action", my complaint was solved.

On the topic of search and replace: a change to menus in Xcode 3.2 means that single file Search and Replace no longer appears in the menu (unless you're holding down the Control key, since its binding is now Ctrl-Command-F and "Ctrl" variants of menu items aren't shown unless "Ctrl" is held). This can make search and replace hard to find in Xcode 3.2. Another feature that has become harder to find are the search options — the little magnifying glass on the search field hides a popup menu that contains the essential options like "Ignore case".

A sideeffect of changing the tab bindings is that all text fields in the user interface — including the Search and Replace text fields — will change their behavior when the Tab key is pressed. Once the bindings are changed, Tab will no longer move the input focus from the search field to the replace field — it will instead insert the tab character into the selected field. This means that to jump from the Search field to the Replace field you will need to type Option-Tab. Of course, the ability to easily enter tab characters in the search field has its advantages too.

Conclusion

Text editing on the Mac is loaded with features that most people never use. While there's often no need to use many of the extra features, extra navigation options or extra kill-and-yank buffers can be useful additions.

The .GlobalPreferences.plist and global DefaultKeyBinding.dict files used to alter global key mappings provide a surprising amount of flexibility to applications that respect their content, like Xcode. You can use them to remap most key combinations to other commands if you choose. A corollary though: you should try to respect these dictionaries if writing your own custom text editor.

The design of an iPhone application

2009-12-08T03:17:00.001-08:00

In this post, I'll discuss iPhone program design using the example of a small but non-trivial iPhone application to provide examples of how the design is implemented. The design includes: how to manage data coming from different sources, how to manage multiple views of that data and how to design your program so it remains simple and manageable as it grows. In short, I'll be discussing how Model-View-Controller (MVC) applies to an iPhone application but I'll also discuss how even simple programs are considerably more hierarchic through their controllers and branched through their models and views than the basic description "Model-View-Controller" might imply.

The sample program

The sample program for this post takes the Core Data SQL database of Australian Postcodes that I created last week from a CSV file and uses that in an iPhone application that allows you to:

Browse and search the database.
Display entries in a MKMapView.
Find the nearest entry to the user's GPS and display that on a map.

The following screenshots show the basic flow of the application.

The "Show current location" step skips the middle screenshot in the workflow and goes straight to the map, displaying the closest "Postcode" in the database for the user's location, or just the user's location (with no pins in the map) if they are more than 0.1 longitude or latitude away from the nearest post office.

You can download the complete project AustralianPostcodes.zip (961kB).

Steps in designing a program

The basic steps in designing a small user program are:

Decide what the program will display to the user.
Work out how the user will navigate through the program to reach each view.
Work out the data that is needed to populate the views that the user will navigate.
Decide where that data will come from and how you will manage access to it.
Decide how and when you will construct your views.
Decide how you will provide your views with data.

The first two points are the program's requirements and the remainder is the high level design. For this post, I'm going to consider the first two points complete (as given in the previous section).

I'll discuss steps 3 and 4 as a single concept "Program data", then steps 5 and 6 as "Program construction".

Program data

While it might not be obvious, this program actually has 3 different sources of data:

Postcodes and their related data
The GPS location
The cache of fetched postcodes, filtered by search terms
The cache of postcodes nearest the selected location or GPS location
List of menu items on the top-level page

The last item doesn't need to be data (it could easily be done in code) but I wanted to talk about a range of different data sources and implementing menus like this from data can dramatically reduce the size and complexity of your code (see my earlier post Simplifying your code using NSDictionary).

Postcode data and the PostcodeController

Obviously in this program, the Core Data SQL database is the source of the postcode data. However, there is more to clarifying the data source than that.

The postcode data is used from multiple views in the application. For this reason, it will need to live in its own persistent location that views can access when needed. To handle its creation, persistence and access, we'll need some form of controller to manage the lifecycle of this data and access to it.

Core Data runs in an NSManagedObjectContext. In some respects, you may consider that the NSManagedObjectContext manages access to the data. While this is true at the low level of reading, writing, cacheing and fetching, the reality is that NSManagedObjectContext is not a manager in a broader sense for your program and your program specific logic.

Specifically, your program will need:

A way to construct the Core Data persistence stack (i.e. open a Core Data SQL store and create an NSManagedObjectContext for it).
A way to access the current context from anywhere in the program.
A place to put context processing code (if needed). This might include importing/exporting code, specialized fetching code, editing and validating code.

While this iPhone application doesn't need the last point, the first two are necessary.

In the default Xcode template for an iPhone application using Core Data, the NSManagedObjectContext is constructed in the AppDelegate object and from there is pushed onto the RootViewController so that it can be used there.

Simply put: I dislike this approach because it gives the AppDelegate multiple responsibilities unrelated to its primary purpose.

The AppDelegate exists to implement functionality during key points in the UIApplication's lifecycle (most importantly startup and shutdown). The AppDelegate doesn't use the NSManagedObjectContext for itself and the AppDelegate's primary responsibility is not document management — you should not be using your AppDelegate as your application's document manager.

Every class should have a single purpose
Every piece of functionality that a class exposes to the rest of the program (i.e. functionality that is part of the class' external interface) should be obviously part of that class' primary role in the program.

For this reason, I create a class (in this project it is named PostcodesController) whose responsibility it is to construct the document (our NSManagedObjectContext) and handle access to it or process the document if needed.

The PostcodesController will be a singleton, as most document managers are (see the NSDocumentController in Mac OS X). Since the application only has one set of Postcode data, there is no need to select the "current" document or manage a set of Core Data persistence stacks but this class is where that behavior would be added if needed in future.

The PostcodesController is then acccessed by the PostcodesViewController to get the current context. However, the data this context contains is not used directly; it is cached by the NSFetchedResultsController as a separate set of data and from there it is used to populate the table view.

Map data

Map data in the application consists of three parts:

The map "tiles" (the street map shown in the view)
The "current location" (which is either the result of a selection or the GPS location).
The array of pins displayed in the map

The actual map tiles are loaded by the MKMapView that Apple's MapKit provides. We don't really need to worry about that.

The selected location or GPS location is a little trickier. This either comes from the user's selection on a previous screen or from the CLLocationManager (which supplies us with location data from the GPS). If this was used by multiple views in the application, then we would need a special class to manage the current location for the whole application (like the PostcodeController manages the postcode database for the whole application) however, we only need location data on the map screen, so the MapViewController which manages this screen can handle this.

The array of pins displayed on the map is really just a selection of the data from the postcodes database, selected using criteria from the current location. Again, since this is only used on the map screen, so it can be controlled by the MapViewController as long as the difficulty of doing so remains low.

List of menu items

Sometimes, data is so simple to load and so customized to the location where it will be used that managing it is no concern at all. The array of dictionaries that provides the structure for the "Main Menu" in the program is a good example of this — the data can be read in a single instruction, its format is written to match the format that the "Main Menu" wants, it has no state to maintain and doesn't require any editing.

Program construction

This program started with a "Navigation-based application" template in Xcode and the project name "AustralianPostcodes". This means that the following steps are setup by the template:

The UIApplication will load the MainWindow.xib on startup
The MainWindow.xib will construct the AustralianPostcodesAppDelegate, a UIWindow and a UINavigationController which will load the RootViewController from RootViewController.xib and set it as the top level view in the navigation hierarchy.
The AustralianPostcoddesAppDelegate will insert the UINavigationController's view into the UIWindow and display the window.

The primary controllers in the program are the PostcodesController (which controls the construction of the Core Data persistence stack), the RootViewController (which shows the main menu), the PostcodesViewController (which displays the table of objects fetched from Core Data) and the MapViewController (which displays a single Postcode object and the map view).

Constructing the RootViewController

The RootViewController needs to display its list of options in the table. When any row in the table is tapped, a new UIViewController subclass will need to be constructed and pushed onto the UINavigationController.

Due to the data-configured nature of the RootViewController, the subclass of UIViewController constructed and any parameters passed into its initializer are all specified in the data file.

This means that this class is incredibly simple. The three different rows perform three different tasks:

Load a PostcodesViewController and sort by postcode
Load a PostcodesViewController and sort by suburb
Load a MapViewController and use the GPS for location data

But the differences come from the data. The work done by the RootViewController is the same in each case.

Constructing the PostcodesViewController

This class displays the postcode data but it has to perform four tasks as part of that job:

Fetch the sorted (and possibly filtered) postcodes from the database
Construct/configure the table view cells to display the fetched results in the table
Respond to changes in the search string by refetching the data
Respond to taps on a row by loading a MapViewController to display the map

In this case, much of the first step is handled by a standard NSFetchResultsController. This class is designed to work closely with the UITableView so it makes sense to keep this work close to the view. If we weren't using an approach so closely tied to the view, it would also be possible to put a fetch method in the PostcodesController and pass parameters to it so that it prepared the data in an appropriate format.

When a row is selected, the Postcode object (the subclass of NSManagedObject associated with the selected row) is passed into a newly constructed MapViewController.

Constructing the MapViewController

The MapViewController needs to perform the following tasks:

If not given a selected Postcode object, then the Postcode in the database nearest the GPS location must be fetched.
Postcodes around the current location must be fetched and displayed on the map
The map view must be centered on the selected postcode
Details about the selected postcode must be displayed in the UILabels at the top of the screen.

To enable the easy display of postcodes as points on the map, the Postcode class (the subclass of NSManagedObject used by the Postcode entity in the Core Data model) implements the MKAnnotation protocol. This means that the Postcode objects returned from a fetch can be immediately added to the MKMapView.

This class needs to perform its own fetching from the Core Data database. Since the PostcodesViewController and MapViewController both need to fetch (albeit in slightly different ways) and they both use a significant volume of code of to do this fetching, it is possible that a common interface to perform fetch actions for both would be a future improvement.

Always be ready to iteratively refactor
As you implement a program, you should always be on the lookout for easy ways to simplify your program by implementing minor redesigns. Looking for multiple places where your program repeats the same functionality is the most prominent example of this. A corollary to this is that you should never copy and paste blocks of code — a copy and pasted block of code should be a single method/function/macro that you simply invoke from multiple places.

Model-View-Controller

Interpreting this program according to model-view-controller would go like this:

Model — the Postcode objects in the NSManagedObjectContext are the model.
View — the UITableViewCell objects on the "Main Menu", "By suburb" and "By postcode" screens and the MKMapView on the map screen.
Controller — the AustralianPostcodesAppDelegate, RootViewController, PostcodesViewController, MapViewController, PostcodesController.

Why do we need so many controllers?

An interesting point to note is that every class in the project (with the exception of Postcode) is a controller class.

Why do we need so many controllers? The answer is that we have a normal number of controllers — the correct analysis is that we have is an absence of custom model and view objects.

A well written model object or view object needs no custom code for customization — the construction provided by the controller and the data (provided from configuration files on construction or from model objects when loaded) is all the customization that they require.

I've written posts about drawing customizing table views without subclassing any views — the customization comes from how the view is constructed and set up.

On the model side, NSManagedObject is configured by the .xcdatamodel file and can be used without further configuration if desired. Similarly, NSDictionary is used by the RootViewController to hold custom structure data without need for custom behavior.

Obviously you will probably need custom model and view objects at some point but the fewer you have, the easier things will be.

A simple diagram of the program

Generally though, I don't like this type of over-simplification. My problem is that while it does describe a single Model-View-Controller path through the program, this program has multiple sources of data and each source of data is managed at a different point and displayed in a different way.

A different way to think about application design

Despite the simplistic diagram shown above, the reality is that we have the following model-controller relationships in the program:

The Postcodes in the NSManagedObjectContext, controlled by PostcodesController
The Plist which describes the Main Menu, controlled by RootViewController
The cached fetch of Postcodes by suburb or postcodes, controlled by NSFetchedResultsController in conjunction with PostcodesViewController
The cached fetch of nearest Postcodes, controlled by MapViewController
The GPS location, controlled by CLLocationManager

So a full diagram of the data paths through the program would be considerably more complex than the diagram shown above.

An important point to note about the above diagram is that there are two layers of controllers: one layer that controls the model at the top and one layer that controls the views at the bottom. The result of this observation is that the view-and-controller pairs and the the model-and-controller pairs are really two instances of the same design pattern. This means that we can add the following view-controller relationships to the list of model-controller relationships shown above:

The UITableViewCells in the UITableViews, controlled by PostcodesViewController and RootViewController
The UILabels and the MKMapView, controlled by the MapViewController

Module-controller

What this does is to break the entire program down into pairings of:

Class that "does" something (store data, display data, fetch data)
and Controller which loads and configures it

Your program is then a hierarchy of controllers (UIApplication/AppDelegate, Document controller, UIViewController subclasses) which load and configure their own modules (.xib files and windows, Core Data, UIView classes) to perform their actual work — but these modules have no connections to the rest of the program, they rely entirely on the controller to set them up, provide their data and make them work.

As your program grows larger and more complex, your controllers may have sub-controllers — in fact, your module objects may become controllers to their own sub-module objects. Through this structure, you can have a giant program but each element is still simple within itself. Simplicity remains as the program grows because every individual element is self-contained.

Implications of this way of thinking

The best programs are highly modular and decoupled
A good application has tightly focussed modules which are totally decoupled from the rest of the program and controllers which are lightly coupled to other controllers in a hierarchical arrangement through the program but do nothing other than provide the contextual information for their controlled objects.

The idea is to make all aspects of your program clean, decoupled and resusable, in the same way that good view and model classes are.

I prefer this way of thinking about application design. In essence, treat every data object, every network connection and every view object in the program (any class which "does" something) in the same way: like its own independent module. These independent module classes should:

have their own controller which loads and configures them
not have a connection (pointer or reference) to any other part of the program (except other objects within the module)

If you feel like one of these module objects needs to access another part of the program, try to redesign so that the controller pushes the information to the modular class, instead of the module object fetching for itself.

The corollary to this is that your controller objects should, as much as possible, avoid "doing" anything except constructing and configuring these document-like objects. Controllers may have a lot of code compared to the module classes but that code should always be responding to a change from a module object and passing a message to another module or constructing another module. Controllers are all about setup, reactions and inter-module communication.

Most of the time, the module objects controlled by the controller will not be your own special subclasses — often they're just default NSDictionary objects or UIViews or NSManagedObjects — but it is important to keep the module object and controller relationship in mind to help guide how you write your program.

Keep the main advantage of Model-View-Controller thinking

Even if you do start thinking about every component in your program in module-controller terms, you shouldn't drop the key advantage of Model-View-Controller — to focus your application around the workflow of your "model".

Specifically: you should always know what the "model" of your program is. All aspects of your program should be directed towards showing, editing, displaying that data. Even if lots of other modules, tasks and activities are implemented as part of the overall process, they should not disrupt the model's workflow.

Conclusion

You can download the complete project AustralianPostcodes.zip (961kB).

I wrote a lot of code for this post but I've included none of it here. The code exists to make the abstract discussion about how to design a program seem less abstract — I hope that you can look at the code and understand the sometimes vague statements I've made in this post.

The first half of the post was about identifying the data your program has and then identifying how to build the controllers in your program to load and display this data. The purpose of going through these steps is to explain that these are the details you must have clear in your mind before you start writing code. Programming requires — above all else — that you be able to absolutely and unambiguously clarify your idea.

The second half of the post was about module-controller relationships. The purpose here is not to say Model-View-Controller is wrong but to point out that the purpose of Model-View-Controller is decoupled, reusable modules with all construction and context provided by hierarchy of lightly coupled controller objects running through the spine of your program — and that this is a pattern that can be applied repeatedly (and even recursively) throughout your program, not just to views or your main model.

There's a Garbage Collection ninja hiding in the project templates

2009-12-01T00:17:00.001-08:00

Not all Xcode project templates are alike. Especially the Core Data Command Line Tool...

An unwanted feature jumped out and attacked me!

In yesterday's post on implementing a CSV parser, I briefly mentioned that the parser took around 0.28 seconds to parse the test data that I provided. I consider this a good time for the parser to take but my first run was not so quick.

The first timing test I ran gave a parsing time of 1.15 seconds. This was slightly shocking to me, since I had already run a "control" test — where I just used componentsSeparatedByString: to break into lines and then into fields — that took just 0.95 seconds.

Had I really spent all that time writing code that was 20% slower (albeit more functional) than a clumsy, brute force approach?

No. As it turns out, the Xcode Project Template I had used for the test project, the:

Mac OS X→Application→Command Line Tool→Type:Core Data

project has Garbage Collection enabled by default.

The only real hint that this template is different is the objc_startCollectorThread() line in the default main() function — of course, I never saw this line because I always replace the source files in the templates with my own versions that follow my own formatting style.

Anyway, I turned Garbage Collection off and... boom 4 times faster.

I'd ask for more warning about these major — but subtle — changes to templates in the future but you know... ninjas, what can you do?

Writing a parser using NSScanner (a CSV parsing example)

2009-11-30T02:56:00.001-08:00

Comma-separated value (CSV) files are one of the most commonly used data formats for exchanging rows of simple data. There are many implementations of CSV parsing for Cocoa strings but the purpose of this post is to use the example of an RFC4180 compliant CSV parser implementation to show you the basics of writing a recursive descent parser for importing data into your Cocoa applications.

Introduction

CSV parsers for Cocoa already exist: Drew McCormack at MacResearch has a good article covering his implementation of a CSV parser and cCSVParse will also do the job. Instead of CSV and the implementation itself, I'm going to try and focus on reading a parser grammar and adapting that into a program of your own.

Most common solutions for parsing CSV files involve quick parsers which don't consider the full format and instead just split strings into lines using -[NSString componentsSeparatedByString:@"\n"] and then split lines into columns with -[NSString componentsSeparatedByString:@","]. This will work for some cases but it does not handle all aspects of RFC4180 and is limited to simple CSV files.

The technical description of a CSV file

Adapting slightly from RFC 4180 - Common Format and MIME Type for Comma-Separated Values (CSV) files, the Extended Backus-Naur Format (EBNF) grammar for a CSV file is as follows:

characters up to the next double quote character, separator string or lineSeparator

If you're not accustomed to reading EBNFs, the very first line here (the "file" line) states that a CSV "file":

optionally has a "header", which if used must be followed by a "lineSeparator"
must have a "record"
the first record may be followed by any number of "lineSeparator" plus "record" entries.

The grammar shown here is slightly less restrictive than RFC4180 in that it allows any data (not just the CSV subset of US-ASCII) in the "textData". I'll also implement the parser so that different separators (including any string that contains no new line or double quote characters) can be used instead of commas. The implementation will also support Unix newlines or classic Mac carriage returns can be used instead of DOS "\r\n" line separators.

Design of the parser

The parser will be a form of recursive descent parser, which is the easiest way to implement most simple grammars like the one above. The idea is that we write a method for each line of the grammar. If any line contains a reference to another line, the implementation method will attempt to descend into the method for the referenced line.

If you're accustomed to the lex/yacc school of thought and are curious to know if the approach will similarly split tokenizing and parsing into separate stages: yes, it will. Most of the tokenizing is done by NSScanner (although it presents each token as requested, not as a pre-prepared stream). The code we actually implement will predominantly deal with the parser/generator side.

Initialization of the parser will be handled by the following method:

- (id)initWithString:(NSString *)csvString
    separator:(NSString *)separatorString
    hasHeader:(BOOL)hasHeader
    fieldNames:(NSArray *)fieldNames;

The structure of CSV files means that it is difficult to guess if the header line is actually present — so we need to tell the parser whether to look for it. An array of names for fields can be provided if there is no header (if no names are provided, they'll be given names with the format "FIELD_X").

The parsing will be initiated by invoking either:

- (NSArray *)arrayOfParsedRows;

where the result is an NSArray of NSDictionary objects or with:

- (void)parseRowsForReceiver:(id)receiver selector:(SEL)receiverSelector;

where the method receiverSelector must take a single NSDictionary parameter. This second method does not return the entire result but instead sends each row as it is parsed to the receiver. It is more efficient since it does not need to keep copies of all row data.

Parser methods

There are two types of parsing methods that we need to implement:

Structural methods which don't directly access the string (parseFile, parseHeader, parseRecord, parseName, parseField, parseEscaped, parseNonEscaped)
Tokenizing methods which use NSScanner to access the string (parseDoubleQuote, parseTwoDoubleQuotes, parseSeparator, parseLineSeparator, parseTextData)

I'm not going to show all of them here (you can download the full code to see them) but I will show one of each type.

The tokenizing methods are the easiest. All they do is invoke NSScanner methods.

- (NSString *)parseLineSeparator
{
    NSString *matchedNewlines = nil;
    [scanner
        scanCharactersFromSet:[NSCharacterSet newlineCharacterSet]
        intoString:&matchedNewlines];
    return matchedNewlines;
}

The structural elements have a bit more to do but are still fairly simple. The "escaped" element in the grammar has the following structure:

doubleQuote {textData | separator | lineSeparator | twoDoubleQuotes} doubleQuote

This structure is directly reflected in its implementation — it starts and ends with a check for "doubleQuote" and loops over checks for "textData", "separator", "lineSeparator" or "twoDoubleQuotes" in the middle.

- (NSString *)parseEscaped
{
    if (![self parseDoubleQuote])
    {
        return nil;
    }
    
    NSString *accumulatedData = [NSString string];
    while (YES)
    {
        NSString *fragment = [self parseTextData];
        if (!fragment)
        {
            fragment = [self parseSeparator];
            if (!fragment)
            {
                fragment = [self parseLineSeparator];
                if (!fragment)
                {
                    if ([self parseTwoDoubleQuotes])
                    {
                        fragment = @"\"";
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        
        accumulatedData = [accumulatedData stringByAppendingString:fragment];
    }
    
    if (![self parseDoubleQuote])
    {
        return nil;
    }
    
    return accumulatedData;
}

An interesting point to note is that most parsing stages return the text that they parse. However, when parseTwoDoubleQuotes is used, we instead append just one double quote character, since the two double quotes is actually an escape sequence representing one.

Lookaheads

The most annoying feature to implement in a recursive descent parser is a lookahead — this happens in the parseTextData method.

Lookahead is required because of my choice to accept separator strings longer than a single character. This means that the "textData" element will end with any of:

\r
\n
U+0085
"
the separator string

Unfortunately, NSScanner can't scan until it reaches one of these 5 elements. The best we can do is create a character set from the first four and the first character in the separator string and use scanUpToCharactersFromSet:intoString:

When scanning through text data, if we reach the first character of the separator string, we need to scan ahead and see if it is actually the whole separator string. The whole separator string will terminate the "textData" without being added, otherwise we backtrack and add the character to the existing "textData" and continue scanning.

If NSScanner had a scanUpToStringFromArray:intoString: method, this lookahead could be avoided (or at least shifted out of our code and into NSScanner). But this method does not exist and it looked like too much work to efficiently implement as part of this post.

The sample program

The sample program that I've provided uses this parser to parse a 1.7 MB CSV file containing 16,081 Australian postcode entries, names and longitude/latitudes (data from SixFive.co.uk). As results are parsed, they are entered into a Core Data SQLite file.

The whole process takes about 0.47 seconds on my Mac Pro with parsing taking 0.28 seconds of this time and Core Data object creation taking 0.19 seconds. I'm sure a more carefully coded parser could halve this time or better but it represents good performance for minimal effort.

Conclusion

You can download the CSVParser class and CSVImporter sample project (315kB).

The aim in this post was to present a complete, flexible CSV parser while making the code as easy to read as possible. I hope that it has shown how you can import data from unconventional formats into Cocoa-friendly formats easily while obeying the more minor quirks that many formats have.

The type of parser presented here is a recursive descent parser. This is the easiest parser to implement for simple grammars. However, this is not how commercial parsers are written — larger parsers use generated action and goto tables to handle their branches instead of manually written methods and code. Have a look at the Wikipedia entry on LR parsers for more on how this is done.

Performance tests: Replacing Core Data Key Paths

2009-11-21T00:31:00.001-08:00

In Mac OS X 10.5, Core Data switched from using valueForKey: as the recommended way to access Core Data attributes and relationships to auto-generated accessor methods. This new approach is faster for fetching values but lacks NSKeyValueCoding's ability to coalesce the values extracted from every object in a "to-many" relationship in a single statement.

In this post, I'll look at replacing the NSSet traversal and NSSet coalescing abilities offered by NSKeyValueCoding with an approach that invokes accessor methods directly to see if I can bring some of the performance improvement of auto-generated accessor methods to situations involving NSSet traversals.

Accessing the attributes and relationships of an NSManagedObject

In this post, I'll look at performance in a Core Data program using the following model:

If you're not familiar with Core Data entity diagrams, the important point here is that every Company can have multiple Projects and every Project can have multiple Employees

Given this model, if I have a pointer, aCompany, which points to one of the Company objects, getting the company's name is straightforward:

NSString *companyName = aCompany.name;

The name property accessed here is implemented in an auto-generated accessor method that NSManagedObject provides for us.

Before Mac OS X 10.5, the only way of accessing values in Core Data was using key value coding:

NSString *companyName = [aCompany valueForKey:@"name"];

Why was the change away from key value coding made? The main reason was performance (although improved syntax and type-safety also helped). Fetching the name one million times using key value coding takes 0.284016 seconds but using the auto-generated property accessor method this drops to 0.109017 seconds — 2.6 times faster.

Set traversal

But key-value coding (the "old" method) still has one important advantage over the auto-generated methods: it's quicker when traversing a set returned from a 'to-many' relationship.

For example, if I want to get the full set of Project names used by aCompany it is easy with Key Value Coding:

NSSet *projectNames = [aCompany valueForKeyPath:@"projects.name"];

This works because the NSSet implementation of the NSKeyValueCoding protocol automatically traverses into itself to get the names for each Project object it contains.

Using the accessor methods, the naïve equivalent would be:

NSMutableSet *result = [NSMutableSet set];
for (Project *project in aCompany.projects)
{
    NSString *name = project.name;
    if (value)
    {
        [result addObject:value];
    }
}

Not only is this more code than the key value coding approach but it is actually slower. For 10,000 Company objects, each with 100 Project objects, the key value coding approach took 0.25692 seconds and the naïve approach using auto-generated accessors took 0.52873 seconds.

The new and improved approach has gone from 2.6 times faster to 2 times slower.

Fixing the speed problems

The old method got faster

Before I get to why the "new" method was slower, the first point to notice is that the key value coding approach (the "old" approach) was actually faster when using set traversal. Despite the extra work involved in traversing from the Company to the Project and uniquing the names to form a single NSSet, the key value coding took just 0.25692 seconds to fetch one million Project names, down from the 0.284016 seconds to fetch one million Company names.

This isn't a glitch; despite more work involved, Key Value Coding improves its performance when sets are iterated internally (as part of the key path) rather than externally (as I did when iterating over one million Company objects).

Despite its improvements, we should still be able to beat Key Value Coding with our approach using the auto-generated accessor methods but the margin is obviously going to be a lot closer than it was for the aCompany.name iteration..

Fixing the new method

Basic profiling quickly reveals that the problems here have little to do with the actual property accessors. The slow speed is primarily due to addObject:

After looking at the private methods on the stack in the profiler, it became clear that the reason was reallocation. Every time the NSMutableSet needed to grow in size, it was reallocating its internal storage, resulting in the poor performance.

We can pre-allocate the entire set based on the worst-case size (all Project names unique). The code then becomes:

NSSet *projects = aCompany.projects;
NSMutableSet *result = [NSMutableSet setWithCapacity:[projects count]];
for (Project *project in projects)
{
    NSString *name = project.name;
    if (value)
    {
        [result addObject:value];
    }
}

Success! This version now runs in 0.19104 seconds (down from 0.52873 seconds) and is now 25% faster than the key value coding approach.

We're no longer 2.6 times faster but NSSet's internal implementation of Key Value Coding has some advantages over us here: since it has internal access to the storage, it can optimize the iteration over the "to-many" relationship and the building of the new set more than we can.

A category implementation

To reuse the above approach in future, we can implement a category on NSSet.

There will be two methods:

objectValuesForProperty:
coalescedValuesForProperty:

The first will implement the previously mentioned example (where the NSSet contains basic objects).

The second will replicate the Key Value Coding operator @distinctUnionOfSets (to handle the case where the NSSet contains an NSSet and you need to coalesce the objects inside the child sets).

An example of this second case is getting all the Employee objects at a Company. In Key Value Coding we would write:

NSSet *allEmployees = [aCompany valueForKeyPath:@"projects.@distinctUnionOfSets.employees"];

With the coalescedValuesForProperty: method, we could write:

NSSet *allEmployees = [aCompany.projects coalescedValuesForProperty:@selector(employees)];

The implementation is then:

#import <objc/message.h>

@implementation NSSet (PropertyCoalescing)

- (NSSet *)objectValuesForProperty:(SEL)propertySelector
{
    NSMutableSet *result = [NSMutableSet setWithCapacity:[self count]];
    for (id object in self)
    {
        id value = objc_msgSend(object, propertySelector);
        if (value)
        {
            [result addObject:value];
        }
    }
    return result;
}

- (NSSet *)coalescedValuesForProperty:(SEL)propertySelector
{
    NSInteger count = 0;
    for (id object in self)
    {
        count += [objc_msgSend(object, propertySelector) count];
    }
    NSMutableSet *result = [NSMutableSet setWithCapacity:count];
    for (id object in self)
    {
        id value = objc_msgSend(object, propertySelector);
        if (value)
        {
            [result unionSet:value];
        }
    }
    return result;
}

@end

With the coalescedValuesForProperty: method we iterate over the whole set twice to get the size but this remains the fastest option — in fact, this method is about 35% faster than the Key Value Coding approach compared to objectValuesForProperty:'s 25% improvement.

Conclusion

By request, here's the code used in the testing: PropertyAccessors.zip (32kB). It's hastily thrown together to accompany this post, so it's not necessarily well written but it's there if you're interested.

I wrote this code and ran these performance tests because I have a lot of code that uses Key Value Coding for traversing "to-many" relationships. I was concerned that since Core Data advocates the use of the auto-generated accessor methods for performance reasons, that my use of key value coding in these cases would be significantly slower than it should be.

The result is that while it is possible to improve upon the performance of Key Value Coding for traversing sets in Core Data, the improvement is only 25-35%, not the 260% improvement from replacing Key Value Coding for individual property access. Key Value Coding is quite efficient when dealing with sets — certainly more efficient than it is when accessing single properties.

Of course, the 35% speed improvement offered by the approach presented here will certainly be beneficial in performance critical areas.

With regards to the implementation itself: never underestimate the performance impact of keeping memory reallocations at a minimum. Starting with a zero capacity NSSet and continually growing it using addObject: was 3 times slower than allocating once.

The capacity of the NSMutableSet allocated is large enough to hold all objects but if the objects are not all unique, this will be bigger than required. If this extra memory usage is a concern, you can copy the set once it is generated. The copy will be only as big as strictly required and you can release the original. The drawback is that this copying process will add another 10-15% onto the time taken.

A drop-in fix for the problems with NSHost

2009-11-14T04:45:00.001-08:00

As pointed out by Mike Ash in his recent Friday Q&A 2009-11-13: Dangerous Cocoa Calls, NSHost is not thread-safe for use outside of the main thread and due to potentially slow, synchronous network access is not really suitable for use on the main thread either. Fortunately, in Cocoa there are often ways to transparently fix classes that don't work as they should. In this post, I'll show you how you can transparently patch NSHost using a drop-in solution and provide a non-blocking solution for NSHost lookups.

NSHost

NSHost is a class with a simple API that fetches the names or addresses of an internet host. You can use it to perform DNS lookups but one of the primary uses is to get the name and address of the current host.

All calls to NSHost are synchronous — they block until the response is fetched. If a network error occurs, this could result in a 60 second delay before a timeout response occurs — definitely not something you want to do in your main thread.

Unfortunately, according to Cocoa's Thread Safety Summary, NSHost is not thread-safe — so we can't simply pass the functionality off to another thread.

Does this mean you must revert to NSHost's CoreFoundation equivalent, CFHost, which is explicitly thread-safe? Not necessarily.

The problems we need to fix

It is not the NSHost objects themselves that are the problem. NSHost objects are immutable once allocated and immutable objects are implicitly thread-safe for most purposes.

The problem is the cache of NSHost objects maintained internally by NSHost when any of the lookups are called — access to this cache is unprotected from the perils of threading.

In addition to this, we need to be able to perform NSHost lookups asynchronously.

Design of the solution

The key consideration in these changes will be a totally drop-in solution — NSHost will immediately and transparently become thread-safe. No further code will be required.

The solution to the threading problem will be to create a corresponding category method for every class method of NSHost which wraps all calls to NSHost in a @synchronized section and then in the load method for the category, swizzle each of these corresponding methods into the place of the original method.

The asynchronous invocations can then be handled like any other asynchronous operation — by spawning a new thread which will call back when complete.

Swizzling alternate implementations

If you don't know what I meant by "swizzle", what we need to do is replace the existing implementations of the NSHost class methods with our own implementations. The code for doing this is as follows:

static void SwizzleClassMethods(Class class, SEL firstSelector, SEL secondSelector)
{
    Method firstMethod = class_getClassMethod(class, firstSelector);
    Method secondMethod = class_getClassMethod(class, secondSelector);
    if (!firstMethod || !secondMethod)
    {
        NSLog(@"Unable to swizzle class methods for selectors %@ and %@ on class %@",
            NSStringFromSelector(firstSelector),
            NSStringFromSelector(secondSelector),
            NSStringFromClass(class));
        return;
    }
    
    method_exchangeImplementations(firstMethod, secondMethod);
}

Then, in the load method for our category...

@implementation NSHost (ThreadSafety)

+ (void)load
{
    SwizzleClassMethods(self, @selector(currentHost), @selector(threadSafeCurrentHost));
    SwizzleClassMethods(self, @selector(hostWithName:), @selector(threadSafeHostWithName:));
    SwizzleClassMethods(self, @selector(hostWithAddress:), @selector(threadSafeHostWithAddress:));
    SwizzleClassMethods(self, @selector(isHostCacheEnabled), @selector(threadSafeIsHostCacheEnabled));
    SwizzleClassMethods(self, @selector(setHostCacheEnabled:), @selector(threadSafeSetHostCacheEnabled:));
    SwizzleClassMethods(self, @selector(flushHostCache), @selector(threadSafeFlushHostCache));
    SwizzleClassMethods(self, @selector(_fixNSHostLeak), @selector(threadSafe_fixNSHostLeak));
}

// category continues...

What this does is swaps in our new implementations, (e.g. threadSafeCurrentHost) in place of Apple's original implementation (e.g. currentHost). Once this is done, any call to currentHost will result in our new code getting executed. Similarly, the original code that we replaced is now reachable by calling threadSafeCurrentHost.

The implementation of each of these thread-safe methods takes the form:

+ (id)threadSafeCurrentHost
{
    @synchronized(self)
    {
        return [self threadSafeCurrentHost];
    }
}

This may look like the method is just calling itself but remember, after swizzling, the call to threadSafeCurrentHost will actually invoke the original currentHost code. So this method is actually running the original code but inside a @synchronized section to maintain thread safety.

Asynchronous lookup

The best way to perform an asynchronous lookup, now that NSHost will work in a thread-safe manner, is simply to perform the lookup in an NSOperation and have that operation call back when done.

To do this, the ThreadSafety category also adds the methods:

currentHostInBackgroundForReceiver:selector:
hostWithName:inBackgroundForReceiver:selector:
hostWithAddress:inBackgroundForReceiver:selector:

to perform lookups and call back when done. These methods take the following form:

+ (void)hostWithName:(NSString *)name
    inBackgroundForReceiver:(id)receiver
    selector:(SEL)receiverSelector
{
    [[self hostLookupQueue]
        addOperation:
            [[HostLookupOperation alloc]
                initWithReceiver:receiver
                receiverSelector:receiverSelector
                receivingThread:[NSThread currentThread]
                lookupSelector:@selector(hostWithName:)
                lookupParameter:name]];
}

and the implementation of the HostLookupOperation's main method is extremely simple:

- (void)main
{
    [receiver
        performSelector:receiverSelector
        onThread:receivingThread
        withObject:[NSHost performSelector:lookupSelector withObject:parameter]
        waitUntilDone:NO];
}

Conclusion

You can download the complete code for NSHost+ThreadedAdditions (3kB).

The main advantage of this approach shown here is that you only need to add the files to your project — you do not need to add or change any other code to make this work.

These additions provide reasonably good thread safety for NSHost as they channel all use of the class through the thread-safe wrapping methods. The limitation to this is that Apple could add further methods in the future that circumvent the @synchonized sections we've added and the thread safety would be breached until swizzled methods were added for these new methods.

On the immutability of NSHost instances — technically, the private instance variables names and addresses of NSHost are allocated mutable but experimentally, I have verified that they are never mutated (in fact, there are no methods on NSHost that would do this). However, localizedName, available in Mac OS X 10.6, uses data from outside NSHost so might not be thread-safe.

In reality, you can avoid all of this code and simply use the CFHost API to achieve the same benefits. This ThreadedAdditions category for NSHost is an effort to continue using the simpler API of NSHost and at the same time, to demonstrate that just because Apple's implementation of something is not thread-safe in its internal implementation, doesn't mean you can't make it thread-safe in the greater context of your whole program.

Creating iPhone and Mac icons using Inkscape (Part 2 of 2)

2009-11-06T22:59:00.001-08:00

In this part, I expand on the simple techniques presented in the first part by adding different line, effect and texture styles. I'll also present some Mac application icons and simple texturing.

Introduction

This series covers the creation of the following different icon styles:

The first icon was created in the first part of the series. I'll go through the creation of the remaining variations on the checkbox/checkmark theme in this post.

I'll assume that you've read the first part or are familiar with the techniques involved.

Icon 2: A brighter, more colorful iPhone icon

Goals in this section

Use a radial gradient
Learn to adjust all of the common stroke properties
Learn to adjust a multi-effect filter

The icon developed in Part 1 is very simple — really just a couple white lines over a typical iPhone icon background — which is appropriate for a serious application but might not stand out as prominently against other icons.

In this variation, I'll have the background reach a bright point behind the checkbox element and change the effect on the lines so that the lines look embossed into this bright point — visually integrating the background and the overlayed element.

I'll also introduce a complimentary (opposite hues) color scheme with an azure blue and a red.

A radial background

Starting with a 57x57 document as created in Part 1, add a rectangle filling the document area.

Set the fill to a radial fill and edit the gradient. In the Gradient Editor, click "Add Stop" twice to make the gradient a four part gradient. Top to bottom, the four gradient colors should be:

RGBA=(192,255,250,255)
RGBA=(99,164,184,255), Offset 0.26
RGBA=(5,74,119,255), Offset 0.62
RGBA=(0,40,80,255)

We now have a bright spot in the center of the background.

Over the top of this, paste (or recreate) the starburst effect from Part — X,Y=(-15.7,-15.7) should center it perfectly.

In the Fill and Stroke palette, set the opacity of the starburst to 100%.

Now, to make the starburst smoother, open the Filter Editor (from the Filters menu) and find the starburst's blur effect (it should be selected in the filter column when the starburst itself is selected). Select the Gaussian Blur effect and set the standard deviation to 0.75.

Different stroke properties for the checkbox and checkmark

Create the checkbox and checkmark in the same way that they were created in the first part or copy them in. If you copy them in, select both the checkbox and the checkmark and choose Filters→Remove Filters to remove the shadow and bevel effect applied in the first part.

Remove the corner radius from the checkbox (select it using the rectangle tool and set the Rx and Ry to zero). In the Fill and Stroke Editor, select the Stroke Style Tab and set the Line Width to 4.0 "px" and the Join Style to rounded. The result of these steps is to create a slightly thicker line that is curved on the corners within its width.

Select the checkmark and set the stroke color to RGBA=(255,42,42,255) and the stroke width to 4.0 "px".

A customized "Cutout glow"

With both checkbox and checkmark selected, choose Filters→Shadows and Glows→Cutout Glow. Go to the Filter Editor and find this Cutout Glow filter. This filter will have 5 effect rows. Select the Offset row and set the X,Y offset to (0.8,0.8). Select the Gaussian Blur row and set the Standard Deviation to 1.0.

Now follow the instructions from the "Apply the gloss effect and round corners" subsection of the previous post to complete the icon.

Icon 3: A cartoonish style

Goals in this section

Directly edit paths for greater control
See a Path Effect (Spiro Spline) in action

This variation will forego the starburst effect and instead go for a smoother, more "cartoonish" approach. The checkbox and checkmark will then need to be more distinctive as they will be the only significant graphical elements

Creating a path

Start with the background rectangle from the "brighter, more colorful iPhone icon" created above (if you created a cloned version for the round corners, don't copy the cloned version as it will behave strangely).

Select the Bezier Path tool (11th icon down in the Tool Area). We'll draw the rough loop first.

You can use the Bezier Path tool in one of two ways: simple click-and-release to create corner points and straight line segments or click and drag to create curve points (the dragging then affects the curvature of each point).

For simplicity here, I'll show you how to create the path using corner points and we'll apply the curve as a second step. When you're more comfortable with the Bezier Tool, this can be done as a single step.

Create a point at the 12 o'clock position, then 9, 6, 3 and then underneath the original 12. Then another inside the second twelve and then inside the 3, 6, 9, and between the first and second 12's. Then close the path by clicking on the first point.

Bezier path creation: If you make a mistake with the path, you can either fix it later or press escape to cancel the whole path. Pressing the return-key will end the path without closing it.

Adjusting path control point properties

Using the Node Tool (2nd icon down in the Tool Area) ensure the path you just created is selected. Drag a selection box around the nodes at 3, 6 and 9 o'clock (don't select the nodes at 12 o'clock). In the toolbar at the top, select the "Make selected nodes smooth" button (should be 8th from the left in the toolbar immediately above the window).

Applying a path effect

Leaving the path selected, choose the Path→Path Effect Editor menu item. In the Path Effect Editor palette, select "Spiro Spline" from the popup menu and click the "Add" button. The "Spiro Spline" is an effect that makes smooth curved paths much easier than regular Bezier curves.

Once this is done, you can tweak the nodes in the path (using the Node Tool) until it is the exact shape desired.

In the Fill and Stroke Editer, remove any stroke, apply a faded yellow to faded orange linear gradient fill from left to right across the checkbox loop and it is done.

Stroke to path

Create the checkmark as for the previous icons but set the Stroke Width to 6 "px" and the Style Join and Cap to square corners. With the path selected, choose the menu item Path→Stroke to Path. This will turn the line into a filled path. Set the stroke of this path to "no stroke" and set the fill to an orange to red linear gradient fill from left to right across the checkmark.

Now we need to adjust the checkmark to have a looser aesthetic. Select the Node Tool and the checkmark. Drag the lines in the short stem upwards slightly and the lines in the long stem inwards slightly. Adjust the control points at the ends of each stem so that they are flared outwards a little.

Follow the instructions from "Bevel effect and shadow" from Part 1 to apply these effects. Follow the instructions from the "Apply the gloss effect and round corners" subsection of the previous post to complete the icon.

Icon 4: A document-based Mac icon

Goals in this section

See the common components of a Mac document-based application icon
Use multiple overlapping gradients to achieve softer gradients
Add a texture to a background by filling with text

In terms of colors and effects, Mac icons tend to be far more subdued than iPhone icons. Where iPhone icons are only shown on the Home screen but are small and need to stand out, Mac icons may sit in the Dock for extended periods and shouldn't be distracting during this time.

For this reason, Mac icon colors tend to be slightly more subdued than iPhone icon colors and are frequently much lighter overall.

While Mac icons are typically larger (an average of around 64x64) they can also be shown at smaller resolutions. The approach to satisfying the size range is normally to compose the icon from two key parts:

An object or item that is easily recognizable in silhouette or at small sizes
Texture or subtler elements that fade away at smaller sizes but add structure and context at larger sizes

Mac icons must also handle a range of different background colors as they may be shown against people's desktop backgrounds, white folder backgrounds or against the near black of a vertical Dock. To achieve good contrast against the background, most icons are generally light in color but with a subtle shadow behind them — not for 3D effect but to contrast with lighter backgrounds. Many icons also incorporate a frame or boundary into the representation which further adds to the strength of the icon's silhouette.

A rotated background

To start the icon, create a 64x64 px document. This size will help us optimize for the expected screen resolution.

Into this, draw a 44 by 50 rectangle. Give it an azure to deep blue linear gradient from left to right and a white 3px stroke.

Using the Selection Tool (first in the Tool Area), select the rectangle. Initially, this will show the resizing arrows around the shape. Click a second time to switch these arrows to the rotating arrows (don't double click as that will switch to the Node Tool). Click and drag one of the corner arrows to rotate the rectangle by 8° (the rotated angle should be visible in the status bar at the bottom of the window while dragging but the exact angle isn't important).

Some effects and another gradient

On its own, a single gradient isn't a very impressive effect. The trick in making a background effect that is both attractive and subtle, is normally to layer a few different effects on top of each other.

With the rectangle selected, select "Path"→"Union". This may seem like a weird thing to do but it actually recreates the object using a path at the rotated orientation. We do this because Effects in Inkscape (like the shadow we're just about to apply) look bad (pixelated) when rotated. Recreating the object at this rotation means the effect will not have a rotation applied.

Copy and paste this rotated rectangle and put the copy next to the original. Apply a drop shadow to the original with 50% opacity, Offset of (1,1) and radius of 1.5.

Now remove the stroke from the copy. You'll notice that without the white stroke covering 1.5 px of the copy, the gradient region of the copy actually looks slightly bigger than the original. We need this shape to be the same size as the colored area of the original, so use the Selection Tool and with the rezize arrows, adjust the two to match (set the color to a flat fill like red and overlap the two objects to make it easier).

Now set the second object to have a top to bottom (parallel to its rotated axis) linear gradient fill with four color points:

RGBA=(168,247,249,255)
RGBA=(144,198,215,0), Offset 0.30
RGBA=(95,144,175,0), Offset 0.70
RGBA=(18,49,106,255)

Since this second gradient is transparent in the middle, it will show the first gradient in varying amounts through the middle. Overlapping the two should result in a softer gradient that vaguely resembles diffuse lighting across a slightly convex surface.

A light text-based texture

The formatting of the following paragraph is not an mistake.

The Text Tool is two icons above the Gradient Tool. Click on the document to create a text object and type the text shown and formatted as above. With the text object selected, choose the Zapfino font from the font popup menu in the top toolbar. I like Zapfino because when zoomed out, it seems ornate and indistinct.

Now use the Selection Tool to scale and position the text object over the other gradient rectangles.

To add a gloss effect over everything, create a 53 by 28 rectangle, with a flat RGBA=(255,255,255,60) fill and no stroke and rotate and position it over the top half of the existing shapes.

The "representative" element

For the representative element, I'll use a checkmark in an orange circle. Create a checkmark line (same as in previous icons) set a white 5 px stroke on the checkmark.

Create a 43 by 43 circle (unlike the Rectangle Tool, you can't specify the size of a circle with the Circle Tool selected. If you want to do this, you'll need to use the Selection Tool). Set a red-orange to yellow-orange radial gradient on the object and no stroke.

Using the Gradient Tool, drag the center control point of the gradient to the bottom-right corner of the circle's bounding box, the endpoint of the horizontal stem to the bottom-left corner and the vertical endpoint to the top-right corner.

With the circle selected, use the menu item Filters→ABCs→Diffuse Light. Then use the Filter Editor to set the Gaussian Blur effect of this filter to a Standard Deviation of 1.0. Then apply a drop shadow to the circle.

Finally, position everything together and the icon is complete.

Icon 5: A circular Mac icon

Goals in this section

See the common components of a Mac "appliance" application icon
Apply effects to a path to make the boundary shape more interesting and more distinct from the background
Create a texture using an effect

A circular icon is constructed in the same way as a rectangular backed icon. The only significant differences are:

gradients tend to be various kinds of radial gradient to give a convex feel to the round shape
the overlayed element will be more centered so it helps if it is less solid (thinner and lighter)

Compose a round icon

Since you've seen how to put together basic shapes and radial fills before, I'll just show you the components I used to create this icon as a graphic:

Notice how bright the elements all are: Mac icons are normally quite bright — you want to avoid a "muddy" effect with too many dark colors.

When composing elements, if one of them is at the wrong depth (overlaps other objects wrong) you can change the depth by selecting the object and using the Page Up/Page Down keys (or by using the "Object"→"Raise"/"Lower" menu items).

Make the checkmark look interesting

The checkmark must stand alone in this icon, which means that it should have a few special effects applied to it so that it doesn't look sterile and boring. I applied the following effects to the checkmark:

Filters→Non-realistic 3D shaders→Comics
Filters→Shadows and Glows→Inner Glow. For this filter, I changed the Flood color to a medium blue and reduced the Gaussian Blur (now the second blur in the Effects list for this object after the Comics blur from the previous effect) to a Standard Deviation of 1.0.
A drop shadow.

To texture the circle, I used the RGBA=(176,112,42,140) circle (middle element shown above) and applied a Filters→Image effects, transparent→Marbled ink effect. This gives a slightly moon cratered look that matches the somewhat planetoid shape of the object.

Conclusion

You can download an Inkscape SVG file containing all the icons and their compositions (482kB).

This two part series has been outside the normal domain of programming information that I provide. However, applications programmers will regularly find themselves needing to create, edit or adjust artwork-related assets in their applications. I hope I've given some useful tips on the way artwork assets are composed and ways you can make your artwork look good, even if it is very simple.

With iPhone or Mac icons, they are typically composed from the same elements:

A background gradient (or two).
A texture or additional effect.
A gloss or lighting highlight.
A foreground element or symbol representing your application which, after the other elements are applied, need only be very simple.

With gradients and effects, it is helpful to use a few so that your icon seems rich on close inspection but to keep each one very subtle since they shouldn't distract or make the icon harder to perceive (in a quick glance, the user shouldn't even see the effects you've added).

Icons do not need to be complex; the most professional icons are often very basic. Lack of artistic skill need not be a hinderance if you keep it simple.

Creating iPhone and Mac icons using Inkscape (Part 1 of 2)

2009-11-03T01:17:00.001-08:00

In this two part series, I'll give a beginner's guide to creating iPhone and Mac application icons using Inkscape — a free, vector illustration program. In this first part, I'll talk about the common styles and traits of icons on the Mac and iPhone and give a step-by-step guide to creating the first iPhone icon in Inkscape.

Introduction

This series will cover the creation of the following different icons:

Only the first icon will be created in this part. The remaining four will be covered in the second part.

It may seem strange to be covering icon creation in a Cocoa programming blog but the icon is an important part of an application and Cocoa is primarily an application programming environment. While larger development teams have dedicated graphic artists to create icons and other artwork assets, the reality is that on smaller teams or on solo projects, a programmer may need to create icons themselves.

The goal of this series is to show non-graphics professionals how to create graphics of an acceptable level for their applications that follow the established visual trends for iPhone and Mac apps.

A vector approach

This post is partly a response to Elite By Design's "Design The iTunes Icon For The iPhone And iPod Touch" which produced an iTunes-style icon at 125x125 pixels in Photoshop.

I wanted to show an alternative approach to the one suggested in that article. This alternative approach has the following advantages:

Entirely vector artwork, so it will scale from 57x57 pixels up to 512x512 pixels as required for App Store submissions.
Rounded corners and gloss are applied to a separate clone of the base artwork so the submission to Apple can be non-prerendered if you choose.
Created using free software as non-professional artists don't always have access to Photoshop.

In addition to detailing iPhone icon creation, the second part will also cover basic Mac icon design.

Established styles

I continue to be surprised when I look at screenshots of the Windows 7 taskbar.

These are the first four icons that a Windows 7 user sees and they are the strangest collection of graphics I've ever seen. They share no obvious visual style; they are all drawn with different perspective, they all have different weights, some are glossy while others are matte, some have line edges while others are self-edged (no lines) and they don't share a color palette.

Icon styles on the Mac

By contrast, icons on the Mac tend to have more in common:

Ignoring the "Finder" icon (which is actually the "Mac OS" icon and predates Mac OS X by about 5 years), these icons come in three distinct styles:

Document applications (rectangular background angled 5-10° left).
Appliance applications (round — or at least non-rectangular — background).
Utilities (orthogonal rectangular background).

Originally, Apple had the guideline that utilities should look like they were "items sitting on a shelf" but only the disk utitilies still follow that guideline.

In addition to these three categories, the icons tend to:

Have approximately the same weight (fill roughly the same amount of their visual area).
Use soft gradients, sometimes (but not always) with a light gloss or highlight.
Use a generally bright but slightly desaturated palette of grays, azure blues, desaturated reds and sandy yellows (utility apps tend to use more blacks and darker colors).
Indicate their function or concept with an overlayed or nested element.
Are self-edged and have almost no internal lines (the outline of the icon is sometimes edged for contrast)

Of course, none of these are immutable but following them will make it easier to create a simple icon that looks like it belongs on the Mac.

Icon styles on the iPhone

The iPhone has a style that is distinct from the Mac:

Aside from the obvious round cornered background and top-down gloss effect, iPhone icons tend to use:

Strongly saturated colors
A bright gradient or colorburst in the background
White silhouetted representative elements over the background

There is certainly variation and some icons that follow their own rules entirely (the "Notes" and "App Store" icons have little in common other than the rounded corners) but the easiest path to creating an icon that looks like it belongs on the iPhone is to incorporate these elements.

Inkscape

The tool that I will use to create the icons is Inkscape. Inkscape is a GPL-licensed SVG-based vector illustration program that you can download from inkscape.org. It is available in a Universal binary for Mac OS X 10.3.9 and newer.

A nice multi-purpose icon but clearly not designed with "standard Mac app" as its primary goal.

You will need X11 installed and pre-Snow Leopard users will need an updated version of X11 (download new versions from here: http://xquartz.macosforge.org/).

Yes, Inkscape is an X11 program, which means that Open/Save dialogs are non-standard, windows may not come to the front when you expect them too and keyboard shortcuts are all Control-X instead of Command-X. Despite this, Inkscape is generally a good program — certainly far better than most X11 applications on the Mac.

If you prefer a different illustration program, most of the techniques in this guide will apply. The Filter Effects and the Path Effects are probably the points that will be most different but I'm sure you can find alternatives.

Page area

Let's start with a blank document in Inkscape.

A new document will appear when you start Inkscape or you can create a new document from the "File"→"New"→"Default" menu.

Go to the "File"→"Document Properties". Set the Default Units to "px" and the custom document size to 57 by 57.

The reason why we set the units and use the actual pixel sizes in a vector program is this will let us align points to whole value boundaries and avoid unnecessary anti-aliasing. For example, drawing a shape with its edge at Y=0.5 will cause the actual shape border to anti-alias across two different pixels when we render at 57x57 pixels but if we set the shape border's Y coordinates to 1.0, it won't have this problem.

The page area will now look tiny in the window. You can zoom in using the middle mouse button (click and drag with the middle mouse button to pan) or the "+" key. Alternately, you can zoom the document area to fill the window by pressing the "5" key.

Zooming: you will need to be comfortable with zooming in the program. The "+" and "-" keys will zoom in and out at any time. The 3 key will zoom to the selection and 4 will show all drawn elements. Clicking and dragging the middle mouse button will pan the document, clicking the middle mouse button will zoom and shift-middle mouse will zoom out.

Creating the glossy round rectangle

The Tool Area is the column of buttons down the left side of the window. The 5th tool from the top is the rectangle tool.

Red round rectangle

Using the rectangle tool, drag out a rectangle to fill the document area.

Open the Fill and Stroke palette (menu item "Object"→"Fill and Stroke" or Control-Shift-F). With the rectangle we created selected in the window, select the Stroke tab of the Fill and Stroke Palette. Make certain there is no stroke (the "X" icon should be selected). Select the Fill tab of the palette. Set a solid color fill (the solid square icon) and use the sliders to set a bright red fill (this is just so that we can see the shape easily).

Quick colors: you can also set solid fill and stroke colors on the selected object by left clicking (fill) or shift-left-clicking (stroke) a swatch at the bottom of the window.

We now need to edit the rectangle properties. Using the rectangle tool again, click the rectangle to select it (if it isn't already selected). In rectangle edit mode, a toolbar will appear at the top of the window labelled "Change" with coordinates "W", "H", "Rx" and "Ry". Set the "W" and "H" to 57 — this will make the rectangle exactly 57 pixels wide and high (if the rectangle auto-locked to the edges of the document, these values may already be set). Set the "Rx" and "Ry" to 10 — this will set the corner radii to 10 (a round rect).

Numerical accuracy: I'm going to quote a lot of coordinates and color values in this post but this is only so I can communicate what I'm doing. Most of the time, you do not need to be pixel accurate and can do things more approximately if you prefer.

Using the selection tool (the first tool in the Tool Area) select the rectangle. The object's "X" and "Y" coordinates will appear in the toolbar at the top. Set these to zero. The rectangle is now exactly the size of the document with round corners.

The gloss round rectangle

Copy the red round rectangle object (select it and press Control-C) and paste it (Control-V) somewhere else (when pasted, the object will be centered where the mouse is, so place the mouse over a different part of the document).

Copy and Paste bug: if the Copy and Paste fails (you get a bitmap instead of a proper editable object or nothing seems to happen), then you may be seeing a bug in Inkscape due to recent X11 changes. To work around this bug, go to the X11 preferences and on the Pasteboard tab, disable "Update Pasteboard when CLIPBOARD changes". Alternatively, you can use "Edit"→"Duplicate" to duplicate without copying.

With the copy selected, go to the Fill tab of the Fill and Stroke palette. Set a radial fill for the object (4th icon from the left at the top). If you've set the red color, then the radial gradient will initially look like a red dot fading outwards.

Click the "Edit" button in the Fill tab to edit the gradient. In the "Gradient Editor" that appears, the popup menu at the top will contain two items (the opaque red color and the fully transparent red color). Hit the "Add Stop" button twice to add two extra items in the gradient.

Edit the topmost item in the list of colors (the opaque red color) and set it to white with an alpha value of 86. Set the second item to white with an alpha of 75. Set the third to black with an alpha of 60. Set the final item to white aith an alpha of 0.

You also need to set the offset of the two middle colors. The black color should have an offset of 0.63. The white color should have an offset of 0.62.

This round rectangle should now look like a faint gray donut. Select it and set its "X" and "Y" coordinates to (0,0) (so that it perfectly overlaps the original red round rectangle).

With the faint gray donut selected, choose the Gradient Tool (second last in the Tool Area — if your vertical screen resolution isn't very high, you may need to select the Gradient Tool from the popup menu at the bottom of the Tool Area). An "L" shape of control points should appear over the donut.

Drag the control point that appears in the middle of the donut to the middle of the top edge of the round rect (it should lock onto the point with the text "Handle to bounding box").

Drag the round control point at the end of the horizontal arm of the "L" to X=-50. You can see the "X" value of the cursor at the bottom right of the window. Hold down the "Control" key while doing this to ensure that the "Y" value remains the same. Similarly, drag the round control point at the end of the vertical arm to Y=12.

On the Stroke tab of the Fill and Stroke palette, set a linear gradient stroke (third icon from the left at the top) for the gloss object. On the Stroke Style tab, set the line width to 1.0 px.

On the Stroke tab, edit the gradient. Set the start color to white and the end color to RGBA=(255,255,255,0). Using the Gradient Tool, select the gloss object. There should now be an extra set of control points in a horizontal line across the middle of the object corresponding to the stroke's gradient. Drag the start point of this line (square control point) to the top right corner of the object and the end point of the line (circular control point) to a position three quarters the way up the right-hand side of the object.

Since the stroke added to the gloss object changed the size of the object, you will need to re-set the size of the gloss object to 57x57 at X,Y=(0,0).

You should now have a glossy red round rectangle in the style of an iPhone icon. If you know what you're doing in Inkscape, you can move these objects to another layer and hide them now however, it's probably easiest just to save this document and copy these objects when they are needed later.

The first iPhone icon

Blue-green background

Create a 57 by 57 rectangle at X,Y=(0,0) again, using the same approach as the red rectangle from the previous section but leave the corners square (you may need to explicitly set Rx and Ry to zero since it may remember the radius from before).

Set the fill of this rectangle to a linear gradient (third icon from the left at the top of the Fill tab in the Fill and Stroke palette). Edit the gradient and set the start point to RGBA=(15,112,126,255) and the end point to RGBA=(0,0,53,255).

Using the Gradient Tool from the Tool Area, select the rectangle and drag the gradient starting point (the square control point) to the center of the bottom edge of the rectangle. Drag the gradient end point (the round control point) to the center of the top edge of the rectangle.

Gradient colors: almost every gradient you use should involve a hue shift. When you want an actual 3D or lighting effect, you can also apply a luminance shift. The gradient here shifts from blue into the green direction as it lightens (a common choice). The other most common gradient would probably be from a darker red or orange towards a lighter yellowy orange. Hues on the green side of yellow or purple hues are rarely ever used.

Starburst object

Now, using the Stars and Polygons tool from the Tool Area (8th from the top) and drag out a shape (it will probably appear as a 5 point star — if it isn't a star, click the star icon in the top toolbar). With the Stars and Polygons tool and the object still selected, you should be able to edit the properties of the star. Set the number of corners to 350, the spoke ratio to 0.3 and the Randomized property to 0.015. Choose the Select and Transform tool (first tool in the Tool Area) and select the star. You can now set the width and height both to 87 and the X,Y to (-15,-15).

In the Fill and Stoke palette, set the opacity of the star to 50%.

Then, set a radial fill on the star from a start color of RGBA=(255,255,255,0) to an end color of RGBA=(0,235,255,255). This radial gradient fades out in the middle which will help the checkbox stand out from the background more.

A blur effect on the starburst

With the star object still selected, select the menu item "Filters"→"ABCs"→"Simple Blur". Then select the "Filters"→"Filter Editor..." menu item. This will display the Filter Editor palette.

Space limitations: If the Fill and Stroke Palette is still showing when the Filter Editor appears, you'll notice that they don't fit well together down the right margin. I recommend you either close the Fill and Stroke Editor or drag the Filter Editor off into its own window.

There should be one filter listed in the list of filters — this is the filter you just created. When you select the filter in the list, the Effect "Gaussian Blur" will appear in the Effect column at the right. Select the Gaussian Blur and the "Effect Parameters" tab will appear at the bottom. Set the "Standard Deviation" to 0.25.

You can also apply "Blur" using the Fill and Stroke palette. The blur radius at the bottom of this palette is 2.74 times the Standard Deviation applied here (no, I'm not really sure why the difference is 2.74 times).

The checkbox and checkmark objects

Now create a 29x29 round rectangle with corner radius 4 at X,Y=(14,14). This is the checkbox. This time, set no fill (the "X" icon on the Fill tab of the Fill and Stroke palette) and set a plain stroke (second icon from the left at the top of the Stroke tab) with a white color. On the "Stroke Style" tab, set the width to 3.0 "px". While here, set the "Cap" to round. It won't matter as much for this object, but we're just about to draw a line and we want it to have round endcaps.

Select the Bezier Line tool (11th icon down in the Tool Area). Click the mouse and release to create points at X,Y = (19.5,30), (28.5,20) and (47,48). Press the return key when done to finish the path. This is the checkmark. Now select the Node Tool (second icon from the top of the Tool Area) and select the checkmark. Click and hold the mouse in the middle of each line segment and drag up slightly to give the lines a slight curve. You can use the control points to tweak the effect if you're not happy.

Bevel effect and shadow

Select the checkmark and the checkbox. From the Filters menu select "Bevels"→"Ridged Border". Then from the Filters menu select "Shadows and Glows"→"Drop Shadow", set the blur to 2.0, the opacity to 35%, the offset to (3,3), hit the "Apply" button and close the Drop shadow dialog.

Speed tip: when zoomed in on objects using effects, the rendering can get slow. To disable effects or to drop entirely into wireframe mode, choose "No Filters" or "Outline" from the "View"→"Display Mode" menu or press Control-Keypad5. The "Ridged border" effect is especially slow in the current version of Inkscape — I recommend zooming out before you apply it and turning effects off before you zoom in close.

If you want to fully integrate the checkmark and the checkbox, you can convert the checkbox object to a path, the checkmark stroke to a path and then create a union of the two. I'll leave that to you if you're interested.

Apply the gloss effect and round corners

Select the green gradient background, the starburst, the checkbox and the checkmark and group them all together (Control-G or menu "Object"→"Group"). This will let you select them all in one go (ungroup with Control-Shift-G or double-click the group to select objects within the group without ungrouping).

With the group selected, from the Edit menu select "Clone"→"Create Clone". This will create a copy that continues to update when the original updates. Move the clone to X,Y=(-115.7,-15.7) (this coordinate include extra padding of approximately 2.74 times the starburst's blur standard deviation of 0.25 which is the amount that a blur will expand an object's boundary).

Now we need the red glossy round rectangle. If you saved them in a different document, copy them into this document now. Select the red background and gloss (drag a rectangle around both using the Selection Tool) and set the X,Y coordinates of the two of them to (-100,0). This may make the two objects hidden behind the cloned group objects so press the "Home" key (or select Raise to Top from the Object menu).

Drag the gloss and the red rectangle off of the objects they are covering (it doesn't matter where you put them). Select the cloned group and the red round rectangle but not the gloss gradient. Undo the two object moves. This should leave the cloned objects and the red round rectangle selected but all of the objects on top of each other. From the Object menu, select "Clip"→"Set". This should clip the cloned group to the boundary of the red round rectangle, and make the red round rectangle disappear.

Clipping: when clipping in Inkscape, the topmost object is always used as the clipping boundary and all other selected objects are clipped to its boundary.

Export the bitmap

Congratulations, your iPhone icon is complete.

You can export the prerendered (cloned, glossed and rounded) version to a PNG by selecting the gloss gradient that's over the clipped shape and selecting "Export Bitmap" from the "File" menu. Make sure that "Selection" is highlighted in the window that appears and set the width and height of the exported image to whatever size you want. Use the Browse button to select a location then hit the export button.

If you want to send the non-prerendered version to Apple, then select the uncloned group and export from that. 57x57 for the application icon and 512x512 for the high resolution version in your App Store submission.

Resampling: You may get a better effect on the small icon if you export at a larger size and use another program (Preview, GIMP, etc) to scale it down. This may give better anti-aliasing performance — particularly if your resizing program uses Lanczos resampling.

If you'd like your icon as a PDF, SVG or a number of other vector graphics types, you can choose "Save As..." and save to the format of your choice.

Conclusion

You can download an Inkscape SVG file containing the final icon (122kb). Note: Safari and other programs will open SVG files but the effects (shadows, blurs, etc) will only appear if the SVG is opened in Inkscape.

In the second part, I will go through the steps for other icons, showing different stylistic options and explaining more of the effects and graphical elements you can use to create your icons. I'll look closer at filter effects in Inkscape, creating more sophisticated line paths, using gradients in multiple directions to achieve softer effects and creating simple textures to fill blank areas.

Memory and thread-safe custom property methods

2009-10-25T04:26:00.001-07:00

Objective-2.0 property methods are a nice convenience but if you need to override a property implementation — particularly an atomic, retained or copied object setter property — there are some potential bugs you can create if you don't follow the rules carefully. I'll show you the pitfalls and the correct way to implement a property accessor. I'll also show a way to directly invoke hidden runtime functions to let Objective-C perform atomic getting and setting safely for you.

Custom getter and setter methods for implicitly atomic types

For implicitly atomic types or for types where memory management doesn't apply, custom getter and setter methods in Objective-C are easy. These "easy" situations include:

Basic value types (char, short, int, float, long, double, etc).
Objective-C objects in a garbage collected environment
Assigned (non-retained) pointers

For these types, it is pretty hard to get a custom getter or setter method wrong. For the following property declaration:

@property SomeAtomicType somePropertyVariable;

the custom getter and setter simply look like this:

- (SomeAtomicType)somePropertyVariable
{
    return somePropertyVariable;
}
- (void)setSomePropertyVariable:(SomeAtomicType)aValue
{
    somePropertyVariable = aValue;
}

Common mistakes in accessor methods for non-atomic types

Non-atomic types require greater care. These types include:

Objective-C objects in a manually managed memory environment
structs and other compound types

Given how simple custom getter and setter methods are for atomic types, it is easy to be complacent about implementing methods for these types. However, following the wrong approach can lead to memory crash bugs and lack of proper thread safety.

To illustrate how simple it can be to introduce bugs while implementing a custom setter method, consider the following declared property:

@property NSString (copy) someString;

A hasty implementation of the setter might be:

- (void)setSomeString:(NSString *)aString
{
    [someString release];
    someString = [aString copy];
}

This implementation actually contains two bugs:

This method is not atomic.
The someString object changes twice: once on release and again when it is assigned the copied object's address. This method is not atomic and therefore violates the declaration (which omits the nonatomic keyword and therefore requires atomicity).
The assignment contains a potential memory deallocation bug.
If someString is ever assigned its own value, it will release it before copying it, causing potential use of a released variable. The code: self.someString = someString; is an example of this potential issue.

Don't feel too bad if you've ever made these mistakes. I spent some time looking at clang's synthesized method implementations when I was researching this post and I noticed that they've forgotten to handle struct accessor methods in an atomic manner when required.

Safe implementations of custom accessor methods for non-atomic types

To address this second issue, Apple's Declared Properties documentation suggests that your setter methods should look like this:

- (void)setSomeString:(NSString *)aString
{
    if (someString != aString)
    {
        [someString release];
        someString = [aString copy];
    }
}

This only fixes the memory issue, it doesn't fix the atomicity issue. To handle that, the only simple solution is to used a @synchronized section:

- (void)setSomeString:(NSString *)aString
{
    @synchronized(self)
    {
        if (someString != aString)
        {
            [someString release];
            someString = [aString copy];
        }
    }
}

This approach will also work for retain properties as well (simply replace the copy method with a retain.

To maintain atomicity, you also need a retain/autorelease pattern and lock on any getter methods too:

- (NSString *)someString
{
    @synchronized(self)
    {
        id result = [someString retain];
    }
    return [result autorelease];
}

The @synchronized section is only required around the retain since that will prevent a setter releasing the value before we can return it (the autorelease is then safely done outside the section).

For struct and other compound data types, we don't need to retain or copy, so only the @synchronized section is required:

- (NSRect)someRect
{
    @synchronized(self)
    {
        return someRect;
    }
}
- (void)setSomeRect:(NSRect)aRect
{
    @synchronized(self)
    {
        someRect = aRect;
    }
}

A faster, shorter way to implement custom accessors

There are two negative points to the custom accessor methods listed above:

They need to be coded exactly to avoid bugs.
The @synchronized section on self is coarse-grained and slow.

There is another way to implement these methods that doesn't require as much careful coding and uses much more efficient locking: use the same functions that the synthesized methods use.

The following functions are implemented in the Objective-C runtime:

id objc_getProperty(id self, SEL _cmd, ptrdiff_t offset, BOOL atomic);
void objc_setProperty(id self, SEL _cmd, ptrdiff_t offset, id newValue, BOOL atomic,
    BOOL shouldCopy);
void objc_copyStruct(void *dest, const void *src, ptrdiff_t size, BOOL atomic,
    BOOL hasStrong);

While these functions are implemented in the runtime, they are not declared, so if you want to use them, you must declare them yourself (the compiler will then find their definitions when you compile).

These methods are much faster than using a @synchronized section on the whole object because (as shown in their Apple opensource implementation) they use a finely grained, instance variable only spin lock for concurrent access (although the copy struct function uses two locks following an interface design mixup).

When you declare these functions, you can also declare the following convenience macros:

#define AtomicRetainedSetToFrom(dest, source) \
    objc_setProperty(self, _cmd, (ptrdiff_t)(&dest) - (ptrdiff_t)(self), source, YES, NO)
#define AtomicCopiedSetToFrom(dest, source) \
    objc_setProperty(self, _cmd, (ptrdiff_t)(&dest) - (ptrdiff_t)(self), source, YES, YES)
#define AtomicAutoreleasedGet(source) \
    objc_getProperty(self, _cmd, (ptrdiff_t)(&source) - (ptrdiff_t)(self), YES)
#define AtomicStructToFrom(dest, source) \
    objc_copyStruct(&dest, &source, sizeof(__typeof__(source)), YES, NO)

I like to include the "To/From" words so I can remember the ordering of the source and destination parameters. You can remove them if they bother you.

With these macros, the someString "copy" getter and setter methods above would become:

- (NSString *)someString
{
    return AtomicAutoreleasedGet(someString);
}
- (void)setSomeString:(NSString *)aString
{
    AtomicCopiedSetToFrom(someString, aString);
}

and the someRect accessor methods shown above would become:

- (NSRect)someRect
{
    NSRect result;
    AtomicStructToFrom(result, someRect);
    return result;
}
- (void)setSomeRect:(NSRect)aRect
{
    AtomicStructToFrom(someRect, aRect);
}

Conclusion

Most of the accessor methods I've shown here are atomic but in reality, most Objective-C object accessors are declared nonatomic.

Even if your properties are declared nonatomic, the memory management rules still apply. These rules are important to follow since they can lead to some very obscure and hard to track down memory bugs.

The macros I've provided are all for atomic properties. For non-atomic properties the boilerplate assignment code is probably simple enough to remember. If not, you could also use a macro:

#define NonatomicRetainedSetToFrom(a, b) do{if(a!=b){[a release];a=[b retain];}}while(0)
#define NonatomicCopySetToFrom(a, b) do{if(a!=b){[a release];a=[b copy];}}while(0)

Update: following comments below, I realize I omitted to qualify the situations in which these accessors are thread-safe. Specifically:

These setter methods are only thread-safe if the parameters passed to them are immutable. For mutable parameters, you may need to ensure thread safety between mutations on the parameter and the assignment of the property.
Atomic accessors only provide thread safety to an instance variable if they are the sole way you access the instance variable. If non-property access is required, you must ensure shared thread safety between property accessor methods and the non-property access.
Atomic assignment for the "implicitly atomic" types I listed does not mean that all CPUs/cores see the same thing (since each CPU/core could have its own cache of the value) — it only ensures that value is wholly set without possibility of interruption. If you require all CPUs/core to be synchronized and see the same value at a given moment, then even the "implicitly atomic" types may require volatile qualifiers or a @synchronized section around the assignment to flush caches.

How blocks are implemented (and the consequences)

2009-10-18T02:12:00.001-07:00

This post is a look at how clang implements blocks and how this implementation leads to a number of strange behaviors including local variables that end up global, Objective-C objects allocated on the stack instead of the heap, C variables that behave like C++ references, Objective-C objects in non-Objective-C languages, copy methods that don't copy and retain methods that don't retain.

What blocks are to the compiler

Blocks are addressable sections of code implemented inline (inside other functions). The inline-edness can be convenient but the real reason why blocks are different to regular functions and function pointers is that they can reference local variables from the scope of the function surrounding their implementation without the invoker of the block needing to know of the surrounding scope variables' existence.

A block is implemented internally using two pieces:

compiled code in the .text segment of the executable
a data structure that predominantly contains the values of the variables that the block uses from its surrounding scope

The compiled code lives in its own separate location and does not actually reside inside inside the code of its surrounding scope. In implementation, the code is a function like any other. If you run:

otool -tV MyCompiledExecutable

then you'll see your blocks appearing immediately after their surrounding functions with names like ___surroundingFunction_block_invoke_21.

So it is not the code which makes blocks special, it is the separate data structure. It is this data structure that I will focus on for the remainder of this post.

The block data structure

Clang's basic documentation on block implementations indicates that the data structure describing the block looks something like this:

struct Block_literal {
    void *isa;

    int flags;
    int reserved; // is actually the retain count of heap allocated blocks

    void (*invoke)(void *, ...); // a pointer to the block's compiled code

    struct Block_descriptor {
        unsigned long int reserved; // always nil
        unsigned long int size; // size of the entire Block_literal
        
        // functions used to copy and dispose of the block (if needed)
        void (*copy_helper)(void *dst, void *src);
        void (*dispose_helper)(void *src); 
    } *descriptor;

    // Here the struct contains one entry for every surrounding scope variable.
    // For non-pointers, these entries are the actual const values of the variables.
    // For pointers, there are a range of possibilities (__block pointer,
    // object pointer, weak pointer, ordinary pointer)
};

Of course, the reality is that this structure is never explicitly declared like this in clang. Clang is a compiler — a code generator — and the format of this structure is generated programmatically from the CodeGenFunction::BuildBlockLiteralTmp method.

Stack blocks and global blocks

Since the biggest difference between a function pointer and a block is the ability to use variables from the surrounding scope, it is interesting to look at what happens when a block does not reference anything in the surrounding scope.

Normally, the Block_literal data appears on the stack (like a regular struct would in its surrounding function). With no references to the surrounding scope, clang configures the Block_literal as a global block instead. This causes the block to appear in a fixed global location instead of on the stack (the flags value has the BLOCK_IS_GLOBAL flag set to indicate this at runtime but it's not immediately clear to me if this is ever used).

The implication of this is that global blocks are never actually copied or disposed, even if you invoke the functions to do so. This optimisation is possible because without any references to the surrounding scope, no part of the block (neither its code nor its Block_literal) will ever change — it becomes a shared constant value.

Blocks are always objects

If you're familiar with how Objective-C objects are declared, the isa field in the Block_literal above should be familiar — blocks are Objective-C objects. This may not seem strange in Objective-C but the reality is that even in pure C or C++, blocks are still Objective-C objects and the runtime support for blocks handles the retain/release/copy behaviors for the block in an Objective-C messaging manner.

Clang uses the class names _NSConcreteStackBlock and _NSConcreteGlobalBlock to refer to the classes for block literals but in CoreFoundation projects, this will map onto NSStackBlock and NSGlobalBlock. If you copy an NSStackBlock, it will return an NSMallocBlock (indicating its changed allocation location).

Blocks are slightly weird objects

The interesting point to note about NSStackBlock is that it is a stack allocated Objective-C object. If you have ever tried to allocate an Objective-C object on the stack (not as a pointer but statically allocated) you'll know that the compiler normally forbids this.

The reason why blocks are placed on the stack by default is speed. In the common case where the lifetime of the block is less than that of the stack function that contains it, this is a very good optimisation.

The implication of stack blocks being allocated on the stack, is that a stack block cannot simply be retained — it will become invalid once the function that contains it is popped from the stack. If you invoke retain on a stack block, it will have no effect (the retain count of the block will remain at 1).

For this reason, if you need to return a block from a function or method, you must [[block copy] autorelease] it, not simply [[block retain] autorelease] it.

__block values can move magically

Scope variables used in a block are normally passed to the block by const value (the compiler won't let you change the value but even if it did, the change wouldn't affect the value of the variable outside the block).

To alter this behavior, the type specifier __block was added. Any variable declared __block is passed by reference into the block (value on the outside will be changed after the block is invoked).

In the implementation, __block variables are initially allocated on the stack but if any block which references them is copied, they are moved onto the heap (malloced). This leads to the following strange situation...

int (^function())()
{
    __block int x = 0;
    
    int (^block)() = ^{
        x += 1;
        return x;
    };
    
    NSLog(@"x's location is on the stack: %p", &x);
    block = [[block copy] autorelease];
    NSLog(@"x's location is now on the heap: %p", &x);
    
    return block;
}

In this example, x's address changes when the copy is invoked. This is because when we declare a __block variable, a pointer to the real variable is created and any attempt to use the variable dereferences it. When copy is invoked, the location pointed to by the pointer changes to the new heap location, so any use of x causes a dereference to this new location.

This makes __block similar to to a reference parameter in C++ since C++ references are also transparently dereferenced pointers.

NSMallocBlock never actually copies

Copying a block doesn't really give you a copy of the block — if the block is already an NSMallocBlock, a copy simply increases the retain count of the block (this retain count is an internal reserved field — the retainCount returned from the object will remain at 1). This is perfectly appropriate since the scope of the block cannot change after it is created (therefore the block is constant) but it does mean that invoking copy on a block is not the same thing as recreating it.

Assume the following code is in the same program as the previous example.

int (^someBlock)() = counterBlock();
int (^someBlockCopy)() = [[someBlock copy] autorelease];
int (^anotherBlock)() = counterBlock();

The block returned from counterBlock() counts the number of times that it is invoked by saving the count in the __block variable x.

In this example though, someBlock and someBlockCopy share the same x variable — they are not actually separate copies. However, anotherBlock does have its own separate x value.

If you need a genuinely separate copy, recreate the block, don't copy it.

Blocks retain their NSObject scope variables

Blocks will retain any NSObject that they use from their enclosing scope when they are copied.

The biggest implication of this is that you must remember to avoid retain cycles if the block will be held beyond a simple stack lifetime.

A pointed out elsewhere, you can suppress this retain of NSObjects by assigning the object to a __block variable outside the block and only ever using the __block variable inside the block.

You can also do the reverse of this and force a pointer that isn't an NSObject derived class to be retained when copied. Do this by declaring the pointer with __attribute__((NSObject)). Of course, the situations where you'd want to do this are exceedingly rare.

Conclusion

Blocks are very simple to use in the case where you declare one inline and immediately pass into another function but once you need to copy or hold onto a block for a while, there are a number of quirks, some of which I've covered in this post.

Sadly at this time, Apple's documentation on blocks is fairly basic and lacking in detail. This is what led me to start looking at clang's source code.

Of course, you don't need to stare at someone else's C++ code to learn about blocks. There are other sources of lighter, more approachable documentation on the topic. In addition to sources that I've already linked, there's also:

Mike Ash's colorfully titled "Friday Q&A 2008-12-26" — an excellent run-down of potential use-cases for blocks in Objective-C.
Joachim Bengtsson's Programming with C Blocks — a good general summary of most aspects of blocks
Jim Dovey's Blocks Episode 2: Life Cycles — a look at stack and heap allocation of blocks with diagrams
clang's BlockLanguageSpec

Objective-C's niche: why it survives in a world of alternatives

2009-10-12T01:47:00.001-07:00

Objective-C remains an impediment for many programmers coming to the Mac or iPhone platforms — few programmers have ever experienced it before learning Cocoa, forcing two learning curves at once for new Cocoa developers. How did Apple end up with such a weird language? And for a company known to replace CPU architectures and their entire operating system, why does Apple persist with Objective-C? The answer lies in the methods.

Virtual methods

Most compiled, object-oriented languages (like C++, Java and C♯) adhere closely to the object-oriented approaches first introduced in Simula 67 — in particular the concept of virtual methods and how they enable methods to be overridden.

Origins in Algol: In much the same way that Objective-C is often called a "pure superset" of C, Simula 67 was a "pure superset" of Algol 60. While Fortran is sometimes remembered as the first high-level language to gain popularity (and disdain), Algol 60 was the first programming language to actually resemble a modern language as it contained the for, if/else, while, return and other procedural contructs that are expected now in programming languages. While Algol was rarely used past the 1970's, Pascal and its descendants closely resemble Algol in syntax.

In a compiled language, a regular function (non-overrideable) ends up as a basic memory address. When the function is invoked, the CPU jumps to the memory address.

Simula 67 introduced virtual method tables to adapt this for object-orientation. Instead of basic memory addresses, methods are compiled to row numbers in a table. To get the memory address, the method table is retrieved from the class of the object and the CPU jumps to the address at the specified row.

Since different objects have different classes, they will have different addresses in their method tables, hereby allowing sublcasses to have different implementations of methods (method overrides) to their base classes.

Message passing

While virtual method tables do introduce a level of indirection that allows method behavior to change from object to object, the offsets into the table and hence the tables themselves all need to be created at compile-time.

History of message passing: As with object-orientation itself, message passing was inspired by Simula 67 but Simula's message passing (called "Simulation") wasn't for method invocations — it was instead used for discrete event simulation (mostly queueing and list processing). Smalltalk expanded upon this idea by using message passing for method invocation. Smalltalk subsequently inspired the Actor Model (used in distributed processing) and remote procedure calls (RPC). Originally, Smalltalk messages were conceived to have a large amount of metadata (more like the full headers on an email) but eventually, this was simplified down to an approach syntactically similar to Objective-C's current implementation (minus square brackets).

Message passing presents an alternative way of solving the method dispatch problem. Instead of the virtual method's compile-time offsets and tables which don't consult the object (except for its type), message passing sends a unique message identifier to the object itself and the object determines at runtime what action to take.

Message passing approaches may still have a virtual method table ("vtable") in the class' representation but this structure is not known at compile time — it is handled entirely at runtime — and instances of the class have the opportunity to take different actions in response to the message that are unrelated to the content of the table.

There are two important differences here:

Runtime resolution — so the connection between message identifier and action can be changed at runtime.
Involvement of the object itself, not just its class.

On a technical level, the difference between a virtual method table and passing a message identifier is relatively minor (since both are really table lookups and both are actually performed at runtime). The difference ends up being conceptual:

Virtual method table languages generally make it hard or impossible to change the virtual method table contents or pointers at runtime.
Type safety is essential in a virtual method table language since the compiler may alter table lookups based on type, particularly in cases of multiple inheritance. In message passing systems, type safety is irrelevant to method invocation.

Why this matters

The short answer is that this dynamic message handling in Objective-C makes it much easier to work within a large framework that you didn't create because you can examine, patch and modify elements of that framework on the fly. The most common situation where this is likely to occur is when dealing with an application framework.

The biggest reason for this is that you can add or change methods on existing objects, without needing to subclass them, while they are running. Approaches for this include categories, method swizzling and isa-swizzling.

This makes the following situations possible:

You want to add a convenience method to someone else's object (a quick search of my own posts reveals that about a dozens of my own posts involve adding convenience methods to Cocoa classes, e.g. Safely fetching an NSManagedObject by URI).
You want to change the behavior of a class you didn't (and can't) allocate because it is created by someone else (this is how Key-Value Observing is implemented in Cocoa).
You want to treat objects generically and handle potential differences with runtime introspection.
You want to substitute an object of a completely different class to the expected class (this is used in Cocoa by NSProxy to turn a regular object into a distributed object).

These points may seem somewhat mild but they are central to maximizing code reuse when working within someone else's framework: if you need existing code to work differently, you don't need to reimplement the whole class and you don't need to change how it is allocated.

Languages using virtual method tables can adopt some of these ideas (like the boost::any class or C♯ 4.0's dynamic member lookup) but these features have additional restrictions and don't apply to all objects, meaning that they can't be used on purely arbitrary objects (such as those you don't control or didn't create) and so don't help when interacting with someone else's framework.

Simply put: dynamic message passing instead of virtual method invocations makes Objective-C a much better language for working with a large library or framework that someone has written.

The tradeoff

The downside to dynamic message invocation is that it is only as fast as virtual method invocation when the message lookup is cached, otherwise it is invariably slower.

Also, in keeping with the philosophy of a purely dynamic messaging system, Objective-C does not use templates or template metaprogramming and does not have non-dynamic (i.e. non-virtual) methods. This means that Objective-C methods will miss out on the compiler optimizations possible when employing these techniques. Also, since modern programming in C++ is substantially focussed on these features, it can difficult to adapt programs using these ideas to Objective-C.

Theoretically, Objective-C could implement these features but they are in opposition to the underlying concepts of flexibility and dynamic behavior in Objective-C — and would shut-down all advantages from the previous section if they were used.

Conclusion

It's not a coincidence that I write an Objective-C/Cocoa blog, I'm obviously an advocate of Objective-C and Cocoa. In my opinion, Objective-C is the best language for programming situations where you must make extensive use of a framework written by someone else (particularly an application framework). The success of Objective-C in this situation is due to the combination of:

speed and precision (from its compiled C roots)
dynamic flexibility (due to using message passing for method invocations)

To frame this conclusion, I'll state that I've written major projects using C/WIN32, C++/PowerPlant, C++/MFC, and Java/Swing/AWT. I've also dabbled in smaller projects using C♯/.Net. In all of these cases I have found the application frameworks to be less flexible and less reusable because they lack the dynamic modifiability of Objective-C.

As I've stated, I do view Objective-C's strength in the area of application frameworks as a niche (albeit a very large niche). If I were writing a compiler, OS kernel, or a low-level/high-performance library, then I would use C++ (I wouldn't use pure C because I'd miss my abstractions) — but these are situations where metaprogramming, greater inlining and faster method invocations would trump flexibility concerns. Of course, if you have a project that needs to satisfy all these criteria: then there's always Objective-C++.

The ugly side of blocks: explicit declarations and casting.

2009-10-05T20:20:00.001-07:00

Blocks are a welcome addition to C/Objective-C/C++/Objective-C++ with Snow Leopard but they carry with them the worst aspect of Standard C: function pointer declaration and casting syntax. In this post, I'll show you how to understand declarations and casting syntax for blocks and function pointers, even in the worst of scenarios.

Simple block declarations and casting

Used as intended (simple inline code implementations) blocks are fairly elegant. This is due to one advantage they offer: in simple cases, you do not need to specify the return type — it can be inferred from the return statement in the block itself.

So declaring a block that returns an int can be as simple as:

int (^alwaysReturnIntZero)() = ^{ return 0; };

In this case though, an unqualified integral value is correctly assumed to be an int. If we want the block to return an NSInteger, we need to either cast the return type or not rely on type inference and declare the return fully:

NSInteger (^alwaysReturnNSIntegerZero)() = ^ NSInteger (){ return 0; };

Notice that the block literal (righthand side) does not follow the structure as the block declaration (lefthand side). The block literal uses a straightforward "caret, return type, parameter list" order but the block declaration uses the C function pointer declaration syntax, which can grow more complex (as I'll show later). At this point though, the two are of similar complexity.

Casting a block looks much like declaring a block, minus the name of the variable from the declaration.

long long (^alwaysReturnLongLongZero)() = (long long (^)())alwaysReturnNSIntegerZero;

If you look at what is done here, all that is needed to create a cast for a value to the variable type, is to copy the variable's declaration, put parentheses around the copied declaration and remove the variable name.

Function pointers

Blocks borrow their syntax from standard C function pointers. In almost all cases, the only difference between a block declaration or cast and a function pointer declaration or cast is the "^" character is used for the block and the "*" character is used for the function pointer. e.g.:

long long (*fnAlwaysReturnLongLongZero)() = (long long (*)())fnAlwaysReturnNSIntegerZero;

Of course, functions cannot be declared inline, so you cannot have function literals in the same way as you can have block literals. However, all other syntactic traits remain the same.

Reading declarations correctly

Unfortunately, blocks follow the typical C declaration rules which become outright confusing when you try to return something. Before it all gets complicated, I'm going to explain something simple about C declarations.

Consider how a pointer is declared:

int *myVariable;

If you're reading this blog at all, you should know that this statement creates a pointer named myVariable which points to an int.

But the operator used here is a "dereference", it is not the "make a pointer" (address of) operator. The correct way to read this line is:

Declare a variable:
myVariable
It can be dereferenced (and by implication is therefore a pointer)
*myVariable
If it is deferenced, then the value yielded from the dereference should be treated as an int:
int *myVariable;.

Let's look at the alwaysReturnIntZero declaration from above again and we'll apply this same reading to it.

int (^alwaysReturnIntZero)() = ^{ return 0; };

Declare a variable:
alwaysReturnIntZero
It can be dereferenced to yield block information (and by implication is therefore a block pointer):
^alwaysReturnIntZero
Its block implementation takes no parameters and returns an int:
int (^alwaysReturnIntZero)()

This approach to reading a declaration is quite simple but you'll need to it to follow the next section.

Declaring a block that returns a block

Imagine you wanted to use a block to compare a double to an int and return true if the double is greater than the int or false if the double is equal or smaller. In the simple case, that might look like this:

bool (^compareDoubleToInt)(int i, double j) = ^{ return j > i; };

Easy enough but imagine now that you want to break this into two pieces:

A first block which takes only the int and returns a second block, pre-configured to use this int.
The second block then takes the double, compares it to its pre-configured int and returns the result.

The first block is then a factory block which creates instances of the second block that operate like the compareDoubleToInt shown above for a single, pre-configured value of i.

The complete implemention of this would be:

bool (^(^newDoubleToIntComparison)(int))(double) =
    ^(int i)
    {
        return Block_copy(^ (double j)
        {
            return j > i;
        });
    };

Pay careful attention to the "new" in the name — this serves to notify that you must use Block_destroy on any blocks created in this fashion when you're done.

If everything about the syntax on that first line (the declaration) makes immediate sense to you, then you may consider yourself skilled at syntactic recursion.

The reason most people find this hard to read is that verbally, we would describe this scenario in a very different order:

Declare a variable:
newDoubleToIntComparison
It can be dereferenced to yield block information (and by implication is therefore a block pointer):
^newDoubleToIntComparison
The block takes an int parameter:
(^newDoubleToIntComparison)(int)
Its return value can be dereferenced to yield block information (and by implication the return value is therefore a block pointer):
(^(^newDoubleToIntComparison)(int))
This returned block takes a double parameter
(^(^newDoubleToIntComparison)(int))(double)
And the returned block returns a bool
bool (^(^newDoubleToIntComparison)(int))(double);

If C declarations read from left-to-right, it would be far less confusing. Instead, we have a situation where blocks that return blocks are recursively nested inside each other.

Of course, most people mitigate this by typedef'ing absolutely function pointer they ever use. Doing this for the previous block declaration changes it to:

typedef bool (^IsDoubleBiggerBlock)(double);
IsDoubleBiggerBlock (^newDoubleToIntComparison)(int);

Functions or methods that return blocks

It may also be helpful to see the subtle difference between declaring a block that returns a block and the definition of of a function returns a block.

Replacing the factory block with a factory function in the previous example would lead to:

bool (^NewDoubleToIntComparisonFunction(int i))(double)
{
    return (bool (^)(double))Block_copy(^ (double j)
    {
        return j > i;
    });
};

This function takes a single int as its parameter and yet the last component on the function prototype line is (double). The int parameter that the function actually takes and the name of the function are nested inside of the return type (the return type comprises the double parameter to the right, the caret character and the bool return value to the left).

Also notice that you need to cast the output of Block_copy to have it recognized as the correct return type.

As with the variable declarations, this nested behaviour is normally considered too annoying, so typedefs are employed to simplify:

typedef bool (^IsDoubleBiggerBlock)(double);
IsDoubleBiggerBlock NewDoubleToIntComparisonFunction(int i)
{
    return (IsDoubleBiggerBlock)Block_copy(^ (double j)
    {
        return j > i;
    });
};

This has the huge advantage that it puts the function's parameter back where it belongs — as the last component on the function prototype line.

An Objective-C method that returns a block is a much simpler situation since the method does not become nested within the return type in the same way. Instead, the return type looks identical to the cast of the returned copied block and the rest of the method remains distinct.

- (bool (^)(double))newDoubleToIntComparison:(int)i
{
    return (bool (^)(double))Block_copy(^ (double j)
    {
        return j > i;
    });
}

Conclusion

The declaration of C function pointers is widely regarded as the worst syntax in the language. There is a good reason for this: the information in a function pointer's declaration flows from the most significant components which are nestled on the inside of the declaration to the least significant components which encircle the outside. They could flow left-to-right like a sentence but instead they flow outwards from an identifier somewhere in the middle.

Sadly, blocks follow in this tradition. All you can do to mitigate the torment is use typedef'd declarations judiciously and try to keep your blocks simple. They're not really intended for large numbers of parameters and complex return values, anyway.