HMDT - Special Issue - Objective-C 最適化 - 不可分な操作

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

Mulle kybernetiK - Tech Info: v0.2

なんてこった、NSString が変更可能になってるじゃないか

「Foundation クラスの最適化」で見落としていたのは、NSString は完全な変更不可のクラスじゃない、っていうことだ。NSString は文字列の内容が変更できない、っていうだけで、実際は retain や release を使えば、retain カウンタを簡単に変えれちゃうんだ。あと、NSString がスレッド間で共有できたら便利だろうから、retain と release はスレッドセーフであるべきだね。この問題を解決するために、NSLock を使ってもいいんだけど、それだと上がったパフォーマンスの大部分が、奪い去られてしまうぜ。もし NSLock を使うなら、reatin や release の度に、2 回のメソッド呼び出しが増えることになるんだ。

なんで PowerPC 上で、inline の retain カウントを使うことがスレッドセーフにならないのか、よく分からないなら、この「並行プログラミングの値の更新の問題」を読んでくれ。

やることがそんなに多くないときの、不可分操作

loop:	
    lwarx  r3,0,(r4)  ;; fetch memory pointed to by r4 
    addi   r3,r3,1    ;; into r3 and now increment r3
    stwcx. r3,0,(r4)  ;; store r3 back
    bne-   loop       ;; someone modified memory ? Try again

すぐに分かる利点は、このコードは 4 つの命令しか使っていないんだ（いちばんいい時で）。NSLock を使ったロックの場合は、普通、数十の命令を呼ぶからな。これは、C 関数のインラインのための、いい候補だね。

こいつの制限は、たった 1 つの読み込み／変更／書き込みしか、不可分操作にならないことだ。1 ワード以上のデータに安全にアクセスするためには、ロック機構に戻らないとね。

不可分な値の増加と減算の操作

ラッキーなことに、retain と release は、安全に変数の値を増加したり減算したりすることだけを求められるんだ。増加と減算は、さっきの読み込み、変更、書き込みみたいなもんで、不可分操作にとってもよく合うんだ。

- (id) retain
{
    MulleAtomicIncrement( &refCountMinusOne_);
    return( self);
}


- (void) release
{
    if( MulleAtomicDecrement( &refCountMinusOne_) == -1)
        [self dealloc];
}

これで、残りは、不可分操作のための 2 つの関数を実装して、テストを走らせて、パフォーマンスにどういう影響を与えるかみるだけだ。

//
// This decrements atomically. It will return the value
// after decrement
//
static inline int   MulleAtomicDecrement( int *p)
{
    int    tmp;

    // code lifted from linux
    asm volatile(
                "1:     lwarx   %0,0,%1\n"
                "	addic   %0,%0,-1\n"  // addic allows r0, addi doesn't 
                "	stwcx.  %0,0,%1\n"
                "	bne-    1b"
                : "=&r" (tmp)
                : "r" (p)
                : "cc", "memory");

    return( tmp);
}


//
// This increments atomically. It will return the value
// after increment
//
static inline int   MulleAtomicIncrement( int *p)
{
    int    tmp;

    // code lifted from linux
    asm volatile(
                "1:     lwarx   %0,0,%1\n"
                "	addic   %0,%0,1\n"
                "	stwcx.  %0,0,%1\n"
                "	bne-    1b"
                : "=&r" (tmp)
                : "r" (p)
                : "cc", "memory");

    return( tmp);
}

これがテストの結果だ。ループの中で retain と release を呼んでいるよ。かかった時間は：

Thread safe with NSLock (using IMPs): 12.3 s
Thread safe with Atomic operations: 2.4 s
Not thread safe (original code): 2.1 s

NSLock と比べると、すごく速いでしょ。

移植性

この方式の不可分操作を使うと、コードはプラットフォームに依存してしまうんだ。この高いパフォーマンスを、x86 みたいな他のプラットフォームでも維持したいなら、i386 のアセンブラで定義しないといけないんだ。

他の手段としては、少しコストがかかっちゃうんだけど、NSLock や pthread に戻る方法があるんだ。プリプロセッサを使えば、こんな風にコードの移植性を高めることができるよ。ま、美しくはないがな。

@interface AtomicIncrementCounter
{
#if ! defined( __ppc__)
    NSLock   *syncLock;
#endif
}

@end


@implementation AtomicIncrementCounter

static int  someCounter;

- (id) init
{
    [super init];
#if ! defined( __ppc__)
    syncLock = [[NSLock alloc] init];
#endif
    return( self);
}


- (void) dealloc
{
#if ! defined( __ppc__)
    [syncLock release];
#endif
    [super dealloc];
}


- (void) incrementSharedCounter
{
#if ! defined( __ppc__)
    [syncLock lock];

    someCounter++;

    [syncLock unlock];
#else
    MulleAtomicIncrement( &someCounter);	  // our inline increment function
#endif
}

@end

Apple の見解

これが悪名高き、古いんだけどね、Technote 1137 だ。Apple が lwarx/stwcx の使用について警告をしている。なぜだ？

• まず、これは PowerPC プロセッサが、結構な数のバグを持っていることを明らかにしたんだ。特に、トリッキーな領域にはいるときね。マルチプロセッサは、たぶん同期をとらないといけないんだ。[事実]
• 数年が経って、多くのバグが直されて、Apple 独自の lwarx/stwcx を作るために、voodoo が入れられたんだ。コードが幅広いプロセッサと互換が取れるように。[規約]
• Mac OS X がサポートする PowerPC には、そんな歴史的な制約はなかったんだ。これはうれしいね。なぜなら、古い修正である voodoo は、多くのパフォーマンスを奪い去っていたからな。[事実]
• Motorola からは、こんな風に lwarx/stwcx を実装しなよ、っていう推奨が出てたんだ。明らかじゃなかったけどね。[事実]
• Apple のエンジニアは、いまは、不可分操作を実装することを「許可」している。だけど、独自のセマフォを作ることは、互換性の観点から、やめとけ、って言ってるんだ。
• Apple の最新のマシンは、PCI ブリッジの反対側の端のアドレスでは、予約付きロードをサポートしてないんだ。[噂]

つまりどういうことかってーと、

• 通常のアプリケーションで不可分操作を使うのは良くて、とってもいいパフォーマンスを得ることができるぜ。
• ドライバを書くなら、注意深くやってくれ！
• 独自のセマフォは使うべきじゃないな。

まとめ

これで、「Foundation の最適化」で残されていた穴は埋まった。不可分操作を使うことで、スレッドセーフなカウンタを、とてもいい効率で PowerPC 上で実装できるぜ。似たような機能は、他の CPU アーキテクチャでもあるよ。いい例は Linux のカーネルのソースコードにあるな。たとえば i386 の不可分操作のためのコードは、linux/include/asm-i386/atomic.h で見ることができるよ。

(1) lwars/stwcx は、普通「予約付きロード／ストア」って言われてるよな。