要素が参照になっていないけども,代入プロパティは存在するようなrange. コンテナにくっついているものが前提.
struct SealedRange
{
// 参照はとれないが,要素の読み書きは出来る
@property E front();
@property void front(E rhs);
}
既存のものだと,std.container.Arrayに付属のRangeはシールされている.
Arrayがまさに好例. このコンテナは要素をC言語のmallocで確保されたメモリに格納して,コンテナ自身にくっついた参照カウンタでメモリ管理する. コンテナが失効すればメモリも不正になるので,要素の参照がとれてはいけない. 参照からアドレスを取り出して,コンテナが死んだあとで変な所から利用されたらたまらない (クロージャで起こり得る!).
GCで確保されたメモリなら,どこかで参照されている限り生きつづけるから安全なんだけど, mallocみたいにアンマネージドなメモリの参照はいつゾンビになるか知れない. そういうケースに対応するため,参照を晒さないsealed rangeというコンセプトが考えられた (んだと思う).
要は「参照を晒さない」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では,コピコンで (おそらくデカい) リソースの複製を作る必要がある. 現状の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をソートしようものなら,果てしなくリソースを食いまくる!
- 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とか登場したけど,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など,コピコンで内部リソースを複製したいものは,軽いコピコンという要請を満たせない!?
…のではなく,Copy-on-Writeのテクニックを使えば不要なリソース複製は封じられる. CoWの場合,コピコンでやる仕事は参照カウンタのインクリメントだけだから,O(1) で収まる.
この新しい制限のせいで「何かが出来なくなる」わけじゃあないんだけど,CoW実装する面倒は受け入れられるよね? というのがサブテーマ.