Writing more performant mobile apps

Although I earned a technical degree in college I would still say that I am in large part a self-taught programmer. Yay for DIY. I started programming in a 100 level CS class at BYU years ago, but I wasn't really programming back then... I was blindly following TA help sessions and being handheld through everything. A few semesters and a couple CS/EE classes later I still wasn't much of programmer. It wasn't until Dr. Liddle's Android class in Winter 2011 that things finally clicked for the first time.

For the semester project I was creating a simple Cow Tipping game where you tap cows until they tip over. I remember trying to figure out how I would track how many taps are left before the cow tips over. I discussed the problem with a friend and he gave me a couple suggestions. I eventually arrived at using a map with keys being cow ImageViews and values as the number of taps left until it falls over. It was the first practical application for data structures that I'd found.

From that point on I did a couple more side Android projects and landed my first Android contract job and, a few months later, an Android internship at rain. Then in summer 2012 I began interning at Solutionreach and was asked to learn iOS. I was gaining experience and a portfolio, yes, but thinking back I made the jump from DIY coder to writing enterprise apps pretty quickly, to be honest. I've spent a lot of the last two years trying to supplement my ability to write apps with software design principles and performance optimizations. Having recently started with iTV and getting exposed to a different, mature iOS codebase it's been a great opportunity to challenge existing lines of thinking and learn about better, more performant approaches and patterns. It's one of my favorite things about the gig.

Okay so finally to the code part. In Objective-C, NSDictionaries and NSArrays can do anything, right? Well, yeah, they can, probably, but what about NSSets? NSSets offer better - O(1) - performance for extremely routine tasks such as accessing items in a collection or checking if a collection contains an item. NSArrays on the other hand must iterate through their entire contents until the particular object is found - O(n). So here's my suggestion: don't forget about the awesomeness of NSSet.

Okay, so some examples... First up I'm going to create a collection of twitter handles for my favorite followers. Here's three potential approaches.

1. NSFastEnumeration

NSMutableArray *mutableFavs = [NSMutableArray array]; 
for (TwitterUser *user in user.followers) { 
  [mutableFavs addObject:user.handle]; 
}
NSArray *favorites = [mutableFavs copy];

2. EnumerateObjectsUsingBlock

NSMutableArray *mutableFavs = [NSMutableArray array];
[user.followers enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    [mutableFavs addObject:[obj handle]];
}];
NSArray *favorites = [mutableFavs copy];

3. NSSet's valueForKey

NSSet *favorites = [user.followers valueForKey:@"handle"];

This is a fairly simple example, with the big question being okay, what now. My ultimate goal is to create a collection of favorite tweets by looking through a timeline full of tweets, comparing the author's Twitter handle, and pulling out the matches. Since I don't care particularly care about the order of the collection, valueForKey and using a set is an excellent option. Or, I may care about order eventually, but for now I don't, and later on I was planning on sorting the results alphabetically anyway, which means I have less reason to preserve order by using NSArrays at this point.

So how can it be done? Here's two approaches:

1. NSFastEnumeration x 2, aka the double for loop - O(n^2)

NSMutableArray *mutableFavs = [NSMutableArray array];
for (TwitterUser *twitterUser in user.followers) {
    for (Tweet *tweet in timelineTweets)  {
        if ([twitterUser.handle isEqualToString:tweet.authorHandle]) {
            [mutableFavs addObject:tweet];
        }
    }
}
NSArray *favoriteTweets = [mutableFavs copy];

2. NSSet's valueForKey + NSPredicate - O(n)

NSSet *favorites = [self.followers valueForKey:@"handle"];
NSPredicate *predicate = [NSPredicate predicateWithBlock:^BOOL(id evaluatedObject, NSDictionary *bindings) {
    Tweet* tweet = evaluatedObject;
    return [favorites containsObject:tweet.authorHandle];
}];
NSArray* favoriteTweets = [timelineTweets filteredArrayUsingPredicate:predicate];

I know what you're thinking....

If you didn't catch it, we used an NSSet to drop the complexity down from a BAD BAD BAD O(n^2), to an ALRIGHT, I CAN DEAL WITH THAT O(n) by using NSSet's constant lookup time. Think about it this way, if this user had 500 followers and we were looking at 200 tweets, with the first approach it could take 100,000 loops until we successfully had our collection of favorite tweets. With the second approach we are looking at orders of magnitude faster, and arguably cleaner code too. (For more on cleaning up these types of operations further, check out ConciseKit... or maybe just forget obj-c and jump into Swift. :)

Moral of the story is to continue to look for ways to improve your code. "Yeah, it works" may be a huge accomplishment in the beginning, but performance is key as you scale. Although it probably won't "make" your app, it can definitely "break" your app if done wrong. It's true that it may not matter either way when dealing with small data sets, but avoid the urge to think meh, it probably won't matter. In your testing you may have 4 or 5 objects in your collection, but in the real world what happens when a user ends up with 700? Combine that with a poorly designed filtering method and you could be in trouble.