ToList と ToArray のどちらを使うべきか
訂正
コメントで指摘を受けてさらに検証したところ、自作クラスのリスト化のみ桁違いに遅くなるということはありませんでした。
ただ、この記事に記載したコードは、私の環境では何度やっても自作クラスのリスト化のみ遅くなります。ガベージコレクションか何かの影響でたまたま常にそのような結果が出るコードが出来上がったものと思われます。
検証の仕方が不十分でした。
また、ToArray と ToList のソースも間違ったところを見ており、実際にはほぼ同じアルゴリズムが使われていました。
はじめに
LINQ は遅延評価されるので、同じ要素を何度も使うと、同じ計算が何度もされることがあります。その場合には IEnumerable<T> をリストや配列に変換して再計算されないようにする必要が出てきます。
変換した後、さらに要素の追加や削除があるなら ToList を使い、リストにすべきでしょう。そうでないなら、ToArray を使って配列でも良いかもしれません。しかしリストは配列の上位互換とも言えるので、配列を使わず全てリストで行っても不自由することはありません。
しかしこれは、パフォーマンスについて一切考えないならばという条件がつきます。
パフォーマンスが重要な場合には、リストでなく配列を使うのが良いと思います。その根拠として、次のコードによる計測結果を提示します。
コードと計測結果
using System;
using System.Diagnostics;
using System.Linq;
namespace ConsoleApp1
{
class Class1 { }
struct Struct1 { }
class Program
{
static void Main(string[] args)
{
var list = Enumerable
.Range(0, 3000000)
.Select(a => a.ToString())
.ToList();
MeasureTime("1 string to List", () =>
{
list.ToList();
});
MeasureTime("2 string to Array", () =>
{
list.ToArray();
});
var list2 = list
.Select(a => new Class1())
.ToList();
MeasureTime("3 original class to List", () =>
{
list2.ToList();
});
MeasureTime("4 original class to Array", () =>
{
list2.ToArray();
});
var list3 = list
.Select(a => new Struct1())
.ToList();
MeasureTime("5 original struct to List", () =>
{
list3.ToList();
});
MeasureTime("6 original struct to Array", () =>
{
list3.ToArray();
});
Console.ReadKey();
}
static void MeasureTime(string title, Action action)
{
var sw = new Stopwatch();
sw.Start();
action();
sw.Stop();
Console.WriteLine($"{title}: {sw.Elapsed.TotalMilliseconds}");
}
}
}
結果は次の通りです。
1 string to List: 14.7559
2 string to Array: 14.3611
3 original class to List: 154.6604
4 original class to Array: 14.0594
5 original struct to List: 2.8031
6 original struct to Array: 2.8535
1 string to List
List<string> を ToList して別のリストに変換しています。
2 string to Array
List<string> を ToArray して配列に変換しています。
3 original class to List
List<Class1> を ToList して別のリストに変換しています。
4 original class to Array
List<Class1> を ToArray して配列に変換しています。
5 original struct to List
List<Struct1> を ToList して別のリストに変換しています。
6 original struct to Array
List<Struct1> を ToArray して配列に変換しています。
それぞれの数値はミリ秒です。つまり、300 万行の List<string> を ToList した場合、14.7559 ミリ秒の時間がかかっています。
1, 2, 4 については違いはありません。この程度の数字の違いは誤差で、次に実行した時には順位も入れ替わります。5, 6 はそれら 3 つに比べてかなり速いようです。
original class to List については、一つだけ桁違いに遅くなっています。
なぜ構造体は速いのか
5, 6 のパフォーマンスが良い理由ですが、クラスと構造体の使い分け にはこうあります。
構造体を選択する大きなポイントとして、配列として使用するかがあげられます。通常は、要素数の多い配列では構造体のメリットが非常に大きく、構造体の使用を考慮する価値が十分にあります。
参照型の配列の場合、要素のインスタンスはメモリにバラバラに置かれます。一方値型の配列は、要素のインスタンスが一塊で（インラインで）メモリに置かれます。そのため、構造体の配列の方が要素の読み込みと書き込みの効率がよく、さらにガベージコレクションの負担が少ないです。
また、配列のすべての要素を初期化する時も、構造体の方が楽です。クラスの場合は、ループを回すなどしてすべての要素にNew演算子で作成したインスタンスを代入する必要があります。一方構造体は、New演算子でインスタンス化する必要がなく、配列を作成するだけで済みます。
今回作ったのは極めて小さな構造体なので、最高のパフォーマンスが出せたのでしょう。int, double などの数値型も構造体の一種なので、同じく良いパフォーマンスが出せると思います。
なぜ独自クラスをリスト化した時だけ桁違いに遅くなるのか
結論から言えば、わかりませんが、推測してみます。
ToArray と ToList のソース を見ると、ToArray は LargeArrayBuilder という謎のクラスを使って配列を構築しています。ToList は普通に List<T> を作って Add しています。
LargeArrayBuilder の中身が公開されていないので詳細は不明ですが、おそらく何度もコピーが発生しないような工夫がなされているのでしょう。
対して ToList ですが、これは内容の保存に配列を用いています。Capacity プロパティで示される大きさの配列を用意し、Add などによってそれ以上のデータが追加された場合には Capacity を大きくしてそれに従った配列を新しく用意し、既存のデータをそこにコピーする仕組みになっています。
従って、あらかじめ追加するデータの量が分かっている場合には Capacity プロパティを最初から広げておいた方がデータのコピーが少なくなってパフォーマンスが上がりますが、ここではデータがどのくらいあるか終わってみなければわからないので、内部配列は繰り返し破棄され、データのコピーが行われることになります。
この配列のコピーには Array.Copy が使われていますが、その実体は別の言語で書かれた外部関数です。なのでこれも詳細は不明です。
ただし、データのコピーに使われる Buffer.BlockCopy(Array, Int32, Array, Int32, Int32) Method には、プリミティブ型しか対象にしないという制限があるところを見ると、Array.Copy でもプリミティブ型とその他の型でコピーのアルゴリズムが違うことは十分考えられそうです。
Class1 はヒープにある参照型ですが、ガベージコレクションによって参照の指すメモリ位置は変動します。なので、単純にポインタをコピーするというわけにはいかないでしょう。どこからも参照されなくなった時、ガベージコレクタによって破棄されるためには、どこかで参照されているということをどこかで知っていなければなりません。
そのため、ToList する際には内部配列の拡張とともに何度も行われるコピーのパフォーマンスが違ってきているのではないかと推測します。
string 型も Class1 と同じくヒープにある参照型ですが、これを特別扱いする仕組みが何かあるのではないかと思います。
結論
どちらでもいい場合には ToArray を使おう
執筆日: 2019/03/13
Discussion