Mit Assembly optimieren lernen [geschlossen]

21

Ich bin ein Student im zweiten Jahr der Computerspieltechnologie. Ich habe kürzlich meinen ersten Prototyp meiner "Art" eines eigenen Pfadfinders fertiggestellt (der kein A * anstelle eines geometrischen Ansatzes / einer Mustererkennung verwendet, der Pfadfinder benötigt nur das Wissen über das Terrain, das er für Entscheidungen hält, weil ich wollte eine KI, die tatsächlich erforschen könnte, wenn das Gelände bereits bekannt ist, dann wird sie den kürzesten Weg leicht zurücklegen können, da der Pfadfinder eine Erinnerung an Knoten hat.

Wie auch immer, meine Frage ist allgemeiner: Wie beginne ich mit der Optimierung von Algorithmen / loops / for_each / etc. Verwenden von Assembly, obwohl allgemeine Tipps willkommen sind. Ich bin speziell auf der Suche nach guten Büchern, weil es wirklich schwierig ist, gute Bücher zu diesem Thema zu finden. Es gibt einige kleine Artikel wie diesen , aber immer noch nicht genug Wissen, um einen Algorithmus / ein Spiel zu optimieren ...

Ich hoffe, es gibt ein modernes gutes Buch da draußen, das ich einfach nicht finden konnte ...

niktehpui
quelle
1
Dies beantwortet Ihre Frage nicht direkt, sondern explorativ (so genanntes adaptives) A ​​* wurde untersucht und hat eine wirklich gute Leistung (was bedeutet, dass Sie es nicht mit ASM optimieren müssen). Schauen Sie sich D * Lite an .
Jonathan Dickinson

Antworten:

21

Ich werde derjenige sein, der hier gegen den Strich geht und sagen, es ist nie zu früh, etwas über Optimierungen zu lernen , insbesondere über Baugruppenoptimierungen und, was noch wichtiger ist, über das Debuggen in der Baugruppe. Ich glaube, dass Sie den größtmöglichen Nutzen daraus ziehen werden, wenn Sie ein Student sind (weil Sie dann sehr wenig zu verlieren haben (dh zeitlich / geldmäßig)) und alles, was Sie gewinnen können.

Wenn Sie in der Branche tätig sind und nicht die Aufgabe haben, in der Montage herumzubasteln, dann tun Sie das nicht. Wenn Sie ein Student sind oder Zeit im Allgemeinen haben, würde ich die Zeit finden, um zu lernen, Programme zu zerlegen und zu sehen, ob ich eine bessere Lösung als der Compiler finden kann. Wenn ich nicht kann, wen interessiert das? Ich habe gerade gelernt, wie man neben dem Compiler auch schreibt, und das ist ein RIESIGES Plus, wenn man mit einem Fehler im Release-Code (ohne Fehlersymbole) konfrontiert ist und auf die Demontage starrt, denn das ist das einzige, worauf man achten kann.

Die Antwort

Dies ist eine der besten Ressourcen, die ich zum Erlernen von Optimierungen gefunden habe.

http://www.agner.org/optimize/

Das Geschwätz

Wenn Sie einige Artikel von großen Entwicklern lesen (zum Beispiel, wenn Sie die Gründe für die Erstellung von EASTL und die nähere Betrachtung des Codes prüfen, werden Sie zu Kommentaren wie diesem geführt, weil GCC schrecklich darin ist, diese if - Anweisung einzutragen , aus der hervorgeht, wovon die Mehrheit stammt) Die Leute sagen, Sie vertrauen darauf, dass der Compiler nicht immer richtig ist (vor allem in der Spieleentwicklung). Wenn Sie dann in der Branche Fuß fassen, werden Sie feststellen, dass Optimierungen alltäglich sind und zu wissen, was die Assembly-Ausgabe bedeutet, ein großes Plus ist. Außerdem scheinen die Leute (insbesondere beim Stackoverflow) nicht zu erkennen, dass das Erstellen von Profilen für Spiele sehr schwierig und nicht immer genau ist.

Es gibt jedoch eine Einschränkung. Sie können Zeit damit verbringen, etwas zu optimieren, und später feststellen, dass Zeit verschwendet wurde. Aber was hast du gelernt? Sie haben gelernt, denselben Fehler unter ähnlichen Umständen nicht zu wiederholen.

Was SO jetzt einnimmt, ist meiner Meinung nach eine religiöse Haltung zu der Aussage , nicht zu optimieren, bis Sie sich profilieren und sich keine Sorgen machen, der Compiler weiß es besser als Sie . Es behindert das Lernen. Ich kenne Experten in der Branche, die sehr gutes Geld erhalten (und ich meine SEHR gutes Geld), um bei der Zusammenstellung herumzuspielen, um das Spiel zu optimieren und Fehler zu beheben, weil der Compiler schlecht darin ist oder Ihnen einfach nicht helfen kann, weil es gut ist kann nicht (GPU-bezogene Abstürze, Abstürze, bei denen Daten in einem Debugger nicht einlesbar sind usw. usw.)!

Was ist, wenn jemand, der das liebt, es noch nicht vollständig erkannt hat, die Frage hier stellt und von den vielen Antworten, die der Compiler kennt, besser als Sie ab- oder abgeschaltet wird? und wird nie einer dieser hochbezahlten Programmierer?

Ein letzter Gedanke. Wenn Sie dies frühzeitig tun, werden Sie feststellen, dass Sie bald anfangen, Code zu schreiben, der im schlimmsten Fall keine Leistungsverbesserungen aufweist, da der Compiler ihn auf die gleiche Weise optimiert hat oder bestenfalls einige Leistungsverbesserungen aufweist, da der Compiler ihn jetzt optimieren kann . In beiden Fällen ist es zur Gewohnheit geworden, und Sie können Code nicht langsamer schreiben als zuvor. Einige Beispiele sind (es gibt viele weitere):

  1. Pre-Incrementing, es sei denn, Sie möchten wirklich ein Post-Incrementing durchführen
  2. Schreiben von Schleifen für Container unter Verwendung einer konstanten lokalen Größenvariablen, anstatt size () für den Container innerhalb der Schleife aufzurufen.

EDIT: Update nach 8 weiteren Jahren in der Branche. Montage lernen. Erfahren Sie, wie Optimierer funktionieren und welche Assembly sie generieren (CompilerExplorer ist ein großartiges Tool dafür). Ich habe unzählige Abstürze in Test-Builds (optimierte Builds für interne Tests) festgestellt, bei denen Sie sich auch mit Debug-Symbolen nicht auf den Debugger verlassen können. Der Compiler hat zu viele Dinge optimiert und die Assembly ist Ihre einzige wertvolle Informationsquelle, um den Fehler aus dem Absturzdump zu finden. Jeder Build dauert 30-40 Minuten, wenn Sie Glück haben und an erster Stelle in der Build-Warteschlange stehen. Sie können sich also nicht auf einige traditionelle Techniken verlassen, um den Fehler zu isolieren. Multiplayer macht es noch schlimmer. Wenn Sie die Baugruppe kennen und wissen, wie Sie die optimierte Baugruppe lesen, werden Sie einfach besser und letztendlich wertvoller für das Team.

Samaursa
quelle
1
Guter Punkt zur Optimierung von Compilern. Es ist großartig, sie zu haben, aber sie sind alles andere als perfekt und im Gegensatz zu dem, was manche Leute glauben, ist es normalerweise nicht schwer, eine einfache Optimierung zu finden, die ein Compiler nicht vorgenommen hat.
aaaaaaaaaaa 13.11.11
3
Es ist zu beachten, dass es einen Unterschied zwischen "Lernen, Assembly zu lesen" und "Lernen, mit Assembly zu optimieren " gibt. Die beiden sind nicht dasselbe, und Ihre Antwort geht nicht wirklich auf die Verwendung von Assembly zum Implementieren von Optimierungen ein. Das Lesen von Assemblys ist eine nützliche Fähigkeit, da es beim Debuggen und Erkennen von Stellen hilfreich sein kann, an denen der Compiler etwas nicht richtig macht. Dies unterscheidet sich jedoch erheblich von der tatsächlichen Verwendung von Assembly zum Schreiben optimierter Routinen, für die umfassende Kenntnisse der Befehlsplanung für eine bestimmte CPU erforderlich sind. Und es ist auch etwas, das Sie nicht behandelt haben.
Nicol Bolas
1
"Ich habe gerade gelernt, wie man neben dem Compiler auch schreibt" Nein, hast du nicht. Sie haben nachgesehen, wie eine bestimmte Routine für eine bestimmte CPU kompiliert wurde. Um zu lernen, wie optimierte Assembler-Routinen implementiert werden, muss man sich nicht nur ansehen, wie der Compiler eine Routine kompiliert hat. Sie müssen verstehen, warum der Compiler diese Opcodes in dieser Reihenfolge ausgewählt hat, um diesen spezifischen C ++ - Code zu reproduzieren. Und das erfordert genaue Kenntnisse der CPU, der Befehlsplanung und so weiter. Um dies zu verallgemeinern, ist jahrelange Erfahrung erforderlich . Sie werden es nicht bekommen, wenn Sie nur ein paar Routinen dekodieren.
Nicol Bolas
7
Also -1 für A: Beantworte die Frage, wie montageoptimierte Routinen geschrieben werden sollen, nicht. B: Falsche Darstellung, wie einfach es ist, den Compiler beim Schreiben von für Assemblys optimierten Routinen zu schlagen. Und C: Förderung einen Programmierer Blick auf Montage-Ebene Optimierungen vor Algorithmus-Level - Optimierungen. Sogar diese hochbezahlten "Branchenexperten" würden Ihnen sagen, dass dies den Wagen vor das Pferd stellt.
Nicol Bolas
2
@Samaursa: Niemand hat gesagt, dass die Leute "die Demontage und die Optimierung von Code nicht verstehen sollten". Dies ist keine religiöse Debatte; Es ist eine einfache Tatsache. Die Menschen haben jahrhundertelang Hand an der Optimierung von Routinen gearbeitet, um herauszufinden, dass dies für die Gesamtleistung nichts bedeutet. Das Erlernen der Optimierung von Algorithmen ist eine äußerst wertvolle Fähigkeit. Das Lesen von Assembler ist ein wenig wertvolles Fachwissen. Das Erlernen des Schreibens von Assembler-Routinen ist nur selten von Nutzen. Die besten Optimierungen resultieren heutzutage aus einer besseren Cache-Auslastung und nicht aus der manuellen Montage.
Nicol Bolas
22

Der erste Tipp, den Sie erhalten, lautet: Nicht.

Moderne Compiler sind wirklich sehr, sehr gut darin, Code zu optimieren, und es ist sehr viel wahrscheinlicher, dass sie das besser können als jede selbst erstellte Assemblersprache, die Sie schreiben.

Die Ausnahme wäre ein spezieller Fall, bei dem Sie mit Sicherheit festgestellt haben, dass der Compiler eine schlechte Optimierungsarbeit leistet. Das ist also der zweite Tipp. Es gibt hier keine allgemeinen Richtlinien. Sie müssen Ihren eigenen Code kennen, wissen, was er tut, in der Lage sein, ihn zu zerlegen und mit absoluter Sicherheit festzustellen, dass der Compiler schlechte Arbeit leistet.

Auch in diesem Fall möchten Sie möglicherweise immer noch nicht. Sie müssen sicher sein, dass für Sie kein laufender Wartungsaufwand entsteht. Möglicherweise möchten Sie in 6 Monaten wieder zu diesem Code zurückkehren und einen Teil davon ändern, oder Sie finden einen äußerst subtilen Fehler, der in einer Assembler-Version schwieriger zu beheben sein wird. Selbst wenn Sie glauben, alle Fehler behoben zu haben, werden die Fehler, von denen Sie nicht einmal gedacht haben, dass sie passieren könnten, für Sie Realität, sobald Ihr Programm an die Öffentlichkeit geht. Das ist ein ziemlicher Augenöffner (und eine demütigende Erfahrung).

Und selbst wenn Sie damit einverstanden sind, werden Sie möglicherweise feststellen, dass es absolut keine messbare Leistungsverbesserung gibt, da Ihr Hauptengpass an einer anderen Stelle in Ihrem Programm liegen könnte. Das bringt mich also wieder zu Nummer 1 zurück. Nicht.

Maximus Minimus
quelle
15

Normalerweise hängt eine solide Optimierung nicht von der Verwendung von Assembly oder der Durchführung von Mikrooptimierungen mit Code in höheren Sprachen ab. Wenn Sie viele Forschungsarbeiten lesen (wie ich - oder es versuchen!), Werden Sie feststellen, dass die an Algorithmen vorgenommenen Verbesserungen häufig eher auf einer breiteren konzeptionellen, "qualitativen" Ebene als auf einer "quantitativeren" Ebene liegen. Ebene der Mikrooptimierung. Ich möchte betonen, dass Gewinne in der Größenordnung wahrscheinlicher zu finden sind, wenn Algorithmen unter diesem Gesichtspunkt betrachtet oder vorhandene Lösungen vektorisiert / parallelisiert werden.

Trotzdem bin ich kürzlich auf dieses Problem gestoßen. Dies ist möglicherweise ein guter Weg, um x86-ASM speziell für Spieleentwickler zu erlernen.


NACHTRAG

Zwei Quellen aus meinem Kopf:

Darüber hinaus ist das Lesen von Forschungsarbeiten eine hervorragende Möglichkeit, die Denkprozesse der Weisen zu verfolgen, da sie Algorithmen optimieren, um eine bessere Leistung zu erzielen. Am häufigsten werden Gewinne gesehen durch:

  • Reduzierung der Verwendung der kostspieligsten Vorgänge (hauptsächlich div, SQRT, Triggeroperationen und Bedingungen);
  • Verbesserung der Cache-Leistung durch effizientere Datenstrukturen, Speicherausrichtung und geringere Bedingungen;
  • Reduzierung der Ausgabequalität in akzeptablen Bereichen für eine verbesserte Leistung;
  • Vektorisierung (SIMD);
  • Parallelisierung (Threading, einschließlich Verlagerung von Aufgaben auf die GPU);
  • Und natürlich (immer seltener) handcodierte Montage. Untersuchen Sie zunächst C / C ++ - Assemblys, um festzustellen, wo der Compiler nicht optimale Entscheidungen trifft. Mehr davon finden Sie in älteren Arbeiten aus den 80er und 90er Jahren, IME.

Das Lesen von Forschungsergebnissen hält Sie auch auf dem neuesten Stand Ihres Fachs, anstatt darauf zu warten, dass dieses Wissen in die Branche gelangt.

Ingenieur
quelle
Sie sprechen von Algorithmusoptimierung, geben aber keine Informationen dazu an. Wenn wir Ihrem Rat folgen und uns das ansehen würden, könnten Sie stattdessen eine Richtung angeben?
Skeith
Tatsächlich erwähne ich es; Sie müssen Algorithmen studieren und verstehen, was Informatiker tun, um die Leistung qualitativ zu verbessern. Tauchen Sie genug ein, und mit der Zeit fangen Sie an, in ähnlichen Begriffen zu denken. Inkrementelle Anstrengungen zahlen sich hier sehr schnell aus, anstatt Jahre (und ich habe dies kürzlich in einem ASM-Forum gesehen) damit zu verbringen, die Vor- und Nachteile von (nur) z. x86-Architektur. Jagen Sie das große Spiel: Lernen Sie, Probleme auf den Punkt zu bringen, und entscheiden Sie dann, was zur Optimierung überflüssig ist. Siehe oben stehende Referenzbücher.
Ingenieur
@NickWiggill Was ist Ihre übliche Quelle für Forschungsarbeiten?
Kizzx2
3

Ich denke, es könnte zu früh sein.

Wie auch immer, es ist wichtig zu verstehen, dass der Compiler selbst keinen langsameren Code als das Assembly-Äquivalent erzeugt. Sie erhalten keine Leistung, wenn Sie einfach den gleichen Assembly-Code wie der Compiler schreiben.

Konzentrieren Sie sich zunächst auf montagefreie Optimierungen. Igor Ostrovsky hat einige gute Artikel, die einige der Grundlagen aufzeigen: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

Beachten Sie, dass Verzweigungsfehlervorhersagen und Cache-Fehler das sind, wogegen Sie in erster Linie optimieren sollten, auch wenn Sie einige zusätzliche Rechenoperationen ausführen müssen. In der Regel lohnt es sich, eine unvorhersehbare Verzweigung zu vermeiden oder zufällig aus zu viel Speicher zu lesen.

Und am wichtigsten ist natürlich, dass Sie zuerst Ihren Algorithmus optimieren. Eine langsame Implementierung eines schnellen Algorithmus ist fast immer schneller als eine schnelle Implementierung eines langsamen Algorithmus.

aaaaaaaaaaa
quelle
2

Dieses Buch ist außergewöhnlich gut für ein Lehrbuch. Aber es ist nicht speziell auf Optimierung ausgerichtet. Assemblersprache für x86-Prozessoren, 6. Ausgabe

Es geht mehr darum, die Grundlagen des Zusammenbaus mithilfe von MASM zu vermitteln. Gegen Ende des Buches erfahren Sie dann, wie Sie Assembler in c ++ einbinden und in größere Programme integrieren können.

Ich habe dies hier aufgeführt, weil es sinnvoll ist, die Grundlagen des Zusammenbaus zu lernen, bevor Sie lernen, wie Sie damit Programme optimieren.

Ich mag dieses Buch, weil Irvine Ihnen beibringt, wie man die Werkzeuge verwendet, die zum Schreiben von Maskenprogrammen benötigt werden. Er geht speziell auf die Verwendung der IDE (Visual Studio C ++) und des Debuggers ein. Jedes Kapitel enthält einige Videos, die sich mit der Lösung von Problemen befassen. Einige dieser Informationen sind auf der angegebenen Website frei verfügbar.

NadtheVlad
quelle
1
"Es ist sinnvoll, die Grundlagen der Montage zu lernen, bevor Sie lernen, wie Sie damit Programme optimieren können" - ein guter Ratschlag.
Maximus Minimus