Czy korzystanie z list o stałej długości w Dart jest korzystne?

Question

Zastanawiam się, czy korzystanie z list o stałej długości zamiast z list o dynamicznej długości ma zalety związane z wydajnością (procesor, pamięć).

Myślę, że w większości języków lista o stałej długości jest po prostu tablicą wskaźników, podczas gdy listy o długości dynamicznej mają nieco bardziej skomplikowaną strukturę danych, taką jak lista linków, która jest oczywiście wolniejsza.

Answer 1

Krótka odpowiedź brzmi: Tak, jest różnica. Listy o stałej długości mają mniejszy narzut zarówno w procesorze, jak i pamięci niż na listach o zmiennej długości.

Uwaga: Odpowiadam na to wyłącznie z perspektywy VM, dotyczy to tylko kodu działającego na maszynie wirtualnej Dart. Podczas uruchamiania przy użyciu wykonywania JS po kompilacji z dart2js obowiązują inne reguły.

---

Teraz trochę więcej szczegółów na temat bieżącej realizacji:

Kiedy trzymasz odniesienie do listy o zmiennej długości w Dart, masz odniesienie do obiektu, który utrzymuje aktualną długość i odniesienie do rzeczywistych danych. Rzeczywiste dane to lista o stałej długości z wystarczającą pojemnością do przechowywania elementów. Zwykle ten magazyn podkładowy ma większą pojemność niż jest to bezwzględnie potrzebne do przechowywania wymaganych elementów długości. To pozwala nam szybko uzyskać add elementów przez większość czasu.

Jeśli teraz uzyskujesz dostęp do elementów na tej liście o zmiennej długości przy użyciu [] lub []=, to implementacja musi najpierw wykonać test długości na liście o zmiennej długości, a następnie odczytać odwołanie do magazynu zaplecza i uzyskać dostęp do żądany element ze sklepu podkładowego. Naiwna implementacja będzie musiała wysłać kolejną kontrolę długości przed uzyskaniem dostępu do magazynu kopii zapasowych, ale istnieje kilka optymalizacji, które wykonuje kompilator optymalizujący maszyny wirtualnej: Nie ma potrzeby sprawdzania redundantnej długości, zakłada się, że obiekt tablicy o stałej długości jest używany jako magazyn zaplecza unikając kontroli typu, a następnie cała ta sekwencja jest umieszczona na stronie wywołania. Mimo to kod ma dwa obciążenia zależne, zanim dostaniesz dane.

Ponieważ dane dla obiektów o stałej długości są zaznaczone wewnątrz obiektu, można uniknąć obciążenia zależnego. Podobnie optymalizujący kompilator ustawia typowe wzorce dostępu i próbuje usunąć nadmiarowe sprawdzenia długości.

Jeśli chodzi o narzut pamięci, lista o stałej długości zajmuje tylko tyle pamięci, ile potrzeba, aby zmieścić wszystkie elementy w jednym obiekcie. Wręcz przeciwnie, lista o zmiennej długości potrzebuje dwóch obiektów i prawie zawsze pozostawia pewną pojemność w magazynie zaplecza. Może to być znaczne obciążenie pamięci w bieżącej implementacji. Gdy magazyn zaplecza ma pojemność, gdy wywoływana jest nazwa add, rozmiar magazynu kopii zapasowej jest podwojony, a wszystkie bieżące elementy są kopiowane do nowego magazynu kopii zapasowej, zanim można dodać dodatkowy element. Prawdopodobnie zmieni się to jednak w przyszłości.

Answer 2

dart2js może wstawiać długość listy wewnątrz pętli, jeśli zna długość listy. Listy Const mają długość statyczną znaną podczas kompilacji.

Rozważmy ten kod Dart:

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

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

dart2js mogą emitować:

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

Wskazówka i < 2, długość lista jest inlined!

Answer 3

Maszyna wirtualna implementuje dostępne do pobrania listy na listach o stałej długości. W najlepszym wypadku oznacza to, że lista dopuszczalnych obciążeń podlega karze w wysokości ~ 3 wskaźniki (jeden dla opisu klasy, jeden dla listy o stałej długości, a drugi dla długości).

Jednak, aby uniknąć nadmiernego kopiowania podczas wzrostu, pojemność listy dopuszczalnej jest zwykle większa niż wymagana długość. O ile mi wiadomo, lista growa może podwajać jego pamięć wewnętrzną, gdy zabraknie jej miejsca. Oznacza to, że możesz skończyć z podwójną potrzebną pamięcią.

Performance-mądry to zależy: po uruchomieniu przez liście w ciasnym pętli VM może inline wskaźnik do listy zagnieżdżonych i pracować z tym jednym:

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

Jest to możliwe, ponieważ VM może zobacz, że długość listy nie może się zmienić. Koncepcyjnie to staje się:

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

pamiętać, że wszelkie wywołania funkcji z pętli byłoby unieważnienie założenie (ponieważ funkcja może zmienić długość tego growable lista) i następnie pętla będzie działać wolniej.