Esiste un vantaggio in termini di prestazioni nell'utilizzo di elenchi di lunghezza fissa in Dart?

Question

Mi chiedevo se c'è un vantaggio di prestazioni (CPU, memoria) nell'utilizzo di elenchi di lunghezza fissa invece di elenchi di lunghezza dinamica.

Penso che nella maggior parte delle lingue la lista di lunghezza fissa sia solo una serie di puntatori mentre le liste di lunghezza dinamica sono una struttura di dati più complicata come la lista collegata che è ovviamente più lenta.

Answer 1

La risposta breve è: Sì, c'è una differenza. Gli elenchi di lunghezza fissa hanno un overhead inferiore sia in termini di CPU che di memoria rispetto agli elenchi di lunghezza variabile.

Nota: la risposta è puramente dal punto di vista della VM, quindi si applica solo al codice in esecuzione su Dart VM. Quando si esegue l'esecuzione di JS dopo la compilazione con dart2js, si applicano altre regole.

---

Ora un po 'più particolare circa l'attuale implementazione:

Quando si tiene un riferimento a un elenco di lunghezza variabile a Dart, si dispone di un riferimento a un oggetto che mantiene la lunghezza attuale e un riferimento ai dati reali. I dati effettivi sono un elenco di lunghezza fissa con una capacità sufficiente per contenere gli elementi. Di solito questo backing store ha più capacità di quanto sia strettamente necessario per contenere gli elementi di lunghezza richiesti. Ciò ci consente di utilizzare rapidamente gli elementi add.

Se ora accedere agli elementi in questo elenco di lunghezza variabile utilizzando [] o []=, quindi l'attuazione deve prima fare il controllo di lunghezza con l'elenco di lunghezza variabile, allora legge il riferimento alla memoria di supporto fuori e accede alla elemento richiesto dal backing store. Un'implementazione ingenua dovrebbe emettere un altro controllo di lunghezza prima di accedere al backing store, ma ci sono diverse ottimizzazioni eseguite dal compilatore di ottimizzazione della VM: il controllo della lunghezza ridondante viene evitato, si presume che un oggetto array a lunghezza fissa venga utilizzato come archivio di supporto evitando un controllo del tipo e quindi tutta questa sequenza è in linea sul sito di chiamata. Tuttavia, il codice ha due carichi dipendenti prima di arrivare effettivamente ai dati.

Poiché i dati per oggetti a lunghezza fissa sono allineati all'interno dell'oggetto, il carico dipendente può essere evitato. Allo stesso modo il compilatore di ottimizzazione inline i modelli di accesso comuni e tenta di rimuovere i controlli di lunghezza ridondanti.

Per quanto riguarda l'overhead di memoria, l'elenco a lunghezza fissa consuma solo la quantità di memoria necessaria per adattare tutti gli elementi in un singolo oggetto. Al contrario, un elenco di lunghezza variabile ha bisogno di due oggetti e quasi sempre ha una capacità residua nel backing store. Questo può essere un sovraccarico significativo della memoria nell'attuale implementazione. Quando il backing store è in grado di chiamare add, la dimensione del backing store viene raddoppiata e tutti gli elementi correnti vengono copiati nel nuovo backing store prima che sia possibile aggiungere l'elemento extra. Questo probabilmente cambierà in futuro però.

Answer 2

dart2js è in grado di elencare la lunghezza dell'elenco all'interno dei loop, se conosce la lunghezza dell'elenco. Le liste di Const hanno una lunghezza statica nota al momento della compilazione.

Considerate questo codice Dart:

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

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

dart2js possono emettere:

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

Avviso i < 2, la lunghezza della lista è inline!

Answer 3

La VM implementa elenchi crescibili sopra elenchi di lunghezza fissa. Nel migliore dei casi ciò significa che un elenco di risorse utilizza una penalità di ~ 3 puntatori (uno per la descrizione della classe, uno per la lista di lunghezza fissa e uno per la lunghezza).

Tuttavia, per evitare una copia eccessiva durante la crescita, la capacità della lista di crescita è in genere superiore alla lunghezza necessaria. Per quanto ne so, un elenco crescente raddoppia la sua memoria interna quando esaurisce lo spazio. Ciò significa che puoi finire con il doppio della memoria necessaria.

vista delle prestazioni dipende: se si esegue attraverso una lista in un loop stretto il VM può inline il puntatore alla lista annidata e lavorare con quella:

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. 
} 

Ciò è possibile perché il VM può vedi che la lunghezza della lista non può cambiare. Concettualmente questo diventa:

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]; 
} 

Nota che ogni funzione di chiamata fuori dal giro invaliderebbe il presupposto (poiché la funzione potrebbe cambiare la lunghezza della lista growable) e poi il ciclo avrebbe eseguito più lentamente.