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

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.

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);
    }
}

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.

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.