擬似的末尾再帰最適化

なんか中国語みたいなタイトルになってますがお気にせずに。
コンパイラには(インタプリタにも?)末尾再帰の最適化がありますが、擬似的に手動でかけないかとやってみた。ちなみに言語はC言語。

こういう0～nまでの和を出す再帰関数を最適化してみる。

long long func(int n)
{
    if (n == 0)
        return 0;
    else
        return n + func(n-1);
}

自分の理解だとスタックを積まないで関数の先頭にgotoするというのが末尾再帰の最適化。なので、再帰するところで関数を呼び出さずに値を更新して先頭に戻ればよい。

long long func2(int n)
{
    long long ans = 0;
f:
    if (n == 0) {
        return ans;
    }
    ans += n;
    n--;
    goto f;
}

精度があんまりよくないclock関数で、テキトーにテストする。

int main()
{
    clock_t start, end;
    int i;

    start = clock();
    for (i = 0; i < 10000; i++) {
        func(65536);
    }
    end = clock();
    printf("%f\n", (double)(end - start) / (double)CLOCKS_PER_SEC);

    start = clock();
    for (i = 0; i < 10000; i++) {
        func2(65536);
    }
    end = clock();
    printf("%f\n", (double)(end - start) / (double)CLOCKS_PER_SEC);

    return 0;
}

Mac OS X, gcc 4.0.1で実験した結果が以下。

[~]% gcc test.c
[~]% ./a.out
12.750000
1.950000
[~]% gcc -O2 test.c
[~]% ./a.out
1.770000
0.740000
[~]% gcc -O3 test.c
[~]% ./a.out
1.900000
0.250000

結構違いがでた。たぶん他の環境でも擬似的に最適化した方が速いと思う。
あと、最適化した方はスタックオーバフローしない。
今回は簡単な関数でやったけど、末尾再帰の部分と関数先頭を少し書き換えるだけなので、他の再帰関数にも結構簡単に適用できる方法かもしれない。

一応まとまったファイルは「test.c」です。コメントゼロでごめんなさい。

シンボルテーブルのFUNCについて

naoyaさんのところで見かけて気になったので調べてみた。

• Executable and Linkable Format - WIkipedia
• オブジェクトファイルについて

などをみてみると、シンボルテーブルのTypeのFUNCはリンクの辺りで必要そう。

そこで、

int add(int x, int y)
{
    return x + y;
}

int sub(int x, int y)
{
    return x - y;
}

をfunc.cとして作成して、

$ gcc -S func.c

としてアセンブリコードを作成。

.globl add
    .type   add, @function

となっているところを

,globl add
    .type    add, @notype

と変更する。それから共有ライブラリを作成する。共有ライブラリを参考に

$ gcc -fPIC -g -c -Wall func.s
$ gcc -shared -Wl,-soname,libfunc.so.1 -o libfunc.so.1.0.1 func.o -lc
$ ln -s libfunc.so.1.0.1 libfunc.so.1
$ ln -s libfunc.so.1.0.1 libfunc.so

一応共有ライブラリのaddの属性の確認をする。

$ readelf -s libfunc.so | grep add
     6: 000003cc    11 NOTYPE  GLOBAL DEFAULT   10 add
    49: 000003cc    11 NOTYPE  GLOBAL DEFAULT   10 add

確かにNOTYPEとなっています。
次にこの共有ライブラリを使用するプログラムをmain.cとして作成します。

     1  #include <stdio.h>
     2
     3  int add(int, int);
     4  int sub(int, int);
     5
     6  int main()
     7  {
     8      int x, y;
     9
    10      x = 8;
    11      y = 4;
    12
    13      printf("%d\n", add(x, y));
    14      printf("%d\n", sub(x, y));
    15
    16      return 0;
    17  }

さて、ここからが本番です。

$ export LD_LIBRARY_PATH=.
$ gcc main.c -L. -lfunc
$ ./a.out
セグメンテーション違反です

となりました。main.cのaddをしている行を消して、

$ gcc main.c -L. -lfunc
$ ./a.out
4

となりsubの実行結果が表示されます。なので、シンボルテーブルのTypeのFUNCは動的リンクに必要にであることが分かりました。mainにFUNCをつける必要はないみたいですね。FUNCじゃなくてEXPO(export)とかの方が分かりやすかったりするのかなとか思ったりしました。

コメントがおかしい?

昨日GCC Wikiaでソースを読んでいて、コメントが変じゃないかというところにぶつかった。
gcc/c-lex.cの513行目と541行目の右にあるコメントが逆になると思う。

513行目を含む関数1つを下に載せます。

  527 static enum integer_type_kind
narrowest_signed_type (unsigned HOST_WIDE_INT low,
 529                        unsigned HOST_WIDE_INT high, unsigned int flags)
 530 {
 531   enum integer_type_kind itk;
 533   if ((flags & CPP_N_WIDTH) == CPP_N_SMALL)
 534     itk = itk_int;
 535   else if ((flags & CPP_N_WIDTH) == CPP_N_MEDIUM)
 536     itk = itk_long;
 537   else
 538     itk = itk_long_long;
 541   for (; itk < itk_none; itk += 2 /* skip signed types */)
 542     {
tree upper = TYPE_MAX_VALUE (integer_types[itk]);
 545       if ((unsigned HOST_WIDE_INT) TREE_INT_CST_HIGH (upper) > high
 546           || ((unsigned HOST_WIDE_INT) TREE_INT_CST_HIGH (upper) == high
 547               && TREE_INT_CST_LOW (upper) >= low))
 548         return itk;
 549     }
 551   return itk_none;
 552 }

ちなみにGCC Wikiaでは
http://ja.gcc.wikia.com/wiki/Narrowest_unsigned_type
http://ja.gcc.wikia.com/wiki/Narrowest_signed_type
 

ここはフラグを元に型を決めている所の一部なのだけど、
513行目からのループはsignedのついた型にするために、
unsignedは不要なので2を加えることで一個とばしで進んでいる。
(enum integer_type_kindは同じ型の符号あり、なしが並んでいる。)

コメントは「singed型を飛ばす」と訳せると思う。
となると、本来の処理と逆なのではないか。と思うわけです。

間違っていたとしてどうしたらいいもんなんだろう。
パッチをメーリングリストに流すのが一番なのかぁ。
でもなんか変な感じがする。

よかったら
このコメントが間違っているかどうかの検証と
間違っていた場合の対策を教えてくれると嬉しいです。

C言語で知らなかったこと

たいしたことじゃないんですけど、C言語での書き方で新しく知ったので書いてみる。
まずはサンプルをprintfの引数に注目。

#include <stdio.h>

int main()
{
    int i;

    printf("%d\n", (i = 3, i * 3));
    printf("%d\n", (assert(i == 3), 10));

    return 0;
}

というプログラムの実行結果が

9
10

となる。
一個目のprintfの引数で、

1. iに3が代入される
2. 3が代入されているiに3をかける

といったように()の中の式がちゃんと評価されている。んでもって最後のが()の最終的な評価の値になっている。
これはSolaris付属?のCコンパイラでも動いたので、GNUの拡張ってわけでもなさそう。

使える場面は、とりあえず二個目のprintfで書いたような、assertを絡めるときくらいしか思いつかないけど、おもしろいうごきだと思う。

はてなスター設置その後

前回の記事にてはてなスターの設置についてのエントリーを書きました。
なにやらブックマークしてくれる人がいたり、はてなスター日記のほうにもほんのちょっと取り上げていただいている様子。

そのコメントの中に、「ただし、このブログでは、Main Index(トップページ)にのみ設置している模様。」というものがありました。気づいてなかった・・・

というわけでいじってみました。不格好な方法かもしれないけれど解決しました。
まず、なんで一記事単位表示だとうまくいかないかについて書きます。

はてなスターが必要とする情報は、タイトルとpermalinkのURLだけです。はてなスターでは、以下のように、h3要素の中にリンクが含まれている場合に、それをタイトルとpermalinkである、と判断します。
はてなスターをブログに貼り付けるより

とあるようにh3要素の中にリンクが必要になっているのですが、一記事単位はタイトルがリンクになっていないのです。

それで解決法ですが、

記事の検出をしているのは「Hatena.Star.EntryLoader」というオブジェクトの「loadEntries」メソッドです。このコードを上書きすることで、はてなスターに正しく記事のタイトルとpermalinkを認識させることができます。
はてなスターをブログに貼り付けるより

とのことですので、同ページにのっているものを参考に

<script type="text/javascript" src="http://s.hatena.ne.jp/js/HatenaStar.js"/>
<script type="text/javascript">
  Hatena.Star.Token = 'd1b02052474b7e28330ad1fbba7513eb57a1ebfe';
</script>
<script type="text/javascript">
  Hatena.Star.EntryLoader.loadEntries = function () {
        var entries = [];
        //var headers = document.getElementsByTagName('h3');
        var c = Hatena.Star.EntryLoader;
        var headers = c.getHeaders();
        for (var i = 0; i < headers.length; i++) {
            var header = headers[i];
            var a = header.getElementsByTagName('a')[0];
            var uri;
            if (a) {
              uri = a.href;
            }
            else {
              uri = Ten.DOM.getElementsByTagAndClassName("a","permalink",document)[0].href
            }
            var title = '';
            var cns = header.childNodes;
            title = c.scrapeTitle(header);
            var cc = c.createCommentContainer();
            header.appendChild(cc);
            var sc = c.createStarContainer();
            header.appendChild(sc);
            entries.push({
                uri: uri,
                title: title,
                star_container: sc,
                comment_container: cc
            });
        }
        return entries;
  }
</script>

というスクリプトをメモのところに置きました。無理やりなので、ココログかはてなスターの仕様が変わったらすぐダメになりそうで怖いです。
ちなみに

<script type="text/javascript">
  Hatena.Star.Token = 'd1b02052474b7e28330ad1fbba7513eb57a1ebfe';
</script>
<script type="text/javascript">
  Hatena.Star.EntryLoader.loadEntries = function () {

の</script><script type="text/javascript">のところを無駄かと思って消したらうまくいきませんでした。これは

外部ブログの認証にはブログトップページにトークンの記述が必要です

はてなスターをブログに貼り付けるより

とうことなのだと思います。