GOTOs verhindern das RAM-Cachen - ist das richtig?

[SirThornberry]

also ich find das mit den GOTO's kein bischen unübersichtlich. Hab zu Basic zeiten mein Dos-Betriebsaufsatz fast nur mit Goto's verwirklicht anstelle mit schleifen. Und vor kurzem hab ich source von meinem scheff mit goto bekommen und da sieht man auch supi durch, man muss sich eben nur dran gewöhnen das nach einem sprung nicht zum sprungaufruf zurückgekehrt wird wie bei einer funktion

[fiasko]

Hallo,

das mit dem Pipelinen ist zwar ganz schön, da wir aber leider CISC Rechner haben ist das doch nicht soo dolle (Opcodes haben unterschiedliche Länge...) auch wenn man versucht durch Microops den CISC Befehlssatz auf RISC artige Teilbefehle zu zerlegen.

Moderne Prozessoren machen Sprungvorhersagen, das einfachste ist z.B. bei fußgesteuerten Schleifen davon auszugehen das immer zurückgesprungen wird - bei einer For Schleife mit n durchläufen liegt man dann in n-1 Fällen schon mal richtig. Das kann man natürlich noch komplizierter machen, indem man einen Sprungcache aufbaut und anhand von Programmstelle und ein paar weiteren Daten die wahrscheinliche Aktion cached. IA64 macht z.B. wieder einen ganz anderen Ansatz - dort werden beide Entscheidungen gleichberechtigt schon mal weiter berechnet und wenn das Ergebnis der Sprungentscheidung bekannt ist wird das falsche verworfen.


Die Ursprüngliche Aussage halte ich für totalen Quatsch. Ein GOTO ist i.A. erstmal weniger Aufwendig, da hier keine Stackarbeit geleistet werden muß die IMHO ziemlich aufwendig ist.

[schoenf]

Heutige Prozessoren machen schon eine recht ausgeklügelte Branch Prediction um den "wahrscheinlich" zutreffenden Fall bei einem Sprung (egal of if oder goto) vorherzusagen. Die läuft natürlich auch oft genug mit dem Kopf gegen die Wand, sodass die Pipeline geleert und neu gefüllt werden muss. Auf gotos zu verzichten macht nur aus Gründen der Übersichtlichkeit und Lesbarkeit des Codes Sinn - für den Prozessor ist es völlig hacke, ob er aufgrund eines "if", "while" oder "repeat" springen muss oder in irgendeinem Zweig ein "goto" steht.

¡Integrator!

[Robin Oehler]

Hi Leute,

Ihr habt schon alle irgendwie recht....

Also das Anwendungsverfahren das derzeit eingesetzt wird nennt sich Pipelining. Man geht davon aus das wenn Befehl 1 ausgeführt wird werden auch die nachfolgenden Befehle 2 u. 3 usw. ausgeführt und deshalb vorsorglich gecacht.

Da es Schleifen und Sprünge gibt müssen noch Andere Taktiken verfolgt werden.

Eine Taktik ist die Statistik (History).
Mann geht erstens davon aus das XX % vorwärts Sprünge sind und der Rest rückwärtz Sprünge. (vorsorgliches Laden). Problem: Solche Systeme laufen bis zu 60 % optimal bei der Befehlsabarbeitung verursachen aber große Wartezeiten (neuaufbau der Pipeline) bei falschen Laden.

Eine andere Taktik ist das anlegen einer History die ebenfalls statistische Auswertungen vornimmt, aber immer wieder mit neuen Werten gefüllt/bereichert wird.

Es gibt noch andere Abarbeitungsmöglichkeiten, aber die sind mir momentan verfallen.

PS: In jeder Programmiersprache gibt es Sprünge, sie werden oft bei der Fehlerbehebung ("auffangbare Fehler") eingesetzt, erschweren aber die Lesbarkeit des Codes.

Robin

[negaH]

Pipelines haben erstmal reingarnichts mit dem Cache zu tun ! Somit mischt ihr da zwei unterschiedliche Techniken wie man heutzutage die Geschwindigkeit der CPU beschleunigen will.

Während ein Cache versucht den langsammen Flaschenhals zwischen CPU und externem RAM zu beseitigen, versucht man mit Pipelines auf einer sequentiell arbeitenden CPU den Code denoch in quasi-parellel auszuführen. D.h. unterstützt die CPU mehrere Pipelines so heist das nicht anderes als das die CPU die Ausführung der einzelnen Maschinenbefehle erstmal in mehrere Schritte zerlegt. Einmal den Instruction-Decoder und einmal die Arithmetische Recheneinheit. Der Instruction-Decoder kann nun für jede Pipeline separat vorliegen und schon mehrere CPU Takte im Vorhinhein die nächsten abzuarbeitenden Befehle vom RAM anfordern und decodieren. Exakt in diesem Zusammenspiel kommt es nun vor das dieser Decoder der Pipeline auf sogenannte Branches trifft, also Verzweigungen im Programmfluß. Es gibt ZWEI Typen von Verzweigungen, die Bedingten und Unbedingten Branches. GOTOs, CALLs usw. sind Unbedingte Verzweigungen, sie sind also ABSOLUT verhersehbar weil sie IMMER verzweigen. Der Instruction-Decoder der einzelnen Pipelines ist also durchaus in der Lage bei GOTOs oder CALLs schon im vorhinhein den cache mit richtigen Daten zu laden. Dies ist bei bedingten Verzweigungen eben nicht mehr so einfach möglich. Um dies zu umgehen enthalten nun die CPU's eine Branch Prediction, eine Verzweigungs-Wahrscheinlichkeits-Maschine. Diese arbeitet wie ein Cache und merkt sich wohin die CPU beim letzten abarbeiten des Branches gesprungen wurde. Bei nächsten mal nutzt sie diese Informationen um eine bessere Wahrscheinlichkeits-Abschätzung zu treffen. Dies ist natürlich nur technologisch begrenzt möglich, aber denoch kann man Pi*Daumen heute sagen das die Branch-Predictions mit > 75% Wahrscheinlichkeit die RICHTIGE Vorhersagen treffen.

So, all dies hat mit Cacheing erstmal rein garnichts zu tun. Man sieht aber das es für eine CPU aus Geschwindigkeitsaspekten gesehen ein GOTO wesentlich effizienter ist. Ein CALL ist nichts anderes wie ein zweigeteiltes GOTO das die Information wohin man zurückgehren soll nach dem GOTO auf dem Stack speichert. Sogesehen gibt es aus Sicht des Programmflusses erstmal keine großen Unterschiede zwischen GOTOs oder CALLs.

Die Caches wiederum speichern NICHT linear einen EINZIGSTEN Speicerbereich zwischen.Dies wäre ja höchstineffizient. Ganz im Gegenteil der Speicher des Caches wird in sogenannte Cache-Lines aufgeteilt, ca. 256-512 Bytes. In jeder Cacheline kann man nun Daten speicher die sich auf UNTERSCHIEDLICHE Datenbereich im externen RAM beziehen. Zusätzlich werden zu jeder Cacheline verschiedene Informationen, wie das Alter der Daten usw. gespeichert. Anhand dieser Daten kann nun der Cacheprozessor erkennen welche Daten er invalidieren muß, wlche Daten er laden muss oder aktualisieren muß (Multiprozessoren). Somit fordern die Instruction-Decoder jeder Piplines der Haupt-CPU erstmal nur Daten aus dem externen RAM an und stellen dies als Aufgabe an den Cachprozessor durch. Dieser kann dann quasi im Hintergund überprüfen ob der diese Daten schon im internen Speicher hat, ob sie gültig sind oder ob er eine neue Cachline aus dem externen RAM laden muß. Je nachdem kann dies dazu führen das nun 128-512 Bytes aus dem externen RAM geladen werden müssen nur weil 1 Byte benötigt wird oder aber nur weil ein Branche FALSCH vorhergesagt wurde. In jedem Falle MUSS der Instruction-Decoder derjeweiligen Pipelin WARTEN mit der Decodierung der nächsten Instruktion, da ja der Cache nocht NICHT die richtigen Daten enthält. Dieses zusätzliche Warten ist es aber was man mit der Branch-Prediction möglichst vermeiden will.

Fazit: GOTOs sind aus Sicht der CPU der zweit-beste Fall einer Verzweigung=Branches, da sie am effizientesten und schnellsten ausgeführt werden können. Der beste Fall einer Verzeigung ist KEINE Verzweigung. CALLs, also nterprogrammaufrufe sind wesentlich ineffizienter !! Aus dieser Sicht wäre GOTO als Programverzweigung also die beste Wahl überhaupt, WENN man verzweigen muß. Das Augrument des Leherer ist also absolut falsch und das exakte GEGETEIL ist der Fall, GOTOs beschleunigen die Caches.


Gruß Hagen

[Tubos]

Danke für die vielen Antworten!

Allerdings...

Zitat:

Man soll keine GOTOs verwenden, weil man dadurch das korrekte Arbeiten des Caches behindert.

-->

Zitat:

Halte ich für ein Gerücht, damit man sich sowas garnicht erst angewöhnt.

Zitat:

Das ist schon richtig, bezieht sich aber nicht nur auf GOTOs, sondern auf jede Art von Sprüngen, also auch Funktionsaufrufe.

Zitat:

Der Cache kann keinen Sprung vorhersagen, da der Sprung letztendlich vom Prozessor ausgeführt wird

Zitat:

Sprünge werden nicht gecacht, um es einfach auszudrücken. Der Prozessor kann nicht vorahnen, wohin gesprungen wird.

Zitat:

Moderne Prozessoren machen Sprungvorhersagen

Zitat:

Heutige Prozessoren machen schon eine recht ausgeklügelte Branch Prediction um den "wahrscheinlich" zutreffenden Fall bei einem Sprung (egal of if oder goto) vorherzusagen

Zitat:

Das Augrument des Leherer ist also absolut falsch und das exakte GEGETEIL ist der Fall, GOTOs beschleunigen die Caches.

ein paar "ja" und ein paar "nein"
Was stimmt jetzt (wenn möglich mit Quellenangabe)?

[negaH]

Caches machen garnichts, ausser cachen und zu den gecachten Daten deren Gültigkeiten etc. speichern.
Die CPU besteht aus vielen Einzelteilen, eines davon ist die Arithmetische Einheit die nachdem durch den Instruction-Decoder die Befehle dekodiert wurden, die Befehle ausführt.
Moderne CPU's besitzen mehrere Instruction-Decoder sogenannte Pipelines. Jede Pipelin holt sich abwechselnd ihre Befehle aus dem RAM. Der RAM Zugriff wird durch den Cache Controller verwaltet.
Im Cache können verschiedene Daten aus verschiedenen physikalischen Speicherbereichen des externen RAMs zwischengespeichert werden.
Branches sind Verzweigungen innerhalb des Programmes und ändern den Programcounter der CPU.
Unbedingte Branches sind verzeigungen die die CPU immer ausführen wird.
Begingte Branches sind Verzweigungen die an zwei verschiedene Programmadressen verzeigen können. Damit sie verzweigen muß eine bestimmte Bedingung erfüllt sein. D.h. in dem Moment wo verzweigt werden soll müssen die Daten für diese Abfrage vollständig berechnet sein. Zb. die Flags oder Register ECX. Sollten diese Flags/Bedingungen in einer anderen Pipelin dekodiert worden sein so muß die aktuelle Pipeline auf diese warten, ein Stall ist eingetreten. Nachdem alle nötigen Begingung erfüllt sind muß nun die Pipeline und der eventuell der Cache mit neuen Daten gefüllt werden. Sollte dies zutreffen zu muß die Pipeline warten bis alle daten geladen wurden. Stehen die Daten im Cache so wird die Pipline nur mit den Daten aus dem Cache geladen. Stehen die daten nicht im Cache so muß zusätzlich der Cachecontroller die daten aus dem externen RAM laden. Damit nun diese Szenario nicht zu häufig eintritt gibt es eine Branch Prediction = Springziel-Vorhersage. Diese Branchprediction arbeitet direkt mit dem Instructiondecoder der einzelnen Pipelines zusammen und ist ca. 4-5 Maschinenbefehlen im vorhinaus. Nun, nur bei bedingten Spüngen trifft all dieses zu.
Ein GOTO ist ein unbedingter Sprung und somit kann der Instructiondecoder der Pipelines den Cache schon viele Maschenzyklen im Vorhinein mitteilen WAS der Cache zu laden hat. Im allgemeinen liegen die Daten schon längst im Cache wenn der eigentliche Sprung tatsächlich ausgeführt wird.
Ein CALL involviert das Tasksheduller des OS, also auch auf CPU Ebene. Zusätzlich schreibt ein CALL die Returnadresse auf den Stack und dieser befindet sich im externen RAM. Es entsteht also zusätzlich zum GOTO bei einem Funktionsaufruf noch mindestens ein RAM-Schreibzugriff.

Fazit: GOTOs = bedingte Sprünge sind die effizienteste Art und Weise auf heutigen CPU's den Programcounter zu ändern. Sie invalidieren NIEMALS den Cache sondernn sie erzwingen allerhöchsten das Nachladen von daten in den Cache. Eine Invalidation des Caches bedeutet das dieser komplett geleert wird und eventuell Daten gespeichert werden müssen und danach erneut Daten geladen werden.

@Sources die das demonstrieren: Du bist lustig, wie willst du das in Delphi Sourcen demonstrieren auf einem Protected Mode Betriebssystem mit mindestens 100 Task die parallel laufen, mit mindestens 17 Interruptroutinen die auf Ring 0 laufen, wie Timer, Mouse, DMA, Soundkarten, IDE, PCI Bus usw. usw. All diese bedingen die Ausführung von asynchronen Interruptserviceroutinen die dann in deinem Beipielssource permanent dazwischen funken. Wie willst du in den internen CPU Cache hineinschauen ohne diesen durch eigene Assemblerbefehle zu modifizieren. Im übertragenen Sinne gilt hier Heisenbergs Vermutung, der Beobachter verändert durch seine Beobachtungen die Realität !!

Lade dir Intel's VTune, das ist ein Simulator der dir auch die Branchprediction ausrechnet.

Gruß Hagen

[nailor]

Zitat von negaH:

[...]Fazit: GOTOs = bedingte Sprünge sind die effizienteste Art und Weise auf heutigen CPU's den Programcounter zu ändern.[...]

*mööp* da ist nen kleiner verdreher drin.

sicher, das man das nicht testen kann, wenn mans ein paarhundertausendmal durchlaufen lässt. auch mit allem was windwos sonst noch macht?

[negaH]

So aber nun doch Beweise im Source.
GOTO als solches haben primär keinerlei Zusammenhang mit dem Cache. Sie sind Sprachkunstrukte die unabhänig von der Hardware sind.

Zb.

Delphi-Quellcode:

procedure Test;
label
  Finish;
var
  I: Integer;
begin
  goto Finish;
  for I := 0 to 1000 do Application.ProcessMessages;
Finish:
end;

Doll. Das obige GOTO ist im Source existent, aber der Compiler, genauer gesagt der Optimierer des Delphi Compilers erkennt die Sinnlosigkeit des GOTOs und optimert es samt der Schleife einfach weg. Somit steht zwar im Source definiv ein GOTO aber im Compilat steht rein GARNICHTS. Dieses GOTO wird niemals irgendeinen Cache invalidieren, da es KEINERLEI Zusammehang zwischen diesem Sprachkonstrukt und der tatsächlichen Hardware gibt.

Weiter:

Delphi-Quellcode:

begin
  goto Finish;
  goto Do1;
  goto Do2;
Do1:
Do2:
Finish:
end;

Diesmal schalten wir den Optimierer ab. In diesem Falle wird immer vom Goto Finish nach Finish: gesprungen. Wenn dann würde also NUR dieses Goto aber NICHT die Gotos Do1 oder Do2 den Cache invalidieren können. Wiederum gibt es keinen zwingend notwendigen Zusammenhange zwischen dem Sprachkonstrukt GOTO und einem Cache.

Weiter:

Delphi-Quellcode:

sub Test
beginsub
  goto Finish:
  Print "Test"
Finish:
endsub

Diesmal benutzen wir einen BASIC Interpreter auf einem Pentium Computer. Es IST ein Interperter der Life zur Laufzeit den Text "GOTO" parst und diesen als Syntaktischen Interpreter Befehl ausführt indem er den virtuellen Programcounter des BASIC Interpreters neu setzt. Dazu scannt der Intepreter die nächsten Sourcezeilen so lange bis er zum Label Finish: angelangt ist. Erst danach setzt er die Befehls-Interpretation fort. Diesmal gibt es nun KEINELEI Zusammenhänge zwischen bem BASIC Befehl GOTO und dem Cache der CPU.

Und weiter:

Delphi-Quellcode:

begin
  goto Finish;
  for I := 0 to 1000 do Application.ProcessMessages;
  Finish;
end;

Ups,der gleiche Source aber diesmal aus einem Z80 Uralt Copmputer. Wiederum sehen wir das GOTO, und wiederum wurd es nicht wegoptimert und es steht im Compilat ein JUMP Machinencode. NUR, der Z80 hat garkeinen Cache und somit kann dieses GOTO niemals den nichtvorhandenen Cache invalidieren.


Dein Lehrer hat absolut unrecht und kann seine Aussage noch nicht einmal objektiv beweisen !!
Sage ihm das er dir seine Aussage hieb und stich fest beweisen soll, er soll dir live demoonstrieren wie ein GOTO eines BASIC Interpreters auf einem Z80 Computer den nicht vorhandenen Cache ungültig macht.

Gruß Hagen