Designing Code for Performance
Description: Effective use of the right data structures can make a big difference in the responsiveness of an app. Come learn about the performance characteristics of the Foundation collections, how to select one that best fits your needs, and how to design software to use them efficiently.
This session is about how to use right Data Structures to improve the app performance as much as possible.
1. When to focus on performance
Trying to improve the parts consume more execution time.
- Premature optimization leads to unnecessary complexity
- “If it ain’t broke, don’t fix it.”
- Use Instruments to focus on bottlenecks
- Informed design leads to elegant, efficient code
- Consider performance during design
- Intelligently avoid real performance pitfalls
- Why design in slowness you can easily avoid?
2. How to evaluate computational complexity
This part presents Big-O notation, which presents the computational complexity of an Algorithm, or Operation.
Example Here:
[NSArray -containsObject:]
vs [NSSet -containsObject:]
[NSArray -containsObject:]
sends-isEqual:
to each objects in the array, which will take O(N).[NSSet -containsObject:]
takes O(1) instead, becauseNSSet
is a Hash-Based Organization, which trying the best to have all the objects uniform distributed.
NSObject
's -isEqual:
and -hash
are functionally equivalent to:
- (BOOL) isEqual:(id)other {
return self == other;
}
- (NSUInteger) hash {
return (NSUInteger)self;
}
To Identify the Custom NSObject
Subclass object, at least -isEqual:
and -hash
needs to be implemented in the subclass. The better -hash
function implemented, the better performance will be retrieved for searching/identifying involved operations.
@interface WWDCNews : NSObject <NSCopying>
@property (readonly, copy) NSString *title;
@property (readonly, copy) NSDate *timestamp;
@end
@implementation WWDCNews
- (NSUInteger) hash {
return [self.title hash];
}
- (BOOL) isEqual:(id)object {
return ([object isKindOfClass:[WWDCNews class]]
&& [self.title isEqual:[object title]]
&& [self.timestamp isEqual:[object timestamp]]);
}
@end
3. How to choose and use data structures
- Plan for scale when appropriate
- All data structures have tradeoffs
- A bad fit hurts performance
- The wrong tool
- The wrong approach
- Immutable vs Mutable
- Immutable provides
- Thread Safety
- Memory and Speed Optimization
- Immutable provides
NSArray
/NSMutableArray
- Ordered, indexed, allows duplicates
- Fast operations
- Indexed access (e.g.
-objectAtIndex:
,-firstObject
,-lastObject
) - Add / remove at either end (e.g.
-addObject:
,-removeLastObject:
)
- Indexed access (e.g.
- Slower operations
- Search (e.g.
-containsObject:
,-indexOfObject:
,-removeObject:
) - Add / remove, arbitrary index (e.g.
-insertObject:atIndex:
)
- Search (e.g.
- Slower operations
- Specialty operations
- Binary search (requires a sorted range of an array)
-indexOfObject:inSortedRange:options:usingComparator:
- Specialty operations
NSSet
/NSMutableSet
- Unordered, no duplicates, hash lookup
- Add, remove, and search are fast
- (e.g.
-addObject:
,-removeObject:
,-containsObject:
)
- (e.g.
- Specialty operations
- Set math: test overlap (e.g.
-intersectsSet:
,-isSubsetOfSet:
) - Set math: modify (e.g.
-intersectSet:
,-minusSet:
,-unionSet:
)
- Set math: test overlap (e.g.
- Specialty operations
- Caveats
- Converting array to set loses ordering and duplicates
- Cannot be stored in a property list or JSON
- Caveats
NSCountedSet
- Unordered, no duplicates, hash lookup
- Subclass of
NSMutableSet
, same operations and caveats - Tracks net insertion count for each object
- Incremented on insert, decremented on remove
-countForObject:
returns individual count-count
still returns number of objects, not sum of insertions
NSDictionary
/NSMutableDictionary
- Unordered, key-value entries, unique keys, hash lookup
- Add, remove, and search are fast
- (e.g.
-objectForKey:
,-setObject:forKey:
,-removeObjectForKey:
)
- (e.g.
- Specialty operations
- Property list file I/O
+sharedKeySetForKeys:
,+dictionaryWithSharedKeySet:
(10.8, iOS 6)
- Specialty operations
- Caveats
- Keys must conform to
NSCopying
(“copy in”) - NEVER mutate an object that is a dictionary key
- Keys must conform to
- Caveats
NSOrderedSet
/NSMutableOrderedSet
- Ordered, no duplicates, index / hash lookup (10.7, iOS 5)
- Effectively a cross of
NSArray
andNSSet
- Not a subclass of either one
- Call
-array
or-set
for immutable, live-updating representations
- Caveats
- Increased memory usage
- Property list support requires conversions
- Caveats
NSIndexSet
/NSMutableIndexSet
- Collection of unique
NSUInteger
values - Reference a subset of objects in
NSArray
- Avoid memory overhead of array copies
- Collection of unique
- Efficient storage and coalescing
- Set arithmetic (intersect, subset, difference)
- Caveats
- Use caution with indexes for mutable arrays
NSMapTable
/NSHashTable
- Similar to
NSMutableDictionary
/NSMutableSet
- More flexibility via
NSMapTableOptions
/NSHashTableOptions
- May use pointer identity for equality and hashing
- May contain any pointer (not just objects)
- Optional weak references to keys and/or values (zeroing under ARC)
- Optional copy on insert
- Similar to
- Caveats
- Can’t convert non-object contents to dictionary/set
- Beware of premature optimization!
- Caveats
NSCache
- Similar to
NSMutableDictionary
- Thread-safe
- Doesn’t copy keys
- Auto-removal under memory pressure
- Ideal for objects that can be regenerated on demand
- Similar to
Summary
- Complexity kills large-scale performance
- Know how much work your code does
- Avoid redundancy, strive for efficiency
- Focus on biggest performance wins
- Profile and analyze, don’t assume
- Prefer built-in collections and API
- Design according to your needs
- Think about performance early
This note was originally published at github.com/antonio081014/WWDC_Learning_Review.