Fast Enumeration Part 2 - Partial Iteration of an Array

It’s been a while since I wrote the first part about Enumeration-Benchmarks. In this second part, I investigate the performance of various methods for achieving a task that seems to be quite common to me: enumerating ‘all but the last’ elements.

Enumerating ‘all but the last’ Elements

or more general, enumerate only a continuous subset of the elements in an array. A typical example of this is the need to consider the neighbors of each element. In particular, methods for iterating subarrays will be needed in the upcoming part 3.

Counting for-loop

This first sample is pretty straight forward, you write a for-loop that counts an index over the range of objects you want to enumerate and then just take the object at that index out of the array.

// Sample 1
for (NSUInteger i = 0; i < [_testArray count] - 1; i++)
{
    NSNumber *number = [_testArray objectAtIndex:i];
    // Your Code here
}

Fast-Enumeration with Check

Another simple way to do this (or skip specific elements in general) is to use fast enumeration and check the current element in each iteration with a prior defined element that should be skipped.

// Sample 2
NSNumber *lastNumber = [_testArray lastObject];
for(NSNumber *number in _testArray)
{
    // We can do this pointer-check here because the we search for the exact same object here
    if(number != lastNumber)
    {
        // Your Code here
    }
}

Enumerating a Sub-Array

An idea that may come to your mind is to define a subarray that contains only the elements in the range needed, and then use fast enumeration on that new array:

// Sample 3
NSRange subArrayRange = NSMakeRange(0, [_testArray count] - 1);
NSArray *subArray = [_testArray subarrayWithRange:subArrayRange];
for(NSNumber *number in subArray)
{
    // Your Code Here
}

You can define an arbitrary sub-range of the whole array, but contrary to the method with an ignore-set, there can only be one connected sub-range.

Attention, this Method needs a whole new copy of the subarray and therefore requires additional memory space in the magnitude of O(n)!

C-Style Subarray

Let’s get a little bit more fancy. The preconception against high level language constructs is that they are slower than lower level constructs. Well, lets see if the benchmark results confirm this. NSArray also provides a method that returns all objects in a given range as c-style array.

// Sample 4
NSRange subArrayRange = NSMakeRange(0, [_testArray count] -1);
__unsafe_unretained id *subarray = (__unsafe_unretained id *)malloc(sizeof(id) * subArrayRange.length);[_testArray getObjects:subarray range:subArrayRange];
for (NSUInteger i = 0; i < subArrayRange.length; i++)
{
    NSNumber *number = subarray[i];
    // Your Code Here
}
free(subarray);

Attention, this Method needs a whole new copy of the subarray and therefore requires additional memory space in the magnitude of O(n)!

Enumerating all but some Distinct Objects

The task of “enumerating all but the last object” can be seen as a special case of the more general problem of “enumerate all but some distinct objects”. Methods for the more general case can of course still be used to achieve the specialized task of excluding the last object from enumeration. Next, I’ll present some methods for the general case:

Fast Enumeration with Ignore-Set

The idea of this method is to just put all the elements that have to be excluded from enumeration into a set and then in the enumeration-loop, check if the current element is excluded and if thats the case, skip it. Sample 5 shows the usage for excluding the last element, Sample 6 shows the usage for the general case of excluding some distinct objects. Usage of this Method is easy and intuitive, because you only put the elements that you want to exclude into the ignore-set.

// Sample 5
NSSet *ignoreItems = [NSSet setWithObject:[_testArray lastObject]];
for(NSNumber *number in _testArray)
{
    if(![ignoreItems containsObject:number])
    {
        // Your Code here
    }
}

// Sample 6
NSNumber *elementToExclude1 = [_testArray objectAtIndex:3];
NSNumber *elementToExclude2 = [_testArray objectAtIndex:3];
NSNumber *elementToExclude3 = [_testArray objectAtIndex:3];
// ...
NSSet *ignoreItems = [NSSet setWithObjects:elementToExclude1, elementToExclude2, elementToExclude3, ..., nil];
for(NSNumber *number in _testArray)
{
    if(![ignoreItems containsObject:number])
    {
        // Your Code here
    }
}

Blocks and Indexset

NSArray offers another method of enumeration its elements based on blocks and NSIndexSet. This a more sophisticated way to enumerate arbitrary elements than to build a set of elements you want to ignore, instead you build an NSIndexSet with indices that you really want to enumerate. For the special case (Sample 7), this IndexSet contains all indices except the last one, for the general case (Sample 8), it contains all indices except the indices of Objects that you want to exclude.

This method is more efficient (which will be shown by the benchmark results) and for constructing the IndexSet conveniently there are two methods. If you want to exclude just few elements, its more convenient to first take all the indices into the set and remove the ones that you want to exclude (for example with [indexSet removeIndexes:indexesToIgnore];), if you want to exclude many, you would rather just build directly the IndexSet of the remaining elements.

// Sample 7
NSRange subArrayRange = NSMakeRange(0, [_testArray count] -1);
NSIndexSet *indexSet = [NSIndexSet indexSetWithIndexesInRange:subArrayRange];
[_testArray enumerateObjectsAtIndexes:indexSet options:0 usingBlock:^(NSNumber *number, NSUInteger idx, BOOL *stop)
{
    // Your Code Here
}];

// Sample 8
NSMutableIndexSet *indexesToIgnore = [[NSMutableIndexSet alloc]init];
// All indices for ignored elements
[indexesToIgnore addIndex:3];
[indexesToIgnore addIndex:42];
[indexesToIgnore addIndex:1337];
// Index-Set with all Indices
NSRange subArrayRange = NSMakeRange(0, [_testArray count]);
NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSetWithIndexesInRange:subArrayRange];
// Remove the excluded indices
[indexSet removeIndexes:indexesToIgnore];
[_testArray enumerateObjectsAtIndexes:indexSet options:0 usingBlock:^(NSNumber *number, NSUInteger idx, BOOL *stop)
{
    // Your Code Here
}];

Blocks and Indexset Concurrent

Blocks are nice and easy. What if the code in the loop body takes a lot of computation time and you want to take advantage of multicore processors? Well its just as easy as changing the options in the last sample to NSEnumerationConcurrent.

// Sample 9
NSRange subArrayRange = NSMakeRange(0, [_testArray count] -1);
NSIndexSet *indexSet = [NSIndexSet indexSetWithIndexesInRange:subArrayRange];
[_testArray enumerateObjectsAtIndexes:indexSet options:NSEnumerationConcurrent usingBlock:^(NSNumber *number, NSUInteger idx, BOOL *stop)
{
    // Your Code Here
}];

Results

Like in part 1, benchmark results were gathered by running the samples on an iPad 2 with an array containing 1.000.000 NSNumber Objects (numbers from 0 to 999.999). Total time is the time needed to iterate over the whole array. Time per element is the total time divided by the total number of objects in the array. The factor is relative to fast enumeration of the whole array.

Because some of the methods include non-neglectible setup overhead (i.e. construction and copying of the subarray), I have meassured that time seperately for better comparability with the pure enumeration results of the last part.

Analysis

Running the Methods with Instruments reveals some insights about how the different samples work

• Use of the for-loop method in sample 1 does not pay off. :) The call objectAtIndex: in every cycle to get the object costs way to much time.
• The fastest method is sample 2 with the pointer-check. The check with ‘==’ is possible because we know the exact instance of the element we want to exclude and this pointer check is very cheap in terms of computation time.
• Enumerating the Subarray like in sample 3 is in terms of the pure enumeration even faster than sample 2 because it is pure fast enumeration, but the construction of the subarray takes a substantial amount of time (O(n))
• Comparing sample 3 to sample 4 reveals that the ‘low level’ c style approach is not worth it. Somehow the construction of the subarray is much faster when creating a c array than creating an NSArray, but the enumeration itself is much slower. I should have compared the c-method for the whole array in part 1 as well, but this impressively shows how optimized fast enumeration really is.
• The self-built ignore-list in sample 5 is not worth it, even if you take into consideration that it is more powerful (excluding more objects than just the last). If you need the general case, then why shouldn’t you use blocks? The difference is even more apparent when compared to the results of sample 6 and 8, where the time for the ignore-list increases notably with the number of elements in the ignore-set. The same difference in ignored elements causes no significant difference for the block based methods.
• I like blocks, and once again it is shown how easy it is to utilize multicore processors. If the computation time necessary in the loop body is of a noteworthy amount, I would choose blocks with concurrent execution.

Sample Project

The Sample Project that was linked in part 1 also contains the samples used for this part.

You can get it here: https://github.com/iv-mexx/enumerationbenchmark