Skip to content

Instantly share code, notes, and snippets.

@markd2

markd2/fast-enum.m

Created Nov 8, 2012
Embed
What would you like to do?
Fast enumeration example
#import <Foundation/Foundation.h>
// clang -g -fobjc-arc -Weverything -framework Foundation -o fast-enum fast-enum.m
#pragma clang diagnostic ignored "-Wobjc-missing-property-synthesis"
// --------------------------------------------------
// Code to iterate a non-array based collection and use fast
// enumeration's stack buffer
// This is a linked list that holds strings. Pretty uninspired.
// Linked list node - holds the string, and a pointer to the next node
@interface Node : NSObject
@property (copy, nonatomic) NSString *string;
@property (strong, nonatomic) Node *next;
@end // Node
@implementation Node
@end // Node
// The collection. Add new strings to the end of the collection,
// and access by index.
@interface LifoList : NSObject <NSFastEnumeration>
@property (readonly, nonatomic) NSUInteger count;
- (void) addString: (NSString *) string;
- (NSString *) stringAtIndex: (NSUInteger) index;
@end // LifoList
@implementation LifoList {
Node *_head;
NSUInteger _count;
unsigned long _mutations;
}
- (NSUInteger) countByEnumeratingWithState: (NSFastEnumerationState *) enumerationState
objects: (id __unsafe_unretained []) stackBuffer
count: (NSUInteger) len {
// Sanity check. I know sizeof(unsigned long) >= sizeof(pointer), but be
// a little paranoid.
assert (sizeof(Node *) <= sizeof(unsigned long));
// Using the enumerationState's extra[0] as the scan pointer.
if (enumerationState->state == 0) { // first time
enumerationState->state = 1; // Must set to non-zero
enumerationState->mutationsPtr = &_mutations; // Can't be NULL.
enumerationState->extra[0] = (unsigned long)_head;
}
Node *scan = (__bridge Node *)((void *)enumerationState->extra[0]);
// Fill up as much of the stack buffer as we can.
NSUInteger i;
for (i = 0; i < len && scan != nil; i++) {
stackBuffer[i] = scan.string;
scan = scan.next;
}
enumerationState->extra[0] = (unsigned long) scan;
// Point the returned items pointer to the stack buffer. We could pass our
// own internal buffer pointers here, or allocate memory and fill it.
enumerationState->itemsPtr = stackBuffer;
return i;
} // countByEnumeratingWithState
- (void) addString: (NSString *) string {
// New node
Node *node = [[Node alloc] init];
// Put it at the start of the list.
node.string = string;
node.next = _head;
_head = node;
// Necessary bookkeeping.
_count++;
_mutations++;
} // addString
- (NSString *) stringAtIndex: (NSUInteger) index {
// Holy O(N) algorithms, BatMan
Node *scan = _head;
for (NSUInteger i = 0; i < index; i++) {
scan = scan.next;
}
return scan.string;
} // stringAtIndex
@end // LifoList
// --------------------------------------------------
// Some timing tests.
// http://weblog.bignerdranch.com/316-a-timing-utility/
#import <mach/mach_time.h> // for mach_absolute_time() and friends
static CGFloat BNRTimeBlock (void (^block)(void)) {
mach_timebase_info_data_t info;
if (mach_timebase_info(&info) != KERN_SUCCESS) return -1.0;
uint64_t start = mach_absolute_time ();
block ();
uint64_t end = mach_absolute_time ();
uint64_t elapsed = end - start;
uint64_t nanos = elapsed * info.numer / info.denom;
return (CGFloat)nanos / NSEC_PER_SEC;
} // BNRTimeBlock
#define LIFO_COUNT 10000
static void TimeLifoList () {
NSLog (@"Timing iteration of %d elements", LIFO_COUNT);
// Build up the list with a bunch of nodes.
LifoList *lifolist = [[LifoList alloc] init];
NSString *value = @"hi";
for (NSUInteger i = 0; i < LIFO_COUNT; i++) {
[lifolist addString: value];
}
// See how long it takes to iterate using stringAtIndex. This is
// O(N^2), so will take a long time.
__block NSUInteger count = 0;
CGFloat indexingTime = BNRTimeBlock (^{
for (NSUInteger i = 0; i < lifolist.count; i++) {
(void)[lifolist stringAtIndex: i];
count++;
}
});
assert (count == LIFO_COUNT); // paranoia
assert (count == lifolist.count);
NSLog (@"lifo list indexing time: %f", indexingTime);
// Now with fast indexing. This is O(N), so will be much, much faster.
// Most sane people won't be using a linked list for indexed access.
count = 0;
CGFloat fastEnumerationTime = BNRTimeBlock (^{
for (NSString *string in lifolist) {
count++;
}
});
assert (count == LIFO_COUNT);
assert (count == lifolist.count);
NSLog (@"fast enumeration time: %f", fastEnumerationTime);
} // timeLifoList
int main (void) {
LifoList *lifolist = [[LifoList alloc] init];
// Exhaustive unit test.
[lifolist addString: @"hello"];
[lifolist addString: @"there"];
[lifolist addString: @"greeble"];
for (NSUInteger i = 0; i < lifolist.count; i++) {
NSLog (@"%ld : %@", i, [lifolist stringAtIndex: i]);
}
TimeLifoList ();
return 0;
} // main
#if 0
% clang -g -fobjc-arc -Weverything -framework Foundation -o fast-enum fast-enum.m
% ./fast-enum
0 : greeble
1 : there
2 : hello
lifo list indexing time: 3.352057
fast enumeration time: 0.001404
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment