Jaka jest idealna stopa wzrostu dynamicznie alokowanej tablicy?

C ++ ma std :: vector, a Java ma ArrayList, a wiele innych języków ma własną formę dynamicznie przydzielanej tablicy. Gdy w tablicy dynamicznej zabraknie miejsca, zostaje ona ponownie przydzielona do większego obszaru, a stare wartości są kopiowane do nowej tablicy. Kluczową kwestią dla wydajności takiej macierzy jest to, jak szybko tablica rośnie. Jeśli zawsze będziesz wystarczająco duży, aby dopasować się do bieżącego pchnięcia, za każdym razem będziesz ponownie przydzielać. Dlatego warto podwoić rozmiar tablicy lub pomnożyć go przez powiedzmy 1,5x.

Czy istnieje idealny czynnik wzrostu? 2x? 1,5x? Przez ideał rozumiem matematycznie uzasadnione, najlepsze równoważenie wydajności i zmarnowaną pamięć. Zdaję sobie sprawę, że teoretycznie, biorąc pod uwagę, że twoja aplikacja może mieć jakąkolwiek potencjalną dystrybucję wypychania, jest to w pewnym stopniu zależne od aplikacji. Ale jestem ciekawy, czy istnieje wartość, która jest „zwykle” najlepsza, czy też jest uważana za najlepszą w ramach jakichś rygorystycznych ograniczeń.

Słyszałem, że jest gdzieś artykuł na ten temat, ale nie mogłem go znaleźć.

Będzie to całkowicie zależało od przypadku użycia. Czy bardziej zależy Ci na marnowaniu czasu na kopiowanie danych (i ponowne przydzielanie tablic) lub na dodatkowej pamięci? Jak długo będzie działać tablica? Jeśli nie będzie istnieć długo, użycie większego bufora może być dobrym pomysłem - kara jest krótkotrwała. Jeśli ma się kręcić (np. W Javie, przechodząc do starszych i starszych pokoleń), jest to oczywiście bardziej kara.

Nie ma czegoś takiego jak „idealny czynnik wzrostu”. To nie tylko teoretycznie zależy od aplikacji, ale zdecydowanie zależy od aplikacji.

2 jest dość powszechny czynnik wzrostu - Jestem prawie pewien, że to, co ArrayListi List<T>zastosowań w .NET. ArrayList<T>w Javie używa 1.5.

EDYCJA: Jak zauważa Erich, Dictionary<,>w .NET używa się opcji „podwoić rozmiar, a następnie zwiększyć do następnej liczby pierwszej”, aby wartości skrótu można było rozsądnie rozłożyć między zasobnikami. (Jestem pewien, że ostatnio widziałem dokumentację sugerującą, że liczby pierwsze nie są tak dobre do dystrybucji pojemników z mieszaniem, ale to argument za inną odpowiedzią).

Pamiętam, jak czytałem wiele lat temu, dlaczego 1,5 jest preferowane zamiast dwóch, przynajmniej w przypadku C ++ (prawdopodobnie nie dotyczy to języków zarządzanych, w których system wykonawczy może dowolnie przemieszczać obiekty).

Powód jest taki:

1. Załóżmy, że zaczynasz od alokacji 16-bajtowej.
2. Kiedy potrzebujesz więcej, przydzielasz 32 bajty, a następnie zwalniasz 16 bajtów. To pozostawia 16-bajtową dziurę w pamięci.
3. Kiedy potrzebujesz więcej, przydzielasz 64 bajty, zwalniając 32 bajty. Pozostawia to 48-bajtowy otwór (jeśli 16 i 32 byłyby sąsiadujące).
4. Kiedy potrzebujesz więcej, przydzielasz 128 bajtów, zwalniając 64 bajty. Pozostawia to 112-bajtowy otwór (zakładając, że wszystkie poprzednie alokacje sąsiadują ze sobą).
5. I tak i tak dalej.

Chodzi o to, że przy dwukrotnym rozszerzeniu nie ma momentu, w którym wynikająca z tego dziura kiedykolwiek będzie wystarczająco duża, aby ponownie wykorzystać ją do następnej alokacji. Używając alokacji 1,5x, mamy zamiast tego:

1. Zacznij od 16 bajtów.
2. Kiedy potrzebujesz więcej, przydziel 24 bajty, a następnie zwolnij 16, pozostawiając 16-bajtowy otwór.
3. Kiedy potrzebujesz więcej, przydziel 36 bajtów, a następnie zwolnij 24, pozostawiając 40-bajtowy otwór.
4. Kiedy potrzebujesz więcej, przydziel 54 bajty, a następnie zwolnij 36, pozostawiając 76-bajtowy otwór.
5. Kiedy potrzebujesz więcej, przydziel 81 bajtów, a następnie zwolnij 54, pozostawiając 130-bajtowy otwór.
6. Gdy potrzebujesz więcej, użyj 122 bajtów (zaokrąglając w górę) ze 130-bajtowego otworu.

Idealnie (w granicy n → ∞) jest to złoty podział : ϕ = 1,618 ...

W praktyce chcesz czegoś bliskiego, na przykład 1,5.

Powodem jest to, że chcesz mieć możliwość ponownego wykorzystania starszych bloków pamięci, skorzystania z buforowania i uniknięcia ciągłego zmuszania systemu operacyjnego do zwiększania ilości stron pamięci. Równanie, które rozwiązałbyś, aby upewnić się, że sprowadza się to do x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ , którego rozwiązanie zbliża się do x = ϕ dla dużego n .

Jednym ze sposobów odpowiadania na takie pytania jest po prostu „oszukiwanie” i przyjrzenie się temu, co robią popularne biblioteki, przy założeniu, że powszechnie używana biblioteka przynajmniej nie robi czegoś okropnego.

Po prostu sprawdzając bardzo szybko, Ruby (1.9.1-p129) wydaje się używać 1,5x podczas dołączania do tablicy, a Python (2.6.2) używa 1,125x plus stała (in Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsizepowyżej jest liczbą elementów w tablicy. Zauważ, że newsizejest to dodawane do new_allocated, więc wyrażenie z przesunięciem bitowym i operatorem trójskładnikowym tak naprawdę oblicza nadmierną alokację.

Powiedzmy, że zwiększasz rozmiar tablicy o x. Więc załóżmy, że zaczynasz od rozmiaru T. Następnym razem, gdy powiększysz tablicę, jej rozmiar będzie T*x. Wtedy będzie T*x^2i tak dalej.

Jeśli Twoim celem jest ponowne wykorzystanie pamięci, która została utworzona wcześniej, chcesz się upewnić, że nowa przydzielona pamięć jest mniejsza niż suma poprzedniej zwolnionej pamięci. Dlatego mamy tę nierówność:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Możemy usunąć T z obu stron. Więc otrzymujemy to:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Nieformalnie mówimy, że przy nthalokacji chcemy, aby cała wcześniej zwolniona pamięć była większa lub równa zapotrzebowaniu na pamięć przy n-tej alokacji, abyśmy mogli ponownie wykorzystać wcześniej zwolnioną pamięć.

Na przykład, jeśli chcemy móc to zrobić na trzecim etapie (tj. n=3), To mamy

x^3 <= 1 + x 

To równanie jest prawdziwe dla wszystkich x takich, że 0 < x <= 1.3(w przybliżeniu)

Zobacz, jakie x otrzymujemy dla różnych n poniżej:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Zauważ, że współczynnik wzrostu musi być mniejszy niż 2od tego czasu x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

To naprawdę zależy. Niektórzy ludzie analizują typowe przypadki użycia, aby znaleźć optymalną liczbę.

Widziałem 1,5 x 2,0 x phi i moc 2 używaną wcześniej.

Jeśli masz rozkład według długości tablic i masz funkcję narzędziową, która mówi, jak bardzo lubisz marnować miejsce w porównaniu do marnowania czasu, zdecydowanie możesz wybrać optymalną strategię zmiany rozmiaru (i początkowej).

Powodem, dla którego używana jest prosta stała wielokrotność, jest oczywiście to, że każdy dodatek ma zamortyzowany stały czas. Ale to nie znaczy, że nie możesz użyć innego (większego) współczynnika dla małych rozmiarów.

W Scali można zastąpić loadFactor dla tabel skrótów biblioteki standardowej funkcją, która sprawdza bieżący rozmiar. Co dziwne, tablice o zmiennym rozmiarze po prostu się podwajają, co większość ludzi robi w praktyce.

Nie znam żadnych podwójnych (lub 1,5 *) tablic, które faktycznie wyłapują błędy pamięci i rosną mniej w takim przypadku. Wygląda na to, że gdybyś miał ogromną pojedynczą tablicę, chciałbyś to zrobić.

Dodałbym ponadto, że jeśli utrzymujesz tablice o zmiennym rozmiarze wystarczająco długo i preferujesz przestrzeń w czasie, sensowne może być początkowe radykalne nadmierne przydzielenie (w większości przypadków), a następnie ponowne przydzielenie do dokładnie odpowiedniego rozmiaru, gdy jesteś Gotowe.

Kolejne dwa centy

• Większość komputerów ma pamięć wirtualną! W pamięci fizycznej możesz mieć wszędzie losowe strony, które są wyświetlane jako pojedyncze ciągłe miejsce w pamięci wirtualnej programu. Rozwiązanie pośrednictwa jest wykonywane przez sprzęt. Wyczerpanie pamięci wirtualnej było problemem w systemach 32-bitowych, ale tak naprawdę nie stanowi już problemu. Więc wypełnienie dziury nie jest już problemem (z wyjątkiem specjalnych środowisk). Od Windows 7 nawet Microsoft obsługuje 64 bit bez dodatkowego wysiłku. @ 2011
• O (1) osiąga się przy dowolnym współczynniku r > 1. Ten sam dowód matematyczny działa nie tylko dla 2 jako parametru.
• r = 1,5 można obliczyć za pomocą, old*3/2więc nie ma potrzeby wykonywania operacji zmiennoprzecinkowych. (Mówię, /2ponieważ kompilatory zastąpią to przesunięciem bitowym w wygenerowanym kodzie asemblera, jeśli uznają to za stosowne).
• MSVC wybrał r = 1,5, więc istnieje co najmniej jeden główny kompilator, który nie używa 2 jako współczynnika.

Jak wspomniała osoba, 2 czuje się lepiej niż 8. A także 2 czuje się lepiej niż 1,1.

Mam wrażenie, że 1.5 to dobra wartość domyślna. Poza tym zależy to od konkretnego przypadku.

Zgadzam się z Jonem Skeetem, nawet mój przyjaciel teoretyka twierdzi, że przy ustawieniu współczynnika na 2x można udowodnić, że jest to O (1).

Stosunek czasu procesora do pamięci jest inny na każdej maszynie, więc współczynnik będzie się różnić tak samo. Jeśli masz maszynę z gigabajtami pamięci RAM i wolnym procesorem, kopiowanie elementów do nowej macierzy jest znacznie droższe niż na szybkiej maszynie, która z kolei może mieć mniej pamięci. To pytanie, na które można odpowiedzieć w teorii, jak na jednolity komputer, który w rzeczywistych sytuacjach wcale ci nie pomaga.

Wiem, że to stare pytanie, ale jest kilka rzeczy, których każdemu wydaje się brakować.

Po pierwsze, to jest mnożenie przez 2: rozmiar << 1. To jest mnożenie przez cokolwiek z przedziału od 1 do 2: int (float (rozmiar) * x), gdzie x to liczba, * to matematyka zmiennoprzecinkowa, a procesor aby uruchomić dodatkowe instrukcje rzutowania między float i int. Innymi słowy, na poziomie maszyny podwojenie wymaga jednej, bardzo szybkiej instrukcji, aby znaleźć nowy rozmiar. Mnożenie przez coś między 1 a 2 wymaga co najmniejjedna instrukcja rzutowania rozmiaru na zmiennoprzecinkową, jedna instrukcja mnożenia (czyli mnożenie przez liczbę zmiennoprzecinkową, więc prawdopodobnie zajmuje co najmniej dwa razy więcej cykli, jeśli nie 4, a nawet 8 razy więcej) i jedna instrukcja rzutowania z powrotem na int, a to zakłada, że ​​Twoja platforma może wykonywać obliczenia zmiennoprzecinkowe na rejestrach ogólnego przeznaczenia, zamiast wymagać użycia specjalnych rejestrów. Krótko mówiąc, należy oczekiwać, że obliczenia matematyczne dla każdego przydziału będą trwały co najmniej 10 razy dłużej niż zwykłe przesunięcie w lewo. Jeśli jednak kopiujesz dużo danych podczas ponownego przydziału, może to nie mieć większego znaczenia.

Po drugie, i prawdopodobnie wielki kicker: każdy wydaje się zakładać, że uwalniana pamięć jest zarówno ciągła ze sobą, jak i sąsiadująca z nowo przydzieloną pamięcią. O ile sam nie przydzielasz wstępnie całej pamięci, a następnie nie używasz jej jako puli, prawie na pewno tak nie jest. System operacyjny może czasamiw końcu tak się stanie, ale przez większość czasu będzie wystarczająco dużo wolnego miejsca, aby każdy w połowie przyzwoity system zarządzania pamięcią był w stanie znaleźć małą dziurę, w której zmieści się twoja pamięć. Gdy dojdziesz do naprawdę ugryzionych kawałków, bardziej prawdopodobne jest, że skończysz z ciągłymi fragmentami, ale do tego czasu twoje przydziały są na tyle duże, że nie robisz ich wystarczająco często, aby miało to już znaczenie. Krótko mówiąc, fajnie jest sobie wyobrazić, że użycie jakiejś idealnej liczby pozwoli na najbardziej efektywne wykorzystanie wolnego miejsca w pamięci, ale w rzeczywistości tak się nie stanie, chyba że twój program będzie działał na czystym metalu (ponieważ nie ma systemu operacyjnego pod nim podejmowanie wszystkich decyzji).

Moja odpowiedź na pytanie? Nie, nie ma idealnej liczby. Jest tak specyficzny dla aplikacji, że nikt nawet nie próbuje. Jeśli Twoim celem jest idealne wykorzystanie pamięci, nie masz szczęścia. Dla wydajności lepsze są alokacje rzadziej, ale gdybyśmy poszli tylko z tym, moglibyśmy pomnożyć przez 4 lub nawet 8! Oczywiście, gdy Firefox przeskakuje z 1 GB do 8 GB za jednym razem, ludzie będą narzekać, więc to nawet nie ma sensu. Oto kilka praktycznych zasad, którymi bym się kierował:

Jeśli nie możesz zoptymalizować użycia pamięci, przynajmniej nie marnuj cykli procesora. Mnożenie przez 2 jest co najmniej o rząd wielkości szybsze niż wykonywanie obliczeń zmiennoprzecinkowych. Może nie będzie to wielka różnica, ale przynajmniej trochę zmieni (szczególnie na początku, podczas częstszych i mniejszych przydziałów).

Nie myśl za dużo. Jeśli właśnie spędziłeś 4 godziny, próbując dowiedzieć się, jak zrobić coś, co już zostało zrobione, po prostu zmarnowałeś swój czas. Szczerze mówiąc, gdyby istniała lepsza opcja niż * 2, zostałaby wykonana w klasie wektorowej C ++ (i wielu innych miejscach) dziesiątki lat temu.

Wreszcie, jeśli naprawdę chcesz zoptymalizować, nie przejmuj się drobiazgami. W dzisiejszych czasach nikt nie przejmuje się marnowaniem 4KB pamięci, chyba że pracuje na systemach wbudowanych. Gdy dojdziesz do 1 GB obiektów, które mają od 1 MB do 10 MB każdy, podwojenie jest prawdopodobnie zbyt duże (mam na myśli od 100 do 1000 obiektów). Jeśli potrafisz oszacować oczekiwany współczynnik ekspansji, możesz wyrównać go do liniowego tempa wzrostu w pewnym momencie. Jeśli spodziewasz się około 10 obiektów na minutę, to wzrost o 5 do 10 rozmiarów obiektów na krok (raz na 30 sekund do minuty) jest prawdopodobnie w porządku.

Wszystko sprowadza się do tego, że nie przemyślaj tego, zoptymalizuj, co możesz, i dostosuj do swojej aplikacji (i platformy), jeśli musisz.