彼女の友人がGCCの中の人から聞いた話

以下，エイプリルフールの記事として書いたものなので現代において読む価値はありません．

ブログには地震後初めて記事を書く事になって、生存報告としては明らかに遅いですね…。でも、twitterでは元気にやっていました。今は実家にいます。

さて、つい先日東京で言語雑談会というイベントがあって、その折につくばのお家の現状を見て来ました。特別大変な事が起こっていたわけでもなく心底ホッとしました。
その翌日には、彼女と東京は新宿バルト9でサヨナラノツバサを観たのですが、その折にgcc-4.6( http://gcc.gnu.org/gcc-4.6/changes.html )の話がでました。

gccの話が出たのはCランゲッジの話をしていたからなのですが、sequence pointをどうして副作用完了点と訳したのでしょうか、とかそういう疑問が発端だった気がします。
"副作用完了点"を認識した事の無い方は、次の参考ページを一読すると大変良いと思います。改めて考えると、ぼくはそんなに意識していませんでしたが…。 → http://www.jpcert.or.jp/sc-rules/c-exp30-c.html

さて、その時の話の核心というのは、gcc-4.6におけるundocumentedな最適化の話です。
次のようなコードを見てください。

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>

uint64_t fib(uint64_t x)
{
    assert(1 <= x);
    if(x == 1)return 1;
    else if(x == 2)return 1;
    else return fib(x-1) + fib(x-2);
}

void print(uint64_t v0,uint64_t v1,uint64_t v2)
{
    printf("v0 = %llu\n",v0);
    printf("v1 = %llu\n",v1);
    printf("v2 = %llu\n",v2);
}

int main()
{
    print(fib(38),fib(39),fib(40));

    return 0;
}

取りあえずこれを実行してみます。

/Users/ranha/Blog/2011AprilFool% gcc -Wall nyan.c -o a.out
/Users/ranha/Blog/2011AprilFool% time ./a.out
v0 = 39088169
v1 = 63245986
v2 = 102334155
./a.out  3.94s user 0.01s system 99% cpu 3.977 total

フムフム。
そして、ここでその友人から教わったというオプションを付けてみます。

フムフム！こちらの方が明らかに速いですね！！

しかし何をしているのだろう…

良く分からないので、gdbを使って調べてみました…。要所要所を抜き出すと…

Breakpoint 1, main () at nyan.c:
23	{
(gdb) n
22	int main()
(gdb) 
38	    if(pthread_create(&thread_a,NULL,a,NULL))exit(1);
(gdb) 
[New Thread 0xaacb70 (LWP 4493)]
39	    if(pthread_create(&thread_b,NULL,b,NULL))exit(1);
(gdb) 
[New Thread 0x12adb70 (LWP 4494)]
40	    if(pthread_create(&thread_c,NULL,c,NULL))exit(1);
(gdb) 
[New Thread 0x1aaeb70 (LWP 4495)]
41	    pthread_join(thread_a,&dummy[0]);
(gdb) 
[Thread 0xaacb70 (LWP 4493) exited]
42	    pthread_join(thread_b,&dummy[1]);
(gdb) 
[Thread 0x12adb70 (LWP 4494) exited]
43	    pthread_join(thread_c,&dummy[2]);
(gdb) 
[Thread 0x1aaeb70 (LWP 4495) exited]
44	    print(v0,v1,v2);
(gdb) 
v0 = 39088169
v1 = 63245986
v2 = 102334155
46	    return 0;

何だコレは！！！！！！

取りあえずシステム情報

/Users/ranha/Blog/2011AprilFool% uname -a
Darwin ranha-macbook.local 10.6.0 Darwin Kernel Version 10.6.0 とか

/Users/ranha/Blog/2011AprilFool% gcc --version
gcc (GCC) 4.6.0 20110401 (experimental)
Copyright (C) 2011 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

こんなコードを生成するらしい

上のフィボナッチ数を計算するコードから、次のようなコードを生成するようです。

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>
#include <pthread.h>

uint64_t fib(uint64_t x)
{
    assert(1 <= x);
    if(x == 1)return 1;
    else if(x == 2)return 1;
    else return fib(x-1) + fib(x-2);
}

void print(uint64_t v0,uint64_t v1,uint64_t v2)
{
    printf("v0 = %llu\n",v0);
    printf("v1 = %llu\n",v1);
    printf("v2 = %llu\n",v2);
}

int main()
{
    uint64_t v0,v1,v2;
    pthread_t thread_a;
    pthread_t thread_b;
    pthread_t thread_c;
    void *dummy[3];
    void* a(void* _){
        v0 = fib(38);return NULL;
    }
    void* b(void* _){
        v1 = fib(39);return NULL;
    }
    void* c(void* _){
        v2 = fib(40);return NULL;
    }
    if(pthread_create(&thread_a,NULL,a,NULL))exit(1);
    if(pthread_create(&thread_b,NULL,b,NULL))exit(1);
    if(pthread_create(&thread_c,NULL,c,NULL))exit(1);
    pthread_join(thread_a,&dummy[0]);
    pthread_join(thread_b,&dummy[1]);
    pthread_join(thread_c,&dummy[2]);
    print(v0,v1,v2);

    return 0;
}

成る程、gccのnested function( http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html )を使った実装で、カジュアルにpthreadに突っ込めるようにしている所が味噌なんですね。しかもnested functionにする事で、割と簡単にスコープのアレコレを解決出来るようになっていると！
(pthreadの扱いが凄い適当なのは御免なさいって事らしいです。)

でも引数の評価を並列にしてしまって問題無いのでしょうか??

これはつまり

f(e1,e2,...,en);

e1からenを並列に計算してもCランゲッジとして、問題は無いのか?という事です。

Cランゲッジは、その言語仕様として、関数の引数の評価に特定の順番を設けていません。
http://www.jpcert.or.jp/sc-rules/c-exp10-c.html

簡単な例を示します。

/* simple1.c */
#include <stdio.h>

int f(void){return puts("f");}
int g(void){return puts("g");}
void h(int a,int b){printf("a = %d,b = %d\n",a,b);}

int main(){
    h(f(),g());
    return 0;
}

/Users/ranha/Blog/2011AprilFool% gcc -Wall simple1.c && ./a.out
g                                                              
f                                                              
a = 10,b = 10                                                  

/Users/ranha/Blog/2011AprilFool% clang -Wall simple1.c && ./a.out
f                                                                
g                                                                
a = 10,b = 10                                                    

成る程、上の例でe1からenでお互いに「依存が存在しない場合」は、並列に動かしたとしても問題は無い気がします。

依存が存在する場合はどうか?

次のプログラムを考えてみます

#include <stdio.h>

int i = 0;

int f(void)
{
  return ++i;
}

int main()
{
  printf("%d %d\n",f(),f());
  return 0;
}

これを並列に実行した場合には、変数iに関して所謂data raceが発生してしまう気がします。所が、Cランゲッジの挙動としては、data raceが発生しても良いのです。

http://www.jpcert.or.jp/sc-rules/c-exp30-c.html

直前の副作用完了点から次の副作用完了点までの間に、式の評価によって1つのオブジェクトに格納された値を変更する回数は、高々1回でなければならない。さらに、変更前の値の読み取りは、格納される値を決定するためだけに行われなければならない。

引数の間に、副作用完了点が存在しないので、つまり上の例だと副作用完了点の間で、大域的な変数iに対して変更が「2回」行われている事に成ります。この場合は、挙動として"undefined"という事に成っています。

http://www.st.rim.or.jp/~phinloda/cqa/cqa7.html
未定義、即ち「鼻から悪魔が飛び出しても仕様に反しない」( http://groups.google.com/group/comp.std.c/msg/dfe1ef367547684b )わけです。

という事は、まぁ並列に走らせても問題はないのでしょう。

いや、嘘かもしれません。undefinedでは無い気がします。
printf中の2つのfのどちらを先に呼び出すのかという点では自由です。しかし、結局の所どちらかを先に呼び出さなければ成りません。
ここで、

int i=0;

int main()
{
  printf("%d %d\n",(λx . i+=1;i)(),(λx . i+=1;i)());
  return 0;
}

なものを考えた時に、副作用完了点の区間としては異なるうちでそれぞれiをmodifyしている気がするので…。

アイエエエ！ C99では、expression-statementというまぁ"exp;"の形の文の終了点に副作用完了点を持っているので、undefinedに成る事を利用した並列化は出来ない気がします。ムネン。

参考 : http://www.open-std.org/JTC1/SC22/wg14/www/docs/n1124.pdf (特にAnnex C)

本当にそう?

共通に可視な変数に対して、引数を評価している間(副作用完了点の間)に0回modify , 2回以上modifyの場合を考えました。では1回の場合で何か不味そうな事は起こるでしょうか?

#include <stdio.h>

int i = 0;

int f(void){ return i; }
int g(void){ i = 42; return i; }
int h(int a,int b){ ... }

int main()
{
  h(f(),g());
  return 0;
}

この場合にfとgが並列に実行されると…。これは高々1回に収まっているのでundefined behaviorでは有りませんが、並列実行した場合は良く無い事が起こる筈です。

この良く無い事は、「評価順に関してspecifyしない」というCランゲッジの仕様から導けない結果です。"順に1つずつ実行した場合"には"発生しえない"挙動をする可能性があります。

結果として

f(e1,e2,...,en);

の形でe1からenを並列に実行する事は単純には行えない事が分かりました。ので、残念ながら上のような最適化手法は使えそうにないです…。

他には何が出来る?

• http://www.kmonos.net/wlog/96.html#_2319090427
  • http://d.hatena.ne.jp/sumii/20090428/p1
  • http://d.hatena.ne.jp/ku-ma-me/20090427/p3

いなばさんの上記エントリに端を発した、「カジュアルのんでたーみにずむ」な話も言えたりします。

unspecifiedであるという事は、その解釈に余地が残されているわけで、私達は良く「処理系や環境依存ではないコードを書きましょう！」など言われるわけで、それ自体は良いのですが、そこからひいては「unspecifiedはどうしようも無い子だし、undefinedって何の為に生きているのでしょうか…」といった考え方になってしまいます。

ちょっと待った！！unspecifiedであるということ、undefinedであるという事をもっと利用出来ないか！！というのが本エントリを書くキッカケでした。

言語仕様におけるundefinedとunspecifiedについて、最近だとこんな話が。

テストに関するお話

TLDI2011でacceptedな話として http://blog.regehr.org/archives/492 があります。これは、differential testingという手法でCのコンパイラをテストしようぜ！！というものです。

differential testingというのは、仕様に関して妥当なプログラムを複数のコンパイラに突っ込んで、その振舞を調べる。振舞が違っていれば、コンパイラのどれかにバグがあるから、それを手がかりにして調べようというお話です。振舞が同じで、実は全てのコンパイラにバグがあるという事も起こりうる筈ですが、まぁそれは…ね。みたいな感じデス。詳しくは上記ブログから論文を読んでみてください。

ここで重要なのは、コンパイラ達の入力とするプログラムが「一意」になるという事です。
もう少し具体的に言うならば、「１つのプログラムから導かれる挙動がただ１つに定まる」という事です。
挙動と言っても、実行するタイミングでシステムコールの結果としての値が違ったりとかそういう細かい部分はあるのですが、それ以前の話として、「仕様レベルで」undefinedやunspecifiedに陥ってしまうコードを生成しないようにしよう、というものです。

そうすれば、一意に成る筈なのに違ってる → コンパイラが何か不味い！と言えそうです。

証明に関するお話

CompCertという検証されたコンパイラがあります。
http://compcert.inria.fr/
特に分かり易い論文は
http://gallium.inria.fr/~xleroy/publi/compcert-CACM.pdf

CompCertは、ソース言語(Cの"サブセット")の意味が、コンパイルされた後のターゲット言語(PowerPCアセンブリ)でも保存されている事を証明した、しかも普通に使える程度に速いコンパイラです。

ここでCの"サブセット"(Clightと呼ばれています)を用いるのには、Cの振舞が「非決定」である所に起因しています。結果から言って、PowerPCアセンブリは「決定的」、つまり1つのコードから生まれる振舞は1つですが、大元のCのコードから生まれる振舞は1つでないわけです。

それだと「ソース言語プログラムの意味がターゲット言語に落ちた時に保存されている」事を証明するのが困難になってしまうので、そこで新たに、Cの仕様として解釈の余地が在った部分を詰め、決定的になったClightをソース言語とし形式化を行ったという話です。

裏を返せば

Cランゲッジは並列に評価出来る所はガンガンしちゃっても良いし、そもそも非決定！
しかも関数引数の評価順だけでなくて、他にもunspecifiedはあるのです。上述のCsmithの論文によると、C99のunspecifiedはその数52種

「好きなように解釈して、好きなようにコンパイラを作ろう！！」

Cランゲッジはまだまだはじまったばかり！！

おわりに

ぼくが欲しいのは、健全かつ完全にundefinedとunspecifiedを検出する多項式時間実行可能なツールですけどね…