このページの英語版を見る

D スライス

溢れ出る問題
スライスについて
責任は誰にあるのか?
追加できるスライス
仕組み
決定論
キャッシュ
スライスメンバーとアペンダ
結論

スティーブン・シュベイホーファー著

D言語の最も優れた機能のひとつは、スライスの実装である。D以外のプログラミング言語を使用するたびに、Dのスライス構文が恋しくなる。スライス構文は簡潔で効率的なだけでなく、スライスを扱う際には「ただ動く」のだ。

Dのスライスと配列の背景と内部についていくつか説明し、これを読んだ後には、Dのスライスの適切な使用方法についてより明確な理解が得られるとともに、通常の配列とは根本的に異なる点についても理解が深まることを期待している。

溢れ出す問題

ほとんどの言語では、配列は組み込み型であり、独自のデータを管理し、参照によって受け渡しされる。全体を「配列」と呼び、配列に対するすべての操作(値の設定、動的配列へのデータの追加、長さの取得など)をその型に関連付ける。

しかし、DはCからその系統を受け継いでおり、Cでは配列は単に連続したデータの塊である。Cでは、配列または配列セグメントへの参照は、ポインタ(明示的な参照)と同じくらい単純である。Cの配列は、参照するポインタの型によって明確に管理されていない。サポートされている操作は、ポインタからのオフセットを使用してデータを取得および設定することだけである。

C言語に不慣れな方のために、C言語での配列の使用例をいくつか挙げる(これらはDでも動作する):

pointerポインタ

arr[0] = 4; /* 配列'arr'の最初の要素を4に設定する */
x = arr[1]; /* 配列'arr'の2番目の要素をxに取り出す */

それ以外(長さ、追加、割り当て、破棄)はライブラリ関数や仮定/文書化に委ねられる。では、この概念のどこが問題なのか?C言語の配列の最大の問題のひとつは、配列に属さないデータであっても、ポインタ経由でアクセスできることだ。負のインデックスも使用できる!言うまでもなく、配列は単一のアイテムへのポインタとまったく同じ型を使用する。関数のパラメータとしてポインタを受け取った場合、それは配列である可能性もあるし、単一のアイテムへのポインタである可能性もある。キューバッファオーバーフロー攻撃。このことについては、Walter Bright氏の「Cの最大の過ち」という記事で詳しく説明されている。

スライスを導入する

では、Dはどのようにして状況を改善するのだろうか? 多くの点で、Dの配列はCの配列と類似している。実際、Dはポインタを使用するCの配列構文をサポートしている。しかし、DはCの配列構文を基に、スライスと呼ばれる新しい型を提供している。スライスは、ポインタとセグメントの長さを追跡する配列(動的または静的)のセグメントである。データの長さを保護する機能と、データのバックアップとなるメモリを管理するガベージコレクタを組み合わせることで、スライスは非常に強力で動的な概念となり、ほとんどのメモリ破壊の問題から保護される。さらに、Dスライスは、スライスを最初のパラメータとして受け取る単純な関数で拡張をサポートしている。これにより、プロパティやメソッドを介して、組み込み型に任意の機能を追加することができる。Dスライスを使用すると、他のほとんどの言語では扱いにくかったり非効率的であったりするような、エレガントで簡潔な構文で、高性能なコードを記述することができる。

Dスライスを実際に見てみよう。

D sliceD スライス

import std.stdio;

void main()
{
    int[] a;             // aはスライスである。

    a = new int[5];      // 少なくとも5つの要素を持つ整数の動的配列を確保する
                         // 要素を持つ動的配列を確保し、最初の5個をスライスする。  注意
                         // Dのデータはすべてデフォルトで代入される。
                         // したがって、この配列には5つの0が含まれる。

    int[] b = a[0..2];   // これは「スライス」操作である。bはaの
                         // 最初の2つの要素を指すようになった。Dは上限値に
                         // オープン・インターバルを使うので、a[2]はbに含まれないことに注意。

    int[] c = a[$-2..$]; // cはaの最後の2つの要素を指す。
                         // ($はスライスまたはインデックス操作内の長さを表す)。

    c[0] = 4;            // これはa[3]も代入する
    c[1] = 5;            // これはa[4]も代入する

    b[] = c[];           // a[]の最初の2つの要素に、
                         // 最後の2つの要素(4, 5)の値を代入する。

    writeln(a);          // "[4, 5, 0, 4, 5]"と表示する

    int[5] d;            // dは固定サイズの配列で、スタックに確保される
    b = d[0..2];         // スライスは固定サイズの配列も指すことができる!
}

配列の割り当ての説明について、何か疑問に思う点があるかもしれない。「少なくとも5つの要素を持つ整数型の動的配列を割り当て、最初の5つの要素のスライスを渡す」なぜ「5つの要素を持つ動的配列を割り当てる」ではいけないのか?Dのベテランプログラマーでも、Dの配列の概念に悩まされることがあり、それには十分な理由がある。 Dのスライスは、一見したところそう見えるにもかかわらず、実際には(少なくとも表面的には)正しい動的配列型ではない。スライスが提供するのは、あらゆる型(動的型またはそれ以外)の配列に対する安全で簡単なインターフェイスである。それでは、おそらくDスライスに関する最も一般的な誤解について説明しよう。

誰が責任を負うのか?

Dのスライスは、その概念のほぼすべての側面において動的配列のように見える。何も装飾せずに渡された場合、参照されるデータは参照渡しされ、動的配列型がサポートするであろうと期待されるすべてのプロパティと関数をサポートする。しかし、非常に重要な違いが1つある。スライスは配列を所有しておらず、参照しているだけである。つまり、スライスはデータの割り当てや解放の責任を負わない。動的配列のメモリ管理の責任は、Dランタイムが負う。

では、Dにおける真の動的配列型はどこにあるのか?それはランタイムによって隠蔽されており、実際には正式な型は存在しない。スライスは十分に良く、そして結論から言えば、ランタイムはあなたがデータに対して行いたいことについて十分に賢く、動的配列が正式な型として欠けていることにほとんど気づかない。実際、ほとんどのDプログラマーはDスライスをダイナミック配列型だと考えている。仕様書にもダイナミック配列型として記載されているほどだ。所有権の欠如は非常に微妙で、見逃しやすい。

この結果、length は配列のプロパティではなく、スライスのプロパティである。つまり、length フィールドは必ずしも配列の長さではなく、スライスの長さである。これは、この言語に初めて触れる人にとっては混乱のもととなる。例えば、次のコードには大きな欠陥がある。

length field大きな欠陥

import std.stdio;

void shrinkTo2(int[] arr)
{
    if (arr.length > 2)
        arr.length = 2;
}

void main()
{
    int[] arr = new int[5];
    arr.shrinkTo2();     // メソッドとしてshrinkTo2を呼び出せることに注意
    writeln(arr.length); // 5を出力する
}

これは、渡されたarr の長さを2に変更したように見えるかもしれないが、実際には何も影響していない(writeln からの出力で証明されている)。これは、データが参照渡しされたとしても、実際のポインタと長さは値渡しされるためである。多くの言語では、配列型はプロパティがすべて参照渡しされる。特に、C#とJavaの配列は実際には完全に参照オブジェクトである。C++のベクトルは、そのデータとプロパティの両方を参照渡しまたは値渡しする。

この問題を解決するには、次の2つのうちいずれかの方法をとることができる。ref キーワードを使用して明示的にスライスを参照渡しするか、結果として得られたスライスを再代入できるように返す。例えば、スライスを参照渡しする場合のシグネチャは次のようになる。

xml-ph-0000@deepl.internalxml-ph-0000@deepl.internal

void shrinkTo2(ref int[] arr)

例えば、この変更を行った場合、2番目の要素以降のデータはどうなるのだろうか?Dでは、スライスがデータを所有しないため、データはあいまいなダイナミック配列型によって管理されたままとなる。その理由は根本的なものである。他のスライスがそのデータを参照している可能性があるからだ。単一のスライスがデータの真の所有者ではないという事実は、単一のスライスが配列データを参照しているものを想定できないことを意味する。

スライスがそのデータを参照しなくなると何が起こるのか?Dのガベージコレクタの出番である。ガベージコレクタは、もはやどのスライスからも参照されていないダイナミック配列をクリーンアップする役割を担っている。実際、ガベージコレクタがDのスライス使用を可能にしているといっても過言ではない。ダイナミック配列のセグメントをスライスして提供することができ、メモリリークや他のスライスの破壊、あるいは配列の寿命管理について心配する必要がない。

追加可能なスライス

Dのスライスは、真のダイナミック配列型のように、スライスの末尾にデータを追加することをサポートしている。この言語には、連結と追加に使用する特殊な演算子チルダ(~ )がある。以下に、配列の追加と連結を行ういくつかの操作を示す。

xml-ph-0000@deepl.internalxml-ph-0000@deepl.internal

int[] a;     // 空のスライスは何もデータを参照しないが、それでも追加することができる。
a ~= 1;      // 整数を追加すると、自動的に新しい
a ~= 2;      // 要素を保持するための新しい配列が確保される。

a ~= [3, 4]; // 別の配列(今回は配列リテラル)を追加する
a = a ~ a;   // aをそれ自身と連結すると、aは[1, 2, 3, 4, 1, 2, 3, 4]になる

int[5] b;    // スタック上の固定サイズ配列
a = b[1..$]; // aはbのスライスである
a ~= 5;      // aはスタックデータを指していたので、追加すると常に再割り当てされる
             // しかし、うまくいく!

パフォーマンスを気にする人なら、4つの要素を連結したときに何が起こるのか疑問に思うだろう。スライスはデータを所有しないため、連結操作のたびに新しい配列を再割り当てしないようにするにはどうすればよいのだろうか。Dスライスの主な要件の1つは、効率性である。そうでなければ、プログラマーは使用しないだろう。Dは、プログラマーにはほとんど意識させない方法でこの問題を解決しており、これがスライスが真のダイナミック配列のように見える理由の1つである。

動作原理

以前、新しい配列を割り当てるとき、私は 少なくともn個の要素からなる動的配列を割り当てて、スライスを渡すと言ったことを覚えているだろうか? ここでランタイムがその存在価値を発揮する。割り当て機能は、ページのデータ(32ビットx86では、1ページのデータは4096バイト)まで、またはページの倍数まで2の累乗のブロックのみを割り当てる。そのため、配列を割り当てる際には、要求されたサイズよりも大きなブロックを簡単に取得できる。例えば、32ビット整数5個分のブロック(20バイトを消費)を割り当てると、32バイトのブロックが得られる。これには、さらに3つの整数分のスペースが残されている。

再割り当てを行わずに配列にさらに整数を追加することは明らかに可能だが、有効で使用中のデータに「上書き」しないようにすることがコツである。スライスは、他のスライスがそのデータを参照していることを知らないし、そのデータが配列のどこにあるのかも知らない(配列の最初か途中のセグメントである可能性もある)。全体を機能させるために、ランタイムはブロック内部で使用されたバイト数を保存する(ブロック内の使用可能なスペースがそれほど大きくないことがマイナス点である。例えば、この例では、別のブロックに再割り当てする必要が生じる前に、本当に7つの整数しか保存できない)。

実行時にスライスへの追加を要求すると、まず、ブロックが追加可能であること(つまり、使用中のフィールドが有効であること)と、スライスが有効なデータの終了位置と同じ位置で終了していることを確認する(スライスの開始位置は重要ではない)。その後、ランタイムは新しいデータが未使用のブロック領域に収まるかどうかを確認する。これらのチェックがすべて通過した場合、データは配列ブロックに書き込まれ、保存された使用済みフィールドは新しいデータを含めるように更新される。これらのチェックのいずれかが失敗した場合、既存のデータと新しいデータを保持する新しい配列ブロックが割り当てられ、そのブロックにすべてのデータが書き込まれる。古いブロックはどうなるのか? もし他のスライスが参照している場合は、変更されることなくそのまま残る。もし他に参照しているものがなければ、"ガベージ" となり、次のコレクションサイクルで再利用される。これにより、他のスライスを無効にすることなく、1つのスライスを安全に再割り当てすることができる。これは、配列の再割り当てやベクトルへの追加によって、そのデータへの他の参照(ポインタやイテレータ)が無効になる可能性があるC/C++とは大きく異なる。

その結果、効率的なだけでなく、汎用性のある便利な追加操作が可能になる。スライスを追加したい場合はいつでも、パフォーマンスや破損の問題を心配することなく追加できる。スライスのデータがヒープに割り当てられているか、スタックに割り当てられているか、ROMに割り当てられているか、あるいはヌルであるかといったことさえも心配する必要はない。追加操作は常に成功し(十分なメモリがある場合)、実行時にはバックグラウンドで面倒な作業がすべて処理される。

決定論

スライスを連結する際に、経験の浅い、あるいは経験豊富なDコーダーでも陥りやすい注意点が1つある。それは、連結の動作が非決定論的であるように見えることだ。

例えば、バッファを渡された関数が、バッファにいくつかの「A」を書き込み(必要に応じて追加)、書き込み済みのバッファを返す場合を考えてみよう。

import std.stdio;

char[] fillAs(char[] buf, size_t num)
{
    if (buf.length < num)
        buf.length = num; // バッファの長さを増やして、'A'を保持できるようにする
    buf[0..num] = 'A';    // Aをすべての要素に代入する
    return buf[0..num];   // 結果を返却する
}

fillAs 関数に問題があるだろうか? 実際には何も問題はないが、長さを増やすことでバッファの再割り当てが必要になった場合はどうなるだろうか? その場合、渡されたバッファは「A」で上書きされず、再割り当てされたバッファのみが上書きされる。同じバッファをさらに処理で使用する予定であったり、元のバッファが「A」で埋められることを期待していた場合は、これは意外な結果となる可能性がある。最終的な結果は、buf[] によって参照されたブロックが元の場所に追加できるかどうかによって決まり、呼び出し元のスライスが「A」で上書きされる場合とされない場合がある。

// 例を続ける...
void main()
{
    char[] str = new char[10]; // このために割り当てられるブロックの容量は
                               // 15要素である
    str[] = 'B';
    fillAs(str, 20);           // バッファは再割り当てされなければならない(20 > 15)
    writeln(str);              // "BBBBBBBBBB"
    fillAs(str, 12);           // バッファはその場で拡張できる(12 <= 15)!
    writeln(str);              // "AAAAAAAAAA";
}

よく考えてみると、このような状況は、コストのかかるコピーオンアペンドのセマンティクスなしでは避けられないという結論に達するはずだ。システムは、データを参照するすべてのスライスを追跡することはできないし、新しいデータをどこかに置かなければならない。しかし、問題を軽減するために、いくつかのオプションがある。

スライスを関数の戻り値に再割り当てする。この関数の最も重要な結果は戻り値であり、バッファが使用されたかどうかではないことに注意すること。
渡されたバッファを再び使用しない。ソーススライスを再び使用しないのであれば、それに関する問題は発生しない。

関数の作成者として、このような問題を回避するためにできることがいくつかある。この状況が発生するのは、関数が渡されたスライスに追加または長さを増やし、そのスライスの元の部分にデータを書き込む場合のみであることに注意することが重要である。この特定の状況を可能な限り回避することで、非決定論的であるという認識を減らすことができる。後ほど、実行時にスライスにどのような影響があるかを予測するために使用できるプロパティについて説明します。渡されたスライスが上書きされる可能性があるか、あるいはされない可能性があるかを、ドキュメントに注釈として記載しておくことをお勧めします。

最後のオプションは、ref を使用してソーススライスが確実に更新されるようにすることである。スライスは簡単に r値(入力のみ)となるため、これはオプションではない場合もある。しかし、これは同じデータに対する他の場所でのエイリアスに関する問題を解決するものではない。

キャッシュ

スライスへの追加に関する問題のひとつは、操作が迅速であるが、十分迅速ではないことである。追加のたびに、ブロックのメタデータ(開始アドレス、サイズ、使用データ)を取得する必要がある。この処理を行うと、追加のたびにGCのメモリプールでO(lg(n))の検索を行うことになる(グローバルGCロックの取得は言うまでもない)。しかし、私たちが望むのは、平均して一定の追加処理である。この高い目標を達成するために、私が知る限りD独自のキャッシュ技術を採用する。

Dにはデフォルトのスレッドローカルストレージの概念があるため、型システムはヒープデータがスレッドローカルであるか(ほとんどのデータはそうである)、あるいはすべてのスレッドで共有されているかを判断できる。この知識を利用することで、スレッドローカルな追加のためのメタデータのロックフリーのキャッシュを、スレッドごとに1つのキャッシュで実現できる。キャッシュは、メタデータのN の最新の検索結果を保存し、スライスが追加可能かどうかを素早くアクセスできるようにする。

スライスのメンバーとアペンダ

Dスライスには興味深い動作があるため、スライスと追加の動作を予測できることが必要になることがある。そのため、スライスにいくつかのプロパティとメソッドが追加された。

size_t reserve(size_t n): スライスに追加する n 個の要素を確保する。スライスがすでにその場所に追加でき、配列に少なくとも n 個の要素分のスペースがすでに確保されている場合(n は既存のスライス要素と追加可能なスペースの両方を表す)、何も変更されない。結果の容量を返す。

int[] slice;
slice.reserve(50);
foreach (int i; 0..50)
    slice ~= i;        // 再割り当てされない

size_t capacity: スライスをアペンドして保持できる要素数を取得するプロパティ。スライスを適切な位置にアペンドできない場合、このプロパティは0を返す。容量(0以外の場合)には現在のスライス要素が含まれることに注意。

capacitycapacity

int[] slice = new int[5];
assert(slice.capacity == 7);  // 割り当て前の5要素を含む
int[] slice2 = slice;
slice.length = 6;
assert(slice.capacity == 7);  // その場で追加しても容量は変わらない。
assert(slice2.capacity == 0); // スライス2を追加することはできない。
                              // スライスの6番目の要素を踏みつけることになるからだ。

assumeSafeAppend(): このメソッドは、スライスを追加しても安全であるとランタイムに仮定させる。本質的には、これは配列の使用フィールドをスライスの終了位置と同じ場所で終了するように調整する。

int[] slice = new int[5];
slice = slice[0..2];
assert(slice.capacity == 0); // ブロック内に他の有効なデータがあるので、追加するのは安全ではない。
slice.assumeSafeAppend();
assert(slice.capacity == 7); // 使用データを強制的に2要素にする

もしDスライスの追加パフォーマンスが、パフォーマンス要件を満たさない場合、別の選択肢がある。 std.array.Appender型は、実行時からのメタデータの検索を必要とせずに、可能な限り高速にデータを配列に追加する。 std.array.Appenderまた、追加操作による出力範囲構文もサポートしている(通常のスライスでは、自身のデータを上書きすることで出力範囲をサポートしている)。

結論

熟練したプログラマーであれ、初心者であれ、D言語における配列とスライスの概念は、配列型でやりたいことのほとんどを可能にする非常に豊富な機能セットを提供している。パフォーマンスと使いやすさに重点を置いて、D言語のスライス型は、それがない他の言語で作業するまで、その素晴らしさに気づかないものの1つである。

この記事のレビューと提案をしてくださったDavid Gileadi、Andrej Mitrovic、Jesse Phillips、Alex Dovhal、Johann !MacDonagh、Jonathan Davisに感謝する。

この作品は、クリエイティブ・コモンズ・ライセンス(表示-改変禁止 3.0 非移植)の下でライセンスされている。

DEEPL APIにより翻訳、ところどころ修正。
このページの最新版(英語)
このページの原文(英語)
翻訳時のdmdのバージョン: 2.109.1
ドキュメントのdmdのバージョン: 2.109.1
翻訳日付 :2025-01-02 22:24:00+09:00
HTML生成日時: 2025-01-09 08:12:03+09:00
編集者: dokutoku