Jaka jest wydajność obiektów / tablic w JavaScript? (specjalnie dla Google V8)

Wydajność związana z tablicami i obiektami w JavaScript (zwłaszcza Google V8) byłaby bardzo interesująca do udokumentowania. Nigdzie w Internecie nie znalazłem wyczerpującego artykułu na ten temat.

Rozumiem, że niektóre obiekty używają klas jako podstawowej struktury danych. Jeśli właściwości jest dużo, czasami jest to traktowane jako tablica mieszająca?

Rozumiem również, że tablice są czasami traktowane jak tablice C ++ (tj. Szybkie losowe indeksowanie, powolne usuwanie i zmiana rozmiaru). Innym razem są traktowane bardziej jak Obiekty (szybkie indeksowanie, szybkie wstawianie / usuwanie, więcej pamięci). A może czasami są przechowywane jako połączone listy (tj. Powolne losowe indeksowanie, szybkie usuwanie / wstawianie na początku / końcu)

Jaka jest dokładna wydajność pobierania i manipulowania tablicami / obiektami w JavaScript? (specjalnie dla Google V8)

A dokładniej, jaki jest wpływ na wydajność:

• Dodawanie właściwości do obiektu
• Usuwanie właściwości z obiektu
• Indeksowanie właściwości w obiekcie
• Dodawanie elementu do tablicy
• Usuwanie elementu z tablicy
• Indeksowanie elementu w tablicy
• Wywołanie Array.pop ()
• Wywołanie Array.push ()
• Wywołanie Array.shift ()
• Wywołanie Array.unshift ()
• Wywołanie Array.slice ()

Wszelkie artykuły lub linki zawierające więcej szczegółów również będą mile widziane. :)

EDYCJA: Naprawdę zastanawiam się, jak tablice i obiekty JavaScript działają pod maską. Ponadto w jakim kontekście silnik V8 „wie” o „przełączeniu” na inną strukturę danych?

Na przykład załóżmy, że tworzę tablicę z ...

var arr = [];
arr[10000000] = 20;
arr.push(21);

Co tu się naprawdę dzieje?

Albo ... co z tym ... ???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

W przypadku konwencjonalnych tablic wydajność byłaby straszna; podczas gdy jeśli użyto LinkedList ... nie jest tak źle.

Stworzyłem zestaw testów, właśnie po to, aby zbadać te problemy (i nie tylko) ( kopia archiwalna ).

W tym sensie możesz zobaczyć problemy z wydajnością w tym 50+ testerze przypadków testowych (zajmie to dużo czasu).

Jak sama nazwa wskazuje, bada użycie natywnego charakteru listy połączonej struktury DOM.

(Obecnie niedostępny, odbudowywany w toku) Więcej szczegółów na temat tego na moim blogu .

Podsumowanie jest następujące

• V8 Array jest szybki, BARDZO SZYBKI
• Array push / pop / shift jest ~ około 20x + szybsze niż jakikolwiek odpowiednik obiektu.
• Zaskakująco Array.shift()jest szybki ~ ok. 6x wolniejszy niż wyskakująca tablica, ale ok. 100x szybszy niż usunięcie atrybutu obiektu.
• Co zabawne, Array.push( data );jest szybszy niż Array[nextIndex] = dataprawie 20 (tablica dynamiczna) do 10 (tablica stała) razy.
• Array.unshift(data) jest wolniejszy zgodnie z oczekiwaniami i ~ około 5x wolniejszy niż dodawanie nowej właściwości.
• Zerowanie wartości array[index] = nulljest szybsze niż usunięcie jej delete array[index](niezdefiniowanej) w tablicy o ~ około 4x ++ szybciej.
• Zaskakujące jest, że zerowanie wartości w obiekcie jest obj[attr] = null~ około 2x wolniejsze niż zwykłe usunięcie atrybutudelete obj[attr]
• Nic dziwnego, że środkowa tablica Array.splice(index,0,data)jest wolna, bardzo wolna.
• Co zaskakujące, Array.splice(index,1,data)został zoptymalizowany (bez zmiany długości) i jest 100x szybszy niż zwykłe splatanieArray.splice(index,0,data)
• nic dziwnego, że divLinkedList jest gorsza od tablicy we wszystkich sektorach, z wyjątkiem dll.splice(index,1)usuwania (gdzie zepsuł system testowy).
• NAJWIĘKSZA NIESPODZIANKA z tego wszystkiego [jak wskazał jjrv], zapisy w tablicy V8 są nieco szybsze niż odczyty V8 = O

Uwaga: te metryki dotyczą tylko dużych tablic / obiektów, które w wersji 8 nie są „całkowicie optymalizowane”. Mogą istnieć bardzo izolowane, zoptymalizowane przypadki wydajności dla rozmiaru tablicy / obiektu mniejszego niż dowolny rozmiar (24?). Więcej szczegółów można znaleźć w kilku filmach Google IO.

Uwaga 2: Te wspaniałe wyniki nie są udostępniane między przeglądarkami, zwłaszcza *cough*IE. Również test jest ogromny, dlatego nie udało mi się jeszcze w pełni przeanalizować i ocenić wyników: edytuj go w =)

Zaktualizowana uwaga (grudzień 2012 r.): Przedstawiciele Google mają na YouTube filmy opisujące wewnętrzne działanie samego Chrome (np. Gdy przełącza się on z tablicy linkedlist na stałą tablicę itp.) Oraz jak je zoptymalizować. Więcej informacji znajdziesz w GDC 2012: From Console to Chrome .

Na podstawowym poziomie, który pozostaje w zakresie języka JavaScript, właściwości obiektów są znacznie bardziej złożonymi jednostkami. Możesz tworzyć właściwości za pomocą metod ustawiających / pobierających, z różnymi możliwościami wyliczania, zapisywalności i konfigurowalności. Elementu w tablicy nie można dostosować w ten sposób: albo istnieje, albo nie. Na podstawowym poziomie silnika pozwala to na znacznie większą optymalizację pod względem organizacji pamięci reprezentującej strukturę.

Jeśli chodzi o identyfikację tablicy z obiektu (słownika), silniki JS zawsze tworzyły wyraźne linie między nimi. Dlatego istnieje wiele artykułów na temat metod tworzenia półfałszywego obiektu podobnego do tablicy, który zachowuje się jak jeden, ale umożliwia inne funkcje. Powodem, dla którego ta separacja w ogóle istnieje, jest to, że same silniki JS przechowują je w różny sposób.

Właściwości mogą być przechowywane w obiekcie tablicy, ale to po prostu pokazuje, jak JavaScript nalega na uczynienie wszystkiego obiektem. Indeksowane wartości w tablicy są przechowywane inaczej niż wszelkie właściwości, które zdecydujesz się ustawić w obiekcie tablicy, który reprezentuje podstawowe dane tablicy.

Ilekroć używasz prawidłowego obiektu tablicy i używasz jednej ze standardowych metod manipulowania tą tablicą, będziesz uderzać w podstawowe dane tablicy. W szczególności w wersji 8 są one zasadniczo takie same jak tablice C ++, więc te zasady będą miały zastosowanie. Jeśli z jakiegoś powodu pracujesz z tablicą, której silnik nie jest w stanie określić z pewnością, jest tablicą, to jesteś na znacznie bardziej chwiejnym gruncie. Jednak w ostatnich wersjach V8 jest więcej miejsca do pracy. Na przykład można utworzyć klasę, której prototypem jest Array.prototype, i nadal uzyskać efektywny dostęp do różnych natywnych metod manipulacji tablicami. Ale to ostatnia zmiana.

Przydać się mogą tutaj konkretne linki do ostatnich zmian w manipulowaniu tablicami:

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

Jako trochę więcej, oto Array Pop i Array Push bezpośrednio ze źródła V8, oba zaimplementowane w samym JS:

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

Chciałbym uzupełnić istniejące odpowiedzi dochodzeniem na pytanie, jak zachowują się implementacje w odniesieniu do rosnących tablic: Jeśli zaimplementują je w "zwykły" sposób, można zobaczyć wiele szybkich wypchnięć z rzadkimi, przeplatanymi powolnymi wypychaniami, w którym to momencie implementacja kopiuje wewnętrzna reprezentacja tablicy z jednego bufora do większego.

Bardzo ładnie widać ten efekt, to z Chrome:

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

Mimo że każde wypchnięcie jest profilowane, dane wyjściowe zawierają tylko te, które wymagają czasu powyżej określonego progu. Dla każdego testu dostosowałem próg, aby wykluczyć wszystkie pchnięcia, które wydają się reprezentować szybkie pchnięcia.

Czyli pierwsza liczba reprezentuje, który element został wstawiony (pierwsza linia dotyczy 17. elementu), druga to ile czasu to zajęło (dla wielu tablic benchmark jest wykonywany równolegle), a ostatnia wartość to dzielenie elementu pierwsza liczba równa tej z poprzedniego wiersza.

Wszystkie wiersze, których czas wykonania jest krótszy niż 2 ms, są wykluczone z przeglądarki Chrome.

Możesz zobaczyć, że Chrome zwiększa rozmiar tablicy w potęgach 1,5 plus pewne przesunięcie, aby uwzględnić małe tablice.

W przypadku Firefoksa to potęga dwóch:

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

Musiałem trochę podnieść próg w Firefoksie, dlatego zaczynamy od # 126.

W IE otrzymujemy mieszankę:

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

Na początku jest to potęga dwóch, a potem przesuwa się do potęgi pięciu trzecich.

Tak więc wszystkie popularne implementacje używają „normalnego” sposobu dla tablic (zamiast na przykład szaleć z linami ).

Oto kod porównawczy, a oto skrzypce , w których się znajduje.

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

Podczas pracy pod node.js 0.10 (zbudowany na v8) zauważyłem użycie procesora, które wydawało się nadmierne dla obciążenia. Wyśledziłem jeden problem z wydajnością do funkcji, która sprawdzała istnienie ciągu w tablicy. Więc przeprowadziłem kilka testów.

• załadowano 90 822 hostów
• ładowanie konfiguracji zajęło 0.087 sekund (tablica)
• ładowanie konfiguracji zajęło 0.152 sekundy (obiekt)

Ładowanie 91 tys. Wpisów do tablicy (z walidacją i wypychaniem) jest szybsze niż ustawienie obj [klucz] = wartość.

W następnym teście sprawdziłem raz każdą nazwę hosta na liście (91k iteracji, aby uśrednić czas wyszukiwania):

• przeszukiwanie konfiguracji zajęło 87,56 sekund (tablica)
• przeszukiwanie konfiguracji zajęło 0,21 sekundy (obiekt)

Ta aplikacja to Haraka (serwer SMTP) i ładuje host_list raz podczas uruchamiania (i po zmianach), a następnie wykonuje to wyszukiwanie miliony razy podczas pracy. Przejście na obiekt było ogromną wygraną w wydajności.