週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

5月16日に修正。call by needをthunkに言い換えました。


C++ template metaprogrammingでthunkがちゃんとthunkになっていることを確認してみました。心配だったので。

確認のためのプログラムを書きます。型リストは例によって自作なので雰囲気だけ見てください。

#include <iostream>
#include "tlist.h"
#include "classname.h"
using namespace std;
using namespace TLAZY;  // namespace for my type-level list.

#ifndef SIZE
#define SIZE 10
#endif
#ifndef COUNT
#define COUNT 10
#endif

// Thunk.  Takes O(SIZE) time just to return IntType<SIZE-1>.
template<int n>
struct Lazied {
  typedef
  typename Head<
    typename Reverse<
      typename ListByRange<0, n>::type>::type>::type type;
};

template<typename F>  struct Apply : public F {};
// Evaluate the thunk $COUNT times.
typedef Map<Apply, Replicate<COUNT, Lazied<SIZE> >::type >::type Result;

int main() {
  cout << className(Phantom<Result>()) << endl;
}

計算にO(SIZE)時間かかるサンクをCOUNT回評価しています。SIZEとCOUNTを変化させつつコンパイルし、コンパイル時間を計測します。次のようになれば成功です。

  • COUNT = 0のときは計算時間はSIZEによらず一定。
  • COUNT > 0のときに計算時間はCOUNTによらずSIZEにのみ依存する。

評価に使用したコンパイラはg++4.3.3。Core 2 Duo 2GHzのマシンにUbuntu 9.04を載せたもので計測しました。コンパイラオプションは-DSIZE=xxxと-DCOUNT=xxxの他は-ftemplate-depth-10000のみ。

$ g++ --version
g++ (Ubuntu 4.3.3-5ubuntu4) 4.3.3
Copyright (C) 2008 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.

結果は次のとおり。左のグラフは横軸にCOUNT, 縦軸にコンパイル時間を、右のグラフは横軸にSIZE、縦軸にまたコンパイル時間を表しています。

Time cost of evaluating thunk, depending on how many times it is evaluated.Time cost of evaluating thunk, depending on SIZE.
ちゃんと高々一回だけ評価されているようです。SIZE > 1000で計算時間がSIZEに対して線形に伸びていないように見えるのが気になりますが、call by needの前では些細なことです。

スポンサーサイト
コメント
この記事へのコメント
例によって、C++ templates : the complete guide あたりからのうろ覚えなんですが、call by need なのは仕様で要求されているんではなかったでしたっけ。
2009/05/13(水) 01:11 | URL | 白のカピバラ #wr.8gKW6[ 編集]
む、ちょっと書き方(特にタイトル)がまずかったですね。

この記事はむしろちゃんとthunkを書く方法と、call by needを確認する方法を知りたかったので書きました。
タイトルはそうなってないですね:(
2009/05/13(水) 08:10 | URL | Gus #-[ 編集]
タイトルと本文を若干書き換えました。具体的にはcall by needをthunkに書き換え。
型名::typeと書くと、それがどこかで使用されているかに関わらず計算が行われます。これはcall by needじゃないような気がしてきたので全般的にthunkに変えました。
2009/05/16(土) 11:30 | URL | Gus #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/449-c39b21df
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。