Jaka jest idealna stopa wzrostu dynamicznie alokowanej tablicy?

84

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źć.

Joseph Garvin
źródło

Odpowiedzi:

44

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ą).

Jon Skeet
źródło
104

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.
Chris Jester-Young
źródło
5
Przypadkowy post na forum, który znalazłem ( objectmix.com/c/ ... ) ma podobne przyczyny. Plakat twierdzi, że (1 + sqrt (5)) / 2 to górna granica ponownego wykorzystania.
Naaff
19
Jeśli to twierdzenie jest poprawne, to phi (== (1 + sqrt (5)) / 2) jest rzeczywiście optymalną liczbą do użycia.
Chris Jester-Young
1
Podoba mi się ta odpowiedź, ponieważ ujawnia uzasadnienie 1,5x w porównaniu z 2x, ale Jona jest technicznie najbardziej poprawna w stosunku do tego, jak to określiłem. Powinienem był zapytać, dlaczego w przeszłości zalecano 1,5: p
Joseph Garvin,
6
Facebook używa 1.5 w swojej implementacji FBVector, artykuł tutaj wyjaśnia, dlaczego 1.5 jest optymalne dla FBVector.
csharpfolk
2
@jackmott Racja, dokładnie tak, jak zauważyłem w mojej odpowiedzi: „prawdopodobnie nie dotyczy to języków zarządzanych, w których system wykonawczy może dowolnie przemieszczać obiekty”.
Chris Jester-Young
48

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 n , którego rozwiązanie zbliża się do x = ϕ dla dużego n .

user541686
źródło
15

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

Jason Creighton
źródło
Tak więc tablica rośnie od n do n + (n / 8 + (n <9? 3: 6)), co oznacza, że ​​w terminologii pytania współczynnik wzrostu wynosi 1,25x (plus stała).
ShreevatsaR
Czy nie byłoby to 1,125x plus stała?
Jason Creighton
10

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.

CEGRD
źródło
Wydaje się, że twierdzisz, że możesz już ponownie wykorzystać wcześniej zwolnioną pamięć przy drugiej alokacji ze współczynnikiem 1,5. To nieprawda (patrz wyżej). Daj mi znać, jeśli cię źle zrozumiałem.
awx
W drugiej alokacji przydzielasz 1,5 * 1,5 * T = 2,25 * T, podczas gdy całkowite cofnięcie alokacji do tego momentu wynosi T + 1,5 * T = 2,5 * T. Czyli 2,5 jest większe niż 2,25.
CEGRD
Ach, powinienem czytać uważniej; powiesz tylko, że całkowita zwolniona pamięć będzie większa niż ilość przydzielonej pamięci przy n-tym przydziale, nie oznacza to, że możesz jej ponownie użyć przy n-tym przydziale.
awx
4

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.

Nieznany
źródło
Phi! To miła liczba do użycia. Powinienem zacząć go używać od teraz. Dzięki! +1
Chris Jester-Young
Nie rozumiem ... dlaczego phi? Jakie ma właściwości, które sprawiają, że jest do tego odpowiedni?
Jason Creighton
4
@Jason: phi tworzy ciąg Fibonacciego, więc następny rozmiar alokacji jest sumą bieżącego rozmiaru i poprzedniego rozmiaru. Pozwala to na umiarkowane tempo wzrostu, szybsze niż 1,5, ale nie 2 (zobacz mój post, dlaczego> = 2 nie jest dobrym pomysłem, przynajmniej dla języków niezarządzanych).
Chris Jester-Young
1
@Jason: Ponadto, według komentatora mojego posta, każda liczba> phi jest w rzeczywistości złym pomysłem. Sam nie wykonałem obliczeń, aby to potwierdzić, więc weź to z przymrużeniem oka.
Chris Jester-Young
2

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.

Jonathan Graehl
źródło
2

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.

Spoza listy
źródło
3
Byłoby lepiej użyć n + n/2do opóźnienia przepełnienia. Użycie n*3/2zmniejsza o połowę możliwą pojemność.
owacoder
@owacoder True. Ale kiedy n * 3 nie pasuje, ale n * 1,5 pasuje, mówimy o dużej ilości pamięci. Jeśli n jest 32-bitowym unsigend, wówczas n * 3 przepełnia się, gdy n wynosi 4G / 3, czyli ok. 1,333G. To ogromna liczba. To dużo pamięci w jednej alokacji. Jeszcze więcej, jeśli elementy nie mają 1 bajtu, ale na przykład 4 bajty każdy. Zastanawiam się nad przypadkiem użycia ...
Notinlist
3
To prawda, że ​​może to być przypadek skrajny, ale przypadki skrajne są tym, co zwykle gryzie. Przyzwyczajenie się do szukania możliwego przepełnienia lub innych zachowań, które mogą wskazywać na lepszy projekt, nigdy nie jest złym pomysłem, nawet jeśli może się to wydawać naciągane w teraźniejszości. Jako przykład weź adresy 32-bitowe. Teraz potrzebujemy 64 ...
owacoder
0

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.

Tomek
źródło
2
Aby rozwinąć, podwojenie rozmiaru tablicy oznacza, że ​​otrzymujesz amotowane wstawki O (1). Chodzi o to, że za każdym razem, gdy wstawiasz element, kopiujesz również element ze starej tablicy. Powiedzmy, że masz tablicę o rozmiarze m , zawierającą m elementów. Podczas dodawania elementu m + 1 nie ma miejsca, więc przydzielasz nową tablicę o rozmiarze 2m . Zamiast kopiować wszystkie pierwsze m elementów, kopiujesz jeden za każdym razem, gdy wstawiasz nowy element. To zminimalizuje wariancję (z wyjątkiem alokacji pamięci), a po wstawieniu 2m elementów skopiujesz wszystkie elementy ze starej tablicy.
hvidgaard
-1

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.

Rybec Arethdar
źródło
11
Oczywiście n + n >> 1jest taki sam jak 1.5 * n. Dość łatwo jest wymyślić podobne sztuczki dla każdego praktycznego czynnika wzrostu, jaki przyjdzie Ci do głowy.
Björn Lindqvist
To dobra uwaga. Należy jednak pamiętać, że poza ARM to przynajmniej podwaja liczbę instrukcji. (Wiele instrukcji ARM, w tym instrukcja add, może wykonać opcjonalną zmianę jednego z argumentów, umożliwiając przykładowi działanie w jednej instrukcji. Jednak większość architektur nie może tego zrobić.) Nie, w większości przypadków podwojenie liczby instrukcji od jednego do dwóch nie jest istotnym problemem, ale w przypadku bardziej złożonych czynników wzrostu, w których matematyka jest bardziej złożona, może to mieć wpływ na wydajność wrażliwego programu.
Rybec Arethdar
@Rybec - Chociaż mogą istnieć programy wrażliwe na zmiany czasu o jedną lub dwie instrukcje, jest bardzo mało prawdopodobne, aby jakikolwiek program korzystający z dynamicznych realokacji kiedykolwiek się tym przejmował. Jeśli potrzebuje precyzyjnie kontrolować taktowanie, prawdopodobnie zamiast tego użyje pamięci przydzielonej statycznie.
owacoder
Robię gry, w których jedna lub dwie instrukcje mogą mieć znaczący wpływ na wydajność w niewłaściwym miejscu. To powiedziawszy, jeśli alokacja pamięci jest obsługiwana dobrze, nie powinno się to zdarzać wystarczająco często, aby kilka instrukcji miało znaczenie.
Rybec Arethdar