Bitmap GCの高速化案 - miura1729の日記

AutorNariさんのBitmap GCの秘蔵パッチを見ていて、
http://www.narihiro.info/resource/patch/gc_diff_bitmap_align_fix.diff

きっと、ここがオーバヘッドだろうと思ったところがあるので、そこの高速化案です。bitmap gcそのものも試していないので、適当です。これまでも私の高速化案が効果があったためしがないので、冗談と思って読んでください。

まな板に上げるのは、

+#define FIND_BITMAP(res, p) do {\
+    if (((RVALUE *)p)->as.free.flags & FL_BMAP_UNDER) {\
+        res = (RVALUE *)((((VALUE)p & BITMAP_MASK) + BITMAP_ALIGN) - (((VALUE)p & BITMAP_MASK) + BITMAP_ALIGN) % sizeof(RVALUE));\
+    }\
+    else {\
+        res = (RVALUE *)(((VALUE)p & BITMAP_MASK) - ((VALUE)p & BITMAP_MASK) % sizeof(RVALUE));\
+    }\
+} while(0)

です。ここで、((VALUE)p & BITMAP_MASK) % sizeof(RVALUE)はいかにも重いなと感じますので、これを何とか速くしようと思いました。

sizeof(RVALUE)は今のRubyの実装では32bit CPUで20になります
(VALUE)p & BITMAP_MASKは必ず4の倍数になります
1,2から((VALUE)p & BITMAP_MASK) % sizeof(RVALUE)は(((VALUE)p & BITMAP_MASK) % 5) * 4と等価(32bitの場合)です

で、5の余りを求める高速な方法が、「ハッカーのたのしみ」の169ページにあります。ただ、この方法は32bit * 32bitの掛け算を行って、上位ワードを得る必要があります。これを高速に行うにはアセンブラが必要そうです。
無理やり64bit演算を使ってCで書いた余りを求めるプログラムです。

main(int argc, char *argv[]) {
  unsigned long long tmp;
  unsigned long a;
  
  a = atoi(argv[1]);
  printf("SLOW: %d %% 5 = %d\n", a, a % 5);
  
  tmp = a * 0x66666667ULL;
  tmp >>= 33;
  printf("FAST: %d %% 5 = %d\n", a,  a - tmp * 5);
}

この場合では素直に%を使った方がよさそうです。

追記2 (2008/9/1)

    asm("mull %1" : "=d" (__tmp) : "m" (__tmp));\

は

    asm("mull %1" : "=d" (__tmp) : "g" (__tmp));\

の方がいいと思うので変更しました。"m"と"g"の違いはmはメモリのみですが、gはメモリとレジスタです。__tmpがレジスタに割り当てられたとき、mですといったんメモリに書き出そうとしますが、gですとそのままそのレジスタが指定されます。

追記(2008/8/31)
AutorNariさんにコメントを頂いて、FIND_BITMAPを作ってみました。でも、秘蔵パッチがどうしてもあたらないので、Rubyでの動作チェックが出来ず、簡易化バージョンのチェックのみです。多分、最初のコメントのようにすればいいのではないかなと思います。
このプログラムを作るにあたって、A. SAITOHさんの「GCCでインラインアセンブリを使用する方法と留意点等 for x86」(http://www.mars.sannet.ne.jp/sci10/on_gcc_asm.html)が大変役に立ちました。ありがとうございます。

あと、マジックナンバー0x66666667は符号つき用みたいです。符号無しは0xcccccccdを使って右シフトを2回するようです。

/*
#define FIND_BITMAP(res, p) do {\
    VALUE __tmp;\
    if (((RVALUE *)p)->as.free.flags & FL_BMAP_UNDER) {\
      __tmp = (((VALUE)p & BITMAP_MASK) + BITMAP_ALIGN; \
    }\
    else {\
      __tmp = ((VALUE)p & BITMAP_MASK; \
    }\
    asm("movl $0xcccccccd, %eax");\
    asm("mull %1" : "=d" (__tmp) : "g" (__tmp));\
    __tmp >>= 4;\
    res = (RVALUE *)(__tmp * 20);\
} while(0)
*/


typedef unsigned long VALUE;
typedef unsigned long RVALUE;

#define FIND_BITMAP(res, p) do {\
    VALUE tmp;\
    tmp = (VALUE)(p);				\
    asm("movl $0xcccccccd, %eax");\
    asm("mull %1" : "=d" (tmp) : "g" (tmp));\
    tmp >>= 4;\
    res = (RVALUE *)(tmp * 20);\
} while(0)

main(){
  RVALUE *b;
  RVALUE *a;
  a = (RVALUE *)0x3208;
  FIND_BITMAP(b, a);
  printf("%d %d", a, b);
}

これで、割り算よりスピードアップしたか調べればいいのですが、もう寝る時間ですので寝ます。おやすみなさい。