CODEWITHSUNDEEP
objective-carraysperformancefor-loopfast-enumeration
MeXx
MeXx

Reputation: 3357

Fast Enumeration slower than for-loop in nested enumeration (with test-results)?

I know there are quite some topics that seem to be about the exact same thing, but I didn't find one that really was about what I wanted.

So I was curious and wanted to compare the performance of Fast Enumeration to NSEnumerator and a for loop. (This is the part that is asked quite frequently)

First I compared Fast Enumeration:

for(NSNumber *number in testArray)
{
    assert(number);
}

NSEnumerator:

NSEnumerator *enumerator = [testArray objectEnumerator];
NSNumber *number;
while (number = [enumerator nextObject]) 
{
    assert(number);
}

for Loop:

for(NSUInteger i = 0; i < [testArray count]; i++)
{
    NSNumber *number = [testArray objectAtIndex:i];
    assert(number);
}

My testArray was an Array consisting of NSNumbers from 0 to 1,000,000 and I ran the tests 100 Times after each other and calculated the mean run time for each test.

Also I ran them on my iPad 2

Results: (mean time of all 100 runs)

As expected, Fast Enumeration is by far the fastest, and NSEnumerator is still a little bit faster than the for-loop, but this was for enumerating quit a large Array

So here's the not so frequent Question:

Actually I was interested in something else: Enumeration in an array to compare each object with each other in the array

First attempt with a nested for-loop:

for(int i = 0; i < [testArray count]-1; i++)
{
    NSNumber *number = [testArray objectAtIndex:i];
    for(int j = i+1; j < [testArray count]; j++)
    {
        NSNumber *innerLoopNumber = [testArray objectAtIndex:j];
        assert(innerLoopNumber);
        assert(number);
    }
}

For these Tests I had to reduce the size of the array and the number of runs to get them done in a reasonable time, because number of iterations grows of course with O(n^2). So I ran them with an array with 5.000 NSNumbers and repeated the tests 5 times.

Result: 7.360645s for 1 run

So I thought, sure, fast Enumeration should be faster. But to achieve the triangular Pattern to avoid comparing each pair of elements two times, I had to mix Fast Enumeration in the outer loop with NSEnumerator in the inner loop

for(NSNumber *number in testArray)
{
    NSEnumerator *reverseEnumterator = [testArray reverseObjectEnumerator];
    NSNumber *innerLoopNumber = reverseEnumterator.nextObject;
    while(innerLoopNumber && ![innerLoopNumber isEqualToNumber:number])
    {
        innerLoopNumber = reverseEnumterator.nextObject;
        assert(innerLoopNumber);
        assert(number);
    }
}

And to my surprise, this was much slower: 18.086980s for 1 run

I then tried a hybrid version as well, using Fast Enumeration for the outer loop and a for-loop for the inner one:

int counter = 0;
for(NSNumber *number in testArray)
{
    for(int j = counter +1; j < [testArray count]; j++)
    {
        NSNumber *innerLoopNumber = [testArray objectAtIndex:j];
        assert(innerLoopNumber);
        assert(number);
    }
    counter++;
}

Result: 7.079600s for 1 Run

Just slightly faster than the plain for-loop.

the numbers in one place:

So I wonder, why is that? Does Fast Enumeration only work well when it is "undisrupted", does the use of NSEnumerator interfere with Fast Enumeration? Or am I just missing something and my Method is wrong?

Upvotes: 4

Views: 1921

Answers (1)

Dustin
Dustin

Reputation: 6803

You're calling additional methods in your fast enumeration loop. Objective-c has non-trivial method call overhead, so your problem is in the setup of the nested loops. As you can see fast enumeration + for loop is faster than for loop + for loop, and here you're avoiding additional method calls.

Upvotes: 3

Related Questions