Beseitigt "mystery-consing" in dieser Common-Lisp-Funktion?

8

Diese Common-Lisp-Funktion, die einfach vier Ecken der Drahtgitterkanten einer Wand mit extrem einfacher Kindergarten-Arithmetik und ein paar "Case" -Tests berechnet, scheint für die dynamische Zuweisung von 196608 Bytes pro gerenderten Frame verantwortlich zu sein; Der Profiler der SBCL sagt mir, dass dies meine problematischste Funktion ist, soweit es sich lohnt. Um einen Überblick zu geben, woran ich gerade arbeite, handelt es sich um ein kleines First-Person-Dungeon-Crawler-Spiel. Ein Dungeon besteht aus genau 32x32 Zellen und jede Zelle hat 4 Wände. 32 * 32 * 4 * x = 196608, und so entpuppt sich x als 48, was zufällig 4 * 12 ist (4 Wände * 12 Schwimmer pro Wand? Vielleicht nicht).

Nun kann ich dieses Performance-Problem leicht beheben, indem ich OpenGL-Display-Listen im Gameplay-Modus verwende, und ich nehme an, dass ich das tun werde. Trotzdem, 1) Ich optimiere generell nicht vorzeitig, und noch wichtiger: 2) Ich mag es immer noch nicht, bestimmte lästige Jucke wie diese unzerkratzt zu lassen, und ich frage mich, was ich sonst hätte tun können. Meine Funktion wie sie ist, ist wie folgt:

%Vor%

Um ein paar Dinge zusammenzufassen, habe ich versucht, das zu beheben:

  1. Erledigen Sie ein "deklarieren", um für "Geschwindigkeit" bei 3 und alles andere bei 0 zu optimieren (sowohl in dieser Funktion als auch in der einzigen Funktion, die es aufruft). Seltsamerweise hat der Profiler diese Funktion etwas weniger berüchtigt gemeldet ... aber er konzedierte immer noch. Ich ziele auf Null-Consing. Arithmetik sollte keine Nachteile haben.

  2. Dann dachte ich, "Werte" könnten dies tun. Vielleicht, dachte ich, ist es innerlich nur etwas wie die Funktion 'liste', die ohne Zweifel (der einzige Zweck der 'Listen'-Funktion im Universum) konsektiert. Was habe ich getan, um dies zu mildern? Nur zum Zweck des Experiments habe ich die Datei modifiziert, um ein einzelnes wall-vertex-buffer globales Array zu erstellen, das 12 Elementen vom Typ float entspricht und sowohl diese Funktion modifiziert, als auch die aufrufende Funktion um nach dem Aufruf dieser Funktion von ihr zu lesen (so würde sie ständig eine einzige Menge von 12 Schwimmern aktualisieren, die an derselben Stelle im Speicher gehalten werden, anstatt etwas zuzuordnen). Seltsamerweise hat dies NICHT verhindert, dass diese Funktion zu einer Schweinerei wurde! Also ... war das "case"? Ich finde es interessant, dass, wie bereits erwähnt, diese Mystery-Nummer 48 war. 48 = 4 * 12, vielleicht diese 4 Case-Tests mal 12 Floats pro "Wert" -Ruf. Oder, das könnte ein Zufall sein, mit 48 Bytes was anderes bedeutet (da ein float NICHT 1 Byte ist, vermute ich, ist -is etwas anderes). Dies scheint signifikant zu sein, aber ich kann mir nicht vorstellen, was mein nächster Ansatz sein sollte.

  3. Versuchte, "case" durch ein "cond" -Äquivalent zu ersetzen, indem man an dieser Stelle nur nach Strohhalmen griff, tat auch nichts.

Wo also könnte das "Mystery Consing" dieser Funktion herkommen? Wie würden Sie erfahrenere Lisp-Programmierer diesen kniffligen Scherz eines Problems angehen?

(EDIT) für @FaheemMitha, ist die Funktion, die die Funktion calculate-wallpoints benutzt; diese lästige Funktion wurde später mit (Deklarieren (Inline-Berechnung-Wand-Punkte)) kurz vor der Berechnung-Wand-Punkte-Definition inline:

%Vor%

nil)

    
valq 01.09.2012, 17:07
quelle

2 Antworten

9

Der consed Speicher wird durch Zuweisen der Gleitkommazahlen verursacht. Jeder Funktionsaufruf gibt Floats zurück, eigentlich 32 Bit single-floats . Consing bedeutet, dass einige Daten auf dem Heap zugewiesen sind: Cons-Zellen, Zahlen, Arrays, ...

A single-float ist ein 32-Bit-Speicherobjekt. 4 Bytes.

%Vor%

In obigem Fall ist 3.0 ein neues Float, möglicherweise neu consed .

%Vor%

Was ist nun über der obigen Berechnung? Die innere Operation + gibt einen float 3.0 zurück. Was passiert damit?

  • es kann in einem Prozessorregister zurückgegeben und dort für die nächste Operation verwendet werden.
  • es kann auf dem Stapel zurückgegeben und dort für die nächste Operation verwendet werden
  • in einer komplexeren Operation kann es im Heap zugeordnet und als Zeiger auf einen Heap-Wert zurückgegeben werden. Dies kann der Fall sein, wenn nicht genügend Register für alle zurückgegebenen Werte vorhanden sind oder die Größe des Stapelrahmens nicht groß genug für alle zurückgegebenen Werte ist.

Was passiert mit diesen Schwimmern später? Sind sie irgendwie gespeichert? In einer Liste? In einem neuen Array? In einem neuen structure ? In einem neuen CLOS-Objekt?

Oben wird deutlich, dass es von der Prozessorarchitektur und der Compiler-Strategie abhängt. Ein x86 hat nicht viele Register. Die 64bit Version hat mehr. Ein RISC-Prozessor darf noch mehr Register haben. Wie groß ist dann der Stack und wie groß sind typische Stack-Frames?

Bei komplexeren Berechnungen, die mehrere Funktionen beinhalten, kann ein optimierender Compiler möglicherweise optimieren, welche Werte in Registern bleiben und so das Consing reduzieren.

Oben wird auch deutlich, dass es für Common Lisp kein vollständiges Rezept gibt, wie float-Operationen nicht konsistent gemacht werden können. Die Fähigkeit, Consing zu reduzieren, hängt von einigen allgemeinen Ideen und vielen compiler / architekturspezifischen Tricks ab.

Da Sie SBCL verwenden, fragen Sie am besten nach der SBCL-Mailingliste und informieren Sie sich über das Betriebssystem, die Architektur (Intel, Arm, ...) und ob es im 32-Bit- oder 64-Bit-Modus läuft. Mehr Kontext-Code ist auch notwendig, um ein besseres Bild zu bekommen, wie man reduziert wird.

Einige Hintergrundinformationen zum Lesen:

Rainer Joswig 01.09.2012, 18:01
quelle
1

Was sagt der Compiler? Wenn Sie für die Geschwindigkeit optimieren, sollte es sich lautstark darüber beschweren, dass es keine Open-Code-Arithmetik geben kann.

Als nächstes, was passiert mit dem Zwang? Ist das auch offen codiert?

Denken Sie daran, dass Sie in der Regel den Assembly-Code überprüfen können, den eine Funktion mit disassemble () generiert.

    
Johan Benum Evensberget 01.09.2012 18:04
quelle

Tags und Links