Sealed Rangeの件

gistfile1.mkd

Sealed Rangeには「安いコピコン」という前提が必須

Sealed Range

要素が参照になっていないけども，代入プロパティは存在するようなrange． コンテナにくっついているものが前提．

struct SealedRange
{
    // 参照はとれないが，要素の読み書きは出来る
    @property E front();
    @property void front(E rhs);
}

既存のものだと，std.container.Arrayに付属のRangeはシールされている．

何でそんなものが欲しい?

Arrayがまさに好例． このコンテナは要素をC言語のmallocで確保されたメモリに格納して，コンテナ自身にくっついた参照カウンタでメモリ管理する． コンテナが失効すればメモリも不正になるので，要素の参照がとれてはいけない． 参照からアドレスを取り出して，コンテナが死んだあとで変な所から利用されたらたまらない (クロージャで起こり得る!)．

GCで確保されたメモリなら，どこかで参照されている限り生きつづけるから安全なんだけど， mallocみたいにアンマネージドなメモリの参照はいつゾンビになるか知れない． そういうケースに対応するため，参照を晒さないsealed rangeというコンセプトが考えられた (んだと思う)．

要は「参照を晒さない」rangeに対してカッコイイ名前をつけただけなんだけど，こいつが面倒な性質を持っている．

Sealed Rangeが抱える問題: 常時コピー

たしかに良いコンセプトなんだけど，参照が返せないということは，常に値コピーをするということ． 例えばfrontとbackを入れ替える場合…

SealedRange r;

auto tmp = r.front;  // コピー
r.front = r.back;    // コピー
r.back = tmp;        // コピー

このように無駄なコピーだらけになってしまう． 素朴なintなら問題ないんだけど，重いコピーコンストラクタを持ったオブジェクトなら大問題． 要素の参照 (つまりメモリアドレス) が取れさえすれば，こういうswap操作は単なるmemcpyでコピコンなしに実行できるのに．

// 一度もコピコンを走らせずにswap
ubyte[E.sizeof] tmp;
memcpy(&tmp, &r.front, E.sizeof);     // コピコンなし!
memcpy(&r.front, &r.back, E.sizeof);  // なし!
memcpy(&r.back, &tmp, E.sizeof);      // ないない!

swapはソートアルゴリズムで O(NlogN) 回実行されるので，swapがコピコンで重くなるのは致命的!

コピーが重いオブジェクトの例: BigInt

例えばBigIntでは，コピコンで (おそらくデカい) リソースの複製を作る必要がある． 現状のstd.bigintは特にケアしてないけど，値型BigIntを素直に実装しようと思ったらこうなる:

struct BigInt
{
    Digit[] digits;

    this(this)
    {
        digits = digits.dup;
    }
}

void main()
{
    BigInt a = 10;
    BigInt b = a;     // コピーしないと ++b で a の値が「リモート破壊」されてしまう

    ++b;
    assert(a == 10);
    assert(b == 11);
}

こんな重いコピコンを持ってるんだから，Array!BigIntをソートしようものなら，果てしなくリソースを食いまくる!

最近提案されたもの: moveナントカ

• moveFront() and friends: Request for comment
• http://lists.puremagic.com/pipermail/digitalmars-d/2010-August/081996.html

Sealed rangeが抱える問題を解決しようと，新しいプリミティブが提案された．

struct SealedRange
{
    E front();
    void front(E rhs);

    // new!
    E moveFront();
    E moveBack();
    E moveAt(size_t i);
}

こいつらは front などと違い，コンテナ内部のオブジェクトを破壊的に読み込む． いわゆるムーブセマンティクスで，コピコンを走らせないのじゃ． これがあれば，swap操作は効率的にできる．

E tmp = r.moveFront();   // コピコンは走らない
r.front = r.moveBack();  // コピコンなし
r.back = move(tmp);      // なしなし!

コピコン走りそうに見えるけど，moveされた場合はcopy elisionがはたらいてコピコンなしにできる． D言語の仕様的に，論理的にコピーが無いのならコピコンは走らないと思って良い．

前の例でコピコンが走ったのは，コンテナ内の実要素と取り出したfrontのふたつ，論理的にコピーが存在してるから． moveではコンテナ内の要素を殺すので，論理的にコピーは存在しない．

moveFront …プリミティブがどんどん増えてイヤ

moveFrontとか登場したけど，rangeが複雑になりすぎて不満だという声もあった． refを晒したくないというStevenに対し，Andreiが「moveFrontがありますよ」と教える． それに対して「まーた余計なものが増えたのか」と文句言われる．

• sorting hidden data.
• http://lists.puremagic.com/pipermail/digitalmars-d/2010-September/083807.html

そして今月，Andreiが代替案を考えてきた．

• Ruling out arbitrary cost copy construction?
• http://lists.puremagic.com/pipermail/digitalmars-d/2010-October/084273.html

コピコンが重いからmoveFront等を考えたんだけど，そいつのせいでインターフェイスがずいぶん複雑になった． ならば，ライブラリの前提として「コピコンは軽いもの」と仮定してしまえという． それならば，moveなど使わなくとも素朴なswapで対応できるという:

E tmp = r.front;   // コピコンは走るが軽い
r.front = r.back;  // 軽い
r.back = tmp;      // 軽いから大丈夫

コピコンは O(1) であると要請することで，ソートの計算量が O(NlogN) に収まるという寸法．

「軽い」?

this(this)を禁止するという話ではなく，「あっても良いけど O(1) で済むような軽い処理だけにしましょう」という紳士協定の話．言語としてはthis(this)の中で何をやっても良いんだけど，そういうオブジェクトを container/range/algorithm で使った場合の性能は保証しませんという．

じゃあBigIntはどうするの?

BigIntなど，コピコンで内部リソースを複製したいものは，軽いコピコンという要請を満たせない!?

…のではなく，Copy-on-Writeのテクニックを使えば不要なリソース複製は封じられる． CoWの場合，コピコンでやる仕事は参照カウンタのインクリメントだけだから，O(1) で収まる．

この新しい制限のせいで「何かが出来なくなる」わけじゃあないんだけど，CoW実装する面倒は受け入れられるよね? というのがサブテーマ．

gistfile2.mkd

rsinfuの意見 (MLに返信したやつ)

Sealed rangeの要素を読み出すと，必ずコピコンが走る．だから安いコピコンという前提は必須． 短くまとめるとそういう意見．以下はその説明でござんす．

問題はswapだけじゃない

過去ログだと，みんなswap操作とmoveについてばかり話してた． でもこれ，swapだけの問題じゃないのに気づいてほしい． あらゆる操作にコピーがつきまとうし，moveで解決できるケースも限られてる．

Swapするときに限らず，いかなる要素アクセスもコピコンを呼び出すのに注意! 例えば Array!BigInt をソートする場合，なんの気なしの要素比較ですらコピーを作ってしまう:

if (!less(r[i], r[p]))  // ここでコピコンが2回走る．

コンテナ内とlessに渡すもので，論理的にオブジェクトが複数存在してるから，このコピコンは消去できない． まあもちろん，moveで取り出してから比較し，そのあとで代入し直せばコピコンは防げる． でもそんなのはヤダヤダ! あらゆる要素アクセスでそれをやるっての!?

たいていのシーンではただ要素を読みたいだけ． swapのようにmoveで解決できるのはごく一部で，ほとんどはコピーせざるをえない． Sealed rangeはそもそも要素を読むのにコピーをする (参照を見せない) というコンセプトなんだから， もしそいつを推してくというのなら，「要素のコピコンは軽いもの」と仮定しないと身動きとれないですよ．

そんなわけで，moveFront等を追放し，代わりにコピコンは安いという前提を要請するのに賛成．

gistfile3.d

// 参照カウントでCopy-on-Writeする例．rangeとかはいったん忘れて，純粋にCoWについて．

//
// CoW: 書き込み操作 (unshare) が無い限り，同じリソースを「共有」し続ける．
//
// unshare 時点でリソースが「自分だけのものでない」ならば，リソースを複製して
// 「自分だけのもの」にする．そういう共有状態を管理するのに参照カウンタを使う．
//

void main()
{
//  alias CopyingArray Array;
    alias CoWArray Array;

    auto a = Array(0, 1, 2, 3);
    auto b = a;
    auto c = a;

    a[2] = 200;
    assert(a[2] == 200);
    assert(b[2] == 2);
    assert(c[2] == 2);

    c[1] = 100;
    assert(a[1] == 1);
    assert(b[1] == 1);
    assert(c[1] == 100);
}



/*
 * 値セマンティクス (copy) の配列．
 */
struct CopyingArray
{
    int[] store;

    this(in int[] init...)
    {
        store = init.dup;
    }

    this(this)
    {
        store = store.dup;  // コピコンでdup
    }


    nothrow int opIndex(size_t i) const
    {
        return store[i];
    }

    nothrow void opIndexAssign(int e, size_t i)
    {
        store[i] = e;
    }
}



/*
 * 値セマンティクス (CoW) の配列．
 */
struct CoWArray
{
    struct Payload
    {
        int[] store;
        uint  refCount = 1;
    }
    Payload* payload;


    this(in int[] init...)
    {
        with (*(payload = new Payload))
        {
            store = init.dup;
        }
    }

    nothrow this(this)
    {
        // コピコンでは参照状態をいじるだけ．
        if (payload) ++payload.refCount;
    }

    nothrow ~this()
    {
        // 参照状態を管理するのにデストラクタがいる
        if (payload) --payload.refCount;
    }


    void unshare()
    out
    {
        // unshare の後は自分だけのものになる
        assert(payload.refCount == 1);
    }
    body
    {
        if (payload.refCount > 1)
        {
            // これは共有物．Copy!
            this = CoWArray(payload.store);
        }
    }


    nothrow int opIndex(size_t i) const
    {
        return payload.store[i];
    }

    void opIndexAssign(int e, size_t i)
    {
        unshare();  // unshare!
        payload.store[i] = e;
    }
}