C ++ valarray vs. wektor

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?

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.

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.

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.

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.

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.

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

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

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.

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.

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.