大晦日ですねー

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

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 あたりに書いてあります。

初耳ですがー

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

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

だそうです。

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

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

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みたいに整数の範囲を犠牲にしたりして工夫すればポインタ一個分に収まらなくもないんですけどね。

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