Frage

Ich kann für das Leben von mir nicht, daran erinnern, was genau unser Lehrer an diesem Tag gesagt und ich bin die Hoffnung, würden Sie wahrscheinlich wissen.

Das Modul ist „Datenstrukturen und Algorithmen“ und er sagte uns etwas entlang der Linien von:

  

Die if Aussage ist die teuerste   [etwas]. [Etwas] Register   [Etwas].

Ja, ich eine schreckliche Erinnerung habe, und ich bin wirklich, wirklich leid, aber ich habe stundenlang googeln und nichts kommen. Irgendwelche Ideen?

War es hilfreich?

Lösung

Auf der untersten Ebene (in der Hardware), ja, , wenn s sind teuer. Um zu verstehen, warum, müssen Sie verstehen, wie Pipelines Arbeit.

Der aktuelle Befehl ausgeführt werden soll, in etwas gespeichert typischerweise die Befehlszeiger genannt (IP) oder Programmzähler (PC); diese Begriffe sind synonym, aber unterschiedliche Begriffe mit unterschiedlichen Architekturen verwendet. Für die meisten Befehle ist der PC der nächsten Anweisung nur der aktuelle PC plus die Länge der aktuellen Anweisung. Für die meisten RISC-Architekturen, Anweisungen sind alle eine konstante Länge, so kann der PC um einen konstanten Betrag erhöht werden. Für CISC-Architekturen wie x86, Befehle können mit variabler Länge sein, so die Logik, die die Anweisung decodiert hat, um herauszufinden, wie lange der aktuelle Befehl den Standort des nächsten Befehls zu finden.

Für Zweig Anweisungen, aber der nächste Befehl ausgeführt werden soll, nicht die nächste Stelle nach der aktuellen Anweisung. Die Zweige sind gotos - sie sagen, den Prozessor, wo der nächste Befehl. Zweige können entweder bedingt oder unbedingt, und der Zielort kann entweder fest oder berechnet werden.

Bedingte vs. bedingungslos ist leicht zu verstehen - eine bedingte Verzweigung nur dann, wenn eine bestimmte Bedingung erfüllt genommen wird (wie zum Beispiel, ob eine Zahl gleich einen anderen); wenn die Verzweigung nicht genommen wird, geht die Steuerung auf den nächsten Befehl nach der Verzweigung wie normal. Für unbedingte Verzweigungen wird der Zweig immer genommen. Bedingte Verzweigungen zeigen in if-Anweisungen und die Kontrolltests der for while und Schleifen auf. Unbedingte Verzweigungen zeigen in Endlosschleifen, Funktionsaufrufen, Funktion zurück, break und continue Aussagen, die berüchtigten goto Aussage auf, und viele mehr (diese Listen sind bei weitem nicht erschöpfend).

Das Zweigziel ist ein weiteres wichtiges Thema. Die meisten Filialen haben eine feste Niederlassung Ziel - sie gehen zu einer bestimmten Stelle im Code, die zum Zeitpunkt der Kompilierung festgelegt ist. Dazu gehört if Anweisungen, Schleifen aller Art, regelmäßige Funktionsaufrufe, und vieles mehr. Computed Filialen das Ziel der Branche zur Laufzeit berechnen. Dazu gehören switch Aussagen (manchmal), aus einer Funktion, virtuelle Funktionsaufrufe zurückkehren und Funktionszeiger Anrufe.

Also, was bedeutet das alles für die Leistung bedeuten? Wenn der Prozessor eine Verzweigungsanweisung erscheinen in seiner Pipeline sieht, braucht es, um herauszufinden, wie sie ihre Pipeline zu füllen, um fortzufahren. Um herauszufinden, was kommen Anweisungen nach der Verzweigung in dem Programmstrom, braucht es zwei Dinge wissen: (1), wenn der Zweig der Verzweigung genommen und (2) das Ziel sein. Herauszufinden this out ist Verzweigungsvorhersage genannt, und es ist ein schwieriges Problem. Wenn der Prozessor korrekt errät, wird das Programm mit voller Geschwindigkeit. Wenn stattdessen der Prozessor Vermutungen falsch , es ist nur etwas Zeit, die Berechnung der falsche Sache ausgegeben. Es hat jetzt seine Pipeline und legen Sie es mit Anweisungen von dem richtigen Ausführungspfad zu spülen. Unterm Strich: a. Performance-Einbruch

So der Grund, warum, wenn Aussagen teuer sind, ist aufgrund Verzweigungsfehlvorhersagen . Dies ist nur auf der untersten Ebene. Wenn Sie High-Level-Code schreiben, müssen Sie nicht über diese Details überhaupt kümmern. Sie sollten nur für diese interessieren, wenn Sie extrem leistungskritischen Code in C oder Assembler zu schreiben. Wenn das der Fall ist, kann astfreien das Schreiben von Code oft überlegen sein zu codieren, dass Äste, auch wenn mehrere Anweisungen benötigt werden. Es gibt ein paar coole Bit-twiddling Tricks, die Sie Dinge zu berechnen tun können, um wie abs(), min() und max() ohne Verzweigung.

Andere Tipps

„teuer“ ist ein sehr relativer Begriff, vor allem mit Beziehung zu einer „if“ Aussage, da Sie auch die Kosten für den Zustand in die Rechnung tragen müssen. Das könnte überall von ein paar kurzen CPU-Anweisungen zu testen das Ergebnis einer Funktion reichen, die zu einer entfernten Datenbank ruft.

Ich würde mir keine Sorgen. Es sei denn, Sie Embedded-Programmierung zu tun sollten Sie wahrscheinlich nicht über die Kosten der „if“ betroffen sein, überhaupt. Für die meisten Programmierer es geht um nicht nur zu immer der treibende Faktor in Ihrem App Leistung.

Branchen, vor allem auf RISC-Architektur Mikroprozessoren, sind einige der teuersten Anweisungen. Dies liegt daran, auf vielen Architekturen, prognostiziert der Compiler, welchen Weg der Ausführung höchstwahrscheinlich genommen wird, und legt diese Anweisungen als nächstes in der ausführbaren Datei, so werden sie bereits in der CPU-Cache sein, wenn die Verzweigung passiert. Wenn die Verzweigung in die andere Richtung geht, hat es wieder aus dem Hauptspeicher zu gehen und die neuen Anweisungen holen - das ist ziemlich teuer. Auf vielen RISC-Architekturen sind alle Anweisungen eines Zyklus mit Ausnahme Zweig (die 2 Zyklen oft ist). Wir reden hier nicht über eine große Kosten hier, also keine Sorge darüber. Außerdem wird der Compiler optimiert besser, als Sie 99% der Zeit :) Einer der wirklich genial Dinge über die EPIC-Architektur zu tun (Itanium ist ein Beispiel) ist, dass es Caches (und beginne mit der Verarbeitung) Anweisungen von beiden Seiten der Branche, dann verwirft den Satz es muss nicht einmal das Ergebnis der Branche bekannt ist. Das spart den zusätzlichen Speicherzugriff einer typischen Architektur in dem Fall, dass es Zweige entlang dem unpredicted Weges.

den Artikel Schauen Sie sich eine bessere Performance durch die Zweig Elimination auf die Leistung der Zelle . Ein weiterer Spaß ist dieser Beitrag zu branchless Auswahl auf der Echtzeit Kollisionserkennung Blog.

Neben den hervorragenden Antworten gepostet bereits als Antwort auf diese Frage, würde Ich mag in Erinnerung bringen, dass, obwohl „wenn“ Aussagen angesehen werden teure Low-Level-Operationen, versuchte astfreien Programmiertechniken in einem nutzen höhere Ebene Umgebung, wie eine Skriptsprache oder eine Business-Logik-Schicht (unabhängig von der Sprache), kann lächerlich ungeeignet sein.

Die überwiegende Mehrheit der Zeit, sollten Programme für Klarheit geschrieben werden erste und für die Leistung zweite optimiert. Es gibt zahlreiche Problembereiche in denen die Leistung im Vordergrund steht, sondern die einfache Tatsache ist, dass die meisten Entwickler nicht Module für den Einsatz Schreiben tief in dem Kern eines Rendering-Engine oder eine Hochleistungs-Fluiddynamik-Simulation, die wochenlang läuft. Wenn die oberste Priorität für die Lösung ist „einfach funktionieren“ das letzte, was auf Ihrem Verstand soll sein, ob Sie auf dem Overhead einer bedingten Anweisung in Ihrem Code speichern.

Auf der untersten möglichen Ebene if besteht aus (nach allen App spezifischen Voraussetzungen für bestimmte if computing):

  • einige Testbefehl
  • Sprung zu einem gewissen Stelle im Code, wenn der Test erfolgreich ist, geht nach vorne sonst.

Kosten im Zusammenhang mit, dass:

  • ein niedriges Niveau Vergleich - in der Regel 1 CPU-Betrieb, super billig
  • Potentialsprung - das kann teuer werden

Reson, warum Sprünge sind teuer:

  • Sie können zu arbirary Code springen, die überall in Erinnerung lebt, wenn es sich herausstellt, dass es nicht von der CPU zwischengespeichert wird - wir haben ein Problem, weil wir den Hauptspeicher zugreifen müssen, die langsamer ist
  • moderner CPUs tut Zweig predition. Sie versuchen zu erraten, ob, wenn erfolgreich sein wird oder nicht, und Ausführen von Code voraus in der Pipeline, so beschleunigen Dinge. Wenn die Vorhersage alle Berechnung voraus hat durch Pipeline erfolgt nicht für ungültig erklärt werden. Auch das ist eine teuere Operation

So zusammenzufassen:

  • Wenn kann expesive sein, wenn Sie wirklich, wirklich, egal relly über die Leistung.
  • Sie sollten darum kümmern , wenn und nur wenn Sie Echtzeit-Raytracer oder biologische Simulation oder ähnliches schreiben. Es gibt keinen Grund, sich um es in den meisten der realen Welt zu sorgen.

if an sich nicht langsam. Langsamkeit ist immer relativ i für mein Leben wetten, dass Sie nicht immer den „Overhead“ einer if-Anweisung zu spüren. Wenn Sie ein High-Performance-Code machen sind, migh wollen Sie Zweige sowieso zu vermeiden. Was if langsam macht, ist, dass der Prozessor-Code aus, nachdem die if auf einige heuristische und so weiter basiert Vorbelastung. Es wird auch Pipelines von Ausführung von Code direkt nach dem if Verzweigungsbefehl in dem Maschinencode zu stoppen, da der Prozessor noch nicht weiß, welcher Weg (in einem Pipeline-Prozessor, mehr Befehle verschachtelt sind und ausgeführt) getroffen werden. Code ausgeführt könnte umgekehrt ausgeführt werden müssen (wenn der andere Zweig genommen wurde. Es heißt branch misprediction) oder noop die an den Stellen gefüllt werden, so dass dies nicht geschieht.

Wenn if böse ist, dann ist switch zu böse und &&, || auch. Mach dir keine Sorgen darüber.

Vielleicht tötet die Verzweigung der CPU Befehlsvorabrufgeräts?

Moderne Prozessoren haben lange Ausführungs-Pipelines, die bedeuten, dass mehrere Befehle in verschiedenen Stufen zur gleichen Zeit ausgeführt werden. Sie können nicht immer wissen, das Ergebnis eines Befehls, wenn die nächste zu laufen beginnt. Wenn sie in einen bedingten Sprung laufen (wenn) sie müssen manchmal warten, bis die Pipeline leer ist, bevor sie wissen können, sollte die Art und Weise der Befehlszeiger gehen.

Ich denke, es als ein langer Güterzug. Es kann eine Menge Fracht schnell in einer geraden Linie tragen, aber es Ecken schlecht.

Pentium 4 (Prescott) hatte eine berühmte lange Pipeline von 31 Stufen.

Mehr Wikipedia

Das einzige, was ich mir vorstellen kann dies könnte zu beziehen, ist die Tatsache, dass eine if Aussage im Allgemeinen in einem Zweig führen kann. In Abhängigkeit von den Besonderheiten der Prozessorarchitektur kann Zweig Pipeline-Blockierungen verursachen oder andere suboptimale Situationen.

Dies ist jedoch extrem Situation spezifisch ist - die meisten modernen Prozessoren haben Verzweigungsvorhersagefunktionen, die die negativen Auswirkungen der Verzweigung zu minimieren versuchen. Ein weiteres Beispiel wäre, wie die ARM-Architektur (und wahrscheinlich noch anderen) bedingte Logik umgehen können - die ARM-Befehlsebene bedingte Ausführung hat, so einfache bedingte Logik führt zu keiner Verzweigung -. Die Anweisungen einfach als NOPs ausgeführt werden, wenn die Bedingungen nicht erfüllt sind,

Alles, was gesagt - erhalten Sie Ihre Logik korrekt ist, bevor über diese Dinge zu kümmern. Falscher Code ist als unoptimized wie Sie bekommen können.

Wie von vielen, bedingten Verzweigungen darauf hingewiesen, kann auf einem modernen Computer sehr langsam sein.

Davon abgesehen, gibt es eine ganze Reihe von bedingten Verzweigungen, die, wenn Aussagen nicht leben, kann man nicht immer sagen, was der Compiler mit kommen wird, und sich Gedanken darüber, wie lange Grundaussagen dauern wird praktisch immer das Falsche zu tun. (Wenn Sie können sagen, was der Compiler zuverlässig generieren, können Sie nicht einen guten optimierenden Compiler haben.)

CPUs sind tief pipelined. Jeder Verzweigungsbefehl (if / for / while / Schalter / etc) bedeutet, dass die CPU nicht wirklich weiß, was Anweisung zu laden und auszuführen nächsten.

Die CPU entweder Stände während des Wartens zu wissen, was zu tun ist, oder die CPU nimmt eine Vermutung. Im Fall einer älteren CPU, oder wenn die Vermutung falsch ist, erhalten Sie eine Pipeline Stall zu leiden haben, während es geht und lädt die richtige Anweisung. In Abhängigkeit von der CPU kann dies als 10-20 Anweisungen so hoch sein im Wert von Stall.

Moderne CPUs versuchen, dies zu vermeiden, indem sie gute Verzweigungsvorhersage zu tun, und durch mehrere Wege zur gleichen Zeit ausgeführt wird, und nur die tatsächlichen eine zu halten. Dies ist sehr hilfreich, aber nur so weit gehen.

Viel Glück in der Klasse.

Auch wenn Sie diese im wirklichen Leben kümmern, sind Sie wahrscheinlich tun OS Design, Echtzeit-Grafiken, wissenschaftliches Rechnen, oder etwas ähnlich CPU-bound. Profil vor besorgniserregend.

Beachten Sie auch, dass innerhalb einer Schleife ist nicht unbedingt sehr teuer.

Moderne CPU übernimmt beim ersten Besuch einer if-Anweisung, dass die „if-body“ ist genommen werden (oder die in die andere Richtung: es geht auch davon aus einer Schleife Körper mehrmals getroffen werden) (*). Auf den zweiten und weitere Besuche, sie (die CPU) kann vielleicht Blick in die Sprungtabelle , und sehen, wie die Bedingung war das letzte Mal (war es wahr? Falsch war es?). Wenn es falsch war das letzte Mal, dann spekulative Ausführung auf die „else“ fortfahren wird des if oder jenseits der Schleife.

(*) Die Regel ist eigentlich " Vorwärts-Verzweigung nicht genommen, rückwärts Verzweigung genommen ". In einer if-Anweisung gibt es nur a [weiter] Sprung (bis zu dem Punkt nach dem if-Körper ), wenn die Bedingung als falsch ausgewertet (zur Erinnerung: die CPU sowieso eine Verzweigung / Sprung) nicht zu nehmen, aber in einer Schleife, gibt es vielleicht eine Vorwärtszweig auf die Position nach der Schleife annimmt (nicht genommen) und eine Rückwärtsverzweigung auf repetetion werden (entnommen) werden.

Dies ist auch einer der Gründe, warum ein Aufruf einer virtuellen Funktion oder eine Funktion-pointer-Call ist das nicht schlechter als viele annehmen ( http://phresnel.org/blog/ )

Teilen Sie Ihre Programme die klarste, einfachste, sauberste Weg, der nicht offensichtlich ineffizient ist. Das macht die optimale Nutzung der teuerste Ressource, Sie. Sei es das Schreiben oder später Debuggen (erfordert Verständnis) das Programm. Wenn die Leistung nicht genug ist, Maß , wo die Engpässe sind, und sehen, wie sie zu mildern. Nur äußerst selten müssen Sie individuelle Sorgen über (Quelle) Anweisungen, wenn dies zu tun. Die Leistung ist, die richtigen Algorithmen auswählen und Datenstrukturen in der ersten Zeile, die sorgfältige Programmierung, eine schnell genug Maschine zu bekommen. Verwenden Sie eine gute Compiler, dann würden Sie überrascht sein, wenn die Art von Code zu sehen, eine moderne Compiler Umstrukturierung der Fall ist. Umstrukturierung Code für die Leistung ist eine Art letzter Ausweg Maßnahme, der Code komplexer wird (also instabiler), schwerer zu ändern, und damit all-around teurer.

Ich hatte dieses Argument mit einem Freund von mir einmal. Er war ein sehr naive Kreis Algorithmus, behauptete aber, seine schneller als meins (Die Art, die dem Kreis berechnet nur 1/8), weil mein falls verwendet. Am Ende wurde die if-Anweisung mit sqrt ersetzt und schneller, das war irgendwie. Vielleicht, weil die FPU hat sqrt eingebaut?

Einige CPUs (wie X86) bietet Verzweigungsvorhersage Programmierebene eine solche Verzweigungsvorhersage Latenz zu vermeiden.

Einige Compiler aussetzt (wie GCC) diese als Erweiterung zu höheren Programmiersprachen (wie C / C ++).

Siehe wahrscheinlich () / unwahrscheinlich () Makros in dem Linux-Kernel - wie arbeiten Sie? Was ist ihr Nutzen? .

Das teuerste in Bezug auf die ALU Nutzung? Es verbraucht CPU-Register, die Werte zu speichern, zu vergleichen und Zeit in Anspruch nimmt zu holen und die Werte jedes Mal, wenn die if-Anweisung zu vergleichen, ausgeführt wird.

Deshalb ist eine Optimierung, dass ist ein Vergleich und das Ergebnis als eine Variable zu tun, bevor die Schleife ausgeführt wird.

Nur versuchen, Ihre fehlenden Worte zu interpretieren.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top