揺動散逸日記

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、縦軸にまたコンパイル時間を表しています。