Dartで固定長のリストを使用するとパフォーマンス上の利点はありますか？

Question

動的長さのリストの代わりに固定長リストを使用すると、パフォーマンス（CPU、メモリ）のメリットがあるのだろうかと思いました。

固定長のリストはポインタの配列にすぎませんが、動的長さのリストはリンクリストのようなもっと複雑なデータ構造ですが、明らかに遅いと思います。

Answer 1

短い答えは：はい、違いがあります。固定長リストは、可変長リストよりもCPUとメモリの両方でオーバーヘッドが低くなります。

メモ：これは純粋にVMの観点から回答しているため、これはDart VMで動作するコードにのみ適用されます。 dart2jsでコンパイルした後にJS実行を使用して実行する場合、他のルールが適用されます。

---

今現在の実装について、もう少し詳しく：

あなたがダートでの可変長リストへの参照を保持するとき、あなたは現在の長さとの参照を保持するオブジェクトへの参照を持っています実際のデータに変換します。実際のデータは、要素を保持するのに十分な容量を持つ固定長リストです。通常、このバッキングストアには、必要な長さの要素を保持するために厳密に必要な容量よりも多くの容量があります。これにより、ほとんどの場合、素早くadd要素を使用することができます。

[]または[]=を使用してこの可変長リストの要素にアクセスする場合、実装では最初に可変長リストに対して長さチェックを行い、次にバッキングストアへの参照を読み取り、バッキングストアから要求された要素。純粋な実装では、バッキングストアにアクセスする前に別の長さチェックを発行する必要がありますが、VMの最適化コンパイラが実行するいくつかの最適化があります。冗長長チェックを避け、固定長配列オブジェクトをバッキングストアタイプチェックを避け、この全シーケンスがコールサイトでインライン展開されます。それでも、コードには実際にデータを取得する前に2つの依存するロードがあります。

固定長オブジェクトのデータがオブジェクト内にインライン展開されるため、依存負荷を回避できます。同様に、最適化コンパイラは共通アクセスパターンをインライン化し、冗長長チェックを削除しようとします。

メモリオーバーヘッドに関する限り、固定長リストは、すべての要素を1つのオブジェクトに収めるために必要なだけのメモリを消費します。逆に、可変長リストには2つのオブジェクトが必要で、ほとんどの場合、バッキングストアに残っている容量がほとんどあります。これは、現在の実装ではメモリオーバーヘッドが大きくなる可能性があります。バッキングストアがaddが呼び出されたときの容量になると、バッキングストアのサイズが2倍になり、余分な要素を追加する前に、現在のすべての要素が新しいバッキングストアにコピーされます。しかしこれは将来変化する可能性が高いです。

Answer 2

dart2jsは、リストの長さを知っていれば、ループ内でリストの長さをインライン化できます。 Constリストは、コンパイル時に知られている静的な長さを持ちます。

final List fruits = const ['apples', 'oranges']; 

main() { 
    for (var i = 0; i < fruits.length; i++) { 
    print(fruits[i]); 
    } 
} 

dart2jsを発することができる：

はこのダーツコードを考えてみましょう

$.main = function() { 
    for (var i = 0; i < 2; ++i) 
    $.Primitives_printString($.toString$0($.List_apples_oranges[i])); 
}; 

お知らせi < 2、リストの長さがインライン化されます！

Answer 3

VMは、固定長リストの上に拡張可能リストを実装します。最良の場合、これは、拡張可能なリストが〜3ポインターのペナルティを受けることを意味します（クラス記述の場合は1つ、固定長リストの場合は1つ、長さの場合は1つ）。

しかし、成長するときに余りに多くのコピーを避けるために、成長可能リストの容量は通常、必要な長さよりも長くなります。私が知る限り、拡大可能なリストは、スペースがなくなったときに内部ストレージを倍増させます。これは、必要なメモリの2倍になることを意味します。

パフォーマンスワイズそれが依存：あなたはVMは、ネストされたリストへのポインタをインライン化し、そのいずれかで動作することができますタイトなループでリストを実行する場合：

var list = foo(); 
var sum = 0; 
for (int i = 0; i < list.length; i++) { 
    sum += list[i]; // The internal pointer can be hoisted outside the loop. 
} 

これが可能であるVMができるので、リストの長さが変更できないことを確認してください。概念的には、これは次のようになります。

var list = foo(); 
var sum = 0; 
_check_that_list_is_growable_list_ // Because we have seen this type before. 
int _list_length_ = list.length; 
List _fixed_list_ = list._internal_fixed_list; 
for (int i = 0; i < _list_length_; i++) { 
    sum += _fixed_list_[i]; 
} 

（関数は可変長リストの長さを変更する可能性があるため）ループのうち任意の関数呼び出しは仮定を無効になる注意して、ループが遅くなるでしょう。