HMDT - Special Issue - Objective-C 最適化 - Foundation クラスの最適化

以下のドキュメントは、Obj-C Optimization: Optimizing Foundation Classes を翻訳したものです。Mac OS X でのObjective-C の最適化手法について述べられています。

Mulle kybernetiK - Tech Info: v0.1

Foundation クラスの最適化

前の記事までで理論は十分なので、実際の最適化をしていみよう。今回は、Obj-C/Foundation にしぼって解説するよ。もっと一般的な最適化手法、アルゴリズムの改良とか、ループの展開とかは、ここでは触れないよ。前の記事の知識が必要になるからな！

コードの中へ

まず、プログラムを書いて、時間を測ってみよう。

このプログラムは UNIX のテキストファイルを読み込んで、行ごとに分解して、配列につっこんで、その順序を逆にするんだ。これをやるために、revers enumerator を使って、配列の後ろから先頭へとアクセスする。それを別の配列につっこんで、返り値にするんだ。これが、これから最適化する部分だ。

result = [NSMutableArray arrayWithCapacity:[lines count]];
rover  = [lines reverseObjectEnumerator];

while( s = [rover nextObject])
    [result addObject:s];

return( result);

Cube 450Mhz で実行したら、4233000 行処理するのに、9.5 秒かかった。ここでの目的は、この 9.5 秒を、できるだけ小さくすることだ。
[ExampleApp: Unoptimized]

最初の機械的な実験

前の記事を覚えているなら、Objective-C の動的ディスパッチ [] を、メソッドの実装を直接呼ぶのに変えればいいじゃん、って思うでしょう。思い出してくれ。オブジェクトのメソッドを呼ぶのに、メソッドのアドレスを決定して、そのアドレスを使って、直接サブルーチンに飛ぶことができるんだ。こんな感じだ：

IMP   address;

adress = [someObject methodForSelector:@selector( someMethod:someOtherArgument:)];
adress( someObject, @selector( someMethod:someOtherArgument:), 
        argument1, argument2);

もし、1 回しか呼ばないのにこれをやったら、普通に [someObject someMethod:argument1 someOtherArgument:argument2] を呼ぶより、明らかに遅いよ。だけど、何回も呼ぶなら、つまりループの中なら、十分ペイするんだ。

上のコードでは、ループの中に、2 つのメソッド呼び出しがあるから、そいつらを IMP で置き換えるんだ。

コードはこんな感じになる。

IMP   impNextObject;
IMP   addObject;

result = [NSMutableArray arrayWithCapacity:[lines count]];
rover  = [lines reverseObjectEnumerator];

addObject     = [result methodForSelector:@selector( addObject:)];
impNextObject = [rover methodForSelector:@selector( nextObject)];

while( s = impNextObject( rover, @selector( nextObject)))
    addObject( result, @selector( addObject:), s);
   
return( result);

結果は 8.5 秒。10% 以上よくなったけど、圧倒的にいい、ってわけでもないね。
[ExampleApp: IMP]

Objective-C の立場からは、この階層ではもうやれることは残ってないんだ。じゃ、Foundation を速く動かす方法はないかどうか、考えなきゃいけないんだ。

8.5 秒は、ほんとのところ、どれぐらいいいんだ？

コードがやっていることは、ある配列を読み込んで、逆から挿入するっていうことだ。同一の C のコードはこんな感じになるだろう：

for( i = n, j = 0; --i >= 0; j++)
    result[ j] = lines[ i];

このテストのコード、結果はすごいんだ、これが。1 秒の数分の 1 だ！
[ExampleApp: C]

Foundation がやることと、この単純な C のコードがやったことには、質的な違いはある。Foundation がやっていて、C のコードがやっていなことは、

• NSObject からの継承（Foundation との互換）
• 参照カウンタ（retain と release）
• 自動的な配列伸長
• 境界チェック
• スレッドセーフか？ここをチェック⁽¹⁾

この記事の前提は、このリストの重要さなんだ。NSObject との互換性がいらなくて、パフォーマンスが大事なら、C コードを使えばいいんだ。参照カウンタが NSObject の間で受け渡されるなら、それを使わないわけにはいかない。配列の伸長がなかったら、NSMutalbeArray の特性がなくなってしまうので、これは維持しないといけない。境界チェックは、なくてもいけるかもね。そして、スレッドセーフは、ここでは必要ない。っつーか、もともとの実装でも使われてないし。

Sampler.app で解析する

8.5 秒のコードに戻って、Sampler.app の目で見てみよう。Sampler.app は、こんな感じの結果をはくよ：

imped（最適化された再配置ルーチン）の 1481 サンプルのうち、実に 90 % 以上が NSMutableArray の addObject: で費やされている！驚くことに、enumerator の nextObject メソッドでは、4% しか使われていない。明らかに NSMutableArray の addObject: が、次の最適化ステップのターゲットだ。

自家製 NSMutableArray

Foundation のクラスは、もう、ものすごく最適化されていて、きみが書いたクラスでしか、パフォーマンスが失われることはない、っていう風に、一般には信じられているんだ。しかしながら、あえて、カスタム化した NSMutableArray のサブクラスを作ってみて、そいつでテストしてみよう！めんどくさいことを避けるために、完全な実装はしないけど、このケースにはこれで十分だ。

@interface PrivateMutableArray : NSMutableArray
{
   id             *pointers_;
   unsigned int   size_;
   unsigned int   nPointers_;
}
@end


@implementation PrivateMutableArray


- (id) initWithCapacity:(unsigned int) n
{
   [super init];

   pointers_  = malloc( sizeof( id) * n);
   nPointers_ = 0;
   size_      = n;
   return( self);
}


- (void) dealloc
{
   unsigned int   i;
   
   for( i = 0; i < nPointers_; i++)
      [pointers_[ i] release];

   free( pointers_);
   [super dealloc];
}


- (void) grow
{
    unsigned int  newsize;

    if( (newsize = size_ + size_) < size_ + 4)
       newsize = size_ + 4;
    if( ! (pointers_ = realloc( pointers_, newsize * sizeof( id))))
        [NSException raise:NSMallocException
                    format:@"%@ can't grow from %u to %u entries", self, size_, newsize];
    size_ = newsize;
}


- (void) addObject:(id) p
{
   if( ! p)
      [NSException raise:NSInvalidArgumentException
                  format:@"null pointer"];
   if( nPointers_ >= size_)
       [self grow];
   self->pointers_[ self->nPointers_++] = [p retain];
}


- (unsigned int) count
{
   return( nPointers_);
}


- (id) objectAtIndex:(unsigned int) i
{
   if( i >= nPointers_)
      [NSException raise:NSInvalidArgumentException
                  format:@"index %d out of bounds %d", i, nPointers_];
   return( pointers_[ i]);
}

@end

もう気付いただろうけど、NSObject からの継承と、retain/release は保たれているんだ。さらに、境界チェックもあって、動的な配列の伸長もあるんだ。

いくつか、NSMutableArray のサブクラスとしては、欠けているメソッドもある。insertObject:atIndex:、removeLastObject、removeObjectAtIndex:、replaceObjectAtIndex:withObject: とかだ。単純にするために、こいつらは実装してないよ。ここでは addObject: のパフォーマンスを上げることだけに、注目しているんだ。insertObject:atIndex: と addObject: の両方を最適化することは、おもしろくて、かつトリッキーになると思うんだけど、そいつは他の記事で取り扱うものだね。さっきのやり方で、NSMutableArray の残ったメソッドを実装したら、addObject: と replaceObjectAtIndex:withObject: と removeLastObject: は速くなるけど、removeObjectAtIndex: と insertObject:atIndex: は遅くなると思うな。

これを突っ込んで使ってみると、3 秒かかる。9 秒よりは悪くないし、そんなにトリッキーってわけでもない。だけど、この成功に甘んじているわけにはいかない。だって、まだ、こいつは C コードより 100 倍遅いんだから⁽³⁾。
[ExampleApp:PrivateMutableArray]

Sampler.app を使った 2 回めの解析

addObject: で費やされる時間は 62% に減った。enumeration のループは、あいかわらず 10% 以下だね。残りの時間は enumerator を作るのに 16%、大きいよ、あと配列を作るのと、実際のコードの実行だ。

そして、addObject: の 60% は retain を呼ぶのに、20% は objc_msgSend に費やされている。

立ち入り禁止

objc_msgSend を最適化することは、できないんだ。なぜなら、どのオブジェクトが retain されるか、知る術がないから。実際の retain の実装は、クラスによって変更されることがあるんだ。だから、オブジェクトの retain メソッドは、NSObject の実装を使っていて、それをキャッシュしている、って仮定してはいけないんだ。retain の代わりに CFRetain を使う、っていうアイディアもある。これはブリッジされた Foundation はパフォーマンスがよくなるんだけど、ブリッジされてないやつは悪くなる。この場合は、まぁいいトレードオフだね。なんでかっていうと、このコードはほとんど string だけを使っていて、そいつはブリッジされているから。この拡張で、0.5 秒稼ぐことができる（これに対するテストはなしね）。

いまあるクラスに対しても、これから作るクラスに対しても、retain を拡張することは、普通のデベロッパにはできない。Apple にしかできないんだ。政治的なルートを通って、Apple にライブラリを最適化するように、要求することになるよ。理想的な世界ならば、これでうまくいくんだけど、、、

自家製 NSString

今回は特別な場合で、すべての配列の要素は NSString なんだ。PrivateMutableArray はすでに時間を削っているんだから、Founadtion のとは違う retain/release を使う、NSString クラスを作るのがいいんじゃない？内部の参照カウンタを使おう。インスタンス変数を使って、retain の回数を覚えておく。コードがやることは、すごく単純だ。

@interface PrivateInlineRefCountingString : PrivateString
{
   unsigned int   refCountMinusOne_;
}

@implementation PrivateInlineRefCountingString

- (id) retain{
   refCountMinusOne_++;
   return( self);
}

- (void) release{
   if( ! refCountMinusOne_)
   {
      [self dealloc];
      return;
   }
   refCountMinusOne_--;
}

- (unsigned int) retainCount
{
   return( refCountMinusOne_ + 1);
}

@end

このアプローチの問題点は、NSString の機能のうち、必要とするものを記憶しておかないといけない、っていうことなんだ。なぜかっていうと、あつかっているインスタンスが、PrivateInlineRefCountingString だからだ。NSString を返すメソッドは、Foundation の NSString を返すようにしないといけない。PrivateInlineRefCountingString のインスタンスじゃなくてね。これは PrivateString クラスの中で行われているんだ。ここには書いてないけどね。例のコードの中で見ることができるよ。

NSString のサブクラスを書くっていうのは、たぶんすごく労力がかかることなんだ。なぜかっていうと、もともとの Foundation から普通に得られる最適化を、失うことになるからだ。NSString のサブクラスは、length と characterAtIndex: しか必要としない。だから、もし substringWithRange: を実装してないサブクラスを使ったとすると、characterAtIndex: を何度も呼び出すことになるんだ。これは、すごくすごく遅くなる。最適化のための変更では、内部のものだけ使って、substring は直接作るようにしないといけない。NSString の仕様を見てみると、実装するルーチンがいっぱいあるよ、、、

とにかく動くようにすると、カスタム化した NSString はすごくいい。この最適化で、また数秒を削り取ることができる。合計で 2 秒以下になる。
[ExampleApp: PrivateInlineRefCountingString]

PrivateInlineRefCountingString は独自の参照カウンタを持っているので、CFRetain を使うと、パフォーマンスが悪くなるんだ。だって CFRetain は Objective-C のメソッド呼び出しを使って、自身の retain メソッドを呼び出すから。CFRetain の呼び出しは、不必要なオーバーヘッドを生み出すんだ。

最後の一押し

最後の一押しでは、境界チェックが犠牲になる。配列の要素にアクセスするのに C のインラインが使われ、enumerator が for ループで置き換えられるんだ。

n = [lines count];
result = [PrivateUnsafeMutableArray arrayWithCapacity:n];

for( i = n; --i >= 0;) {
    s = PrivateUnsafeMutableArrayObjectAtIndex( lines, i);
    PrivateUnsafeMutableArrayAddObject( result, s);
}

PrivateUnsafeMutableArray は PrivateMutableArray のサブクラスで、インスタンス変数をいじるための、2 つの C のインライン関数を提供しているんだ。もし、(struct { @defs( Class) } *) self) っていうパターンになじみがなかったら、前の記事を参照してくれ。

#import "PrivateMutableArray.h"


@interface PrivateUnsafeMutableArray : PrivateMutableArray
{
}

@end


#define PrivateUnsafeMutableArrayCast( self)  \
   ((struct { @defs( PrivateUnsafeMutableArray) } *) self)


static inline void  PrivateUnsafeMutableArrayAddObject(
   PrivateUnsafeMutableArray *self,
                             id p)
{
    if( PrivateUnsafeMutableArrayCast( self)->nPointers_ 
        >= PrivateUnsafeMutableArrayCast( self)->size_)
      [self grow];
   PrivateUnsafeMutableArrayCast( self)->
      pointers_[ PrivateUnsafeMutableArrayCast( self)-> nPointers_++] = 
         [p retain];
}


static inline id  PrivateUnsafeMutableArrayObjectAtIndex( 
   PrivateUnsafeMutableArray *self,
   unsigned int index)
{
   return( PrivateUnsafeMutableArrayCast( self)->pointers_[ index]);
}

これで、実行時間はもう半分になるんだ。
[ExampleApp: Final Effort]

Sampler.app を使った最後の解析

この最後の出力から、Obj-C のメッセージパッシングに大部分の時間が費やされていることが分かるんだ。動的な retain は最適化できないからね。これでたった 10% になった！

こうして、10 分の 1 になったカスタム Foundation を手に入れたんだ。これは、この記事を書きはじめた時の、予想以上だね。

まとめ

この記事から、いくつかの結論が出てくるんだ。メソッドの実装をキャッシュすること（IMP）は、実行されるメソッドが、とっても速く実行される時だけに、有効なんだ。こういうときは、動的なメッセージパッシングにかかる時間が、貴重になる。メソッドの実行が速い時、単純なアクセッサや計算みたいなやつ、IMP をキャッシュするのは、やる価値がある。

Foundation のカスタムサブクラスを作ることは、スピードを上げるのに、とってもいい方法なんだ。NSNumber とか SDictitu`ﾊｽary とか NSString とか NSArray みたいな、そんなに複雑じゃないクラスが、カスタム化の候補だね。NSTask のサブクラスを作ってパフォーマンスを上げよう、ってのは、明らかに時間の無駄だね。だけど、他の機能を逆最適化しないように、気をつけてくれ。隠れた Foundation のクラスによる最適化を、取り除いてしまうことがあるからね。

パフォーマンスがとても貴重だ、と考えるならば、C のコードを使おう。たとえば、NSObject から継承される Pixel クラスで、何メガもあるピクセルの画像を保持する、っていうのは、馬鹿げている。最適化された C のコードを、Obj-C のクラスで、便利なように、ラップしよう。NSBitmapImageRep は、その例だ。NSPixel クラスってのは、ないからね。

(1) Developer Documentation の Release Note の ThreadSupport.html を見てくれ。

(2) もし retain をしない NSMutableNonRetainingArray を作るなら、少なくとも、追加される前に retain されて、配列を廃棄する前に release するインタフェースを示さなくちゃいけないんだ。そうじゃないと、メモリリークの危険が高くなる。

これだと、追加されるオブジェクトが、作られたばっかりで、autorelease されていないときにだけ、うまく動くことになる。例の中の PrivateMutableNonRetainingArray をチェックしてくれ。

(3) addObject: のパフォーマンスが比較的悪い他の理由は、たぶん Foundation は arrayWithCapacity: で使われる、キャパシティのパラメタを無視しているからだ。それで、配列が大きくなるとき、しょっちゅう reallocate してる。クラスの仕様書を見ると、こうしてもかまわないことになってるんだ。

これを変える方法はない。