Schnelles Iterieren über "pyramidale" Matrix

Eisflamme

Die Idee gefällt mir super.

Aber jetzt haben wir insgesamt ja 66*21 * 21 Iterationen. Der äußere Iterator sollte doch nur über X1,X3 iterieren. Hast du vorausgesetzt, dass der äußere Iterator eine Spezialanfertigung ist, welche immer brav 21 Elemente springt? Oder man schreibt halt i += 21.

Den gesamten Algorithmus packe ich bei mir ohnehin ebenfalls in einen Iterator, wie von dir vorgeschlagen.

Werner Salomon

Eisflamme schrieb:

Aber jetzt haben wir insgesamt ja 66*21 * 21 Iterationen. Der äußere Iterator sollte doch nur über X1,X3 iterieren. Hast du vorausgesetzt, dass der äußere Iterator eine Spezialanfertigung ist, welche immer brav 21 Elemente springt? Oder man schreibt halt i += 21.

Ja klar - hast Recht.
Der äußere Iterator i muss nachgeführt werden. i+=21 wäre eine Option - oder i=i2_end .

Gruß
Werner

Werner Salomon

.. oder gleich i2 einsparen und nur i nehmen!

knivil

Die Iteration ist garantiert performancekritisch

Das bedeutet in Zahlen? Wieviel % vom Rest faellt allein der Iteration zu? Hast du verschiedene Varianten ausprobiert? Was sind die Ergebnisse deiner Zeitmessungen im Vergleich zur trivialen Implementierung?

Die Matrix könnte also auch viel größer sein

Optimierung fuer verschiedene Problemgroessen ist ebenfalls verschieden. Gib eine realistische Groesse an, denn 21*66 Elemente (von welchem Typ?) ist sehr klein!

Ansonsten: Gibt keine generellen Tips, da Speicherlayout deiner Matrix unbekannt ist.

volkard

Eisflamme schrieb:

Sie hat 3 Dimensionen X1,X2,X3. X1,X3 spannen sich auf von 0-10, also 11 mögliche Werte je. X2 spannt sich auf von 0-20, also 21 Werte je. Jetzt gibt es aber eine Zusatzbedingung für x1 aus X1, x3 aus X3: x1 + x3 <= 10

Man braucht jetzt also keinen Vektor der Größe 21*11^2 mehr, sondern nur noch 21*(11+1)*11/2 = 21*66.

Also nur 50%. Beachte, daß Du durch unordentliche Herumhüpferei im RAM evtl viel mehr bezahlen musst. Wäre schlichtes if angemessen, wieviel mal mehr kostet die eigentliche Berechnung? Das Muster in Iteratoren wegzustopfen macht evtl den Optimierer dafür blind.

Eisflamme schrieb:

Sie hat 3 Dimensionen X1,X2,X3. X1,X3 spannen sich auf von 0-10,

for(int x1=0;x1<=10;++x1)
   for(int x2;;)
      for(int x3=0;x3<=10;++x3)

also 11 mögliche Werte je. X2 spannt sich auf von 0-20, also 21 Werte je.

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2)
      for(int x3=0;x3<=10;++x3)

Jetzt gibt es aber eine Zusatzbedingung für x1 aus X1, x3 aus X3: x1 + x3 <= 10

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2)
      for(int x3=0;x1+x3<=10;++x3)

Um ehrlich zu sein verstehe ich die Frage nicht. Ging es nur darum, "x1 + x3 <= 10" aus Deinem Posting in den Code zu copy&pasten?
Oder fürchstest Du, daß ein + auf int mehr als eine Nanosekunde kostet? Eine Nanosekunde sind nur 20 Centimeter, das ist winzig.

Eisflamme

Werner Salomon:
Okay, danke

knivil:
So genau kann ich das nicht beantworten. Es gibt innerhalb der Schleifen nochmal 1-2 kleinere Schleifen, worin wiederum nur ein paar Multiplikationen ausgeführt werden. Ich habe ein paar unterschiedliche Varianten ausprobiert, nicht nachgemessen aber einen Unterschied gespürt. Daraus ergab sich für mich, dass man hier optimieren sollte - ist vom Aufwand gegenüber dem restlichen Programm über auch recht vertretbar. Die anderen Teile werde ich aber ebenfalls noch versuchen so weit wie möglich zu optimieren. Der eigentliche Algorithmus ist sehr simpel, wird nur auf einer großen Datenmenge ausgeführt, daher besteht das Programm fast nur aus "Mikro"optimierungen.

Es gibt zwei Anwendungsfälle, einmal enthält die Matrix 21*66 Elemente und einmal 21*66^2. 21*66^3 ist unwahrscheinlich, weil es zu groß wird. Die beiden Fälle würde ich optimierungstechnisch gerne erschlagen, im Zweifelsfall ist 21*66 aber interessanter.

Das sind dann noch nicht viele Iterationen, aber diese 21*66 Iterationen werden wiederum 20-50 Mal ausgeführt. Und im inneren der Schleife iteriere ich wiederum über dieselbe Matrix, also eigentlich (21*66)^2 (aber ich bin gerade dran, die Anzahl innerer Iterationen auch noch zu verbessern).

Das Matrixdesign bin ich bereit komplett für die Optimierung anzupassen. Zurzeit habe ich einen ~~linearen~~eindimensionalen Vektor und X1,X2,X3 ist die Reihenfolge der Dimensionen. Was gibt es zum Speicherlayout noch zu wissen? Ich nutze MSVC12 und dessen STL-Vektor-Implementierung.

volkard:
Ungefähr 50%, ja.

Wenn ich es so wie du beschrieben mache, muss ich halt den Index innerhalb der Schleife jedes Mal berechnen, um auf das Objekt zuzugreifen. In einem anderen Thread, wo die pyramidale Anforderung noch nicht gegeben war, sprach sich Shade of Mine dafür aus von 0 bis N zu iterieren statt mehrere Schleifen zu nutzen: http://www.c-plusplus.net/forum/p2371119#2371119

Kann natürlich sein, dass ich da zu wenige Infos geliefert habe.

volkard

Eisflamme schrieb:

Wenn ich es so wie du beschrieben mache, muss ich halt den Index innerhalb der Schleife jedes Mal berechnen, um auf das Objekt zuzugreifen.

Nicht unbedingt.

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2)
      for(int x3=0;x1+x3<=10;++x3)	
         tuwas(vec[x1][x2][x3]);

for(int x1=0;x1<=10;++x1)
   for(int x2=0;x2<=20;++x2){
      auto& zeile=vec[x1][x2];
      for(int x3=0;x1+x3<=10;++x3)	
         tuwas(zeile[x3]);
   }

Aber mir scheint, das Speicherlayout der Matrix bestimmt hier alles und das kenne ich nicht.

Eisflamme

Ich wiederhole die Frage Mal: Was gehört zum Speicherlayout der Matrix, was ich nicht beschrieben habe? Kann man das überhaupt wissen?

Eisflamme schrieb:

Ich wiederhole die Frage Mal: Was gehört zum Speicherlayout der Matrix, was ich nicht beschrieben habe? Kann man das überhaupt wissen?

um die Pyramide zu speichern? Das ist grottenlahm.

Hast du ein vector<vector<vector<int>>> hast um die Pyramide zu speichern? Das ist noch grottiger.

Pyramiden speichert man in einem vector<int>.
Wenn ich auf x,y,z zugreifen will, berechnet man halt z*z + y*y_max + x (oder so, habs jetzt nicht genauer überlegt).

Der Iterator geht dann einfach von vector.begin() nach vector.end(). Das ist am schnellsten. Nicht, weil it++ so billig zu berechnen ist, sondern weil das perfect im Speicher liegt und ohne Cache-Misses drauf zugegriffen werden kann.

Eisflamme

Ich ging davon aus, dass das aus meinem Text hervorging, aber scheint doch nicht so klar:

vector<int> matrix;

ist so abgelegt. Aber, wie schon gesagt, ändere ich mein Speicherlayout gerne so, dass es optimal ist. Soweit ich das Speicherlayout beeinflussen kann jedenfalls. Die Reihenfolge der Dimensionen ist gerade wie gesagt X1,X2,X3 mit X3 am granularsten, d.h. über X3 kann man via +1 iterieren, das X2-Offset für den Index erhält man durch Multiplikation mit der möglichen Anzahl von X3, X1-Offset durch entsprechend größeren Multiplikator...

Werde ich aber dann so ändern wie es Werner Salomon vorgeschlagen hat, d.h. Reihenfolge zu X1,X3,X2 ändern.

volkard

Eisflamme schrieb:

Ich wiederhole die Frage Mal: Was gehört zum Speicherlayout der Matrix, was ich nicht beschrieben habe? Kann man das überhaupt wissen?

Werden die nichtbenötigten Plätze gespeichert oder nicht? Falls nicht, wie wird der Zugriff gemacht, Hashtable über Indextripel vielleicht? Werden alle nichtbenötigten Plätze gestrichen oder für mehr Performance eine Hybridform gewählt, wie könnte die aussehen? Sind die Indizes x1, x2, x3 sorum da oder lieber x2, x1, x3? Werden x1 und x3 zu einem n=66-(11-x1)*(12-x1)/2+x3 verrechnet? Soll die ganze x1-x3-Schleife, sind ja bloß 66 Durchläufe, normalerweise ausgerollt werden, dann darf die Index-Berechnung auch hübsch teuer sein, passiert ja zur Compilezeit. Warum der Versuch, aus n wieder x1 und x3 zu berechnen, andersrum ist doch viel einfacher. Und was soll überhaupt damit gemacht werden? Iterieren sagste. Wenn dabei x1, x2 und x3 gebraucht werden für eine Rechnung, dann bezweifle ich doch mal stark, daß der Indexzugriff das Teure ist. Noch weiter innere Schleifen voller Plutimikationen? Dann ist der Zugriff egal.

Eisflamme

Werden die nichtbenötigten Plätze gespeichert oder nicht?

Also das geht aber aus meinem OP alles hervor. Da sage ich ja genau, dass weniger gespeichert werden muss, eben 21*66. Und ich beschreibe auch genau, wie ich basierend auf der Zählvariable dann x1,x2,x3 bestimme. Also ja, es werden nur die benötigten Plätze gespeichert.

Sind die Indizes x1, x2, x3 sorum da oder lieber x2, x1, x3?

Siehe mein letzter Post, aber ich habe nun wirklich auch davor schon deutlich gesagt, dass X1,X2,X3 die Reihenfolge ist.

Werden x1 und x3 zu einem n=66-(10-x1)*(11-x1)/2+x3 verrechnet? Warum der Versuch, aus n wieder x1 und x3 zu berechnen?

Ich hab doch explizit dir bereits beantwortet, dass und warum ich von 0 bis N iteriere statt drei einzelne Schleifen zu nutzen: http://www.c-plusplus.net/forum/p2375528#2375528

Und was soll überhaupt damit gemacht werden? Iterieren sagste. Wenn dabei x1, x2 und x3 gebraucht werden für eine Rechnung, dann bezweifle ich doch mal stark, daß der Indexzugriff das Teure ist.

Damit werden Berechnungen angestellt, genau. Aber die sind auch recht trivial, deswegen werden die ebenfalls ziemlich stark optimiert. Teilweise steck ich die sogar in Lookup-Tables, soweit es geht, aber das ist auch schon ne echt feine Optimierung.

knivil

Ganz ehrlich: Ich glaube kaum, dass das Optimieren des Iterationsschema signifikante Verbesserungen bringt, jedenfalls nicht bei 1386 ints. Ausnahme: Man hat sich vorher dumm angestellt.

Desweiteren: Alles hier geschriebene ist Laber-Rhabarber. Nur Messwerte zaehlen.

volkard

Eisflamme schrieb:

Werden die nichtbenötigten Plätze gespeichert oder nicht?

Also das geht aber aus meinem OP alles hervor. Da sage ich ja genau, dass weniger gespeichert werden muss, eben 21*66. Und ich beschreibe auch genau, wie ich basierend auf der Zählvariable dann x1,x2,x3 bestimme. Also ja, es werden nur die benötigten Plätze gespeichert.

Sind die Indizes x1, x2, x3 sorum da oder lieber x2, x1, x3?

Siehe mein letzter Post, aber ich habe nun wirklich auch davor schon deutlich gesagt, dass X1,X2,X3 die Reihenfolge ist.

Werden x1 und x3 zu einem n=66-(10-x1)*(11-x1)/2+x3 verrechnet? Warum der Versuch, aus n wieder x1 und x3 zu berechnen?

Ich hab doch explizit dir bereits beantwortet, dass und warum ich von 0 bis N iteriere statt drei einzelne Schleifen zu nutzen: http://www.c-plusplus.net/forum/p2375528#2375528

Und was soll überhaupt damit gemacht werden? Iterieren sagste. Wenn dabei x1, x2 und x3 gebraucht werden für eine Rechnung, dann bezweifle ich doch mal stark, daß der Indexzugriff das Teure ist.

Damit werden Berechnungen angestellt, genau. Aber die sind auch recht trivial, deswegen werden die ebenfalls ziemlich stark optimiert. Teilweise steck ich die sogar in Lookup-Tables, soweit es geht, aber das ist auch schon ne echt feine Optimierung.

lol

Eisflamme

jedenfalls nicht bei 1386 ints

Ich habe schon ausführlich beschrieben, dass die nicht einmal iteriert werden.

Und wenn ich spürbar zwischen zwei Verfahren einen Unterschied merke, brauche ich nicht messen.

Nach Umsetzung Werners Lösung läuft es schneller. Dankeschön dafür. Was der Rest vom Schützenfest hier wieder fürn Problem hat, weiß ich nicht.

volkard:
?

Schnelles Iterieren über &quot;pyramidale&quot; Matrix

Schnelles Iterieren über "pyramidale" Matrix