Fragen zur Geschwindigkeitsoptimierung
-
langi09 schrieb:
Konkret:
lieber x mal auf
alpha[t].k zugreifen
oder lieber
test = alpha[t].k
x mal auf test zugreifen?zusätzlich zum messen auch noch den assembler-output beider varianten anschauen. ist 'alpha' ein pointer, könnte immer noch ein indirekter zugriff mit drinstecken, den du durch die zwischenspeicherung rausschmeissen kannst.
btw, wenn der code-abschnitt zeitkritisch ist, dann versuch mal, aus 'alpha' ein globales array zu machen. wenn du glück hast, rechnet dann schon der compiler struct-member offset und indirektion weg. muss 'alpha' ein pointer sein und du machst C99, dann verwende 'restrict'langi09 schrieb:
Ist eigentlich ein kleinergleich (<=) Vergleich langsamer als ein kleiner (<) Vergleich und wenn ja warum?
normalerweise nicht. bei <= werden zwar in vielen CPUs zwei flags geprüft (subtraktion beeinflusst carry- und zero-flag), aber das passiert gleichzeitig.
sowas wie: if (a < b || a == b), auch wenn a sehr häufig < b ist, als ersatz für <=, bringt natürlich nix *fg*
-
langi09 schrieb:
Ist eigentlich ein kleinergleich (<=) Vergleich langsamer als ein kleiner (<) Vergleich und wenn ja warum?
;fricky schrieb:
normalerweise nicht. bei <= werden zwar in vielen CPUs zwei flags geprüft (subtraktion beeinflusst carry- und zero-flag), aber das passiert gleichzeitig.
sowas wie: if (a < b || a == b), auch wenn a sehr häufig < b ist, als ersatz für <=, bringt natürlich nix *fg*
Mit solch pauschalen Behauptungen bin ich vorsichtiger, hängt von der Architektur ab. Beim 6502 und ähnlichen Akkumaschinen kriegst Du je nach Anordnung a<=b oder a<b schneller raus. Nach dem Vergleich macht man einen branch on carry für die Fälle a>=b bzw a<=b, was nicht gebrancht wird, steht für die Gegenfälle a<b bzw. a>b. Wenn man jedoch im Branch den Fall ausschließen mag, daß a==b ist, muß noch ein branch on (not) equal her.
Das können beileibe nicht alle Compiler optimieren, weil sie dazu eine ausgefuchste Strategie bräuchten, was sie besser im Akku halten und was sie von externen Speicherzellen verwenden, weil ja Umladen auch Zeit kostet.Andererseits macht's selten wirklich viel aus, wenn's nicht gerade in einer Schleife steckt, die möglichst durchrasen soll. Außer bei wenigen Embedded- Prozessoren, für die ich viel Assembler handgeschnitzt habe, sehe ich selten Möglichkeiten zur Handoptimiuerung.
-
pointercrash() schrieb:
langi09 schrieb:
Ist eigentlich ein kleinergleich (<=) Vergleich langsamer als ein kleiner (<) Vergleich und wenn ja warum?
;fricky schrieb:
normalerweise nicht. bei <= werden zwar in vielen CPUs zwei flags geprüft (subtraktion beeinflusst carry- und zero-flag), aber das passiert gleichzeitig.
sowas wie: if (a < b || a == b), auch wenn a sehr häufig < b ist, als ersatz für <=, bringt natürlich nix *fg*Mit solch pauschalen Behauptungen bin ich vorsichtiger, hängt von der Architektur ab.
ja, da hast du natürlich recht. ich hatte eine CPU vor augen, die sowohl einen 'branch on less' als auch einen 'branch on less or equal' kennt.
-
hey...danke schonmal für die zahlreichen antwroten. da ich ein blutiger anfänger bin verstehe ich nur leider so manche sachen nicht:
1. bei <= werden zwar in vielen CPUs zwei flags geprüft (subtraktion beeinflusst carry- und zero-flag), aber das passiert gleichzeitig. Was bedeutet das denn genau?
2. ich hatte eine CPU vor augen, die sowohl einen 'branch on less' als auch einen 'branch on less or equal' kennt. Was ist das für ein branchen von dem ihr redet?
ich hoffe das sind keine allzu doofen fragen.
Zu meiner Frage mit dem alpha-Array:
Inzwischen bin ich doch am überlegen, ob es nicht längert dauert auf alpha[t] zuzugreifen, da während der laufzeit ja immer durch zeigerarithmetik auf das t.-Element des Arrays gesprungen werden muss...
-
langi09 schrieb:
1. bei <= werden zwar in vielen CPUs zwei flags geprüft (subtraktion beeinflusst carry- und zero-flag), aber das passiert gleichzeitig. Was bedeutet das denn genau?
bei vergleichsbefehlen macht 'ne CPU eine subtraktion beider operanden. zusätzlich zum ergebnis werden bestimmte bits in einem sogannten flagregister gesetzt. z.b. a<b wird als a-b gerechnet. wenn a kleiner als b ist, dann gibts bei a-b einen überlauf und das carry-flag wird gesetzt. ist a=b, dann gibt a-b null und das zero-flag wird gesetzt, carry nicht. ist a grösser als b, dann wird keins der beiden flags gesetzt. bei 'nem <= müsste die CPU testen, ob carry- oder zero-flag (also eins von beiden) gesetzt ist. das macht sie, wenn sie entsprechende befehle hat, intern mit 'nem 'or-gatter' (das ist eine kleine elektronische schaltung mit zwei eingängen und einem ausgang, der ausgang geht auf 1, wenn mindestens ein eingang auch 1 ist).
langi09 schrieb:
2. ich hatte eine CPU vor augen, die sowohl einen 'branch on less' als auch einen 'branch on less or equal' kennt. Was ist das für ein branchen von dem ihr redet?
damit sind bedingte sprünge gemeint, die nach zustand der flags (siehe oben) verzweigungen im programm machen, oder nicht. ein 'branch on less' springt nur, wenn das carry-flag gesetzt ist, der 'branch on less or equal' springt, wenn die oben erwähnte oder-verknüpfung von carry- und zero-flag 1 ergibt.
-
;fricky schrieb:
bei vergleichsbefehlen macht 'ne CPU eine subtraktion beider operanden. zusätzlich zum ergebnis werden bestimmte bits in einem sogannten flagregister gesetzt. z.b. a<b wird als a-b gerechnet. wenn a kleiner als b ist, dann gibts bei a-b einen überlauf und das carry-flag wird gesetzt. ist a=b, dann gibt a-b null und das zero-flag wird gesetzt, carry nicht. ist a grösser als b, dann wird keins der beiden flags gesetzt. bei 'nem <= müsste die CPU testen, ob carry- oder zero-flag (also eins von beiden) gesetzt ist. das macht sie, wenn sie entsprechende befehle hat, intern mit 'nem 'or-gatter' (das ist eine kleine elektronische schaltung mit zwei eingängen und einem ausgang, der ausgang geht auf 1, wenn mindestens ein eingang auch 1 ist).
Will jetzt nicht pingelig sein, aber das stimmt so nicht:
Bei der Test-Subtraktion wird der carry zunächst gesetzt, durch die Subtraktion a-b tritt bei a<b ein BORROW ein und carry wird GELÖSCHT, nicht gesetzt. Bei a>=b bleibt der carry bestehen. Exemplarisch hab' ich mal das 6502- CMP herangezogen.
-
pointercrash() schrieb:
Will jetzt nicht pingelig sein, aber das stimmt so nicht...
aber ungefähr, sollte ja kein 6502-assemblerkurs werden. aber gut, dass du erwähnt hast, dass < und > eine 'probe-subtraktion' machen. ich hab' nämlich vergessen zu erzählen, dass das ergebnis verworfen wird (also nur die flags gesetzt werden).
-
langi09 schrieb:
da ich ein blutiger anfänger bin verstehe ich nur leider so manche sachen nicht:
Gerade als "blutiger Anfänger" kannst du davon ausgehen, dass mit sehr hoher Wahrscheinlichkeit das entscheidende Optimierungspotenzial nicht bei solchen Mikrooptimierungen liegt, sondern, wie rüdiger schon gesagt hat, in der Wahl der Algorithmen und Datenstrukturen.
-
MFK schrieb:
Gerade als "blutiger Anfänger" kannst du davon ausgehen, dass mit sehr hoher Wahrscheinlichkeit das entscheidende Optimierungspotenzial nicht bei solchen Mikrooptimierungen liegt, sondern, wie rüdiger schon gesagt hat, in der Wahl der Algorithmen und Datenstrukturen.
Das widerspricht holistischer Denkweise und fordert Erziehung zum Fachidioten für Algorithmen. Natürlich darf sich jeder zu jedem Wissensstand darüber Gedanken machen, was ihm im Endeffekt an Ressourcen zur Verfügung steht. Nur, wenn man beide Seiten kennt und berücksichtigt, führt das zu genialen Geistesblitzen wie z.B. den Cordic- Automaten und anderen Abkürzungen (FFT).
Hätte man unendliche Rechenleistung, wäre beides wohl nie entwickelt worden, aber geniale Algorithmen entstanden überwiegend aus der Not, bestehende Rechenleistung optimal ausnutzen zu müssen.
-
pointercrash() schrieb:
Das widerspricht holistischer Denkweise und fordert Erziehung zum Fachidioten für Algorithmen.
Kann es sein, dass du in meinen Hinweis etwas hineininterpretierst? Ich habe gar nichts gefordert.
-
MFK schrieb:
pointercrash() schrieb:
Das widerspricht holistischer Denkweise und fordert Erziehung zum Fachidioten für Algorithmen.
Kann es sein, dass du in meinen Hinweis etwas hineininterpretierst? Ich habe gar nichts gefordert.
Ganz klares Jein. Mich stört das "wird der Compiler schon machen, denk' jetzt nicht drüber nach, sondern lern' erstmal programmieren". Ich bin der Meinung, daß man so früh wie möglich über den Tellerrand rausgucken sollte.
;fricky schrieb:
aber ungefähr, sollte ja kein 6502-assemblerkurs werden.
Ich hab' nie darüber nachgedacht, ob es andersrum Sinn machen könnte und meine ALUs immer mit der konventionellen Carry- Logik versehen und 'nen CLA (carry- look- ahead) von den Templates geripped. Auch wenn ich ein bisserl in den OpenCores stöbere, ich finde kein Gegenbeispiel, eher gelegentlich falsche Dokus. Ist also nicht 6502- spezifisch, carry wird immer bei carry/borrow durch den CLA getoggelt und vor'm Testen gesetzt, also brauch' ich nach dem Rest nimmer zu gucken. Carry ist eine positive Borge/Überlauf- Eins.
-
pointercrash() schrieb:
Mich stört das "wird der Compiler schon machen, denk' jetzt nicht drüber nach, sondern lern' erstmal programmieren".
Ich weiß beim besten Willen nicht, wo du das herausliest. Ich habe nur darauf hingewiesen, wo bei Anfängern das größte Optimierungspotenzial liegt. Und nach meiner Erfahrung kann man selten durch Anpassungen auf Assemblerebene so viel herausholen wie durch geschicktes Umstellen des Codes.
pointercrash() schrieb:
Ich bin der Meinung, daß man so früh wie möglich über den Tellerrand rausgucken sollte.
Nach welchen Kriterien teilst du denn Optimierungsmöglichkeiten danach ein, ob sie im Teller oder außerhalb liegen?
Warum ist das geschickte Ausnutzen von CPU-Flags jenseits des Tellerrandes, und das Wissen, wann man statt einer linearen eine binäre Suche benutzen kann, diesseits?
Mir scheint diese Einteilung willkürlich.
-
pointercrash() schrieb:
Ist also nicht 6502- spezifisch, carry wird immer bei carry/borrow durch den CLA getoggelt und vor'm Testen gesetzt, also brauch' ich nach dem Rest nimmer zu gucken. Carry ist eine positive Borge/Überlauf- Eins.
nun sei doch nicht so pingelig, so kennt man dich ja garnicht. *fg* umgekehrt würde es genauso funktionieren, viel digitales zeug arbeitet mit invertierter logik. und ob der befehl 'branch on greater' sich an einer 0 oder 1 im flag orientiert, ist doch wumpe, solange der asm-coder das weiss.
-
MFK schrieb:
... Ich habe nur darauf hingewiesen, wo bei Anfängern das größte Optimierungspotenzial liegt. Und nach meiner Erfahrung kann man selten durch Anpassungen auf Assemblerebene so viel herausholen wie durch geschicktes Umstellen des Codes.
Der OP hatte nach Möglichkeiten der Speed- Optimierung gefragt, dazu zählt der Gebrauch schlauer Algorithmen genauso, wie mal ein Blick auf den ASM- Output.
MFK schrieb:
Nach welchen Kriterien teilst du denn Optimierungsmöglichkeiten danach ein, ob sie im Teller oder außerhalb liegen?
Was dem Progger sofort einfällt, ist Teller. Der OP hat ja gefragt, ob >= oder > schneller läuft, wir haben korrekt geantwortet, daß das auf die Hardware ankommt, in dem Zug ist "kümmer' Dich besser um Algorithmen" nicht unbedingt ein Kreativbeitrag.
Wobei man das Thema beliebig verkomplizieren könnte, wenn man noch über branch prediction, queue wasting usw. zu philosophieren anfängt.MFK schrieb:
Warum ist das geschickte Ausnutzen von CPU-Flags jenseits des Tellerrandes, und das Wissen, wann man statt einer linearen eine binäre Suche benutzen kann, diesseits?
Beides kann man erwähnen, aber der OP hatte nur nach >= und > gefragt.
;fricky schrieb:
nun sei doch nicht so pingelig, so kennt man dich ja garnicht. *fg* umgekehrt würde es genauso funktionieren, viel digitales zeug arbeitet mit invertierter logik. und ob der befehl 'branch on greater' sich an einer 0 oder 1 im flag orientiert, ist doch wumpe, solange der asm-coder das weiss.
Beim CMOPS isses in jeder Hinsicht egal, ich glaube, bei ECL hat man ganz gerne die Logik umgedreht, aber logisch war trotzdem Carry bei Überlauf eins. Lassen wir das Carry doch einfach das 9., 17. 33. usw. Bit eines Rechenwerks sein.
Erinnert mich an eine Vorlesung in Digitaltechnik (5.Sem.), wo der Prof gefragt hat, ob es sinnvoller ist, logisch "1" als "Hi" zu definieren oder als "Low" und ein Studi ernsthaft gemeint hat, "besser als Low, damit sich die Bits nicht so schnell abnutzen".
Hat einige Zeit gedauert, bis sich die Letzten vor Lachen wieder eingekriegt haben ...
-
langi09 schrieb:
Zu meiner Frage mit dem alpha-Array:
Inzwischen bin ich doch am überlegen, ob es nicht längert dauert auf alpha[t] zuzugreifen, da während der laufzeit ja immer durch zeigerarithmetik auf das t.-Element des Arrays gesprungen werden muss...ich persönlich denke, dass die Auslagerung (temp = array[x]; ...) vielleicht besser wäre. Es ist wahrscheinlich, dass der Wert in einem Register der CPU festgehalten wird, wodurch kein Zugriff auf den Speicher mehr notwendig ist. Aber wie die anderen schon sagten, du musste es messen bzw. den ASM-output vergleichen.
-
pointercrash() schrieb:
Der OP hatte nach Möglichkeiten der Speed- Optimierung gefragt, dazu zählt der Gebrauch schlauer Algorithmen genauso, wie mal ein Blick auf den ASM- Output.
Und ich habe darauf hingewiesen, wo meiner Meinung nach mehr rauszuholen ist. Vielleicht hast du da andere Erfahrungswerte mit Anfängercode, mag ja sein.
pointercrash() schrieb:
MFK schrieb:
Nach welchen Kriterien teilst du denn Optimierungsmöglichkeiten danach ein, ob sie im Teller oder außerhalb liegen?
Was dem Progger sofort einfällt, ist Teller. Der OP hat ja gefragt, ob >= oder > schneller läuft, wir haben korrekt geantwortet, daß das auf die Hardware ankommt, in dem Zug ist "kümmer' Dich besser um Algorithmen" nicht unbedingt ein Kreativbeitrag.
Dann soll also mein Vorschlag jenseits des Tellerrandes sein? Dann musst du mir mal erklären, wie du es gemeint hast, dass "man so früh wie möglich über den Tellerrand rausgucken sollte." Denn das ist dann ja genau das, was ich getan habe.
pointercrash() schrieb:
MFK schrieb:
Warum ist das geschickte Ausnutzen von CPU-Flags jenseits des Tellerrandes, und das Wissen, wann man statt einer linearen eine binäre Suche benutzen kann, diesseits?
Beides kann man erwähnen, aber der OP hatte nur nach >= und > gefragt.
Richtig. Aber man sollte ja auch den OP darauf hinweisen, dass es noch andere Optimierungsmöglichkeiten gibt. Sozusagen ein Blick über den Tellerrand.