C ++ valarray vs. wektor

159

Bardzo lubię wektory. Są sprytne i szybkie. Ale wiem, że istnieje coś takiego jak valarray. Dlaczego miałbym używać valarray zamiast wektora? Wiem, że valarrays mają trochę cukru syntaktycznego, ale poza tym, kiedy są przydatne?

rlbond
źródło
2
Zastanawiałem się nad tym też pewnego dnia. O ile wiem, to tak naprawdę wyspecjalizowany wektor matematyczny.
GManNickG
Czy valarray nie obsługuje szablonów wyrażeń?
Mooing Duck
Fizyk Ulrich Mutze przedstawia przypadek użycia valarray tu i tutaj
Lifebalance,

Odpowiedzi:

70

Valarrays (tablice wartości) mają na celu zwiększenie szybkości języka Fortran do C ++. Nie tworzyłbyś tablicy wskaźników, aby kompilator mógł przyjąć założenia dotyczące kodu i lepiej go zoptymalizować. (Głównym powodem, dla którego Fortran jest tak szybki, jest brak typu wskaźnika, więc nie może być aliasingu wskaźnika).

Valarrays mają również klasy, które pozwalają ci je pokroić w dość łatwy sposób, chociaż ta część standardu może wymagać trochę więcej pracy. Zmiana ich rozmiaru jest destrukcyjna i brakuje im iteratorów.

Tak więc, jeśli chodzi o liczby, z którymi pracujesz, a wygoda nie jest tak ważna, użyj wartości. W przeciwnym razie wektory są po prostu znacznie wygodniejsze.

Tim Allman
źródło
11
Nie mają one na celu unikania wskazówek. C ++ 11 definiuje begin () i end () w valarray, które zwracają do nich iteratory
Mohamed El-Nakib,
3
@ user2023370: dlatego tak wielu użytkowników Fortrana woli Fortran 77. :)
Michael
152

valarrayjest sierotą, która urodziła się w niewłaściwym miejscu o niewłaściwym czasie. Jest to próba optymalizacji, całkiem konkretnie dla maszyn, które były używane do ciężkiej matematyki, kiedy została napisana - w szczególności procesorów wektorowych, takich jak Crays.

W przypadku procesora wektorowego zwykle chciałeś zastosować jedną operację do całej tablicy, a następnie zastosować następną operację do całej tablicy i tak dalej, aż zrobisz wszystko, co trzeba.

Jeśli jednak nie masz do czynienia z dość małymi tablicami, to zwykle źle działa z buforowaniem. W przypadku większości nowoczesnych maszyn, generalnie wolisz (w miarę możliwości) załadować część tablicy, wykonać wszystkie operacje na niej, które zamierzasz, a następnie przejść do następnej części tablicy.

valarrayma również wyeliminować jakąkolwiek możliwość aliasingu, co (przynajmniej teoretycznie) pozwala kompilatorowi zwiększyć szybkość, ponieważ ma większą swobodę przechowywania wartości w rejestrach. W rzeczywistości jednak nie jestem wcale pewien, czy jakakolwiek rzeczywista implementacja wykorzystuje to w jakikolwiek sposób. Podejrzewam, że jest to raczej problem typu kura i jajko - bez wsparcia kompilatora nie stał się popularny i dopóki nie jest popularny, nikt nie będzie zadawać sobie trudu pracy nad ich kompilatorem, aby go wspierać.

Istnieje również oszałamiająca (dosłownie) tablica klas pomocniczych do użycia z valarray. Masz slice, slice_array, gslicei gslice_arraybawić się z kawałków valarray, i sprawiają, że zachowują się jak wielowymiarowej tablicy. Możesz także mask_array„zamaskować” operację (np. Dodać elementy w x do y, ale tylko w pozycjach, w których z jest niezerowe). Aby zrobić więcej niż trywialny użytek valarray, musisz się wiele nauczyć o tych klasach pomocniczych, z których niektóre są dość złożone i żadna z nich nie wydaje się (przynajmniej mi) dobrze udokumentowana.

Podsumowując: chociaż ma momenty błyskotliwości i może robić pewne rzeczy całkiem zgrabnie, istnieją również bardzo dobre powody, dla których jest (i prawie na pewno pozostanie) niejasne.

Edycja (osiem lat później, w 2017 r.): Niektóre z powyższych stały się przynajmniej w pewnym stopniu przestarzałe. Na przykład Intel wdrożył zoptymalizowaną wersję valarray dla swojego kompilatora. Używa Intel Integrated Performance Primitives (Intel IPP), aby poprawić wydajność. Chociaż dokładna poprawa wydajności jest niewątpliwie różna, szybki test z prostym kodem pokazuje poprawę szybkości około 2: 1 w porównaniu z identycznym kodem skompilowanym przy użyciu „standardowej” implementacji valarray.

Tak więc, chociaż nie jestem do końca przekonany, że programiści C ++ zaczną używać valarrayw ogromnych ilościach, są przynajmniej pewne okoliczności, w których może to zapewnić poprawę szybkości.

Jerry Coffin
źródło
1
Czy jest szczególnie zabronione przechowywanie dowolnych typów obiektów wewnątrz valarray?
user541686
6
@Mehrdad: Tak - istnieje (dość długa) lista ograniczeń w [Numeric.Requirements]. Tylko dla kilku przykładów wszystkie klasy abstrakcyjne i wyjątki są zabronione. Wymaga również równoważności między (na przykład) konstrukcją kopii a sekwencją domyślnej konstrukcji, po której następuje przypisanie.
Jerry Coffin
@JerryCoffin sheesh to straszne. obiecujemy, że nie będziemy go używać.
Hani Goc
4
Nie zdecydowałbym tego na podstawie strachu. Postanowiłbym to na podstawie tego, czy musisz przechowywać elementy, które używają funkcji, których ona zabrania.
Jerry Coffin
3
@annoying_squid: Jeśli masz bardziej szczegółowe i (Twoim zdaniem) dokładne informacje do dodania, możesz dodać odpowiedź, która je pokazuje. W obecnym stanie Twój komentarz nie wydaje się jednak zawierać żadnych przydatnych informacji.
Jerry Coffin
39

Podczas standaryzacji C ++ 98 valarray został zaprojektowany, aby umożliwić pewnego rodzaju szybkie obliczenia matematyczne. Jednak mniej więcej w tym czasie Todd Veldhuizen wynalazł szablony wyrażeń i stworzył blitz ++ , a także wynaleziono podobne techniki szablonów-meta, które sprawiły, że valarrays stały się przestarzałe, zanim jeszcze standard został wydany. IIRC, pierwotny projektodawca Valarray porzucił ją w połowie procesu standaryzacji, co (jeśli to prawda) też jej nie pomogło.

ISTR, że głównym powodem, dla którego nie został usunięty ze standardu, jest to, że nikt nie poświęcił czasu na dogłębną ocenę problemu i napisanie propozycji jego usunięcia.

Należy jednak pamiętać, że wszystko to jest niejasno zapamiętane z pogłosek. Weź to z przymrużeniem oka i miej nadzieję, że ktoś to poprawi lub potwierdzi.

sbi
źródło
szablony wyrażeń można również przypisać Vandevoorde, prawda?
Nikos Athanasiou
@Nikos: Nie o tym wiem. Chociaż mogę się mylić. Co przemawiasz za tym odczytem?
sbi
1
wspomniano o tym w książce „Szablony C ++ - kompletny przewodnik”, myślę, że ogólnie przyjmuje się, że obaj wymyślili je niezależnie .
Nikos Athanasiou
27

Wiem, że valarrays mają trochę cukru syntaktycznego

Muszę powiedzieć, że nie sądzę std::valarrays, aby mieć dużo cukru syntaktycznego. Składnia jest inna, ale nie nazwałbym tej różnicy „cukrem”. API jest dziwne. Sekcja na temat std::valarrays w C ++ Programming Language wspomina o tym niezwykłym API oraz o fakcie, że ponieważ std::valarrayoczekuje się , że s będą wysoce zoptymalizowane, wszelkie komunikaty o błędach, które otrzymasz podczas ich używania, będą prawdopodobnie nieintuicyjne.

Z ciekawości mniej więcej rok temu walczyłem std::valarrayprzeciwko std::vector. Nie mam już kodu ani dokładnych wyników (chociaż napisanie własnego nie powinno być trudne). Używając GCC, odniosłem niewielką korzyść w zakresie wydajności, gdy używam std::valarraydo prostej matematyki, ale nie w moich implementacjach do obliczania odchylenia standardowego (i oczywiście odchylenie standardowe nie jest tak skomplikowane, jeśli chodzi o matematykę). Podejrzewam, że operacje na każdym elemencie w dużej std::vectorgrze działają lepiej z pamięciami podręcznymi niż operacje na std::valarrays. ( UWAGA , po porady od musiphil , udało mi się dostać niemal identycznej wydajności vectori valarray).

W końcu zdecydowałem się użyć std::vector, zwracając szczególną uwagę na takie rzeczy, jak alokacja pamięci i tworzenie tymczasowych obiektów.


Oba std::vectori std::valarrayprzechowują dane w ciągłym bloku. Jednak uzyskują dostęp do tych danych przy użyciu innych wzorców, a co ważniejsze, API for std::valarrayzachęca do innych wzorców dostępu niż API for std::vector.

W przypadku przykładu odchylenia standardowego na określonym kroku musiałem znaleźć średnią zbioru i różnicę między wartością każdego elementu a średnią.

Dla tego std::valarrayzrobiłem coś takiego:

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;

Mogłem być mądrzejszy z std::slicelub std::gslice. Minęło już ponad pięć lat.

Bo std::vectorzrobiłem coś w stylu:

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

Dziś na pewno napisałbym to inaczej. Jeśli nic więcej, skorzystałbym z lambd C ++ 11.

Jest oczywiste, że te dwa fragmenty kodu robią różne rzeczy. Po pierwsze, std::vectorprzykład nie tworzy pośredniej kolekcji, jak w std::valarrayprzykładzie. Uważam jednak, że warto je porównać, ponieważ różnice są powiązane z różnicami między std::vectori std::valarray.

Kiedy pisałem tę odpowiedź, podejrzewałem, że odjęcie wartości elementów od dwóch std::valarrays (ostatnia linia w std::valarrayprzykładzie) byłoby mniej przyjazne dla pamięci podręcznej niż odpowiadająca jej linia w std::vectorprzykładzie (która jest również ostatnią linią).

Okazuje się jednak, że

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;

Robi to samo, co std::vectorprzykład i ma prawie identyczną wydajność. Na koniec pozostaje pytanie, który interfejs API preferujesz.

Max Lybbert
źródło
Nie przychodzi mi do głowy żaden powód, dla którego a std::vectormiałby grać lepiej z pamięciami podręcznymi niż std::valarray; oboje przydzielają pojedynczy ciągły blok pamięci dla swoich elementów.
musiphil
1
@musiphil Moja odpowiedź stała się zbyt długa na komentarz, więc zaktualizowałem odpowiedź.
Max Lybbert,
1
W valarraypowyższym przykładzie nie musiałeś konstruować temp valarrayobiektu, ale mogłeś to zrobić std::valarray<double> differences_from_mean = original_values - mean;, a zachowanie pamięci podręcznej powinno być podobne do tego z vectorprzykładu. (Nawiasem mówiąc, jeśli meantak naprawdę intnie jest double, możesz potrzebować static_cast<double>(mean).)
musiphil
Dzięki za sugestię dotyczącą uporządkowania pliku valarray. Muszę sprawdzić, czy to poprawi wydajność. A jeśli chodzi o meanbycie int: to był błąd. Pierwotnie napisałem przykład używając ints, a potem zdałem sobie sprawę, meanże wtedy byłby bardzo daleko od rzeczywistej średniej z powodu obcięcia. Ale przegapiłem kilka potrzebnych zmian podczas mojej pierwszej rundy edycji.
Max Lybbert,
@musiphil Masz rację; ta zmiana przyniosła przykładowy kod do prawie identycznej wydajności.
Max Lybbert,
23

Valarray miał pozwolić niektórym zaletom przetwarzania wektorów FORTRAN na C ++. W jakiś sposób niezbędne wsparcie kompilatora tak naprawdę nigdy się nie wydarzyło.

Książki Josuttisa zawierają interesujące (nieco lekceważące) komentarze na temat valarray ( tu i tutaj ).

Jednak obecnie wydaje się, że Intel ponownie odwiedza valarray w swoich ostatnich wydaniach kompilatorów (np. Patrz slajd 9 ); jest to interesujący rozwój, biorąc pod uwagę, że do ich 4-kierunkowego zestawu instrukcji SIMD SSE dołączą 8-kierunkowe instrukcje AVX i 16-kierunkowe instrukcje Larrabee, a ze względu na przenośność prawdopodobnie znacznie lepiej będzie kodować z abstrakcją valarray niż (powiedzmy) wewnętrzne.

Timday
źródło
16

Znalazłem jedno dobre zastosowanie dla valarray. Używa valarray tak jak numpy tablic.

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

wprowadź opis obrazu tutaj

Powyższe możemy wdrożyć za pomocą 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;
}

Potrzebujemy również skryptu 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()
Zeta
źródło
2
Miałem dosłownie te same myśli co ty, kiedy dowiedziałem się o Valarray dzisiaj w pracy. Myślę, że od teraz w przypadku problemów z przetwarzaniem matematycznym w c ++ będę używał valarray, ponieważ kod wygląda o wiele łatwiej, aby zrozumieć go z punktu widzenia matematyki.
Zachary Kraus
8

Standard C ++ 11 mówi:

Klasy tablic valarray są zdefiniowane jako wolne od pewnych form aliasingu, co pozwala na optymalizację operacji na tych klasach.

Zobacz C ++ 11 26.6.1-2.

Lingxi
źródło
Ponieważ zakładam, że norma definiuje, które formularze, czy możesz je zacytować? Ponadto, czy są one zaimplementowane przy użyciu sztuczek kodowania, czy też są to oparte na kompilatorze wyjątki od reguł aliasingu w innym miejscu w języku?
underscore_d
2

Dzięki temu std::valarraymożesz użyć standardowej notacji matematycznej jak po v1 = a*v2 + v3wyjęciu z pudełka. Nie jest to możliwe w przypadku wektorów, chyba że zdefiniujesz własne operatory.

Paweł Jurczak
źródło
0

std :: valarray jest przeznaczony do ciężkich zadań numerycznych, takich jak obliczeniowa dynamika płynów lub obliczeniowa dynamika struktur, w których masz tablice z milionami, czasem dziesiątkami milionów elementów i iterujesz po nich w pętli z milionami kroków czasowych. Może dzisiaj std :: vector ma porównywalną wydajność, ale jakieś 15 lat temu valarray był prawie obowiązkowy, jeśli chciałeś napisać wydajne rozwiązanie numeryczne.

mrpivello
źródło