W.Deeの2008年12月の日記

kikyou.info»日記

誠に勝手ながら、kikyou.infoは2017年12月いっぱいをもって閉鎖します。ながらくありがとうございました。

最新月 : 2008年10月
2003年 [             3    4    5    6    7    8    9   10   11   12  ] 月
2004年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2005年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2006年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2007年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2008年 [   1    2    3    4    5    6    7    8    9   10   11   12  ] 月
2009年 [   1    2    3    4    5    6    7    8    9   10   11       ] 月
前月の日記  次月の日記

2008年12月31日

RisseのtString(その2)

大晦日ですねー

RisseにはtSS<>というちょっとアレなテンプレートクラスがあります。

Risseのソースを見ると随所に

tSS<'r','i','s','a'>

のような変な記述があると思いますが、これはtString型のstaticなインスタンスを作るテンプレートクラスです。

上記ならば

template <risse_char c0,risse_char c1,risse_char c2,risse_char c3>
struct tSS<c0,c1,c2,c3,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>
{
    static tStringData data;
    static risse_char string[4+3];
public:
    operator const tString & ()
    { return *reinterpret_cast<const tString *>(&data); }
};
template <risse_char c0,risse_char c1,risse_char c2,risse_char c3>
risse_char tSS<c0,c1,c2,c3,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>::string[4+3]=
    {tStringData::MightBeShared,c0,c1,c2,c3,0,
     tSSN<tSSS4<0,c0,c1,c2,c3>::r>::r};
template <risse_char c0,risse_char c1,risse_char c2,risse_char c3>
tStringData tSS<c0,c1,c2,c3,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>::data =
{ tSS<c0,c1,c2,c3,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>::string + 1, 4};

みたいな鬼のようなテンプレートが使われます。tStringと同じデータ構造を持ったstaticな文字列をこれで実体化できるというわけですね。ハッシュ表検索で用いる文字列のハッシュもコンパイラにより自動的に計算されて格納されます。

文字列をこんな感じで扱える利点は

  • 同じ文字列のインスタンスをリンカが勝手に一個にまとめてくれる
  • 他のテンプレートに文字列を「型」として渡すことができる

欠点として

  • tSS<'r','i','s','a'> みたいに入力するのが面倒
  • コンパイラいじめ、リンカいじめ
  • static な文字列しか扱えない

な感じでしょうか。

今年最後の日記でした。今年もお世話になりました。来年もよろしくお願い致します。とりあえず年明けには毎年恒例のcopyright付け替え祭りだw

  • 2009-01-03 15:21 lucius : 昔 boost の ML にあげられてた static_string の tString 版ですかね?
  • 2009-01-04 18:59 W.Dee : そのMLみてないんで分かりません
  • 2009-01-05 15:02 W.Dee : http://lists.boost.org/Archives/boost/2003/03/45172.php あー、これですか?(探した) まぁこんなかんじですかね
  • 2009-01-05 22:23 lucius : しまった、探させてしまったようですみません。それです。

2008年12月30日

RisseのtString

tStringはいわゆる文字列型です。

tStringは二つのデータフィールドからなるクラスで、前の前のエントリにも書きましたが、以下のようになってます。

struct tStringData
{
    mutable risse_char  *    Buffer;    //!< 文字列バッファ
    risse_size               Length;    //!< 文字列長 (最後の \0 は含めない)
};

class tString : protected tStringData { ... };

文字列バッファは、複数のtStringインスタンス間で共有されます。たとえば、

tString a = "XYZ", b;
b = a;

となっていた場合、b = a の部分は、以下のようなコードが実行されます(あとで説明しますが実際はちょっと違います)。

b.Buffer = a.Buffer;
b.Length = a.Length;

インスタンスごとに文字列の長さをもっているので、たとえば"XYZ"の"Y"の部分だけ取り出したい場合は

b.Buffer = a.Buffer + 1;
b.Length = 1;

のようにすることで、他の文字列の部分文字列を効率的に取り出すことができます。

ところで、Risseのスクリプト上のStringはJavaやTJS/TJS2のStringと同じで、immutable(不変)なオブジェクトであり、一旦値を代入すると中身を変えることができませんが、その下層実装であるtStringはmutableなオブジェクトです。

単純に上記のようなコピーをしたあとの文字列の内容を変更すると、他の文字列の内容も変わってしまいます。なので、いわゆるCopy On Write (COW)という手法で、内容を変更するタイミングで文字列そのものをコピーして独立させ、それに対して変更を加えるようになっています。

もちろん、文字列が共有されていなければコピーする必要はありません。なので、COWをやる前に、その文字列が共有されているかどうかを知る必要があります。

TJS2の実装では、各文字列インスタンスが参照カウンタをもっていたので、共有されているかどうかを簡単に知ることができました(参照カウンタ>1ならば共有されている)。

Risseの場合、参照カウンタを持つことは現実的ではありません。バッファの実際の管理は外部のGCまかせだからです。参照カウンタのインクリメントはともかく、デクリメントがやり辛いです。おのれBoehm GC。

なので、その文字列が共有されているかどうかを厳密に管理することはあきらめ、その文字列が「共有されているかもしれない」というフラグを管理するようにしました。要するに、一回でもバッファが共有されれば、そのバッファは共有されているとしてマークされ、たとえ実際には共有されないようになったとしてもCOWされるようになります。まー、しょうがない。

で、問題はさっきのバッファの一体どこにその情報をいれるか、です。

種明かしをすると、Buffer[-1]がその情報を持っています。

文字列が新規に確保されたとき、Buffer[-1]は0になっています。

実際のtString::operator =(const tString &)はどうなっているのかというと、

tString & operator = (const tString & ref)
{
    if(ref.Buffer[-1] == 0)
        ref.Buffer[-1] = MightBeShared; // 共有可能性フラグをたてる
    Buffer = ref.Buffer;
    Length = ref.Length;
    return *this;
}

となってます。要するに、文字列をコピーするときはBuffer[-1]にMightBeSharedという値を代入することで、文字列が共有されている可能性があることを表しています。MightBeSharedはいまのところ(risse_char)-1という値になっています。

文字列が共有されている可能性があれば文字列バッファをコピーする部分は以下のようになっています。

risse_char * Independ() const
{ 
    if(Buffer[-1]) // 共有可能性フラグが立っている?
        return InternalIndepend();
    return Buffer;
}

つまり、Buffer[-1]が0以外であればInternalIndepend()を呼んでいます。実際のバッファのコピーはInternalIndepend()内で行われています。

部分文字列をとってきたときはどうなるか……ということになりますが、親文字列の最初から部分文字列をとった場合(Lengthだけが違う場合)はBuffer[-1]は親文字列と同じですのでとくに考慮なしですが、親文字列の途中からとった場合、たとえば"XYZ"の"Y"だけをとった場合はBuffer[-1]は'X'になっています。この場合は上記のIndepend()内のif(Buffer[-1])において真を示すため、共有の可能性があるとして扱われます。上記のoperator =の実装でref.Buffer[-1] == 0をチェックしているのも、部分文字列を扱っていた場合に、Buffer[-1]をMightBeSharedの値で潰してしまわないようにするためです。

これを書いてるとき、tStringをimmutableなオブジェクトにしてしまえば良かったんじゃないのかね、と思っていろいろ検討したんですが、mutableな今の状況でも大してパフォーマンスかわらんだろうということでこのままに。

もうちょっと詳しい話は https://sv.kikyou.info/trac/kirikiri/browser/kirikiri3/trunk/src/core/risse/src/risseString.h あたりに書いてあります。

2008年12月28日

IGDA日本ゲームテクノロジー研究会(SIG-GT)第12回研究会「ゲームにおけるスクリプト言語の現状」

初耳ですがー

http://d.hatena.ne.jp/epics/20081228

http://www.igda.jp/modules/eguide/event.php?eid=58

だそうです。

うーん、日程的に微妙だなぁ

けどなるべく空けていってみるか

  • 2008-12-28 22:13 W.Dee : 懇親会込みで申し込んじゃいました
  • 2008-12-29 14:51 える : パネラーとしてW.Deeさんが行ったほうがいいんじゃないかとおもいました(^_^;)
  • 2008-12-29 19:30 W.Dee : なんか他のひとからもにたようなこと言われましたwまあニヨニヨしながら聞いていることにします。
  • 2008-12-30 11:42 epics : 今回はゲームスクリプト総論なので、どうしてもADV系の割合が薄めになるのですよー。すみません。ADV系中心の回をやるときには、ぜひぜひ。懇親会でお話しできるのを楽しみにしております。
  • 2008-12-31 20:58 W.Dee : 一応誤解される方がいらっしゃるかもしれないので弁解しておきますけど吉里吉里はADV/ノベルが主用途とはいえADVやノベル専用じゃないですけどね(^^;; 搭載しているスクリプト言語は汎用言語なので尚更です。あとADV関連のスクリプトということならば私よりも現場に即しててよくお分かりの方がたくさんいらっしゃるので私は役に立ちません(汗)。当日は楽しみにしていますー
  • 2009-01-16 00:19 epics : うっ。すみません。うかつな表現をしてしまいました。TJS2やRisseが汎用言語なのは重々承知しております。吉里吉里3は本当に期待しております!ちなみに、自分もtype Pを衝動買いしてしまいました。刻印サービスを使ってしまったので届くのが下旬になりそうなのが待ち遠しいです。
  • 2009-01-17 23:09 W.Dee : いってきました~。スクリプトをどう使うかという点に期待してこられた方が今回は多かったのかな?というとCRIScriptの話はスクリプトをどう実装するか、でしたのでちょっと違うイメージでしたね。パネルディスカッションは後半スキップされてしまった質問内容に興味がありました。
  • 2009-01-17 23:32 W.Dee : 全体的には面白かったかと思います。皆様お疲れさまでした。typeP買いましたかwうちもまだ来ていませんです。

2008年12月24日

RisseのtVariant

tVariant はいわゆるバリアント型です。tVariant一つで整数だとか実数だとか文字列だとかいろいろ表すことができます。どんな型を表すことができるかというと…

  • String
  • Octet
  • Data
  • Void
  • Integer
  • Real
  • Null
  • Boolean
  • Object (上記以外の型は全部これ)

と、9種類の型を表すことができます。たとえば、文字列は、

struct tStringData
{
    mutable risse_char  *    Buffer;    //!< 文字列バッファ
    risse_size                Length;    //!< 文字列長 (最後の \0 は含めない)
};

みたいな感じで、文字列バッファと文字列長をデータとして持っています。これにより他の文字列の部分文字列を効率的に取り出せるようになっています。

Dataは任意のプリミティブ型を表すデータ型で、それほど複雑なデータ構造を持たないかわりに、Risseとのバインディングも単純(サブクラスを持てないなどの制約がある)で軽量なデータ型で、これも

struct tData
{
    tPrimitiveClassBase * Class; //!< クラスインスタンスへのポインタ
    void * Data; //!< データ(なんでもよい。何を表しているかは Class が決める)
};

みたいな感じで、クラスへのポインタとデータ本体へのポインタを持っています。

実数の場合は

struct tReal
{
    risse_ptruint Type; //!< バリアントタイプ: 6 固定
    // ここに パディングが入っている場合アリ
    risse_real Value; //!< 値
};

となっていて、バリアントのタイプを表す整数値と、値その物が入っています。

これらがすべてunionになったのがtVariantということになります。つまり最大でポインタ二つ分のデータを保持しています。LP64の場合は128bitとなります。ILP32の場合は64bitとはならず、パディングの関係でLP64と同じく128bitとなります。

…で、たとえば上記のtDataとtRealをunionにした場合、tData::ClassとtReal::Typeが、tData::DataとtReal::Valueがそれぞれ同じ領域を共有することになります。tRealはTypeが6なのでこれが実数型だとわかりますが、tDataの場合はどうやってこれがData型だと分かるのでしょうか?(ちなみにrisse_ptruintはデータポインタ型と同じサイズを持ったunsigned)。

実はtData::Classのポインタの下位2ビットは常に2に固定されています。下位2ビットを取り出してそれが2だったらData型ということになります。newされたオブジェクトはまず間違いなく4や8などの何らかの倍数のアドレスに配置されるので、下位の数ビットはいつも0になり、遊んでいます。そこに型情報を突っ込む、というトリックになっています。もちろんそのままではtData::Classの本当のインスタンスにはアクセスできませんから、実際に使うときは下位2ビットをマスクして使うことになります。

あれれ、tReal::Typeも常に6じゃ、下位2ビットは2だよ、ということですが、メモリアロケータは普通6とかいう低いアドレスにメモリブロックを配置しないのでこれは問題になりません。

tStringの場合は、、、となりますが、risse_charはUTF-32なのでrisse_char *は4バイト単位にしか移動せず、常に下位2ビットは0になります。

このような特性により、tVariant::GetType() (型を返す関数) は以下のように実装されています。

tType GetType() const
{
    return static_cast<tType>(Type < 9 ? Type : (Type & 3));
}

Typeが9未満であればTypeそのまま、それ以上であれば(おそらくこれはオブジェクトへのポインタなので) 下位2ビットを取り出します。

tType は以下のようになっています。

enum tType
{
    vtVoid            = 4,
    vtInteger        = 5,
    vtReal            = 6,
    vtNull            = 7,
    vtBoolean        = 8,
    vtString        = 0,
    vtOctet            = 1,
    vtData            = 2,
    vtObject        = 3,
};

Typeが9未満であれば vtVoid, vtInteger, vtReal, vtNull, vtBooleanで、9以上であれば下位2ビットを取り出したのちvtString, vtOctet, vtData, vtObjectのいずれかになるといった具合です。

rubyみたいにポインタ一個分だけでいろいろ表せるようにしようとも思ったのですが、なんとなくこんな感じに。もともとrubyの実装から着想したものですけど。rubyみたいに整数の範囲を犠牲にしたりして工夫すればポインタ一個分に収まらなくもないんですけどね。

パフォーマンスはどうなんだろ。演算性能よりメモリ帯域のほうが大幅な制限を受けやすいからどうなることやら……。

  • 2008-12-25 02:12 ひろにー : Valiantって便利なんですけど、管理を間違えるとバグの元なんですよねー。VC2008って、そのへんすごくうるさいし。自分の能力を試されてる気がします。
  • 2008-12-28 19:53 Chiharu : アライメントを逆手にとって省メモリプログラミングとはなかなかおもしろいですね。独自のVariantは私も実装したことありましたが、typeは可変長データのサイズと共用してました。struct Variant { Type type:4; unsigned length:28; union {...} impl; };な感じで。ポインタとの共用は…、なかなかアグレッシブですね。移植性に課題はありますが、おもしろい方法だと思います。
  • 2008-12-29 19:36 W.Dee : VCのvariantというとOLE由来のアレですかな?僕はあんまり使ったこと無いです。
  • 2008-12-29 19:47 W.Dee : たしかrubyでも似たことをやっていて、僕のしるかぎりLinuxやWindowsがまともに動くアーキテクチャで問題を起こすのはないです。他にもポインタのMSBやLSBをGCのマーキングにつかう処理系とかありますよね。
  • 2009-01-02 00:21 Chiharu : なるほど。型情報も enum 型そのままでなくポインタサイズの整数値として用意しているあたり、気を配ってるなーと感じてます。アライメントの件は、何となれば、メモリアロケータを自作すればいいだけの話ですし。いやぁ、いずれにしても凝ったことをしているなと感心しました。
  • 2009-01-04 22:49 W.Dee : C言語のアロケータが保証するアラインメントはそのプロセッサにおいてもっとも制限の強い型に合わせられる(Programing language C, 8.7 Example - A Storage Allocator)とのことで最近のVC++のlibcとかでは16byteアラインメントみたいですね(SSE命令関連が16byteアラインメントを要求するはず)。MIPSやSPARCではそもそもミスアラインメントするとクラッシュしますしアロケータがアラインメントされてないメモリ領域をかえすことはまずありえないと思います。もっともRisseではBoehm GC使ってますがこっちもドキュメントでも明示的にアラインメントされたメモリが帰ることが保証されてます。
  • 2009-01-05 21:45 Chiharu : VC++/libcが16byteアライメントは初耳でした。以前は予約語やSIMD用の組み込み型を使ったりしてお手軽アライメントしていたものですが。まぁ、アライメント違反の復帰はPowerやx86等の結構高級なCPUでないとサポートしてない上、パフォーマンスへの悪影響がひどいのでアライメント違反なんてやらないのが普通だと思います。あぁ、そうか。言い換えておかないと誤解がありますね。『移植性の課題』と言ったのは単に『ANSI Cで保証される範囲で完結していない』というだけです。現状ではDSPでもない限り、変則的なアライメントやアドレッシングはないと思ってますよ。ミドルウェアでアライメントを保証しているのであれば、なおのこと安全ですね。