Skip to content

Instantly share code, notes, and snippets.

@sinfu

sinfu/gist:657669

Created Nov 1, 2010
Embed
What would you like to do?
Sealed Rangeの件

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ナントカ

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がありますよ」と教える. それに対して「まーた余計なものが増えたのか」と文句言われる.

そして今月,Andreiが代替案を考えてきた.

コピコンが重いから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実装する面倒は受け入れられるよね? というのがサブテーマ.

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等を追放し,代わりにコピコンは安いという前提を要請するのに賛成.

// 参照カウントで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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.