Objective-C 高性能的循环 已翻译 100%

isaced 投递于 2014/02/13 11:18 (共 14 段, 翻译完成于 02-14)
阅读 8187
收藏 66
4
加载中

A common task in Cocoa programming is to loop through a collection of objects (e.g. an NSArray, NSSet or NSDictionary). This seemingly simple problem has a wide variety of solutions, many of them with subtle performance considerations.

The Need for Speed

First, a disclaimer: The raw speed of one Objective-C method versus another is one of the last things you should worry about when programming – the difference is unlikely to be dramatic enough to matter compared with other, more important considerations, such as code clarity and readability.

But not prioritising speed is no excuse for not understanding it. You should always learn the performance implications of the code you are writing so that on the rare occasions when it does matter, you’ll know what to do.

Also, in the case of looping, much of the time it doesn’t matter which technique you choose from a readability or clarity perspective, so you might as well choose the fastest. There’s no point writing code that is slower than it needs to be.

已有 1 人翻译此段
我来翻译

With that in mind, here are the options:

The Classic For Loop

for (NSUInteger i = 0; i < [array count]; i++){
  id object = array[i];
  …}

This is a simple and familiar way to loop through an array; it’s also pretty poor from a performance perspective. The biggest problem with this code is that we’re calling the count method each time round the loop. The count doesn’t change, so this is redundant. Normally the C compiler would optimise away something like this, but the dynamic nature of Objective-C means that method calls cannot be optimised away automatically. So, to improve performance, it’s worth storing the count in a variable before beginning the loop, like this:

NSUInteger count = [array count];for (NSUInteger i = 0; i < count; i++){
  id object = array[i];
  …}
已有 1 人翻译此段
我来翻译

NSEnumerator

NSEnumerator is an alternative way of looping through collections. All collections have one or more enumerator methods that return a new NSEnumerator instance each time they are called. A given NSEnumerator contains an internal pointer to the first object in the collection, and has a nextObject method that returns the current object and increments the pointer. You call it repeatedly until it returns nil, indicating the end of the collection has been reached:

id obj = nil;NSEnumerator *enumerator = [array objectEnumerator];while ((obj = [enumerator nextObject]));{
  …          
}

The performance of NSEnumerator is comparable to an ordinary for loop, but it’s useful because it abstracts the concept of indexing, meaning it can be used with structures such as linked lists, or even infinite sequences or data streams where the item count is unknown or undefined.

已有 1 人翻译此段
我来翻译

Fast Enumeration

Fast enumeration was introduced in Objective-C 2.0 as a more convenient (and faster, obviously) replacement for the traditional NSEnumerator. It doesn’t make the enumerator class obsolete because it is still used for situations such as reverse enumeration, or when you want to mutate the collection (more on this later).

Fast enumeration adds a new enumeration method that looks like this:

- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state 
   objects:(id *)stackbuf count:(NSUInteger)len;

If you’re thinking “that doesn’t look very convenient!”, I don’t blame you. But the new method came coupled with a new loop syntax, the for…in loop. This uses the new enumeration method behind the scenes, and significantly reduces both the syntax and performance overheads of using the traditional for loop or NSEnumerator approaches:

for (id object in array){
  …}
已有 2 人翻译此段
我来翻译

Enumeration blocks

With the advent of blocks, Apples added a fourth enumeration mechanism based on the block syntax. This is arguably more unwieldy than fast enumeration, but does have the benefit of returning both the object and index, whereas the other enumeration methods just return the object.

Another key feature of enumeration blocks is the option of concurrent enumeration (enumerating the objects on several threads in parallel). This isn’t always useful, depending on exactly what you are doing in your loop, but for cases where you are doing a lot of work per item, and where you don’t care about the enumeration order, this might yield a significant performance boost on multicore processors (which all modern Macs and iOS devices have).

已有 1 人翻译此段
我来翻译

Benchmarks

So how do these methods stack up, performance-wise? Here is a simple benchmark command-line app that compares performance of enumerating an array using the various different methods. We’ve run it with ARC disabled to prevent any behind-the-scenes retain or release from distorting the results. Because this is running on a fast Mac, all these methods are so fast that we’ve actually had to use an array of 10,000,000 (ten million) objects to get measurable results. If you decide to run this test on an iPhone, it would be wise to use a much smaller count!

To compile the code:

  • Save the code in a file with the name benchmark.m

  • From terminal, compile the application:
    clang -framework Foundation benchmark.m -o benchmark

  • Run the app: ./benchmark

#import <Foundation/Foundation.h> int main(int argc, const char * argv[]){
  @autoreleasepool  {
    static const NSUInteger arrayItems = 10000000;
     NSMutableArray *array = [NSMutableArray arrayWithCapacity:arrayItems];    for (int i = 0; i < arrayItems; i++) [array addObject:@(i)];
    array = [array copy];
 
    CFTimeInterval start = CFAbsoluteTimeGetCurrent();
     // Naive for loop
    for (NSUInteger i = 0; i < [array count]; i++)
    {
      id object = array[i];    } 
    CFTimeInterval forLoop = CFAbsoluteTimeGetCurrent();
    NSLog(@"For loop: %g", forLoop - start);
     // Optimized for loop
    NSUInteger count = [array count];    for (NSUInteger i = 0; i <  count; i++)
    {
      id object = array[i];    } 
    CFTimeInterval forLoopWithCountVar = CFAbsoluteTimeGetCurrent();
    NSLog(@"Optimized for loop: %g", forLoopWithCountVar - forLoop);
     // NSEnumerator
    id obj = nil;    NSEnumerator *enumerator = [array objectEnumerator];    while ((obj = [enumerator nextObject]))
    {     } 
    CFTimeInterval enumeratorLoop = CFAbsoluteTimeGetCurrent();
    NSLog(@"Enumerator: %g", enumeratorLoop - forLoopWithCountVar);
     // Fast enumeration
    for (id object in array)
    {     } 
    CFTimeInterval forInLoop = CFAbsoluteTimeGetCurrent();
    NSLog(@"For…in loop: %g", forInLoop - enumeratorLoop);
     // Block enumeration
    [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {     }];
 
    CFTimeInterval enumerationBlock = CFAbsoluteTimeGetCurrent();
    NSLog(@"Enumeration block: %g", enumerationBlock - forInLoop);
     // Concurrent enumeration
    [array enumerateObjectsWithOptions:NSEnumerationConcurrent 
      usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {     }];
 
    CFTimeInterval concurrentEnumerationBlock = CFAbsoluteTimeGetCurrent();
    NSLog(@"Concurrent enumeration block: %g", 
      concurrentEnumerationBlock - enumerationBlock);  }
  return 0;}

The results are shown below:

$ For loop: 0.119066
$ Optimized for loop: 0.092441
$ Enumerator: 0.123687
$ For…in loop: 0.049296
$ Enumeration block: 0.295039
$ Concurrent enumeration block: 0.199684
已有 1 人翻译此段
我来翻译

Pay no attention to the magnitudes of these timings. What we are interested in is their relative size compared with one another. If we place them in order, fastest first, we get:

  1. For…in loop – the fastest.

  2. Optimized for loop – 2 times slower than for…in.

  3. Unoptimized for loop – 2.5 times slower than for…in.

  4. Enumerator – about the same as unoptimised for loop.

  5. Concurrent enumeration block – about 6 times slower than for…in.

  6. Enumeration block – almost 6 times slower than for…in.

For…in is the standout winner. Clearly they call it fast enumeration for a reason! Concurrent enumeration seems a little faster than single-threaded, but you shouldn’t read too much into that: We’re enumerating a very large number of objects here, but for a smaller array the overhead of concurrent execution outweighs the benefits.

The primary advantage of concurrent execution comes into play when the code inside your loop takes a significant time to execute. If you do a lot of work inside your loop, consider trying parallel enumeration if you don’t care about the order (but measure to see if it’s faster, don’t assume).

已有 1 人翻译此段
我来翻译

Other Collection Types

So what about other collection types, such as NSSet and NSDictionary? NSSet is unordered, so has no concept of fetching an object by index. We can benchmark enumeration though:

$ Enumerator: 0.421863
$ For…in loop: 0.095401
$ Enumeration block: 0.302784
$ Concurrent enumeration block: 0.390825

The results are similar to NSArray; again, for…in is the clear winner. What about NSDictionary? NSDictionary is a bit different because we have both keys and objects to iterate over. It’s possibly to just iterate over either keys or values in a dictionary, but we typically need both. Here is an adapted version of our array benchmark to handle NSDictionary:

#import <Foundation/Foundation.h> int main(int argc, const char * argv[]){
  @autoreleasepool  {
    static const NSUInteger dictItems = 10000;
     NSMutableDictionary *dictionary = 
      [NSMutableDictionary dictionaryWithCapacity:dictItems];    for (int i = 0; i < dictItems; i++) dictionary[@(i)] = @(i);
    dictionary = [dictionary copy];
 
    CFTimeInterval start = CFAbsoluteTimeGetCurrent();
     // Naive for loop
    for (NSUInteger i = 0; i < [dictionary count]; i++)
    {
      id key = [dictionary allKeys][i];      id object = dictionary[key];    } 
    CFTimeInterval forLoop = CFAbsoluteTimeGetCurrent();
    NSLog(@"For loop: %g", forLoop - start);
     // Optimized for loop
    NSUInteger count = [dictionary count];    NSArray *keys = [dictionary allKeys];    for (NSUInteger i = 0; i <  count; i++)
    {
      id key = keys[i];      id object = dictionary[key];    } 
    CFTimeInterval forLoopWithCountVar = CFAbsoluteTimeGetCurrent();
    NSLog(@"Optimized for loop: %g", forLoopWithCountVar - forLoop);
     // NSEnumerator
    id key = nil;    NSEnumerator *enumerator = [dictionary keyEnumerator];    while ((key = [enumerator nextObject]))
    {
      id object = dictionary[key];    } 
    CFTimeInterval enumeratorLoop = CFAbsoluteTimeGetCurrent();
    NSLog(@"Enumerator: %g", enumeratorLoop - forLoopWithCountVar);
     // Fast enumeration
    for (id key in dictionary)
    {
      id object = dictionary[key];    } 
    CFTimeInterval forInLoop = CFAbsoluteTimeGetCurrent();
    NSLog(@"For…in loop: %g", forInLoop - enumeratorLoop);
     // Block enumeration
    [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {     }];
 
    CFTimeInterval enumerationBlock = CFAbsoluteTimeGetCurrent();
    NSLog(@"Enumeration block: %g", enumerationBlock - forInLoop);
     // Concurrent enumeration
    [dictionary enumerateKeysAndObjectsWithOptions:NSEnumerationConcurrent 
      usingBlock:^(id key, id obj, BOOL *stop) {     }];
 
    CFTimeInterval concurrentEnumerationBlock = CFAbsoluteTimeGetCurrent();
    NSLog(@"Concurrent enumeration block: %g", 
      concurrentEnumerationBlock - enumerationBlock);  }
  return 0;}
已有 1 人翻译此段
我来翻译

NSDictionary is much slower to populate than NSArray or NSSet, so we’ve reduced the item count to 10,000 (ten thousand) to avoid locking up the machine. You should therefore ignore how the magnitudes of the results below compare with those of NSArray because we are using 1000 times fewer objects:

$ For loop: 2.25899
$ Optimized for loop: 0.00273103
$ Enumerator: 0.00496799
$ For…in loop: 0.001041
$ Enumeration block: 0.000607967
$ Concurrent enumeration block: 0.000748038

The unoptimized for loop here is spectacularly slow because we are copying the key array each time. By storing both the keys array and count in variables we get much better speeds. The cost of object lookup now dominates the other factors, so there is little difference between using a for loop, NSEnumerator or for…in. But the enumeration block method, which returns both key and value in a single function, is now the fastest option.

已有 1 人翻译此段
我来翻译

Reverse Gear

Base on what we’ve seen, if all other factors are equal, you should try to use for…in (aka, fast enumeration) when looping over arrays, and block enumeration when looping over dictionaries. There are some scenarios where this isn’t possible though, such as when we need to enumerate backwards, or when we want to mutate the collection as we’re going through it.

To enumerate an array backwards, we can call the reverseObjectEnumerator method to get an NSEnumerator that steps through the array from the last to the first item. NSEnumerator, like NSArray itself, supports the fast enumeration protocol. That means we can still use for…in with this approach, with no loss of speed or concision:

  for (id object in [array reverseObjectEnumerator]) 
  {
    …  }

(In case you are wondering, there’s no equivalent method for NSSet or NSDictionary, but enumerating an NSSet or NSDictionary backwards is meaningless anyway, since the keys are unordered.)

If you want to use block enumeration, there’s an NSEnumerationReverse option you can use, like this:

  [array enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    …  }];
已有 1 人翻译此段
我来翻译
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(10)

且行且珍惜吧
且行且珍惜吧

引用来自“afpro”的评论

Object-C的语法简直就是XXXXX

我顶你
afpro
afpro
Object-C的语法简直就是XXXXX
pollex
pollex

引用来自“sucker”的评论

这种编译器自己做的事,非要人工去优化啊,每天的破事都忙不完了,人艰不拆啊

在很多三流论坛里,这些还是高手技巧呢,比如那个著名的移位代替乘法
pollex
pollex

引用来自“sucker”的评论

这种编译器自己做的事,非要人工去优化啊,每天的破事都忙不完了,人艰不拆啊

在很多三流论坛里,这些还是高手技巧呢,比如那个著名的移位代替乘法
Adams丶
Adams丶
大数据考虑多线程循环。不知为何要关闭ARC
无锡首席大都督程序员
这种编译器自己做的事,非要人工去优化啊,每天的破事都忙不完了,人艰不拆啊
isaced
isaced
大功告成!
isaced
isaced

引用来自“LeoXu”的评论

引用来自“isaced”的评论

@LeoXu 大哥,你看看这篇文章标题翻译对了吗?

没看出啥问题啊

哦,那就好。你这速度太猛了。。。我也尝试翻了下最后一段,嘿嘿~
LeoXu
LeoXu

引用来自“isaced”的评论

@LeoXu 大哥,你看看这篇文章标题翻译对了吗?

没看出啥问题啊
isaced
isaced
@LeoXu 大哥,你看看这篇文章标题翻译对了吗?
返回顶部
顶部