was genau ist vektorisierung

Liebe Leute,

ich lese ständig was von Vektorisierung und dass da effizienter (schnellerer) code programmiert werden kann. Allerdings verstehe ich die beschreibungen die ich finde so gut wie gar nicht. Hat das was mit arrays zu tun? Könnt ihr mir helfen?

Danke

Mechanics

Meinst du SIMD? Single Instruction, Multiple Data. Kannst mit einem Befehl gleich Vektoren verarbeiten. Stell dir vor, du hast jeweils zwei Vektoren mit 6 ints, und die willst du addieren. Das kannst du mit einem entsprechenden SIMD Befehl halt schneller machen, als mit 6 einzelnen Additionen.

SeppJ

Genau das. Vielleicht noch zur Erläuterung: Viele Prozessoren haben spezielle Erweiterungen, um die gleichen Anweisungen gleichzeitig auf mehrere Variablen anzuwenden (läuft unter Namen wie SSE, MMX, 3DNow, ...). Das ist auch tatsächlich ein Anwendungsfall, den man sehr häufig hat. Sehr gute Compiler erkennen solche Programmstrukturen automatisch und können dann speziellen Code erzeugen, der diese Erweiterungen nutzt und dann ein vielfaches schneller verarbeitet wird, als mehrmals die gleiche Rechnung sequenziell auf unterschiedlichen Variablen anzuwenden. Damit Compiler das automatisch können, ist es manchmal ganz angebracht, ihnen entgegenzukommen und seinen Code nicht zu chaotisch und die Daten schön beisammen zu halten. Man kann auch spezielle Compilerfeatures/Bibliotheken benutzen (z.B. Integrated Performance Primitives und viele andere), die diese Prozessorfeatures auf einer halbwegs benutzbaren Abstraktionsebene anbieten, so dass man nicht in Assembler programmieren muss, wenn man diese nutzen möchte.

Die aktuelle Compilergeneration (zumindest GCC und Intelcompiler) ist meiner Erfahrung nach aber schon extrem gut darin geworden, diese Strukturen automatisch zu erkennen. Es ist mir nie gelungen, durch händische Benutzung der Prozessorfeatures die aktuellen Compiler zu schlagen^*. Am meisten bringt's noch, so zu programmieren, dass die Optimierung dem Compiler leicht fällt (Tipps dazu gibt es in tiefergehenden Optimierungshandbüchern der Compiler).

^*: Ein paar Kollegen und andere Forenteilnehmer berichten aber auch von wahren Wunderleistungen, wenn sie selber Hand angelegt haben. Ich kenne deren Codes aber nicht. Bild dir deine eigene Meinung.

danke für die guten erklärungen.
@ SeppJ: dürfte ich Dich bitten noch mal zu deinem sätzchen

...und die Daten schön beisammen zu halten...

etwas genauer einzugehen? Was meinst Du damit? Daten kompakt im Array zu halten? Oder arrays alle gesammelt an einer stelle initialisieren weil sie dann (falls groß genuges speicherloch frei) alle im block nebeneinander liegen?

danke

SeppJ schrieb:

Es ist mir nie gelungen, durch händische Benutzung der Prozessorfeatures die aktuellen Compiler zu schlagen^*.

Dein Code ist halt Müll.

^*: Ein paar Kollegen und andere Forenteilnehmer berichten aber auch von wahren Wunderleistungen, wenn sie selber Hand angelegt haben.

Siehste die kriegen das besser hin als du.

SeppJ

Daten die gleichzeitig verarbeitet werden sollen möglichst auch beisammen im Speicher zu halten. Da ist der echte Performancenachteil der objektorientierten Programmierung (und nicht der Unsinn von Möchtegernoptimierern, die denken, Klassenabstraktion an sich würde irgendwie magisch Zeit kosten), denn sie verführt zu Strukturen wie (in C++ geschrieben):

class Foo
{
  int data1;
  int data2;
};

// ...

Foo foos[999999];
for (schleife über alle foos)
 tue_irgendwas_performancekritisches_mit_den_foos_data1;

Da würden dann nämlich immer abwechselnd die data1 und data2 der Foos im Speicher liegen. Das ist dann ungünstiger als wenn man

int data1[999999];
int data2[999999];
for (schleife über alle data1)
 tue_irgendwas_performancekritisches_mit_den_data1;

haben würde, wo die für die kritische Rechnung alle Daten schön lückenlos hätte, wodurch man die breiten SSE-Register optimal befüllen kann.

Aber gewöhn dir jetzt bloß nicht an, dass in jedem Popelprogramm so zu machen. Den Mehraufwand beim Programmieren bekommst du bei der Ausführung nie wieder rein. Es ist bloß hübsch zu wissen, wenn du mal wirklich eine hochkritische Schleife programmierst.

knivil

Da kommt dann aber noch mehr: Cache, Datenabhaengigkeit, ...

SeppJ schrieb:

Daten die gleichzeitig verarbeitet werden sollen möglichst auch beisammen im Speicher zu halten. Da ist der echte Performancenachteil der objektorientierten Programmierung (und nicht der Unsinn von Möchtegernoptimierern, die denken, Klassenabstraktion an sich würde irgendwie magisch Zeit kosten), denn sie verführt zu Strukturen wie (in C++ geschrieben):
class Foo
{
  int data1;
  int data2;
};

// ...

Foo foos[999999];
for (schleife über alle foos)
 tue_irgendwas_performancekritisches_mit_den_foos_data1;
Da würden dann nämlich immer abwechselnd die data1 und data2 der Foos im Speicher liegen. Das ist dann ungünstiger als wenn man
int data1[999999];
int data2[999999];
for (schleife über alle data1)
 tue_irgendwas_performancekritisches_mit_den_data1;
haben würde, wo die für die kritische Rechnung alle Daten schön lückenlos hätte, wodurch man die breiten SSE-Register optimal befüllen kann.

Aber gewöhn dir jetzt bloß nicht an, dass in jedem Popelprogramm so zu machen. Den Mehraufwand beim Programmieren bekommst du bei der Ausführung nie wieder rein. Es ist bloß hübsch zu wissen, wenn du mal wirklich eine hochkritische Schleife programmierst.

Dein Beispiel ist aber für schlechten OOP Code (also langsamen, über den Stil ist ja nichts zu sagen, außer dass niemand auf data1 und data2 von außen zugreifen kann :P) denke ich ein bisschen ungünstig gewählt.

Die ganzen "data2"s würden ja mit ziemlicher Sicherheit auch in einer Cache-Line mit den dazugehören "data1"s liegen und somit hätte man trotzdem deutlich weniger Cache-Misses, als wenn data2 z.b. ein Zeiger auf irgendwas wild verteilt im Speicher wäre (Bemerkung für afaiko: In C++ werden die Daten einer Klasse in der gleichen Reihenfolge in den Speicher gelegt, wie man sie im Quellcode angibt. D.h. hier wäre immer direkt hintereinander data1 und data2 im Speicher). Da Cache-Lines wegen den ganzen SSE-Datentypen ja generell ziemlich groß sind (irgendwie hab ich da 32 Byte als Norm für Desktop-CPUs im Kopf), würden bei deinem Code in dem Array immer noch die nächsten 4 "data1"s bei einem auftretenden Cache-Miss in den Cache geholt werden (davon ausgehend dass int 4 byte sind).

Gibt es für den GCC eigentlich irgendeine öffentliche Referenz, in der man nachlesen kann, welche Fälle der Compiler so optimieren kann? Oder muss ich mich dazu tatsächlich durch den GCC-Code wühlen.

SeppJ

Es geht bei meinem Code nicht um Cache-Misses. Und ich habe bei Konstrukten wie for (schleife über alle foos) nicht auf syntaktische Korrektheit geachtet. Es geht darum, dass die Daten gepackt sein müssen, damit du SSE-Register optimal füttern kannst und so mehr Daten parallel verarbeiten kannst.

TravisG schrieb:

Gibt es für den GCC eigentlich irgendeine öffentliche Referenz, in der man nachlesen kann, welche Fälle der Compiler so optimieren kann? Oder muss ich mich dazu tatsächlich durch den GCC-Code wühlen.

Ja. Ich weiß aber nicht auswendig, wo genau das zu finden ist. Aber das gibt es und finden kannst du es daher genau so gut wie ich. Es liegt aber nicht als zusammenhängende Dokumentation von Optimierungstipps vor (falls doch, dann würde ich auch sehr gerne davon erfahren), sondern als eine genaue Einzelbeschreibung aller Optimierungsdurchgänge. Also im Prinzip auch recht schwer zu lesen, aber weniger schwer als direkt den Code anzugucken.

Ja, sorry, irgendwie hat mein Gehirn komplett weggestrichen, dass es um SIMD Optimierungen geht