do{}while(false); -- ein besseres goto?
-
Echter Progger schrieb:
Ich habe festgestellt, dass echte Programmierer mit Sprüngen in Assembler-Code klar kommen. Das heißt ohne, dass sie Ausschläge, Haarausfall, oder Sonstiges bekommen. Dementsprechend kommen Programmierer auch mit gotos in Hochsprachen klar...
Manche Programmierer versuchen, im Assembler-Code auch so wenig wie möglich Sprünge einzubauen. Weil beim Ausführen eines Sprungbefehls in der CPU die "Pipeline" (was immer man unter der Pipeline versteht) "entleert" und wieder "befüllt" werden muss, was vertane CPU Takte bedeutet.
-
das gilt aber nur unter bestimmten und ungünstigen Umständen, zB wenn die branch-prediction eine bedingte Verzweigung falsch vorhersagt (=> pipeline- und cache-flush). Die branch-prediction units moderner RISC-CPUs können Sprünge schon ziemlich gut vorhersagen und damit pipeline hazards usw vermeiden.
Oder natürlich, wenn die CPU gar keine branch-prediction hat - dann wird die CPU aber eventuell (wahrscheinlich) auch keine pipeline haben, und dann ist es wieder mehr oder minder egal, ob ein Sprung stattfindet oder nicht.
-
@u-ser_l:
Diese ungünstigen Umstände hat man in einigen Fällen recht oft. Bedingte Sprünge die ohne Muster "mal so mal so" ausgehen sind die Hölle.
Da kann es sich auch auf einer CPU mit guter Branch-Prediction auszahlen, Code zu schreiben, der gewisse Branches einspart.
-
sicher, sparen kann man immer was. Aber ich denke, das Thema branch-prediction ist recht gut erforscht - 96-99% korrekte Vorhersagen keine Seltenheit.
Gegen Zufallsbedingtes Verzweigungsverhalten ist natürlich schwierig anzukommen, aber die meisten bedingten Sprünge weisen offensichtlich Verhaltensmuster auf, die für gute Vorhersagen nutzbar sind.
-
96-99% korrekte Vorhersagen keine Seltenheit.
In einem for-loop mit nur 100 Iterationen rate ich einfach immer den Neueintritt in den Loop. Beim letzten Durchgang rate ich einmal falsch. Daraus folgt eine Vorhersagegenauigkeit von 99%, also kein grosses Kunststueck. Was will ich damit sagen? Zeige mir die Tests!
-
u-ser_l schrieb:
sicher, sparen kann man immer was. Aber ich denke, das Thema branch-prediction ist recht gut erforscht - 96-99% korrekte Vorhersagen keine Seltenheit.
Kindchen, das ist in Schleifen kein Wunder. Freu Dich über 99% bei Bubble-Sort und die anderen sind halt traurig über 50% bei Merge-Sort.
-
goto hell;*scnr*
-
ach ja, in jedem thread über 'goto' darf das hier nicht fehlen: http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf
^^witzig, das pdf sieht so aus, als hätte jemand das papier 10 mal durch 'nen kopierer gezogen und dann eingescannt. trotzdem kann man textstellen auswählen und rauskopieren.
-
knivil schrieb:
Was will ich damit sagen? Zeige mir die Tests!
such sie dir doch selber heraus. Es gibt jedenfalls erheblich raffiniertere Strategien als nur zu sagen "Rücksprünge gehören meistens zu Schleifen, also unterstellen wir, daß Rücksprünge stets auch wirklich ausgeführt werden."
-
-
u-ser_l schrieb:
knivil schrieb:
Was will ich damit sagen? Zeige mir die Tests!
such sie dir doch selber heraus. Es gibt jedenfalls erheblich raffiniertere Strategien als nur zu sagen "Rücksprünge gehören meistens zu Schleifen, also unterstellen wir, daß Rücksprünge stets auch wirklich ausgeführt werden."
Und diese Strategien können auch einen Quicksort vorhersagen?
Clamping von beliebigen Eingabedaten?
Das Hinabsteigen in einen Baum zum Huffman Dekodieren?
-
hustbaer schrieb:
Und diese Strategien können auch einen Quicksort vorhersagen?
Clamping von beliebigen Eingabedaten?Na klar! Und auch noch das Wetter von übermorgen.
In der Praxis ist das Verhalten bedingter Sprünge nicht so zufällig, und dies kann man ausnutzen; durch Beobachtung der Vergangenheit und Vorhersage, durch Statistik, durch Heuristik, durch Analyse von Kombinationen verschiedener Sprungstellen im Code usw ...
Daß man selbst mit der besten Taktik keine zufälligen Sprünge oder Verhalten auf unstrukturierte Eingabedaten vorhersagen kann, ist so banal, daß sich eine Antwort darauf verbietet.
In der Praxis zählt halt meistens der average case und nicht der worst case.
-
u-ser_l schrieb:
In der Praxis ist das Verhalten bedingter Sprünge nicht so zufällig, und dies kann man ausnutzen; durch Beobachtung der Vergangenheit und Vorhersage, durch Statistik, durch Heuristik, durch Analyse von Kombinationen verschiedener Sprungstellen im Code usw ...
naja, ich weiss ja nicht ob viele prozessoren so ausgefeilte techniken benutzen. die meisten werden wohl nur statische 'branch prediction' machen. witzigerweise (habs erst letztens irgendwo gelesen) hat multitasking auf single-core CPUs (also wo durch'n timer-interrupt alle paar ms ein taskwechsel stattfindet) kaum 'nen negativen einfluss auf die sprungvorhersage.
btw, auf 'nem ARM7 z.b. verbrät eine 'mis-prediction' bloss 3 taktzyklen, bei 'ner x86-krücke sind's (glaub ich) ganze 20 oder so.
-
@;fricky:
Dass die Effizienz der Sprungvorhersage nicht grossartig durch preemptives Multitasking leidet, liegt einfach daran, dass eine Zeitscheibe für die CPU eine kleine Ewigkeit ist.Die Zeiten wo eine verpatzte Branch-Prediction 20 Zyklen gekostet hat sind AFAIK vorbei. Ich glaube die ganze Pipeline von einem Core 2/i7 ist keine 20 Zyklen mehr lang.
Und zumindest Pentium 3, 4, Core 2, i7, Athlon etc. machen alle ziemlich schlaue Branch-Prediction, mit Muster-Erkennung und allem Pipapo.
---------------------
@u-ser_l:
Touché
-
hustbaer schrieb:
Diese ungünstigen Umstände hat man in einigen Fällen recht oft.
in einigen Fällen recht oft - was jetzt: "in einigen Fällen" oder "recht oft" ?
wie oft ist recht oft nach deiner subjektiven Meinung ?
Ich hoffe, wir wissen beide, daß der Fall vollkommen zufälliger branches in der Praxis selten vorkommt und deshalb moderne branch-predictions einen guten Job machen.
-
u-ser_l schrieb:
Ich hoffe, wir wissen beide, daß der Fall vollkommen zufälliger branches in der Praxis selten vorkommt und deshalb moderne branch-predictions einen guten Job machen.
Klar. In den Sachen wie Sortieren, wo man auf den Rechner warten muß, kommen sie vor und werden nicht optimiert.
In Warteschleifen, wo man endlos Zeit hat, kommen sie auch vor und werden optimiert.
Und natürlich in Kopierschleifen, da würde es aber auch jede statische Optimierung tun.
-
und? deshalb funktioniert branch-prediction jetzt nicht oder was?
-
da behauptet ihr (hustbär und volkard) dann sicherlich auch, Lineare Optimierung funktioniert in der Praxis nicht, weil der Simplex in ungünstigen Fällen ja exponentiell läuft.
uiuiuiuiui ...
-
ps. der letzte Beitrag war ironisch gemeint. Habe leider die <irony on> ... <irony off>-Tags vergessen ...
-
u-ser_l schrieb:
da behauptet ihr (hustbär und volkard) dann sicherlich auch, Lineare Optimierung funktioniert in der Praxis nicht, weil der Simplex in ungünstigen Fällen ja exponentiell läuft.
uiuiuiuiui ...Kannst Du lesen? Dann tu es!
Tip: In meinen Postings stecken Aussagen über Relevanz.
