Un buon esempio di matrice di lunghezza variabile C [chiuso]

Ho appena hackerato un piccolo programma che genera una serie di numeri casuali che ricominciano ogni volta sullo stesso seme, per garantire che sia "equo" e "confrontabile". Mentre procede, rileva il minimo e il massimo di questi valori. E quando ha generato l'insieme di numeri, conta quanti sono al di sopra della media di min e max .

Per gli array MOLTO piccoli, mostra un chiaro vantaggio con VLA oltre std::vector<> .

Non è un problema reale, ma possiamo facilmente immaginare qualcosa in cui dovremmo leggere i valori da un piccolo file invece di usare numeri casuali e fare altri calcoli conteggio / min / max più significativi con lo stesso sorta di codice.

Per valori MOLTO piccoli del "numero di numeri casuali" (x) nelle funzioni pertinenti, la soluzione vla vince con un enorme margine. Man mano che le dimensioni diventano più grandi, la "vittoria" diventa più piccola e, date dimensioni sufficienti, la soluzione vettoriale sembra essere PIÙ efficiente; non ha studiato troppo la variante, poiché quando iniziamo ad avere migliaia di elementi in un VLA, non è davvero quello che dovevano fare ...

E sono sicuro che qualcuno mi dirà che c'è un modo di scrivere tutto questo codice con un sacco di template e farlo funzionare senza eseguire più RDTSC e cout bit in runtime ... Ma io non pensare che sia davvero il punto.

Quando eseguo questa particolare variante, ottengo circa il 10% di differenza tra func1 (VLA) e 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

Questo è compilato con: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Ecco il codice:

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

Riguardo agli VLA rispetto a un vettore

Hai considerato che un vettore può trarre vantaggio dagli stessi VLA. Senza VLA, il vettore deve specificare alcune "scale" di array, ad es. 10, 100, 10000 per l'archiviazione in modo da terminare l'allocazione di un array di 10000 elementi per contenere 101 elementi. Con gli VLA, se si ridimensiona a 200, l'algoritmo potrebbe assumere che occorrerà solo 200 e che sia possibile allocare un array di 200 elementi. Oppure può allocare un buffer di say n * 1.5.

Ad ogni modo, direi che se si conosce il numero di elementi necessari al runtime, un VLA è più performante (come dimostrato dal benchmark di Mats). Ciò che ha dimostrato è stata una semplice iterazione di due passaggi. Pensa alle simulazioni di monte carlo in cui vengono presi ripetutamente campioni casuali o alla manipolazione di immagini (come i filtri di Photoshop) dove i calcoli vengono eseguiti su ciascun elemento più volte e molto probabilmente ogni computazione su ciascun elemento riguarda la visualizzazione dei vicini.

Il puntatore in più salta dal vettore al suo array interno.

Risposta alla domanda principale

Ma quando parli di usare una struttura allocata dinamicamente come una LinkedList, non c'è paragone. Una matrice fornisce l'accesso diretto utilizzando l'aritmetica del puntatore ai suoi elementi. Usando un elenco collegato devi percorrere i nodi per arrivare ad un elemento specifico. Quindi il VLA vince le mani in questo scenario.

Secondo a questa risposta , dipende dal punto di vista dell'architettura, ma in alcuni casi l'accesso alla memoria nello stack sarà più veloce a causa dello stack disponibile sulla cache. Con un gran numero di elementi questo può essere negato (potenzialmente la causa dei rendimenti decrescenti che Mats ha visto nei suoi benchmark). Tuttavia, vale la pena notare che le dimensioni della cache stanno aumentando in modo significativo e potenzialmente vedrai un numero maggiore di quel numero crescere di conseguenza.

La ragione per usare un VLA è principalmente la prestazione. È un errore trascurare l'esempio wiki come se avesse solo una differenza "irrilevante". Riesco facilmente a vedere casi in cui esattamente quel codice potrebbe avere un'enorme differenza, ad esempio, se quella funzione è stata chiamata in un ciclo chiuso, dove read_val era una funzione IO che ritornava molto velocemente su una sorta di sistema in cui la velocità era critica.

In effetti, nella maggior parte dei casi in cui gli VLA vengono utilizzati in questo modo, non sostituiscono le chiamate heap, ma sostituiscono qualcosa come:

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

La cosa su qualsiasi dichiarazione locale è che è estremamente veloce. La riga float vals[n] generalmente richiede solo un paio di istruzioni del processore (forse solo una.) Semplicemente aggiunge il valore in n al puntatore dello stack.

D'altra parte, un'allocazione dell'heap richiede una struttura dati per camminare per trovare un'area libera. Il tempo è probabilmente più lungo di un ordine di grandezza anche nel caso più fortunato. (Ad esempio, l'atto di collocare n nello stack e chiamare malloc è probabilmente 5-10 istruzioni.) Probabilmente molto peggio se c'è una quantità ragionevole di dati nell'heap. Non mi sorprenderebbe affatto vedere un caso in cui malloc era da 100x a 1000x più lento in un programma reale.

Ovviamente, hai anche un impatto sulle prestazioni con il free corrispondente, probabilmente simile in grandezza alla chiamata malloc .

Inoltre, c'è il problema della frammentazione della memoria. Molte piccole allocazioni tendono a frammentare l'heap. Gli heap frammentati sprecano memoria e aumentano il tempo richiesto per allocare memoria.