Dobry przykład tablicy o zmiennej długości C [zamknięty]

9

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:

  1. Osiągnij łatwą do zmierzenia (może 10%) przewagę wydajności nad używaniem sterty.
  2. Nie ma dobrego obejścia, które w ogóle nie wymagałoby całej tablicy.
  3. W rzeczywistości skorzystaj z dynamicznego rozmiaru zamiast ustalonego maksymalnego rozmiaru.
  4. Jest mało prawdopodobne, aby spowodować przepełnienie stosu w scenariuszu normalnego użytkowania.
  5. 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 njest 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.

hyde
źródło
1
Trochę spekulatywny (ponieważ jest to młotek szukający gwoździa), ale być alloca()może naprawdę przyćmiewałby malloc()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.
chrisaycock
1
@chrisaycock Tak, bardzo młotek szuka gwoździa, ale młotek, który faktycznie istnieje (czy to C99 VLA, czy też nie w jakimkolwiek standardzie alloca, które moim zdaniem są w zasadzie takie same). Ale ta wielowątkowa rzecz jest dobra, edytując pytanie, aby ją uwzględnić!
hyde
Jedną wadą VLA jest brak mechanizmu wykrywania awarii alokacji; jeśli nie ma wystarczającej ilości pamięci, zachowanie jest niezdefiniowane. (To samo odnosi się do tablic o stałym rozmiarze - i do przydziału ().)
Keith Thompson
@KeithThompson Cóż, nie ma gwarancji, że malloc / new wykryje również błąd alokacji, na przykład patrz strona podręcznika Notes for Linux malloc ( linux.die.net/man/3/malloc ).
hyde
@hyde: I jest dyskusyjne, czy malloczachowanie Linuksa jest zgodne ze standardem C.
Keith Thompson

Odpowiedzi:

9

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 mini max.

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 vlarozwią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 coutbitó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) a func2(std :: vector).

count = 9884
func1 time in clocks per iteration 7048685
count = 9884
func2 time in clocks per iteration 7661067
count = 9884
func3 time in clocks per iteration 8971878

Jest to skompilowane z: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Oto kod:

#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>

using namespace std;

const int SIZE = 1000000;

uint64_t g_val[SIZE];


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


int func1(int x)
{
    int v[x];

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}

int func2(int x)
{
    vector<int> v;
    v.resize(x); 

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

int func3(int x)
{
    vector<int> v;

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v.push_back(rand() % x);
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

void runbench(int (*f)(int), const char *name)
{
    srand(41711211);
    uint64_t long t = rdtsc();
    int count = 0;
    for(int i = 20; i < 200; i++)
    {
        count += f(i);
    }
    t = rdtsc() - t;
    cout << "count = " << count << endl;
    cout << name << " time in clocks per iteration " << dec << t << endl;
}

struct function
{
    int (*func)(int);
    const char *name;
};


#define FUNC(f) { f, #f }

function funcs[] = 
{
    FUNC(func1),
    FUNC(func2),
    FUNC(func3),
}; 


int main()
{
    for(size_t i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
    {
        runbench(funcs[i].func, funcs[i].name);
    }
}
Mats Petersson
źródło
Wow, mój system wykazuje 30% poprawę w porównaniu z wersją VLA std::vector.
chrisaycock
1
Spróbuj z zakresem wielkości około 5-15 zamiast 20-200, a prawdopodobnie uzyskasz poprawę o 1000% lub więcej. [Zależy również od opcji kompilatora - Będę edytować powyższy kod, aby wyświetlić moje opcje kompilatora na gcc]
Mats Petersson
Właśnie dodałem, func3który używa v.push_back(rand())zamiast v[i] = rand();i eliminuje potrzebę resize(). To trwa około 10% dłużej w porównaniu do tego, który używa resize(). [Oczywiście, w trakcie tego procesu odkryłem, że użycie v[i]jest głównym czynnikiem wpływającym na czas, jaki zajmuje ta funkcja - jestem trochę zaskoczony].
Mats Petersson
1
@MikeBrown Czy znasz rzeczywistą std::vectorimplementację, która użyłaby VLA / alloca, czy to tylko spekulacje?
hyde
3
Wektor rzeczywiście używa tablicy wewnętrznie, ale o ile rozumiem, nie ma sposobu na użycie VLA. Wierzę, że mój przykład pokazuje, że VLA są przydatne w niektórych (być może nawet wielu) przypadkach, w których ilość danych jest niewielka. Nawet jeśli wektor korzysta z VLA, byłoby to po dodatkowym wysiłku wewnątrz vectorimplementacji.
Mats Petersson
0

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.

Michael Brown
źródło
Nie jestem pewien, czy rozumiem twoje odniesienie do list połączonych, więc dodałem sekcję do pytania, wyjaśniając nieco kontekst i dodając przykłady alternatyw, o których myślę.
hyde
Dlaczego std::vectorpotrzebna 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 a realloc()(sama tablica zmienia rozmiar), i tak zabroniłoby VLA.
chrisaycock
@chrisaycock C ++ z jakiegoś powodu nie ma funkcji realloc (), zakładając, że pamięć jest przydzielana z nowym []. Czy to nie główny powód, dla którego std :: vector musi używać skal?
@Lundin Czy C ++ skaluje wektor o potęgi dziesięciu? Odniosłem wrażenie, że pytanie Mike'a Browna było naprawdę zdezorientowane, biorąc pod uwagę odnośnik do listy linków. (Poczynił również wcześniejsze stwierdzenie, które sugerowało, że C99 VLA żyją na stosie).
chrisaycock
@hyde Nie zdawałem sobie sprawy, że o tym mówisz. Myślałem, że masz na myśli inne struktury danych oparte na stercie. Interesujące teraz, gdy dodałeś to wyjaśnienie. Nie jestem wystarczająco maniakiem C ++, aby powiedzieć ci różnicę między nimi.
Michael Brown
0

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_valbył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:

float vals[256]; /* I hope we never get more! */

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ść ndo 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 nna stosie i sprawdzanie mallocto prawdopodobnie 5-10 instrukcji.) Prawdopodobnie znacznie gorzej, jeśli na stosie znajduje się jakaś rozsądna ilość danych. Nie zaskoczyłoby mnie wcale, gdyby przypadek mallocbył 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 do mallocpołą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.

Gort the Robot
źródło
O przykładzie z Wikipedii: może być częścią dobrego przykładu, ale bez kontekstu, więcej kodu wokół niego, tak naprawdę nie pokazuje żadnej z 5 rzeczy wymienionych w moim pytaniu. W przeciwnym razie tak, zgadzam się z twoim wyjaśnieniem. Chociaż należy pamiętać: korzystanie z VLA może kosztować dostęp do zmiennych lokalnych, przy czym przesunięcia wszystkich zmiennych lokalnych niekoniecznie są znane w czasie kompilacji, dlatego należy zachować ostrożność, aby nie zastąpić jednorazowego kosztu sterty kara w wewnętrznej pętli za każdą iterację.
hyde
Um ... nie jestem pewien, co masz na myśli. Deklaracje zmiennych lokalnych są pojedynczą operacją, a każdy umiarkowanie zoptymalizowany kompilator wyciągnie alokację z wewnętrznej pętli. Dostęp do zmiennych lokalnych nie wiąże się z żadnym „kosztem”, z pewnością nie takim, który zwiększy VLA.
Gort the Robot
Konkretny przykład: int vla[n]; if(test()) { struct LargeStruct s; int i; }przesunięcie stosu snie będzie znane w czasie kompilacji, a wątpliwe jest również, czy kompilator przeniesie pamięć ipoza 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;)
hyde
Kompilator nie musi przydzielać w kolejności napotkanej w kodzie i nie ma znaczenia, czy miejsce jest przydzielane i nie jest używane. Inteligentny optymalizator przydzieliłby przestrzeń dla si ikiedy funkcja zostanie wprowadzona, zanim testzostanie wywołana lub vlazostanie przydzielona, ​​jako alokacje dla si inie mają skutków ubocznych. (I w rzeczywistości imoż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.
Gort the Robot
(usunął komentarz, który był błędny z powodu głupiej pomyłki)
hyde