2007-11-22

GCC の switch と ishex

Program

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 より分岐一個増えててちょっと遅くなってるけど自動でこれだけ最適化できててえらいなぁと。

2007-11-22

OOM killer

Program

http://mkosaki.blog46.fc2.com/blog-entry-416.html

このへん見ててなんか前なんかの拍子に OOM killer をながめたのを思い出しました。場所は mm/oom_kill.c 。

こんなかの badness() で各プロセスのメモリに関しての危険度を調べてるんだけど、さっきの switch でどの最適化使うか、って部分もそうなんですが、こういうヒューリスティックスの塊を見るのは面白いなぁと思いました。

例えば一番最初の

        /*
         * swapoff can easily use up all memory, so kill those first.
         */
        if (p->flags & PF_SWAPOFF)
                return ULONG_MAX;

とかはああなるほどねえと。 PF_SWAPOFF ってのは swapoff(2) を発行したプロセスにくっつく属性みたい。

で次に子がいるプロセスはその子プロセスのメモリの半分だけ親プロセスにペナルティがかかる、っていうのがあって、

        /*
         * Processes which fork a lot of child processes are likely
         * a good choice. We add half the vmsize of the children if they
         * have an own mm. This prevents forking servers to flood the
         * machine with an endless amount of children. In case a single
         * child is eating the vast majority of memory, adding only half
         * to the parents will make the child our kill candidate of choice.
         */
        list_for_each_entry(child, &p->children, sibling) {
                task_lock(child);
                if (child->mm != mm && child->mm)
                        points += child->mm->total_vm/2 + 1;
                task_unlock(child);
        }

適当に要約すると、子プロセスいっぱいいる子は悪い子なのでペナルティあげる☆、でも一つの子プロセスだけがアホみたいに使ってる時に親が死ぬ(Apache+アホCGIとか)と悲しいので半分だけね☆、って感じでしょうか。

でもこれだとひたすら fork しまくる fork bomb には無力だよなーとか思ってちょっとぐぐってみるとやっぱダメらしいと書いてあった。

https://lwn.net/Articles/133924/

で、なんかその後も root だったら 4 割るとかそんなんばっかで面白い。 Robocode とかそいうの思い出す感じ。

まぁ echo -17 > /proc//oom_adj かなんかで特定のプロセスを守ることができる、ってのはまぁ知っといていい気がした。 sshd とかは死守したいし。

http://itpro.nikkeibp.co.jp/article/COLUMN/20061117/254053/

あと init はそもそも最初から殺す候補から除外されてて、 sshd 殺すくらいならいっそ init 殺して欲しいよなぁとか思った。