Profiling: Performanceloch gefunden, wie gehts weiter?

SeppJ

Will denn niemand darauf aufmerksam machen, dass du gerade ausgerechnet den Teil des Codes optimieren möchtest, wo dies am wenigsten bringt? Selbst wenn du es schaffst die Funktion doppelt so schnell zu machen wie vorher (was eine unglaubliche Topoptimierung wäre, für die man sicherlich viele Mannmonate Entwicklung bräuchte, falls sie überhaupt möglich ist), würdest du bloß 5 Sekunden gewinnen. Bei dem anderen Codeabschnitt bräuchtest du für den gleichen Gewinn bloß 5% Leistungssteigerung, welche man sogar realistisch mit billigen Tricks, z.B. besser angepassten Compileroptionen, erreichen kann.

rapso

otze schrieb:

float entry(unsigned long i , unsigned long j){
    return rbfkernel->eval(*x[i],*x[j]);
}

entweder entry oder eval sollte inlined sein, falls dem nicht ist, kann es sein, dass beides virtual functions sind? in dem fall kann dich ein aufruf ca 10 bis 20 cycle kosten, da es wie ein branch miss ist, das solltest du versuchen zu umgehen.
es koennten zwar auch cache misses sein, aber 2.9Mrd auf einem 3GHz prozessor und 10cycle/aufruf -> ~10s, mit cache misses waerst du bei 70s bis 100s denke ich.

Ich habe einige mögliche Ansätze, aber ich kann jetzt schlecht im Nebel stochern. Gibt es eventuell Tools, die mir genauer auflösen, wo jetzt was die Zeit verschlingt?
Ich benutze gcc.

ich weiss garnicht wie man mit sowas wie gprof arbeiten kann, das waere wie ein debugger der dir nur den thread angibt in dem dein programm abstuertzt und dann stochert man blind rum. du brauchst definitiv einen richtigen profiler!
versuch AMD codeanalyst oder falls du auf linux unterwegs bist, sollte auch Intel vtune kostenlos nutzbar sein (wobei das ein wenig aufwendiger zu durchschauen ist aufgrund der unmengen an daten die die presentieren).

rapso

SeppJ schrieb:

Will denn niemand darauf aufmerksam machen, dass du gerade ausgerechnet den Teil des Codes optimieren möchtest, wo dies am wenigsten bringt? Selbst wenn du es schaffst die Funktion doppelt so schnell zu machen wie vorher (was eine unglaubliche Topoptimierung wäre, für die man sicherlich viele Mannmonate Entwicklung bräuchte, falls sie überhaupt möglich ist), würdest du bloß 5 Sekunden gewinnen. Bei dem anderen Codeabschnitt bräuchtest du für den gleichen Gewinn bloß 5% Leistungssteigerung, welche man sogar realistisch mit billigen Tricks, z.B. besser angepassten Compileroptionen, erreichen kann.

der punkt ist, dass diese funktion 0s ziehen sollte, da der compiler die wegoptimiert. wenn er also 25s hinter der referenzimplementierung ist und 2 funktionen hat die je 10s ziehen, aber eigentlich 0s ziehen sollten, ist es ein guter punkt sich das anzuschauen. es ist mehr ein 'bugfix' als eine optimierung.
(beim optimieren sollte man erstmal die dummheiten wegbekommen die einen 1min arbeit kosten und dann an die funktionen gehen die 90% der laufzeit und tage/wochen an arbeit werden).

hustbaer

otze schrieb:

Hmm da fängts ja an. Ich weiß nicht, wie ich den Assembler von nur dieser einen Funktion kriege...

Ich arbeite nicht mit GCC, aber vielleicht geht es da ja ähnlich. (Ich würde mich sogar halbwegs wundern wenn nicht.)

Mit MSVC geht es so (EIN möglicher Weg):
* Release-Build mit Debug-Symbolen erstellen
* Release-Build im Debugger starten
* Breakpoint in die Funktion setzen und warten bis er anhält
* Disassembly Fenster aufmachen
-> Tadaa

hustbaer

otze schrieb:

Warum nicht geinlined wird, gute Frage, aber ich vertraue dem Compiler mal soweit, dass ich da nichts erzwingen werde.

Vielleicht sieht er die Implementierung nicht, und LTCG ist nicht an?
Guck auf jeden Fall zu dass solche Funktionen direkt im Header-File implementiert werden.

otze schrieb:

trotzdem ist der RBf-Kern in dem Fall auch virtual(und wir habn ungefähr 20 verschiedene Kerne zwischen denen wir dispatchen, tendenz rasant steigend), aber das kostet irgendwie nicht viel.

Da wär' ich mir mal nicht so sicher.
Geh mal davon aus dass virtual für den Compiler ein schwarzes Loch ist. Demzufolge muss er auch damit rechnen dass die virtuelle Funktion alles erdenkliche ändert was sie theoretisch nur ändern könnte (und natürlich auch alles liest was sie nur lesen kann).

Das führt oft dazu dass Dinge vor dem Aufruf einer virtuellen Funktion in den Speicher zurückgeschrieben werden, und danach wieder neu aus dem Speicher geladen werden, obwohl sich an denen nie im Leben was ändern kann. Weil der Compiler es eben nicht wissen kann.

otze

SeppJ schrieb:

Will denn niemand darauf aufmerksam machen, dass du gerade ausgerechnet den Teil des Codes optimieren möchtest, wo dies am wenigsten bringt? Selbst wenn du es schaffst die Funktion doppelt so schnell zu machen wie vorher (was eine unglaubliche Topoptimierung wäre, für die man sicherlich viele Mannmonate Entwicklung bräuchte, falls sie überhaupt möglich ist), würdest du bloß 5 Sekunden gewinnen. Bei dem anderen Codeabschnitt bräuchtest du für den gleichen Gewinn bloß 5% Leistungssteigerung, welche man sogar realistisch mit billigen Tricks, z.B. besser angepassten Compileroptionen, erreichen kann.

Stop Stop Stop. Der Profiler sagt, dass dies die Funktion ist, in der 90% der Rechenzeit stecken bleibt. Die andere Funktion die da aufgerufen wird, ist todoptimiert. Der RBFKern ist nicht mehr als exp(-||x-y||^2) mit spärlichen Vektoren. Die Optimierungsmöglichkeiten sind da echt begrenzt. Uns trennen auch nur 20% Prozent von der Referenzimplementierung und ich habe Grund zur Annahme, dass diese paar Prozent in den 20 Sekunden stecken, die zwischen entry und eval verballert werden. Nur so als Beispiel: würde der Compiler inlinen und raffen, dass er 32000mal hintereinander das selbe Ergebnis für *x[i] erhält und das Ergebnis nicht verwerfen, dann würde es uns direkt 5 Sekunden liefern. Jetzt muss ich das eben selbst machen...

@rapso
Es ist ein v-call dabei. Aber kostet das wirklich soviel? ich würde ja vermuten, dass nur der erste call so viel kostet und die weiteren calls danach nur noch soviel wie ein normaler Funktionsaufruf kosten. Wenn nicht: könnte ich das mit Funktionszeigern umgehen? Also direkt die Adresse der virtuellen Funktion holen, die vtable damit umgehen und somit das tun, was ich eigentlich gehofft hatte, dass es der Compiler tut? Würde es sich lohnen, das zu profilen?

Ich schau mir mal vtune an.

@hustbaer die implementation sieht er, da es in dem Bereich nur so von templates wuchert. Aber die Funktion ist nicht so lieb und nett, wie sie aussieht. So ein *x[i] ist eher etwas wie:

SparseMatrix const& m = x[i]->matrix;
//compressedStorage holt sich die Zeiger auf den Speicherbereich der matrixzeile
CompressedStorage storage = compressedStorage(m.row(x[i].matrixRow));
VectorProxy prox(storage,r.size());

und compressedStorage sind wiederum so 10 Zeilen code.

und ich werde mir deinen Kommntar zu virtual nochmal durch den Kopf gehen lassen.

volkard

Ich weiß ja nicht. Aber ich tippe mal auf schlechtere Cache-Lokalität und mehr Kollissionen in der Hashtable.

wenn der compiler nicht inlined. Hast du auch wirklich alle optimierungen an?

otze

Kleines Update:

volkard schrieb:

Ich weiß ja nicht. Aber ich tippe mal auf schlechtere Cache-Lokalität und mehr Kollissionen in der Hashtable.

Das kann ich ausschließen. Wenn überhaupt, dann haben wir eine leicht bessere Cache-Lokalität. Wir speichern immer mehrere sparse-vektoren am Stück im als Matrix im Speicher, und die calls *x[i] friemeln sich dann den Anfang einer Matrixzeile aus dem Array. Ich glaube einfach, dass das rausfriemeln zu lange dauert. Mit dichten Vektoren reduziert sich der Overhead nahe gegen 0, da ist aber auch das indizieren der Matrixzeilen auch nur eine Addition auf den Offset.

ich habe jetzt einmal der Kernmatrix folgende Methode spendiert:

void row(std::size_t i, float* storage){
    VectorProxy xi= *x[i];
    for(std::size_t j = 0; j != size(); ++j){
        storage[i] = rbfkernel->eval(xi,*x[j]);
    }
}

und den Aufrufercode entsprechend modifiziert. Das Resultat hat mich erstaunt: 1. die FUnktion wurde geinlined, 2. ich habe ca 10 Sekunden Laufzeit gespart, also 50% des gesamten overheads. Das korreliert ziemlich gut damit, dass ich 50% der Zeilen-rausfriemel-operationen entfernt habe. Ich werde also als nächstes diese Operation etwas optimieren.

rapso

otze schrieb:

Es ist ein v-call dabei. Aber kostet das wirklich soviel? ich würde ja vermuten, dass nur der erste call so viel kostet und die weiteren calls danach nur noch soviel wie ein normaler Funktionsaufruf kosten.

fuer den compiler bzw prozessor ist es immer eine addresse auslesen und danach diese zum springen nutzen, bis das lesen fertig ist, laeuft die pipeline also durch, das sind bei neusten i7 ca 14cycles. seit zwei generationen gibt es da wohl ein paar optimierungen, aber ganz bekommt man die nicht weg. du hast also die kosten wie bei einem branch mit falscher vorhersage, was sich nicht sondelrich aendern laesst.

Wenn nicht: könnte ich das mit Funktionszeigern umgehen?

ein wenig, statt

function[vtable[this]+functionIdx]();

haettest du dann wohl nur

function[functionIdx]();

aber falls du wuestest, dass eine der spezialisierungen besonders oft vorkommt, koenntest du das mit einem 'if' loesen, das wuerde viel bringen.

Würde es sich lohnen, das zu profilen?

profilen wird sich immer lohnen, lass code analyst oder vtune laufen, was du da an zeit investierst, sparst du sicherlich indem du unnuetze optimierungen ausschliesst. zu wissen ob du cache, branch, alu, fpu etc. limitiert bist, hilft sehr zu entscheiden was fuer eine optimierung die nuetzlichste ist. am ende kann auch eine schlecht optimierung performance bringen, aber du weisst nie, ob das das beste war was du machen konntest, ob das wirklich das problem loeste und wie weit du noch vom optimum entfernt bist.

und wie "nurmalso" sagte, sicher dass alle optimierungen an sind? fall ja, muss da mehr geinlined sein. pack notfalls __attribute__((always_inline)) vor die kritischen funktionen.

ein compiler kann zwar statistiken haben wie was optimiert werden soll, aber kann nie wissen welche 10% von deinem code die 90% performance ausmachen, entsprechend inlinen die nur so, dass sie nicht schlimmer machen im worst case. du musst ihnen ein paar hintes geben und die optimierungsflags anschauen.

geh auch sicher dass die "translation unit" die das inlinen soll die implementierung sieht, nicht nur die deklaration.