HMDT - Special Issue - Objective-C 最適化 - Mac OS X でのハッシュの最適化

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

Mulle kybernetiK - Tech Info: v0.2

Mac OS X でのハッシュの最適化

この記事は、駆け出しのプログラマのための、ハッシュのイントロから始めよう。ベテランは、「残念なことに Mac OS X ではそんなに単純ではない」まで行ってくれ。

- (unsigned int) hash

NSObject とそのサブクラス（もっと正しく言うと、NSObject プロトコルを実装しているすべてのクラス、ってことだ）のインスタンスは、メッセージ - (unsigned int) hash を受け付けるんだ。ほんとのことをいうと、すべてのクラスの 99% が、インスタンスメソッド hash を受け付けるんだ。

hash の返り値の 1 つの使い方は、isEqual: メッセージのショートカットだ。もし 2 つのオブジェクトを比較して YES が返るなら、ハッシュ値も同じはずだ。逆は正しくなくて、2 つの等しくないオブジェクトが、同じハッシュ値を持つことも結構よくあるんだ。つまり、ハッシュ値を比べることは、等しいかどうかのテストにはならない、ってことね。でも、2 つのオブジェクトが等しく「ない」ってういことの早いテストとしては、全然オッケーなんだ。たとえば、ループの中でこんな感じで使える。

//
// example code, looking though an array couting
// the number of occurrences of "object" in it
//
- (unsigned int) countOccurrencesOfObject:(id) object
	                          inArray:(NSArray *) array
{
   unsigned int   count;
   unsigned int   hash;
   unsigned int   i, n;
   id             p;

   count = 0;
   hash  = [object hash];

   n = [array count];
   for( i = 0; i < n; i++)
   {
      p = [array objectAtIndex:i];
      if( [p hash] == hash)
         if( [p isEqual:object])
            ++count;     
   }
   return( count);
}

もしハッシュ値の計算が isEqual: よりすごく速いなら、これはハッシュの比較がない物よりも速いよ。

だけど、ハッシュにはもっといい使い方があるんだ。NSDictionary とか NSSets とかで見ることができる。ハッシュ値を順々に比較していく代わりに、一部かすべてのハッシュ値がインデックスの候補として使われるんだ。簡単な辞書の実装の例の一部ね。

@interface SimpleDictionary : ...
{
   NSMutableArray  *keyBuckets;
   NSMutableArray  *objectBuckets;
}

...


- (void)setObject:(id) anObject
           forKey:(id) aKey
{
   NSArray      *keyBucket;
   NSArray      *objectBucket;
   unsigned int	 bucketIdx;

   // Get buckets using the key's 
   // hash value (non-optimally as we will soon
   // see)
  
   bucketIdx    = [aKey hash] % [keyBuckets count];
   keyBucket    = [keyBuckets objectAtIndex:bucketIdx];
   objectBucket = [objectBuckets objectAtIndex:bucketIdx];

   // Now add the key and object to their buckets. 
   // They will end up at the same position in 
   // each array.

   [keyBucket addObject:anObject];
   [objectBucket addObject:anObject];
}


- (id) objectForKey:(id) aKey
{
   NSArray       *keyBucket;
   NSArray       *objectBucket;
   unsigned int   bucketIdx;
   unsigned int   i, n;

   // Get buckets using the key's hash value

   bucketIdx    = [aKey hash] % [keyBuckets count];
   keyBucket    = [keyBuckets objectAtIndex:bucketIdx];
   objectBucket = [objectBuckets objectAtIndex:bucketIdx];

   // Search for key in its bucket

   n = [keyBucket count];
   for( i = 0; i < n; i++)
   {
      if( [[keyBucket objectAtIndex:i] isEqual:aKey])
         break;
   }

   // If i equals n we didn't find the key 
   // and must return nil

   if( i == n)
      return( nil);

   // Otherwise i is the position of the key and the
   // object in it's respective buckets. 
   // Return the object

   return( [objectBucket objectAtIndex:i]);
}

このクラスには 2 つのバケツの配列があるんだ。1 つはキー用で、1 つはオブジェクト用だ。バケツの配列に入っている、それぞれのバケツの正体は NSArray だ。NSArray にキーとオブジェクトが入っている。

右のはとっても小さい辞書の図だ。それぞれのバケツの配列には、バケツが 2 つ入ってる。キーと、それに対するオブジェクトは、それぞれのバケツの配列の、同じインデックスに入れられるんだ。ハッシュは、バケツを決定するのに使われるんだ。そのバケツに対して、挿入したり、検索したりする。こいつでの検索は速いぜ。なぜならキー全体のうち、一部しか検索されないからな。

すぐ分かるように、バケツの数は、辞書に入れるオブジェクトの数に比例して増やすべきだな。

いいハッシュ、悪いハッシュ

   s = [NSMutableString stringWithString:@"A"];
   set = [NSMutableSet set];
   [set addObject:s];
   [s appendString:@"B"];
   [set addObject:s];
   NSLog( @"A  : %@", [set containsObject:@"A"]);
   NSLog( @"AB : %@", [set containsObject:@"AB"]);

ハッシュ関数がだめだめだったり、たとえばプログラマがバグを書いてハッシュ関数が常に 0 を返すようになっちゃったら、いったいどうなる？すべてのオブジェクトが 1 つのバケツに入ってしまう。っていうことは、かならず等しいかどうかのチェックをして、そいつは（役立たずの）ハッシュを呼び出す。こいつは単に isEqual: を実行するのよりも遅いぜ。

下のグラフは小さいでもプログラムを実行したときのものだけど、だめだめハッシュ（X=0）は、実際ハッシュなし（X=-1）より悪い。あんまり賢くないハッシュ（X=2）でも、有用だ。ハッシュがよくなれば（X=32）、結果もよくなる。

このプログラムは、限られた文字（a と b）の、同じ長さの、ランダムな文字列を作るんだ。

X=2 のハッシュは 4 つのハッシュ値を取ることができて、X=32 は unsigned int の領域を使うことができる。

というわけで、ハッシュ関数が次のような特徴を持つことが重要だ：

1. 速くなくてはいけない。すごく速く。
2. あるオブジェクトのハッシュ値が、他のオブジェクトのと違ったら、その 2 つは等しくない。もしスピードが犠牲になるようだったら、違うオブジェクトが同じハッシュ値を返していいから、かかる時間を最小にしなくてはいけない

[Example: hashvaluetest]

残念なことに Mac OS X ではそんなに単純ではない

ハッシュ値は Foundation と CoreFoundation のいろんな場所で使われているんだ。もちろん、いちばん分かりやすいのは NSDictionary だ。ハッシュが辞書のキーの素早い検索に使われる。そして、NSSet や NSHashTable や NSMapTable や CFDicionary にも使われてるし、コレクションや検索テーブルを提供するものにも使われてるよ。

CoreFoundation の開発で、Foundation の実際の中身はこいつに移ったんだけど、ハッシュの求め方とその使い方は、あからさまによくない。次の例で、それを示すぜ。

すべてのオブジェクトが等しくないクラスを作るとしよう。これをやる簡単な方法（ベストじゃないけど、とりあえず問題ない）は、init でユニークな数をインスタンス変数として保持することだ。こんな感じに。

- (unsigned int) _hash1
{
   static unsigned int  counter;

   ++counter;
   return( counter);
}

- (id) init
{
   [super init];
   hash = [self _hash1];
   return( self);
}


- (unsigned int) hash
{
   return( hash);
}

もう 1 つの有効なやり方（後であんまりよくないと分かるけど）は、こんな感じでハッシュを作ることだ。

- (unsigned int) _hash2
{
   static unsigned int  counter;

   ++counter;
   return( ((counter >> 24) & 0xFF)      |
           ((counter >> 16) & 0xFF) << 8 |
           ((counter >> 8)  & 0xFF) << 16 | 
           ((counter) & 0xFF) << 24); 
}

こいつは、ハッシュのバイトオーダーをひっくり返すぜ。

両方のメソッドは、ユニークな unsigned int 値を作って、それはハッシュ値としては同じ能力を提供するはず。あぅ、でも実はそうじゃないんだ！（Mac OS X 10.0 から 10.2 で）

NSHashTable に 5000 個のオブジェクトを入れるプログラムをテストしてみよう。_hash1 を使えば 0.03 秒で、_hash2 では 7.4 秒だ。

250 倍も遅いぜ！

明らかに、CoreFoundation では、低ビットの方が高ビットの方より有利なのか、高ビットがぜんぜん使われてないか、だ。たぶん、ハッシュのバケツを選ぶコードは、上の辞書で使った例と同じだと思う。

CFDictionary の関連するコードを見てみよう。実は、恐れていたとおり、低ビットだけがインデックスを決めるのに使われているんだ。

static CFIndex __CFDictionaryFindBuckets1a(
                        CFDictionaryRef dict, 
                        const void *key) {
    CFHashCode keyHash = (CFHashCode)key;
    const void **keys = dict->>_keys;
    uint32_t mask = dict->>_bucketsNum - 1;
    uintptr_t marker = dict->>_marker;
    CFIndex probe = keyHash & mask;
    CFIndex probeskip = ((keyHash << 1) + 1) & mask;
    CFIndex start = probe;
    for (;;) {
        uintptr_t currKey = (uintptr_t)keys[probe];
        if (marker == currKey) {                /* empty */
            return kCFNotFound;
        } else if (~marker == currKey) {        /* deleted */
            /* do nothing */
        } else if (currKey == (uintptr_t)key) {
            return probe;
        }
        probe = (probe + probeskip) & mask;
        if (start == probe) return kCFNotFound;
    }
}

だから、ハッシュ関数は次のようなルールに従うんだ：

• 下位ビットのランダムさかエントロピーは、最大でなくてはいけない。上位ビットの方しか違いのないハッシュ値は、避けなくてはいけない。こうしてみると、_hash1 は完璧だ。なにせ、下位ビットのエントロピーが大きくなることが保証されているからな。

もっといい NSObject のハッシュは？もっといい CFHash は？

NSObject のハッシュメソドを逆アセンブルした。オブジェクトのアドレスをハッシュ値にしているのが分かるんだ：

rlwinm r3,r3,30,2,31
blr

これは、こういう風に戻せる。

- (unsigned int) hash
{
return( (unsigned int) self >> 2);
}

これはうまいやり方だね。だって NSObject の isEqual: は、アドレスを比較するからだ。これで、ハッシュ値の比較を事前にやっておけば、isEqual: を呼ぶのを抑えることができるんだ。あと、違う 2 つのオブジェクトが同じメモリを共有することはないから、違ったオブジェクトのハッシュ値は完全に違うぜ。普通はオブジェクトは、お互いメモリの近いとこに置かれるから、低ビットのエントロピーは、極めていい（だけど最適化がなかったらよくない）。このことは、16 のオブジェクトのランダムに取り出してみて、そのアドレスを出力すると分かるんだ：

4f600 4f520 4fc20 4f580
51040 5bb40 5bb50 5bb60
5bb70 5bb80 5bb90 5bba0
5bbb0 5bbc0 5bbd0 5bbe0

シフトする理由

-[ NSObject hash] の作者は、疑いなく、PPC では最低でも 4 バイトがオブジェクトに必要なことに気付いてたね（isa ポインタの分だ）。だから、どのオブジェクトも下位の 2 ビットはクリアされてるんだ。下位ビットのエントロピーを上げることによって、よりよいハッシュ値を作れるんだ。

一般的には、オブジェクトは malloc で確保されるんだけど、PPC の Mac OS X の malloc では、16 byte のアライメントが保証されているんだ。だから、シフトはほんとは 4 つやるべきだ（これを上の出力の例と使ってみてくれ）。

- (unsigned int) hash
{
   return( (unsigned int) self >> 4);
}

簡単な例を走らせると、改良が見られる。こいつは 0.9 秒で、前のやつは 1.4 秒だ。

とっても面白いのは、シフトなしで実験したときだ。なんと、こいつは 3.7 秒まで落ちるぜ！

いけないやり方

じゃ、CoreFoundation の CFHash のコードを見てみよう。

CFHashCode CFHash(CFTypeRef cf) {
#if defined(DEBUG)
    if (NULL == cf) HALT;
#endif
    CFTYPE_OBJC_FUNCDISPATCH0(CFHashCode, cf, "hash");
    __CFGenericAssertIsCF(cf);
    if (NULL != __CFRuntimeClassTable[__CFGenericTypeID(cf)]->>hash) {
        return __CFRuntimeClassTable[__CFGenericTypeID(cf)]->>hash(cf);
    }
    return (CFHashCode)cf;
}

見ての通り、シフト演算をやっていないんだ。CoreFoundation のオブジェクトは、自身のハッシュ関数を実装していないから、こいつは問題だ。これらのオブジェクトは、辞書の操作で、25% のパフォーマンスしか出すことができない。幸運なことは、多くの CFRuntimeClass は Objective-C のクラスと同値なんだ。そいつらは、自身のハッシュ関数を実装している⁽¹⁾。

もし NSObject とは別に、CFRuntimeClass を実装するなら、CFHash の実装を考えないといけない。だけど NSObject のサブクラスを作るなら、自動的に NSObject のデフォルトの hash メソッドを引き継ぐからね。

（ちょっとアカデミックな）次のステップ

アドレスをシフトする、っていう hash の実装は、次善の策だ。なぜなら、上位ビットを 0 にするからな。すべてのシフト演算は、ハッシュ値のユニーク性を壊してしまうんだ。ってことは、シフト演算よりも、ロテーションを使うコードの方がいいんじゃないか？：

- (unsigned int) hash
{
   return( ((unsigned int) self >> 4) | 
            (unsigned int) self << (32 - 4));
}

このコードは、下位ビットのエントロピーを増やす、アドレスビットをフルに使う、っていう両方の意味でベストなコードだ。

さらにうれしいことに、gcc で最適化したコード（-O3 で）では、こんなコードが吐かれるんだ：

rotlwi  r3,r3,28
blr

これを NSObject のカテゴリにつっこめば、フリーでできあがる、Cocoa の少しスピードアップバージョンだ！これが全体的にどういうスピードアップになるのか？なにか見つけたら、教えてね。

[Example nsobjecthashtest]

まとめ

現在の Mac OS X では、ハッシュ関数をチェックすることが、とってもとっても重要なんだ。

最下位または下位のビットのエントロピー（ランダムさ、分布）を高く保ってくれ。

NSObject のカテゴリで hash メソッドを上書きすれば、NSObject を継承しているクラスで、独自の isEqual: を実装していないやつのパフォーマンスを上げることができるぜ！もしいいハッシュが必要なんだけど、計算するのに手間がかかるようなら、インスタンス変数にキャッシュすることを考えてみてくれ。

ハッシュを使ったコレクションに、可変オブジェクトを加えちゃだめだよ。

次の記事は、まだ書かれてない前の章なんだけど、すごいやつになるよ！速いロックのことだけじゃなくて、gawk の実行を 25%（ベンチマークによる）も速くするんだぜ！Objective-C 関連でな！

(1) 10.2 の CoreFoundation クラスでハッシュを実装してないのは、CFUserNotification、CNull、CFAllocator、CFTree、CFBoolean、CFXMLParser、CFBundle、CFPlugInInstance、CFRunLoop、CFSocket だ。

この最後の注釈まで読んでる読者には、ちょっとしたおまけがあるんだ。CFData のハッシュ関数は、ELF ハッシュアルゴリズムを使っている。残念なことに、このアルゴリズムは PPC アーキテクチャの利点をいかすように実装されてないんだ。

さらにアルゴリズム自体にバグがある。なぜなら返ってくるハッシュ値の上位 4 bit が、意味なく 0 になってるからな。ここで示すのが、変更された ELF ハッシュコードだ。こいつは、私の Cube で gcc -O3 でコンパイルして、30% 速かったぜ。上位 4 bit を保持しているんだ。

#define MULLE_ELF_STEP( B) 	?do			 	?{			 	?   H  = (H << 4) + B;		?   H ^= (H >> 24) & 0xF0;	?}				?while( 0)

// original ELF_STEP
// #define ELF_STEP(B) T1 = (H << 4) + B; T2 = T1 & 0xF0000000; if (T2) T1 ^= (T2 >> 24); T1 &= (~T2); H = T1


unsigned int  mulle_elf_hash( unsigned char *bytes, unsigned int length)
{
    unsigned int H = 0;
    int rem = length;
    while (3 < rem) {
        MULLE_ELF_STEP(bytes[length - rem]);
        MULLE_ELF_STEP(bytes[length - rem + 1]);
        MULLE_ELF_STEP(bytes[length - rem + 2]);
        MULLE_ELF_STEP(bytes[length - rem + 3]);
        rem -= 4;
    }
    switch (rem) {
    case 3:  MULLE_ELF_STEP(bytes[length - 3]);
    case 2:  MULLE_ELF_STEP(bytes[length - 2]);
    case 1:  MULLE_ELF_STEP(bytes[length - 1]);
    case 0:  ;
    }
    return H;
}

#undef ELF_STEP

[Example elfhashtest]

例にあるソースは、別のハッシュ関数も含んでいるんだ。こいつは、もとのより悪いところはなくて、40% も速いんだ。