本文是关于通过Objective C++的强大功能提高iPhone程序的性能。通过讨论现实世界中Savoy的Spots应用程序遇到的问题，本文展示了通过3个步骤对程序进行优化使其顺利运行的过程。


Spots


使用Objective C++提高iPhone应用程序的性能


我十分喜爱软件开发的一个原因是总是会遇到这样那样的问题，而总能找到相应的解决方法。在开发Spots时，我多次遇到了UI设计的问题。为 iPhone设计一个精简的用户界面是不容易的。比如，我应该提供一个提供者过滤器（指Hotspot）按钮或将其放在Settings.app中？关于这个问题，我至少改变了二十次主意？


本文不是关于用户界面设计而是有关编程与性能。本文并不是针对用户界面而是有关编程和性能。一个最大的难题是地图的绘制（屏幕下方的长方形）。经过几种方法的试用，我发现在绘制230，000个点时，只有使用OpenGL以及大量的旁门左道才能使绘图的性能勉强被接受。根据放大的级别以及可见点点数量，我最后使用了三种不同的技术。由于我需要地图交互动作（拖动和缩放）尽可能地平滑，理想情况下为60HZ，性能是最为重要的问题。


map_spots


本文中我将分享一些能提高性能的技术。虽然它们都很简单和直接，但因为在Cocoa中很少见，所以我还是花了不少时间。例如，尽管C++和Objective C可以非常高效地混合使用，但我在Cocoa中并没有见到许多C++。当你的目标是高性能时，Objective C++是纯Cocoa的很好的扩展。而在iPhone上，性能是应该首先需要考虑到因素。


难题


对于分布在一个矩形区域包括230，000个热点位置的地图（麦卡托投影的世界地图 the world map in mercator projection），首先必须清楚当前地图矩形区域中有多少个可见点，因为此数值可以决定使用何种绘图技术。指标值必须归一，因此整个地图覆盖了一个{{0.0, 1.0}, {0.0, 1.0}}的矩形区域。通常情况下，程序使用的地图矩形是很小的：通常小于整个地图宽度和高度的百分之二。



map


但是我怎样有效地在数据库成千上万的点中找到可见点的数量？


我准备了一个XCode项目，它包括了这里讨论的所有代码。此示例项目并未包括了所有点的原始数据库。它仅包含了一些世界地图上的随机数据。虽然与真实情况有所区别，但它们的处理方法与我收集的原始数据的大同小异。


第一种方法: 普通Cocoa方法


第一种方法十分简单而且并没有采用十分高效的方法。使用Object C对象（@class Spot）来表示位置，它们以NSArrary的形式被保存在一个数据库对象中（@class SpotsDB1）。

@interface Spot : NSObject {
    CGPoint _position;
}
@property (nonatomic) CGPoint position;
@end

@interface SpotsDB1 : NSObject {
    NSArray* _spots;
}
- (NSUInteger)countSpotsInRect:(CGRect)rect;
@end


为进行一个指定CGRect内地位置计数，数据库对象简单地循环整个数组并检查各位置。


NSUInteger count = 0;
for (Spot* spot in _spots) {
if (CGRectContainsPoint(aRect, spot.position))
++count;
}


使用上述代码，在总数为230，000个点的区域上的任意一个{0.02, 0.02}矩形内进行计数大概需要250毫秒。太糟糕了，如果你的目标是刷新率60Hz，那么你只有16 ms绘制一帧。使得此方案过慢的原因不仅在于其缺乏聪明的算法，而且在循环中浪费了许多时间在调用了几个函数上。另一个对性能产生负面影响的因素是位置被保存在NSArray中的对象，这是由于对象占用了大量的内存以及数组指针的非直接性导致了处理器时间的增加。


第二种方法: 简单优化


为使同样的方案运行得更快，我们只需简单地将位置存储与一个更为紧凑的数据结构中：一个CGPoint结构的标准C数组。为使用方便，我们将C数组保存在一个NSMutableData 对象中。


_spotCount = [spots count];
_spotsData = [[NSMutableData alloc] init];
for (Spot* spot in spots) {
CGPoint p = spot.position;
[data appendBytes:&p length:sizeof(CGPoint)];
}


消除了循环内函数调用的负面影响，我们使得性能有四倍的提升：


CGFloat xMin = CGRectGetMinX(aRect);
CGFloat yMin = CGRectGetMinY(aRect);
CGFloat xMax = CGRectGetMaxX(aRect);
CGFloat yMax = CGRectGetMaxY(aRect);

CGPoint* begin = (CGPoint*)[_spotsData bytes];
CGPoint* end = begin + _spotCount;

NSUInteger count = 0;
for (CGPoint* i = begin; i != end; ++i) {
if (i->x > xMin && i->y > yMin && i->x < xMax && i->y < yMax)
++count;
}


在没有改变基本算法的基础上，点计数的计算现在只需55毫秒，这大概比原来方法快了四倍。另一个好处是现在使用的内存是原来版本的一半。

第三种方法：算法优化


当然，还有许多聪明的方法来优化平面地图点的查询。例如，你可以使用四边形树来保存这些点。在本例中我使用了一种比较简单的解决方案，所以没有涉及数据存储的方式。我使用了C++的内置功能所以甚至不需要写任何代码来处理数据的存储。


sorted


我的设想是将数组中的位置从左至右分类。这样做的好处是确定指定正方形的左右边界十分快速（见下图）。当数组中边界已知时，仅需要检查边界间的点。


sorted2


所以此算法是有关快速寻找边界的。我们使用的是二进制搜索， 它适用于已排序的数组。它并不检查每个值以找到匹配的位置，而是直接跳到数组的中点，检查其值是小于还是大于给点值，然后跳到剩余部分的中心点，重复以上步骤。使用这种方法，二进制搜索需要 log2(n)的时间来查找最佳元素。对于一个拥有230，000个位置的数组，只需22次搜索！回到代码，我们发现上述算法的实现是很简单的。当然，我们必须为数据库排序：

// comparison function for array sorting
NSInteger leftToRight(Spot* a, Spot* b, void* context) {
    CGFloat xa = a.position.x;
    CGFloat xb = b.position.x;
    if (xa < xb)
        return NSOrderedAscending;
    return xa > xb ? NSOrderedDescending : NSOrderedSame;
}

...

spots = [spots sortedArrayUsingFunction:leftToRight context:NULL];


现在是有趣的部分：使用C++进行二进制搜索。我们使用了#include <algorithm>中的库函数 std::lower_bound。它需要一个起点，终点，要查找的值以及比较函数。它返回比较为false的第一个值。起点和终点可以是简单的指向数组的C指针。


#include <algorithm>
…

bool cmpX(const CGPoint& a, const CGPoint& b) {
return a.x < b.x;
}
…

CGFloat yMin = CGRectGetMinY(aRect);
CGFloat yMax = CGRectGetMaxY(aRect);

CGPoint* begin = (CGPoint*)[_spotsData bytes];
CGPoint* end = begin + _spotCount;

CGPoint leftMargin = aRect.origin;
CGPoint rightMargin;
rightMargin.x = CGRectGetMaxX(aRect);

CGPoint* left  = std::lower_bound(begin, end, leftMargin, cmpX);
CGPoint* right = std::lower_bound(left, end, rightMargin, cmpX);

NSUInteger count = 0;
for (CGPoint* i = left; i != right; ++i) {
if (i->y > yMin && i->y < yMax)
++count;
}


注意第二个二进制搜索，它仅从左边界而不是整个数组查找右边界。另一个优化是从循环中移除X-轴的检查，这是因为已经通过指定边界完成了这部分工作。


通过这些优化，只需要1毫秒来对长方形进行计数。这是第一个版本的200倍。

结果


下面是运行在三种不同设备上的示例项目的输出。如果你需要运行在你自己的设备上，你只需将目标设定中将代码签名标识符改为自己的。如果你不希望用在通用标识符的程序上，你还需要更改Info.plist中的包标识符（Bundle Identifier）。


iPhone 3G：

SpotsDB1 needed 3.2 seconds to count spots in 13 rects
that's 244.423 ms per rect
SpotsDB2 needed 3.0 seconds to count spots in 55 rects
that's 55.230 ms per rect
SpotsDB3 needed 3.0 seconds to count spots in 2988 rects
that's 1.004 ms per rect

第二代iPod Touch：

SpotsDB1 needed 3.1 seconds to count spots in 16 rects
that's 194.756 ms per rect
SpotsDB2 needed 3.0 seconds to count spots in 65 rects
that's 46.450 ms per rect
SpotsDB3 needed 3.0 seconds to count spots in 3399 rects
that's 0.883 ms per rect

运行在Mac Pro之上的模拟器：

SpotsDB1 needed 3.0 seconds to count spots in 687 rects
that's 4.372 ms per rect
SpotsDB2 needed 3.0 seconds to count spots in 2687 rects
that's 1.117 ms per rect
SpotsDB3 needed 3.0 seconds to count spots in 187276 rects
that's 0.016 ms per rect
结论


观察结果我们可以看出在桌面电脑和iPhone上性能有显著的区别。有一个金科玉律是：在Mac上只需一秒的操作在iPhone上要一分钟。或者有一个更悲观的说法：Mac上60Hz的刷新率在iPhone上每秒钟只能更新一次。


所以显而易见在iPhone上进行优化是完全必须的。本文中我展示了几种方法来减小Object C的开销以及怎样使用C++来获得最大的性能。当然找到性能的瓶颈并转而使用数据结构使代码性能提升并不总是很容易的事情。但是在设计一个使用大量数据的程序时，绝对有必要考虑使用非Cocoa的方法。

原文见：My iPhone is not a Mac Pro