C ++ Valarray vs. Vektor

Ich mag Vektoren sehr. Sie sind geschickt und schnell. Aber ich weiß, dass dieses Ding namens Valarray existiert. Warum sollte ich einen Valarray anstelle eines Vektors verwenden? Ich weiß, Valarrays haben syntaktischen Zucker, aber abgesehen davon, wann sind sie nützlich?

Valarrays (Wert-Arrays) sollen einen Teil der Geschwindigkeit von Fortran in C ++ bringen. Sie würden kein Valarray von Zeigern erstellen, damit der Compiler Annahmen über den Code treffen und ihn besser optimieren kann. (Der Hauptgrund dafür, dass Fortran so schnell ist, ist, dass es keinen Zeigertyp gibt, sodass es kein Zeiger-Aliasing geben kann.)

Valarrays haben auch Klassen, mit denen Sie sie auf relativ einfache Weise aufteilen können, obwohl dieser Teil des Standards etwas mehr Arbeit erfordern könnte. Die Größenänderung ist destruktiv und es fehlen Iteratoren.

Wenn es sich also um Zahlen handelt, mit denen Sie arbeiten, und Bequemlichkeit nicht so wichtig ist, verwenden Sie Valarrays. Ansonsten sind Vektoren viel bequemer.

valarrayist eine Art Waisenkind, das zur falschen Zeit am falschen Ort geboren wurde. Es ist ein Optimierungsversuch, ziemlich speziell für die Maschinen, die beim Schreiben für Hochleistungsmathematik verwendet wurden - speziell für Vektorprozessoren wie die Crays.

Bei einem Vektorprozessor wollten Sie im Allgemeinen eine einzelne Operation auf ein gesamtes Array anwenden und dann die nächste Operation auf das gesamte Array anwenden usw., bis Sie alles getan haben, was Sie tun mussten.

Wenn Sie jedoch nicht mit relativ kleinen Arrays arbeiten, funktioniert dies beim Caching in der Regel schlecht. Auf den meisten modernen Computern würden Sie es im Allgemeinen (soweit möglich) vorziehen, einen Teil des Arrays zu laden, alle Operationen auszuführen, die Sie ausführen möchten, und dann mit dem nächsten Teil des Arrays fortzufahren.

valarraysoll auch jede Möglichkeit von Aliasing ausschließen, wodurch der Compiler (zumindest theoretisch) die Geschwindigkeit verbessern kann, da es freier ist, Werte in Registern zu speichern. In Wirklichkeit bin ich mir jedoch keineswegs sicher, ob eine echte Implementierung dies in nennenswertem Maße ausnutzt. Ich vermute, es ist eher ein Henne-Ei-Problem - ohne Compiler-Unterstützung wurde es nicht populär, und solange es nicht populär ist, wird sich niemand die Mühe machen, an seinem Compiler zu arbeiten, um es zu unterstützen.

Es gibt auch eine verwirrende (buchstäblich) Reihe von Nebenklassen, die mit Valarray verwendet werden können. Sie erhalten slice, slice_array, gsliceund gslice_arraymit Stücken von a zu spielen valarray, und es wie ein mehrdimensionales Array handeln machen. Sie können auch mask_arrayeine Operation "maskieren" (z. B. Elemente in x zu y hinzufügen, jedoch nur an den Positionen, an denen z ungleich Null ist). Um mehr als nur trivial davon Gebrauch zu machen valarray, muss man viel über diese Nebenklassen lernen, von denen einige ziemlich komplex sind und von denen (zumindest für mich) keine sehr gut dokumentiert erscheint.

Fazit: Während es Momente der Brillanz hat und einige Dinge ziemlich ordentlich erledigen kann, gibt es auch einige sehr gute Gründe, warum es dunkel ist (und mit ziemlicher Sicherheit bleiben wird).

Bearbeiten (acht Jahre später, im Jahr 2017): Einige der vorhergehenden sind zumindest teilweise veraltet. Zum Beispiel hat Intel eine optimierte Version von Valarray für seinen Compiler implementiert. Es verwendet die Intel Integrated Performance Primitives (Intel IPP), um die Leistung zu verbessern. Obwohl die genaue Leistungsverbesserung zweifellos unterschiedlich ist, zeigt ein schneller Test mit einfachem Code eine Verbesserung der Geschwindigkeit um 2: 1 im Vergleich zu identischem Code, der mit der "Standard" -Implementierung von kompiliert wurde valarray.

Obwohl ich nicht ganz davon überzeugt bin, dass C ++ - Programmierer valarrayin großer Zahl eingesetzt werden, gibt es zumindest einige Umstände, unter denen dies zu einer Geschwindigkeitsverbesserung führen kann.

Während der Standardisierung von C ++ 98 wurde Valarray entwickelt, um schnelle mathematische Berechnungen zu ermöglichen. Zu dieser Zeit erfand Todd Veldhuizen jedoch Ausdrucksvorlagen und erstellte Blitz ++ , und ähnliche Template-Meta-Techniken wurden erfunden, die Valarrays ziemlich veraltet machten, bevor der Standard überhaupt veröffentlicht wurde. IIRC, die ursprünglichen Antragsteller von Valarray, gaben es auf halbem Weg in die Standardisierung auf, was (falls zutreffend) auch nicht half.

ISTR, dass der Hauptgrund dafür, dass es nicht aus dem Standard entfernt wurde, darin besteht, dass sich niemand die Zeit genommen hat, das Problem gründlich zu bewerten und einen Vorschlag zu schreiben, um es zu entfernen.

Bitte denken Sie jedoch daran, dass all dies vage an Hörensagen erinnert wird. Nehmen Sie dies mit einem Körnchen Salz und hoffen Sie, dass jemand dies korrigiert oder bestätigt.

Ich weiß, dass Valarrays syntaktischen Zucker haben

Ich muss sagen, dass ich nicht std::valarraysviel syntaktischen Zucker habe. Die Syntax ist anders, aber ich würde den Unterschied nicht "Zucker" nennen. Die API ist komisch. Der Abschnitt über std::valarrays in der Programmiersprache C ++ erwähnt diese ungewöhnliche API und die Tatsache, dass, da std::valarrayerwartet wird , dass s stark optimiert ist, alle Fehlermeldungen, die Sie während der Verwendung erhalten, wahrscheinlich nicht intuitiv sind.

Aus Neugier habe ich mich std::valarrayvor ungefähr einem Jahr dagegen gestellt std::vector. Ich habe nicht mehr den Code oder die genauen Ergebnisse (obwohl es nicht schwer sein sollte, einen eigenen zu schreiben). Mit GCC habe ich zwar einen kleinen Leistungsvorteil bei der Verwendung std::valarrayfür einfache Mathematik erzielt, aber nicht für meine Implementierungen zur Berechnung der Standardabweichung (und natürlich ist die Standardabweichung nicht so komplex, was die Mathematik betrifft). Ich vermute, dass Operationen an jedem Element in einem großen std::vectorSpiel besser mit Caches spielen als Operationen an std::valarrays. ( HINWEIS : Nach den Ratschlägen von musiphil habe ich es geschafft, von vectorund eine nahezu identische Leistung zu erzielen valarray.)

Am Ende entschied ich mich für die Verwendung, std::vectorwährend ich mich intensiv mit Dingen wie Speicherzuweisung und temporärer Objekterstellung befasste.

Beide std::vectorund std::valarrayspeichern die Daten in einem zusammenhängenden Block. Sie greifen jedoch mit unterschiedlichen Mustern auf diese Daten zu, und was noch wichtiger ist, die API für std::valarrayfördert andere Zugriffsmuster als die API für std::vector.

Für das Beispiel der Standardabweichung musste ich in einem bestimmten Schritt den Mittelwert der Sammlung und die Differenz zwischen dem Wert jedes Elements und dem Mittelwert ermitteln.

Für die habe std::valarrayich so etwas gemacht wie:

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;

Ich war vielleicht schlauer mit std::sliceoder std::gslice. Es ist jetzt über fünf Jahre her.

Denn std::vectorich habe etwas in der Art getan:

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

Heute würde ich das sicherlich anders schreiben. Wenn nichts anderes, würde ich C ++ 11 Lambdas nutzen.

Es ist offensichtlich, dass diese beiden Codeausschnitte unterschiedliche Funktionen haben. Zum einen erstellt das std::vectorBeispiel keine Zwischensammlung wie das std::valarrayBeispiel. Ich denke jedoch, dass es fair ist, sie zu vergleichen, da die Unterschiede mit den Unterschieden zwischen std::vectorund zusammenhängen std::valarray.

Als ich diese Antwort schrieb, vermutete ich, dass das Subtrahieren des Werts von Elementen von zwei std::valarrays (letzte Zeile im std::valarrayBeispiel) weniger cachefreundlich wäre als die entsprechende Zeile im std::vectorBeispiel (die zufällig auch die letzte Zeile ist).

Es stellt sich jedoch heraus, dass

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;

Funktioniert genauso wie im std::vectorBeispiel und hat eine nahezu identische Leistung. Am Ende stellt sich die Frage, welche API Sie bevorzugen.

valarray sollte einige FORTRAN-Vektorverarbeitungsgüte auf C ++ abfärben lassen. Irgendwie ist die notwendige Compiler-Unterstützung nie wirklich passiert.

Die Josuttis-Bücher enthalten einige interessante (etwas abfällige) Kommentare zu Valarray ( hier und hier ).

Intel scheint Valarray jedoch in seinen jüngsten Compiler-Versionen erneut zu besuchen (siehe z. B. Folie 9 ). Dies ist eine interessante Entwicklung, da der 4-Wege-SIMD-SSE-Befehlssatz bald durch 8-Wege-AVX- und 16-Wege-Larrabee-Befehle ergänzt wird. Im Interesse der Portabilität ist es wahrscheinlich viel besser, mit einer Abstraktion wie zu codieren Valarray als (sagen wir) intrinsics.

Ich habe eine gute Verwendung für Valarray gefunden. Es ist Valarray genau wie Numpy Arrays zu verwenden.

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

Wir können oben mit Valarray implementieren.

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

Außerdem benötigen wir ein Python-Skript.

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

Der C ++ 11 Standard sagt:

Die Valarray-Array-Klassen sind so definiert, dass sie frei von bestimmten Formen des Aliasing sind, sodass Operationen für diese Klassen optimiert werden können.

Siehe C ++ 11 26.6.1-2.

Mit können std::valarraySie die mathematische Standardnotation wie v1 = a*v2 + v3im Auslieferungszustand verwenden. Dies ist mit Vektoren nur möglich, wenn Sie Ihre eigenen Operatoren definieren.

std :: valarray ist für schwere numerische Aufgaben wie Computational Fluid Dynamics oder Computational Structure Dynamics vorgesehen, bei denen Sie Arrays mit Millionen, manchmal mehreren zehn Millionen Elementen haben und diese in einer Schleife mit ebenfalls Millionen von Zeitschritten durchlaufen. Vielleicht hat std :: vector heute eine vergleichbare Leistung, aber vor etwa 15 Jahren war valarray fast obligatorisch, wenn Sie einen effizienten numerischen Löser schreiben wollten.