|
Mulle kybernetiK - Tech Info: v0.2
Obj-C 最適化：オブジェクト生成の最適化
|
「Objective-C 最適化」シリーズ、5 回目は、オブジェクトの生成と破棄のトピックに向かうぜ。オブジェクトのメモリ割り当てのスピード。これこそ、最後のフロンティアだ！
|
(c) 2002 Mulle kybernetiK - text by Nat!
オブジェクトの生成を最適化する
プログラムを最適化するために打ち破らなくてはいけない障壁の一つは、Objective-C のメモリ割り当ての速さ（っつーか遅さ）だ。前の記事「メモリ確保の基本と Foundation」から分かるように、ぜんぜん聖なるものじゃない三位一体の alloc/init/autorelease が、メモリの割り当て、初期化、オブジェクトのオートリリースに使われるんだ。ここではいくつかのアイディアを使って、Foundation がやるよりも 300% 速く、オブジェクトのメモリ割り当てをする方法を考えてみよう。
|
こっからテストケースをダウンロードできるよ。これは PorjectBuilderWO で作られているんで、ProjectBuilderWo をインストールしてないなら、新しい ProjectBuilder にインポートしないといけない(1)。または、カスタムインストールオプションを使うと、ProjectBuilderWO を developer CD からインストールできるよ。
|
オートリリースを避ける
1 勝目は、可能な限りオートリリースを避けることだ。たとえば、新しく作ったオブジェクトを NSMutableArray に追加する場合、
NSMutableArray *array;
NSString *s;
s = [NSString stringWithCString:"bla bla bla"];
[array addObject:s];
これは、こう書くともっと効率がいい。
NSMutableArray *array;
NSString *s;
s = [[NSString alloc] initWithCString:"bla bla bla"];
[array addObject:s];
[s release];
2 回 Objective-C の呼び出しを増やすことになるけど、裏で行われている処理は減っているんだ。
私のマシンでは、autorealse バージョンだと 11 秒かかって、alloc/init バージョンだと 7 秒かかったんだ。これは autorelease プールの解放を入れてない状態で測ったんで、それを入れると、もっと時間が改良されているはずだ。
[Example: allocautorelease]
alloc の代わりに allocWithZone: を使う
現在の実装では、NSObject の alloc はこんな感じなんだ。
+ (void) alloc
{
return( [self allocWithZone:NULL]);
}
だから、allockWithZone: を直接呼べば、余計な NSObject のコードが減るんで、ほんの少し時間を節約することができるんだ。
[Example: alloczone]
new を作る
new を使うことによって、初期化とメモリ割り当ての組み合わせの時間を節約することができるんだ。
static inline void _init( MyObject *self)
{
self->myArray_ = [NSMutableArray new];
self->myCounter_ = 2;
}
- (id) init
{
[super init];
_init( self);
return( self);
}
+ (id) new
{
MyObject *obj;
obj = NSAllocateObject( self, 0, NULL));
_init( obj);
return( obj);
}
完全にするには、全てのオブジェクトが同じメモリ割り当てをするように、alloc と allocWithZone: も書いてやらないといけない。
+ (id) alloc
{
return( NSAllocateObject( self, 0, NULL));
}
+ (id) allocWithZone:(NSZone *) zone
{
return( NSAllocateObject( self, 0, zone));
}
- (void) dealloc
{
[myArray_ release];
NSDeallocateObject( self);
}
この方法から得られるものは、あまり大きくないんだ。alloc/init は 7.4 秒で動いて、new は 6.7 秒だった。NSObject の new は、ただ単に alloc/init を呼び出すだけなので、Foundation のクラスの場合は、変わらないよ。
[Example: allocnew]
オブジェクトをプールする
再利用するために、解放されたオブジェクトをプールしておく、ってのは興味深いアイディアだと思わないかい？プールされたオブジェクトは、オブジェクトを新たに割り当てるより先に使われるので、malloc の呼び出し分の時間が節約されるんだ。allocWithZone: と dealloc をプールのためにカスタム化した、単純な実装を見てみよう。
プールは、固定長の環状のバッファとして、実装されているんだ。バッファが空のときは、メモリからオブジェクトが割り当てられる。環状のバッファがいっぱいなら、オブジェクトのメモリは、実際に、解放される。そうじゃない場合は、バッファからオブジェクトが確保されて、バッファに戻されるんだ。
#import <Foundation/Foundation.h>
typedef struct
{
Class poolClass;
unsigned int low;
unsigned int high;
unsigned int poolSize;
id *pool;
} Pool;
@interface PoolObject : NSObject
{
}
+ (Pool *) instancePool;
@end
#import "PoolObject.h"
#import <objc/objc.h>
#import <objc/objc-class.h>
static NSString *COMPLAIN_MISSING_IMP = @"Class %@ needs this code:\n\
+ (Pool *) instancePool\n\
{\n\
static Pool myPool;\n\
\n\
return( &myPool);\n\
}";
@implementation PoolObject
+ (id) allocWithZone:(NSZone *) zone
{
Pool *pool;
id obj;
pool = [self instancePool]; // get this class' pool
if( ! pool->poolClass) // if first time alloc
{
pool->poolClass = self; // init pool structure
pool->poolSize = 10000; // pool 10000 objects
pool->pool = malloc( sizeof( id) * pool->poolSize);
}
else
if( pool->poolClass != self) // sanity check
[NSException raise:NSGenericException
format:COMPLAIN_MISSING_IMP, self];
if( pool->low == pool->high) // if pool empty, allocate
{
obj = NSAllocateObject( self, 0, NULL);
return( obj);
}
//
// reuse and clear
//
obj = pool->pool[ pool->low];
pool->low = (pool->low + 1) % pool->poolSize;
memset( obj + 1, 0, ((struct objc_class *) self)->instance_size - 4);
return( obj);
}
- (void) dealloc
{
Pool *pool;
unsigned int next;
pool = [isa instancePool];
next = (pool->high + 1) % pool->poolSize;
if( next == pool->low) // pool full ?
{
NSDeallocateObject( self);
return;
}
//
// add object to pool
//
pool->pool[ pool->high] = self;
pool->high = next;
}
+ (Pool *) instancePool
{
[NSException raise:NSGenericException
format:COMPLAIN_MISSING_IMP, self];
return( 0);
}
@end
この PoolObject のサブクラスは、プールのインスタンスを提供するために、次のメソッドを実装するんだよ。
+ (Pool *) instancePool
{
static Pool myPool;
return( &myPool);
}
この実装はスレッドセーフじゃないことに気をつけてくれ！
プールの大きさを調節すれば、最終的には、オブジェクトの割り当てはほとんどプールから来て、メモリからは来ないんだ。私の計測によれば、メモリ確保の時間は、alloc/init/release の 9.5 秒から 3.6 秒に減った。これはプールが最適に使われたときね。
- 利点：メモリ確保と解放のスピードが速くなる
- 欠点：メモリのフットプリントが大きくなる。プールがあふれたとき、メモリ確保のスピードが遅くなる。最初のオブジェクトが解放されるまでは遅い(2)。正しいプールのサイズを求めるのが難しい。アプリケーションの alloc/release のパターンによっては、プールのオブジェクトのアドレスがランダムに近付くので、リファレンスを消すのが遅くなる。malloc にも同じことが言えるけどね。
この考えを広げて、様々なサイズのオブジェクトを扱うことを考えてみよう。malloc の最小単位は 16 byte なので、0 から 512 byte までのオブジェクトを「たったの」32 個のプールで取り扱えるんだ。明らかに、このやり方はメモリのフットプリントが大きくなる。だって多くのオブジェクトを確保しておかないといけないからな。
それとは別に、プールのサイズを可変にすることを考えてみよう。すべての解放されたオブジェクトを、プールの中でとっておくんだ。Mac OS X の仮想メモリのおかげで、これはそんなに無駄じゃない。長い時間が経てば、結局は使われないオブジェクトはスワップされるからね。
[Example: allocpool]
Bunch（固まり）にオブジェクトを割り当てる
 別のプールのやり方は、オブジェクトの数だけメモリを確保して、共通のメモリ領域に置くことによって、メモリの確保と解放の数を減らす方法だ。これだと、共有領域のオブジェクトの数に、スピードは依存する。8 つのオブジェクトが共有領域にあったら、malloc/free の回数は 1/8 になるんだ。
このアイディアの実装は、下にある。それぞれの確保されたメモリブロックは Bunch 情報を含むんだ。この構造体は、オブジェクトの確保と解放を何個管理するか、っていう情報を持っている。オブジェクトのアドレスのすぐ上には、オフセットフィールドがあって、これから Bunch のオブジェクトのアドレスを求められる。
すべてのオブジェクトが使われて、その後確保されたオブジェクトが解放されたら、Bunch は空になるよ。
メモリのレイアウトも自前でやってるから、プールの時のコードよりも複雑になっているよ。
#import <Foundation/Foundation.h>
typedef struct {
{
void *currentBunch; // need this be volatile?
} BunchInfo;
@interface BunchObject : NSObject
{
unsigned int retainCountMinusOne_;
}
+ (BunchInfo *) bunchInfo;
@end
#import "BunchObject.h"
#import <objc/objc.h>
#import <objc/objc-class.h>
//
// The structure at the begining of
// every Bunch
//
typedef struct
{
long instance_size_;
unsigned int freed_;
unsigned int allocated_; // allocated by "user"
unsigned int reserved_; // reserved from malloc
} Bunch;
//
// the size needed for the bunch
// with proper alignment for objects
//
#define S_Bunch ((sizeof( Bunch) + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1))
#define ALIGNMENT 8
#define OBJECTS_PER_MALLOC 16
@implementation BunchObject
static Bunch *newBunch( long bunchInstanceSize)
{
unsigned int len;
unsigned int nBunches;
unsigned long size;
Bunch *p;
bunchInstanceSize = (bunchInstanceSize + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1);
size = bunchInstanceSize + sizeof( int);
nBunches = OBJECTS_PER_MALLOC;
len = size * nBunches + S_Bunch;
if( ! (p = calloc( len, 1))) // calloc, for compatibility
return( nil);
p->instance_size_ = bunchInstanceSize;
return( p);
}
static inline void freeBunch( Bunch *p)
{
free( p);
}
static inline BOOL canBunchHandleSize( Bunch *p, long size)
{
//
// We can't deal with subclasses, that are larger then what we
// first allocated.
//
return( p && size <= p->instance_size_);
}
static inline unsigned int nObjectsABunch( Bunch *p)
{
return( OBJECTS_PER_MALLOC);
}
static inline BOOL isBunchExhausted( Bunch *p)
{
return( p->allocated_ == nObjectsABunch( p));
}
static inline id newBunchObject( Bunch *p)
{
id obj;
unsigned int offset;
//
// Build an object
// put offset to the bunch structure ahead of the isa pointer.
//
offset = S_Bunch + (sizeof( int) + p->instance_size_) * p->allocated_;
obj = (id) (char *) p + offset);
*((unsigned int *) obj)++ = offset + sizeof( int);
//
// up the allocation count
//
p->allocated_++;
return ( obj);
}
//
// determin Bunch address from object address
//
stataic inline Bunch *bunchForObject( id self)
{
int offset;
Bunch *p;
offset = ((int *) self[ -1];
p = (Bunch *) &((char *) self)[ -offset];
return( p);
}
+ (BunchInfo *) bunchInfo
{
static BunchInfo bunchinfo;
return ( &bunchInfo);
}
/*
##
## override alloc, dealloc, retain and release
##
*/
static inline BunchObject *alloc_object( struct objc_class *self)
{
BunchObject *obj;
BOOL flag;
BunchInfo *p;
obj = nil;
p = [self bunchInfo]; // this hurts a little, becuase we call it every time
//
// first time ? malloc and initialize a new bunch
//
if( ! p->currentBunch)
p->currentBunch = newBunch( ((struct objc_class *) self)->instance_size);
if( canBunchHandleSize( p->currentBunch, self->instance_size))
{
//
// grab an object from the current bunch
// and place isa pointer there
//
obj = newBunchObject( p->currentBunch);
obj->isa = self;
}
//
// bunch full ? then make a new one for next time
//
if( isBunchExhausted( p->currentBunch))
p->currentBunch = newBunch( ((struct objc_class *) self)->instance_size);
//
// Failed means, some subclass is calling...
//
if( ! obj)
[NSException raise:NSGenericException
format:@"To be able to allocate an instance,\
your class %@ needs this code:\n\
\n\
+ (volatile BunchInfo *) bunchInfo\n\
{\n\
static BunchInfo bunchInfo;\n\
\n\
return( &bunchInfo);\n\
}\
", self];
return( obj);
}
+ (id) allocWithZone:(NSZone *) zone
{
BunchObject *obj;
obj = alloc_object( self);
return( obj);
}
//
// Only free a bunch, if all objects are
// allocated(!) and freed
//
- (void) dealloc
{
Bunch *p;
p = bunchForObject( self);
if( ++p->freed_ == nObjectsABunch( p))
freeBunch( p);
}
- (id) retain
{
++retainCountMinusOne_;
return( self);
}
- (void) release
{
if( ! retainCountMinusOne_--)
[self dealloc];
}
@end
この実装はスレッドセーフじゃないことに気をつけてくれ！
私の計測だと、alloc/init/release によるメモリの割り当て時間は、9.5 秒から 2.9 秒に減ったんだ。プールの時との違いは、malloc のコールの回数が絶対的に少ないことによるんだ。プールがウォームアップされて、十分な数のオブジェクトを持っていれば、プールの方が Bunch よりもパフォーマンスがいいことが予想されるんだけどね。
- 利点：メモリ確保と解放のスピードはとっても速い。たぶん、参照の位置が改善されてて、連続的に配置されてる
- 欠点：Bunch が再構築されないと、たぶんメモリがリークする
オブジェクトの Bunch は複雑なんだけど、プールにみられる「チューニング」問題はないんだ。メモリリークの問題は、実際のアプリケーションで問題になるだろうけどね。
実験によると、Bunch の中のオブジェクトの数を少なくする（4 つとか）と、効果的にスピードを上げることができるんだ。Bunch のオブジェクトの数を 64 以上にするのは、賢い方法じゃないね。Bunch が解放されない可能性が大きくなるからな。
[Example: allocbunch]
まとめ
ちょっとうまいコーディングを使えば、オブジェクトのメモリ割り当ての限界を超えることができるぜ。メモリのフットプリントが大きくなったり、メモリフラグメンテーションの危険があるけどな。ここで紹介した方法は、自分で作ったクラスに使える方法で、NSString みたいな Foundation のクラスには使えないぜ。
好奇心旺盛なハッカーなら、NSObject の pose を使って、デフォルトの alloc/dealloc を書き換えるでしょ。この場合、Foundation のオブジェクトもスピードアップの恩恵を受けるよ。
次の記事では、パフォーマンスを失うことなく、スレッドセーフにすることに挑戦するぜ。
(1) これを書いている時点では、残念ながら、新しい ProjectBuilder は便利というにはクラッシュしすぎるんでね。
(2) この初期のばらつきを避けるために、初期化メソッであらかじめプールをオブジェクトで埋めておくこともできるよ。
|
