C ++ valarray vs. vettore

Question

Mi piacciono molto i vettori. Sono eleganti e veloci. Ma so che esiste una cosa chiamata valarray. Perché dovrei usare un valarray invece di un vettore? So che i valarrays hanno dello zucchero sintattico, ma a parte questo, quando sono utili?

Answer 1

Valarrays (array di valori) hanno lo scopo di portare parte della velocità di Fortran a C ++. Non faresti una valarray di puntatori in modo che il compilatore possa fare ipotesi sul codice e ottimizzarlo meglio. (Il motivo principale per cui Fortran è così veloce è che non esiste un tipo di puntatore, quindi non può esserci alcun alias puntatore.)

Valarrays ha anche delle classi che ti permettono di suddividerle in un modo ragionevolmente semplice sebbene quella parte dello standard potrebbe usare un po 'più di lavoro. Il ridimensionamento è distruttivo e mancano di iteratori.

Quindi, se si tratta di numeri con cui si sta lavorando e la convenienza non è poi così importante usare valarrays. Altrimenti, i vettori sono solo molto più convenienti.

Answer 2

valarray è una specie di orfano che è nato nel posto sbagliato al momento sbagliato. È un tentativo di ottimizzazione, in particolare per le macchine utilizzate per la matematica pesante quando è stato scritto, in particolare i processori vettoriali come Crays.

Per un processore vettoriale, ciò che generalmente volevi fare era applicare una singola operazione a un intero array, quindi applicare l'operazione successiva all'intero array e così via fino a quando non avessi fatto tutto ciò che dovevi fare.

A meno che non si tratti di array abbastanza piccoli, tuttavia, ciò tende a funzionare male con la memorizzazione nella cache. Sulla maggior parte delle macchine moderne, ciò che generalmente preferiresti (nella misura del possibile) sarebbe caricare parte dell'array, eseguire tutte le operazioni su di esso che stai andando, quindi passare alla parte successiva dell'array.

valarray dovrebbe anche eliminare ogni possibilità di aliasing, che (almeno teoricamente) consente al compilatore di migliorare la velocità perché è più libero di archiviare i valori nei registri. In realtà, tuttavia, non sono affatto sicuro che qualsiasi reale implementazione ne tragga vantaggio in misura significativa. Ho il sospetto che sia piuttosto una specie di problema con l'uovo e la gallina - senza il supporto del compilatore non è diventato popolare, e finché non è popolare, nessuno si prenderà la briga di lavorare sul proprio compilatore per supportarlo.

C'è anche una sconcertante (letteralmente) matrice di classi accessorie da usare con valarray. Ottieni slice , slice_array , gslice e gslice_array per giocare con pezzi di valarray e farlo agire come un array multidimensionale. Ottieni anche mask_array su " mask " un'operazione (ad esempio aggiungere elementi da x a y, ma solo nelle posizioni in cui z è diverso da zero). Per fare un uso più che banale di valarray , devi imparare molto su queste classi accessorie, alcune delle quali sono piuttosto complesse e nessuna delle quali sembra (almeno per me) molto ben documentata.

Linea di fondo: mentre ha momenti di brillantezza e può fare alcune cose abbastanza bene, ci sono anche delle ottime ragioni per cui è (e quasi sicuramente rimarrà) oscuro.

Modifica (otto anni dopo, nel 2017): alcuni dei precedenti sono diventati almeno obsoleti. Ad esempio, Intel ha implementato una versione ottimizzata di valarray per il proprio compilatore. Utilizza Intel Integrated Performance Primitives (Intel IPP) per migliorare le prestazioni. Sebbene l'esatto miglioramento delle prestazioni vari senza dubbio, un test rapido con un codice semplice mostra un miglioramento della velocità di 2: 1 rispetto a un codice identico compilato con lo "standard" implementazione di valarray .

Quindi, anche se non sono del tutto convinto che i programmatori C ++ inizieranno a usare valarray in grandi numeri, ci sono almeno alcune circostanze in cui può fornire un miglioramento della velocità.

Answer 3

Durante la standardizzazione di C ++ 98, valarray è stato progettato per consentire una sorta di rapidi calcoli matematici. Tuttavia, in quel periodo Todd Veldhuizen inventò modelli di espressioni e creò blitz ++ e furono inventate tecniche simili per meta-template , che ha reso Valarrays praticamente obsoleto prima ancora che lo standard fosse rilasciato. IIRC, il / i proponente / i originale / i di Valarray lo ha abbandonato a metà strada verso la standardizzazione, che (se vera) non ha aiutato neanche.

ISTR afferma che il motivo principale per cui non è stato rimosso dallo standard è che nessuno si è preso il tempo di valutare attentamente il problema e scrivere una proposta per rimuoverlo.

Tieni presente, tuttavia, che tutto ciò è vagamente ricordato per sentito dire. Prendi questo con un granello di sale e spera che qualcuno lo corregga o lo confermi.

Answer 4

  

So che i valarrays hanno dello zucchero sintattico

Devo dire che non penso che std :: valarrays abbia molto in termini di zucchero sintattico. La sintassi è diversa, ma non definirei la differenza "zucchero". L'API è strana. La sezione su std :: valarray s in Il linguaggio di programmazione C ++ menziona questa API insolita e il fatto che, dal momento che std :: valarray sono dovrebbe essere altamente ottimizzato, eventuali messaggi di errore che riceverai durante il loro utilizzo saranno probabilmente non intuitivi.

Per curiosità, circa un anno fa ho confrontato std :: valarray contro std :: vector . Non ho più il codice o i risultati precisi (anche se non dovrebbe essere difficile scrivere il tuo). L'uso di GCC I ha ottenuto un piccolo vantaggio in termini di prestazioni quando si utilizza std :: valarray per la matematica semplice, ma non per le mie implementazioni per calcolare la deviazione standard (e, ovviamente, la deviazione standard non è così complesso, per quanto riguarda la matematica). Ho il sospetto che le operazioni su ciascun elemento in un grande std :: vector giochino meglio con le cache rispetto alle operazioni su std :: valarray s. (< strong> NOTA , seguendo i consigli di musiphil , sono riuscito a ottenere prestazioni quasi identiche da vector e valarray ).

Alla fine, ho deciso di usare std :: vector prestando molta attenzione a cose come l'allocazione della memoria e la creazione temporanea di oggetti.

---

Sia std :: vector che std :: valarray memorizzano i dati in un blocco contiguo. Tuttavia, accedono a tali dati utilizzando modelli diversi e, cosa più importante, l'API per std :: valarray incoraggia modelli di accesso diversi rispetto all'API per std :: vector .

Per l'esempio della deviazione standard, in una fase particolare ho dovuto trovare la media della raccolta e la differenza tra il valore di ciascun elemento e la media.

Per std :: valarray , ho fatto qualcosa del tipo:

std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> temp(mean, original_values.size());
std::valarray<double> differences_from_mean = original_values - temp;

Potrei essere stato più intelligente con std :: slice o std :: gslice . Sono passati più di cinque anni.

Per std :: vector , ho fatto qualcosa del tipo:

std::vector<double> original_values = ... // obviously, I put something here
double mean = std::accumulate(original_values.begin(), original_values.end(), 0.0) / original_values.size();

std::vector<double> differences_from_mean;
differences_from_mean.reserve(original_values.size());
std::transform(original_values.begin(), original_values.end(), std::back_inserter(differences_from_mean), std::bind1st(std::minus<double>(), mean));

Oggi lo scriverei sicuramente diversamente. Se non altro, approfitterei di C ++ 11 lambdas.

È ovvio che questi due frammenti di codice fanno cose diverse. Per esempio, l'esempio std :: vector non crea una raccolta intermedia come nell'esempio std :: valarray . Tuttavia, penso che sia giusto confrontarli perché le differenze sono legate alle differenze tra std :: vector e std :: valarray .

Quando ho scritto questa risposta, sospettavo che sottraendo il valore degli elementi da due std :: valarray s (ultima riga nell'esempio std :: valarray ) essere meno compatibile con la cache della riga corrispondente nell'esempio std :: vector (che sembra essere anche l'ultima riga).

Si scopre, tuttavia, che

std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> differences_from_mean = original_values - mean;

Fa la stessa cosa dell'esempio std :: vector e ha prestazioni quasi identiche. Alla fine, la domanda è quale API preferisci.

Answer 5

valarray avrebbe dovuto lasciare un po 'di bontà di elaborazione vettoriale FORTRAN cancellarsi su C ++. In qualche modo il supporto del compilatore necessario non è mai realmente accaduto.

I libri di Josuttis contengono alcuni interessanti commenti (in qualche modo denigratori) su valarray ( qui e qui ).

Tuttavia, Intel sembra ora rivisitare valarray nelle recenti versioni del compilatore (ad es. vedi slide 9 ); questo è uno sviluppo interessante dato che il loro set di istruzioni SSD SIMD a 4 vie sta per essere affiancato da istruzioni AVX a 8 vie e Larrabee a 16 vie e nell'interesse della portabilità sarà probabilmente molto meglio codificare con un'astrazione come valarray di (diciamo) intrinseci.

Answer 6

Ho trovato un buon utilizzo per valarray. Usare valarray proprio come array intorpiditi.

auto x = linspace(0, 2 * 3.14, 100);
plot(x, sin(x) + sin(3.f * x) / 3.f + sin(5.f * x) / 5.f);

Possiamo implementare sopra con valarray.

valarray<float> linspace(float start, float stop, int size)
{
    valarray<float> v(size);
    for(int i=0; i<size; i++) v[i] = start + i * (stop-start)/size;
    return v;
}

std::valarray<float> arange(float start, float step, float stop)
{
    int size = (stop - start) / step;
    valarray<float> v(size);
    for(int i=0; i<size; i++) v[i] = start + step * i;
    return v;
}

string psstm(string command)
{//return system call output as string
    string s;
    char tmp[1000];
    FILE* f = popen(command.c_str(), "r");
    while(fgets(tmp, sizeof(tmp), f)) s += tmp;
    pclose(f);
    return s;
}

string plot(const valarray<float>& x, const valarray<float>& y)
{
    int sz = x.size();
    assert(sz == y.size());
    int bytes = sz * sizeof(float) * 2;
    const char* name = "plot1";
    int shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
    ftruncate(shm_fd, bytes);
    float* ptr = (float*)mmap(0, bytes, PROT_WRITE, MAP_SHARED, shm_fd, 0);
    for(int i=0; i<sz; i++) {
        *ptr++ = x[i];
        *ptr++ = y[i];
    }

    string command = "python plot.py ";
    string s = psstm(command + to_string(sz));
    shm_unlink(name);
    return s;
}

Inoltre, abbiamo bisogno dello script python.

import sys, posix_ipc, os, struct
import matplotlib.pyplot as plt

sz = int(sys.argv[1])
f = posix_ipc.SharedMemory("plot1")
x = [0] * sz
y = [0] * sz
for i in range(sz):
    x[i], y[i] = struct.unpack('ff', os.read(f.fd, 8))
os.close(f.fd)
plt.plot(x, y)
plt.show()

Answer 7

Lo standard C ++ 11 dice:

  

Le classi di array valarray sono definite come libere da alcune forme di   aliasing, consentendo così di ottimizzare le operazioni su queste classi.

Vedi C ++ 11 26.6.1-2.

Answer 8

std :: valarray è destinato a compiti numerici pesanti, come la fluidodinamica computazionale o la dinamica della struttura computazionale, in cui si hanno array con milioni, a volte decine di milioni di elementi, e si esegue l'iterazione in un ciclo con anche milioni di timesteps. Forse oggi std :: vector ha prestazioni comparabili ma, circa 15 anni fa, valarray era quasi obbligatorio se si voleva scrivere un risolutore numerico efficiente.