NSSet Iteration consumes more time than NSMutableArray Iteration and NSArray Iteration consumes more time than NSMutableArray Iteration

Question

Even though , I traverse through the following NSSet,NSMutableArray,NSFastEnumeration documentation, I cannot find satisfactory source for the below mentioned scenario:

Here , the NSMutableArray , NSArray and NSSet contains equally 10000000 objects.

for (NSString *strIn in MutableArray) //NSMutableArray
{
    // same Implementation
}
NSLog(@"Time for Mutable Array  %d Iteration : %f",ObjectCount,[[NSDate date]timeIntervalSinceDate:startDate]);
startDate = [NSDate date];
for (NSString *strIn in array)  //NSArray
{
    // same Implementation
}
NSLog(@"Time for  NSArray  %d Iteration : %f",ObjectCount,[[NSDate date]timeIntervalSinceDate:startDate]);
startDate = [NSDate date];
for (NSString *strIn in Set) //NSSet
{
    // same Implementation
}
NSLog(@"Time for Set  %d Iteration : %f",ObjectCount,[[NSDate date]timeIntervalSinceDate:startDate]);

The output is as follows:

Time for NSMutableArray 10000000 Iteration : 0.048785

Time for NSArray 10000000 Iteration : 0.390537

Time for NSSet 10000000 Iteration : 4.684203

Why there such a huge difference between NSSet and NSArray iterating time.

Please be thorough with your answers.

Edit : I've found the actual cause behind the above iteration time it's because of the unequal count in array and Set . I have posted the actual question here. Also , I can post the same here but it seems too undocumented nature for this page and also the reason behind the cause was also deviated. Again, thanks for everyone with their response.

Very interesting, just to validate your testing procedure, did you try changing the order of iterations? This way you assure the external factors like temporary performance drops caused by other apps and what not don't influence your results. Also, it would be good to actually iterate a couple of times and use the average time values. — lawicko, Nov 13 '13 at 10:54
@lawicko: Thanks for your comment. I have changed the order of iterations in all the possible 3! ways but approximately it remained the same. Also , only the frequent re-executions varies iterating time up to micro level. — itechnician, Nov 13 '13 at 11:03
I would expect the set to be somewhat slower, but the two array values should be the same, given that their implementations are identical. There is clearly a problem with your method. — Hot Licks, Nov 13 '13 at 12:23

score 3 · Answer 1 · answered Nov 13 '13 at 11:23

I disagree with your results:

#import <Foundation/Foundation.h>

#define COLLECTION_SIZE 10000000

static NSString *randomString() {
    unichar buffer[18];
    NSUInteger size = (arc4random() % 12) + 6;
    for (NSUInteger i = 0; i < size; i++) {
        buffer[i] = (arc4random() % 93) + '!';
    }
    return [[NSString alloc] initWithCharacters:buffer length:size];
}

static NSSet *createCollection(NSUInteger size) {
    NSMutableSet *collection = [[NSMutableSet alloc] init];
    for (NSUInteger i = 0; i < size; i++) {
        for (;;) {
            NSString *s = randomString();
            if (![collection member:s]) {
                [collection addObject:s];
                break;
            }
        }
    }
    return collection;
}

static NSTimeInterval timedIter(id<NSFastEnumeration> collection) {
    NSUInteger totalLength = 0;
    NSDate *startDate = [NSDate date];
    for (NSString *s in collection) {
        totalLength += [s length];
    }
    return [[NSDate date] timeIntervalSinceDate:startDate];
}

int main(int argc, const char **argv) {
    @autoreleasepool {
        NSSet *set = createCollection(COLLECTION_SIZE);
        NSArray *array = [set allObjects];
        NSMutableArray *mutArray = [[set allObjects] mutableCopy];

        NSLog(@"set iteration=%f", timedIter(set));
        NSLog(@"array iteration=%f", timedIter(array));
        NSLog(@"mutArray iteration=%f", timedIter(mutArray));
    }
    return 0;
}

$ clang -o itertime itertime.m -fobjc-arc -framework Foundation
$ ./itertime
2013-11-13 11:23:13.344 itertime[77576:707] set iteration=0.422592
2013-11-13 11:23:13.654 itertime[77576:707] array iteration=0.309387
2013-11-13 11:23:13.964 itertime[77576:707] mutArray iteration=0.309107

score 2 · Answer 2 · answered Nov 13 '13 at 11:05

The difference is way to big. Probably it is like that, because you have emitted loop body. I just did the same with 10M NSNumbers and difference is much smaller:

Time for __NSArrayM: 0.334106
Time for __NSArrayI: 0.335368
Time for __NSSetI: 0.373651

You should provide loop body, because right now is really hard to tell why you have such a big difference.

NSSet Iteration consumes more time than NSMutableArray Iteration and NSArray Iteration consumes more time than NSMutableArray Iteration

2 Answers2