GCC の switch と ishex

http://alohakun.blog7.fc2.com/blog-entry-878.html

なんかこのへん見て GCC の switch の最適化とか見てたら、単なるテーブルジャンプ以外のちょっと面白い最適化が目につきました。

http://shinh.skr.jp/m/?date=20071121#p01

でもテーブルルックアップにはかなわんかなぁとまぁ適当に自分でちょっとやってみました。

 #include <stdio.h>
 
 int table[] = {
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,
     0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 };
 
 __inline__ int ishex(int c) {
     return table[c];
 }
 
 __inline__ int ishex2(int c) {
     unsigned int v = c-48;
     if (v > 22) return 0;
     if ((1 << v) & 8258559) return 1;
     return 0;
 }
 
 int main() {
     int i, j, k;
     k = 0;
     for (i = 0; i < 10000; i++) {
         for (j = 0; j < 10000; j++) {
             //k += rand()&255;
             //k += ishex(rand()&255);
             k += ishex2(rand()&255);
         }
     }
     printf("%d\n", k);
 }

結果は Core2 Duo 2.0GHz, GCC-4.1.3, Parallels 上の linux 、という環境で、 ishex しないヤツが 2.50秒、 ishex が 2.60秒、 ishex2 が 2.85秒、ってとこでした。まぁこの結果だけ見るとやっぱ分岐予測とかでアレかなぁという感じなんですが、 ishex2 の方がキャッシュ汚さないから実際のアプリケーションだといい場合とかもあるかもなぁという感じではあります。知らんけど。

あと

 __inline__ int ishex3(int c) {
     switch (c) {
     case '0':  case '1':  case '2':  case '3':  case '4':
     case '5':  case '6':  case '7':  case '8':  case '9':
     case 'A':  case 'B':  case 'C':  case 'D':  case 'E': case 'F':
         return 1;
     }
     return 0;
 }

みたいなのを作って GCC-3.3 (件の最適化がまだ入ってないのでテーブルジャンプになる) では 3.3 秒でした。同じコードが GCC-4.1.3 だと 2.90 秒くらい。 ishex2 より分岐一個増えててちょっと遅くなってるけど自動でこれだけ最適化できててえらいなぁと。