To pytanie zyskało mroźny odbiór w SO, więc postanowiłem je tam usunąć i spróbować tutaj. Jeśli uważasz, że tutaj też nie pasuje, zostaw przynajmniej komentarz dotyczący sugestii, jak znaleźć przykład, którego szukam ...
Czy możesz podać przykład , w którym użycie C99 VLA oferuje rzeczywistą przewagę nad czymś takim, jak obecne standardowe mechanizmy C ++ RAII wykorzystujące stertę?
Przykład, który szukam powinien:
- Osiągnij łatwą do zmierzenia (może 10%) przewagę wydajności nad używaniem sterty.
- Nie ma dobrego obejścia, które w ogóle nie wymagałoby całej tablicy.
- W rzeczywistości skorzystaj z dynamicznego rozmiaru zamiast ustalonego maksymalnego rozmiaru.
- Jest mało prawdopodobne, aby spowodować przepełnienie stosu w scenariuszu normalnego użytkowania.
- Bądź wystarczająco silny, aby kusić programistę potrzebującego wydajności do włączenia pliku źródłowego C99 do projektu C ++.
Dodając pewne wyjaśnienie kontekstu: mam na myśli VLA w rozumieniu C99 i nieujęte w standardowym C ++: int array[n]
gdzie n
jest zmienną. I jestem za przykładem przypadku użycia, w którym przebija alternatywy oferowane przez inne standardy (C90, C ++ 11):
int array[MAXSIZE]; // C stack array with compile time constant size
int *array = calloc(n, sizeof int); // C heap array with manual free
int *array = new int[n]; // C++ heap array with manual delete
std::unique_ptr<int[]> array(new int[n]); // C++ heap array with RAII
std::vector<int> array(n); // STL container with preallocated size
Jakieś pomysły:
- Funkcje przyjmujące varargs, które w naturalny sposób ograniczają liczbę przedmiotów do czegoś rozsądnego, ale nie mają żadnego użytecznego górnego limitu na poziomie API.
- Funkcje rekurencyjne, w których zmarnowany stos jest niepożądany
- Wiele małych przydziałów i wydań, w których narzut byłby zły.
- Obsługa tablic wielowymiarowych (takich jak matryce o dowolnym rozmiarze), w których wydajność ma kluczowe znaczenie i oczekuje się, że drobne funkcje będą często wprowadzane.
- Z komentarza: algorytm współbieżny, w którym przydział sterty ma narzut synchronizacji .
Wikipedia ma przykład, który nie spełnia moich kryteriów , ponieważ praktyczna różnica w stosowaniu sterty wydaje się nieistotna, przynajmniej bez kontekstu. Nie jest także idealny, ponieważ bez większego kontekstu wydaje się, że liczba przedmiotów może równie dobrze spowodować przepełnienie stosu.
Uwaga: konkretnie szukam przykładowego kodu lub sugestii algorytmu, który by z tego skorzystał, abym sam zaimplementował ten przykład.
alloca()
może naprawdę przyćmiewałbymalloc()
w środowisku wielowątkowym z powodu rywalizacji o blokadę w tym drugim . Ale to jest prawdziwy odcinek, ponieważ małe tablice powinny po prostu mieć ustalony rozmiar, a duże tablice i tak prawdopodobnie będą potrzebowały sterty.alloca
, które moim zdaniem są w zasadzie takie same). Ale ta wielowątkowa rzecz jest dobra, edytując pytanie, aby ją uwzględnić!malloc
zachowanie Linuksa jest zgodne ze standardem C.Odpowiedzi:
Właśnie zhakowałem mały program, który generuje zestaw liczb losowych restartujących się za każdym razem o tym samym ziarnie, aby upewnić się, że jest „sprawiedliwy” i „porównywalny”. W miarę upływu czasu oblicza min i maks tych wartości. A kiedy wygeneruje zestaw liczb, zlicza, ile jest powyżej średniej
min
imax
.W przypadku BARDZO małych tablic pokazuje wyraźną przewagę nad VLA
std::vector<>
.Nie jest to prawdziwy problem, ale możemy łatwo wyobrazić sobie coś, w którym czytalibyśmy wartości z małego pliku zamiast liczb losowych i robili inne, bardziej znaczące obliczenia zliczania / min / maks przy użyciu tego samego rodzaju kodu .
Dla BARDZO małych wartości „liczby liczb losowych” (x) w odpowiednich funkcjach
vla
rozwiązanie wygrywa z ogromnym marginesem. Gdy rozmiar się powiększa, „wygrana” maleje, a biorąc pod uwagę wystarczający rozmiar, rozwiązanie wektorowe wydaje się WIĘCEJ wydajne - nie studiowałem zbytnio tego wariantu, ponieważ kiedy zaczynamy mieć tysiące elementów w VLA, nie jest to naprawdę, co mieli zrobić ...I jestem pewien, że ktoś powie mi, że jest jakiś sposób na napisanie całego tego kodu za pomocą wielu szablonów i sprawi, że zrobi to bez uruchamiania więcej niż RDTSC i
cout
bitów w czasie wykonywania ... Ale nie sądzę, że to naprawdę punkt.Korzystając z tego konkretnego wariantu, dostaję około 10% różnicy między
func1
(VLA) afunc2
(std :: vector).Jest to skompilowane z:
g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp
Oto kod:
źródło
std::vector
.func3
który używav.push_back(rand())
zamiastv[i] = rand();
i eliminuje potrzebęresize()
. To trwa około 10% dłużej w porównaniu do tego, który używaresize()
. [Oczywiście, w trakcie tego procesu odkryłem, że użyciev[i]
jest głównym czynnikiem wpływającym na czas, jaki zajmuje ta funkcja - jestem trochę zaskoczony].std::vector
implementację, która użyłaby VLA /alloca
, czy to tylko spekulacje?vector
implementacji.Odnośnie VLA kontra Vector
Czy bierzesz pod uwagę, że Vector może korzystać z samych VLA. Bez VLA Vector musi określić pewne „skale” tablic, np. 10, 100, 10000 do przechowywania, więc ostatecznie przydzielisz tablicę 10000 elementów, aby pomieścić 101 elementów. W przypadku VLA, jeśli zmienisz rozmiar na 200, algorytm może założyć, że będziesz potrzebował tylko 200 i może przydzielić tablicę 200 elementów. Lub może przydzielić bufor, powiedzmy n * 1.5.
W każdym razie argumentowałbym, że jeśli wiesz, ile elementów będziesz potrzebować w czasie wykonywania, VLA jest bardziej wydajna (jak wykazał test Matsa). To, co pokazał, było prostą iteracją dwuprzebiegową. Pomyśl o symulacjach Monte Carlo, w których wielokrotnie pobierane są losowe próbki, lub manipulacji obrazem (takich jak filtry Photoshopa), w których obliczenia są wykonywane na każdym elemencie wiele razy i całkiem możliwe, że każde obliczenie na każdym elemencie wymaga patrzenia na sąsiadów.
Ten dodatkowy wskaźnik przeskakujący z wektora do wewnętrznej tablicy sumuje się.
Odpowiedź na główne pytanie
Ale kiedy mówimy o używaniu dynamicznie alokowanej struktury, takiej jak LinkedList, nie ma porównania. Tablica zapewnia bezpośredni dostęp za pomocą arytmetyki wskaźnika do jej elementów. Za pomocą połączonej listy musisz przejść węzły, aby dostać się do określonego elementu. Więc VLA wygrywa w tym scenariuszu.Zgodnie z tą odpowiedzią jest on zależny od architektury, ale w niektórych przypadkach dostęp do pamięci na stosie będzie szybszy, ponieważ stos będzie dostępny w pamięci podręcznej. Przy dużej liczbie elementów można to zanegować (potencjalnie przyczyną malejących zwrotów, które Mats widział w swoich testach porównawczych). Warto jednak zauważyć, że rozmiary pamięci podręcznej znacznie rosną i potencjalnie zobaczysz, że liczba ta odpowiednio wzrośnie.
źródło
std::vector
potrzebna jest skala tablic? Dlaczego potrzebowałoby miejsca na elementy 10K, gdy potrzebuje tylko 101? Ponadto pytanie nigdy nie wspomina o połączonych listach, więc nie jestem pewien, skąd je masz. Wreszcie, VLA w C99 są przydzielane stosowo; są standardową formąalloca()
. Wszystko, co wymaga miejsca na sterty (żyje po powrocie funkcji) lub arealloc()
(sama tablica zmienia rozmiar), i tak zabroniłoby VLA.Powodem korzystania z VLA jest przede wszystkim wydajność. Błędem jest ignorowanie przykładu wiki, który ma jedynie „nieistotną” różnicę. Z łatwością widzę przypadki, w których dokładnie ten kod może mieć ogromną różnicę, na przykład, jeśli ta funkcja została wywołana w ciasnej pętli, gdzie
read_val
była funkcja IO, która bardzo szybko zwróciła się w jakimś systemie, w którym szybkość była krytyczna.W rzeczywistości w większości miejsc, w których VLA są używane w ten sposób, nie zastępują one wywołań sterty, ale zamiast tego zastępują coś takiego:
Rzeczą w każdej lokalnej deklaracji jest to, że jest ona niezwykle szybka. Linia
float vals[n]
generalnie wymaga tylko kilku instrukcji procesora (może tylko jednej). Po prostu dodaje wartośćn
do wskaźnika stosu.Z drugiej strony przydział sterty wymaga przejścia struktury danych w celu znalezienia wolnego obszaru. Czas jest prawdopodobnie o rząd wielkości dłuższy nawet w najszczęśliwszym przypadku. (Tj. Samo umieszczanie
n
na stosie i sprawdzaniemalloc
to prawdopodobnie 5-10 instrukcji.) Prawdopodobnie znacznie gorzej, jeśli na stosie znajduje się jakaś rozsądna ilość danych. Nie zaskoczyłoby mnie wcale, gdyby przypadekmalloc
był 100x do 1000x wolniejszy w prawdziwym programie.Oczywiście wtedy masz również wpływ na wydajność dzięki dopasowaniu
free
, prawdopodobnie podobnej wielkości domalloc
połączenia.Ponadto istnieje problem fragmentacji pamięci. Wiele małych przydziałów ma tendencję do rozdrabniania stosu. Rozdrobnione sterty zarówno marnują pamięć, jak i zwiększają czas potrzebny do przydzielenia pamięci.
źródło
int vla[n]; if(test()) { struct LargeStruct s; int i; }
przesunięcie stosus
nie będzie znane w czasie kompilacji, a wątpliwe jest również, czy kompilator przeniesie pamięći
poza zasięgiem wewnętrznym na stałe przesunięcie stosu. Potrzebny jest więc dodatkowy kod maszynowy, ponieważ pośrednie, i może to również pochłonąć rejestry, ważne na sprzęcie komputerowym. Jeśli chcesz dołączyć przykładowy kod z danymi wyjściowymi zestawu kompilatora, zadaj osobne pytanie;)s
ii
kiedy funkcja zostanie wprowadzona, zanimtest
zostanie wywołana lubvla
zostanie przydzielona, jako alokacje dlas
ii
nie mają skutków ubocznych. (I w rzeczywistościi
może nawet zostać umieszczony w rejestrze, co oznacza, że w ogóle nie ma „alokacji”). Nie ma gwarancji kompilatora na kolejność alokacji na stosie, ani nawet, że stos jest używany.