Compiler: MinGW / GCC
Probleme: Kein GPL / LGPL-Code erlaubt (GMP oder irgendeine Bignum-Bibliothek in dieser Angelegenheit, ist für dieses Problem übertrieben, wie Ich habe bereits die Klasse implementiert).
Ich habe meine eigene 128-bit große Integer-Klasse mit fester Größe erstellt (die für die Verwendung in einer Game-Engine gedacht ist, aber für jeden Anwendungsfall verallgemeinert werden kann) und finde die Leistung der aktuellen Multiplikation und dividiere die Operationen als ziemlich abgründig (ja, ich habe sie zeitlich festgelegt, siehe unten), und Ich möchte die Algorithmen verbessern oder ändern, die die low-level Zahlenverarbeitung durchführen.
Wenn es zu den Multiplikations- und Divisionsoperatoren kommt, sind sie im Vergleich zu allem anderen in der Klasse unerträglich langsam.
Dies sind die ungefähren Maße für meinen eigenen Computer:
%Vor%Wie Sie sehen können, ist die Multiplikation viel, viel langsamer als addieren oder subtrahieren. Division ist etwa 10 mal langsamer als Multiplikation.
Ich möchte die Geschwindigkeit dieser beiden Operatoren verbessern, da pro Frame sehr viele Berechnungen durchgeführt werden können (Skalarprodukte, verschiedene Kollisionserkennungsmethoden usw.).
Die Struktur (Methoden weggelassen) sieht ungefähr so aus:
%Vor% Multiplikation wird derzeit mit der typischen Methode long-multiplication (in Assembly, sodass ich die Ausgabe EDX abfangen kann) ausgeführt, während die Wörter ignoriert werden, die nicht mehr enthalten sind Bereich (das heißt, ich mache nur 10 mull im Vergleich zu 16).
Division verwendet den Algorithmus shift-subtract (die Geschwindigkeit hängt von den Bit-Zahlen der Operanden ab). Es ist jedoch nicht in der Montage getan. Ich fand das ein wenig zu schwierig und entschied mich, den Compiler zu optimieren.
Ich habe Google mehrere Tage lang herumgehört und Seiten betrachtet, die Algorithmen wie Karatsuba-Multiplikation , High-Radix-Division, beschreiben , und Newton-Rapson Division , aber die mathematischen Symbole sind ein wenig zu weit über meinen Kopf. Ich möchte einige dieser fortgeschrittenen Methoden verwenden, um meinen Code zu beschleunigen, aber ich müsste das "Griechisch" zuerst in etwas Verständliches übersetzen.
Für diejenigen, die meine Bemühungen als "vorzeitige Optimierung" betrachten; Ich halte diesen Code für einen Engpass, weil die sehr elementaren mathematischen Operationen selbst langsam werden. Ich kann solche Arten der Optimierung auf Code höherer Ebene ignorieren, aber dieser Code wird so oft verwendet / verwendet, dass er wichtig ist.
Ich hätte gerne Vorschläge, welchen Algorithmus ich verwenden sollte, um die Multiplikation und Teilung zu verbessern (wenn möglich), und eine grundlegende (hoffentlich leicht zu verstehende) Erklärung, wie der vorgeschlagene Algorithmus funktioniert, wäre hoch geschätzt.
Ich war in der Lage, die Multiplikationsoperation zu verbessern, indem ich Code in Operator * = einfügte, und es scheint so schnell wie möglich zu sein.
%Vor%Hier ist ein blanker Code, den Sie untersuchen sollten (beachten Sie, dass meine Typnamen tatsächlich verschieden sind, dies wurde zur Vereinfachung geändert):
%Vor%Was die Aufteilung betrifft, ist die Prüfung des Codes ziemlich sinnlos, da ich den mathematischen Algorithmus ändern muss, um wesentliche Vorteile zu sehen. Die einzig machbare Wahl scheint die High-Radix-Teilung zu sein, aber ich muss noch (in meinen Gedanken) nur ausbügeln, wie es funktionieren wird.
Ich würde mir über Multiplikation keine Sorgen machen. Was Sie tun, scheint ziemlich effizient zu sein. Ich habe das Griechische bei der Karatsuba-Multiplikation nicht wirklich befolgt, aber mein Gefühl ist, dass es nur mit viel größeren Zahlen effizienter wäre, als du es zu tun hast.
Ein Vorschlag, den ich habe, ist zu versuchen, die kleinsten Blöcke der Inline-Assembly zu verwenden, anstatt Ihre Logik in Assembly zu codieren. Sie könnten eine Funktion schreiben:
%Vor% Die Funktion wird in Inline-Assembly implementiert und Sie rufen sie aus C ++ - Code auf. Es sollte so effizient sein wie die reine Assemblierung und viel einfacher zu programmieren.
Über die Teilung weiß ich nicht. Die meisten Algorithmen, die ich gesehen habe, sprechen von asymptotischer Effizienz, was bedeutet, dass sie nur für sehr hohe Bit-Zahlen effizient sind.
Verstehe ich Ihre Daten richtig, dass Sie Ihren Test auf einem 1,8-GHz-Rechner ausführen und das "u" in Ihren Zeiten Prozessorzyklen sind?
Wenn dem so ist, 546 Zyklen für 10 32x32 Bit MULs scheinen mir ein bisschen langsam. Ich habe meine eigene Marke von Bignums hier auf einem 2GHz Core2 Duo und ein 128x128 = 256 Bit MUL läuft in etwa 150 Zyklen (ich mache alle 16 kleine MULs), d. H. Etwa 6 mal schneller. Aber das könnte einfach eine schnellere CPU sein.
Stellen Sie sicher, dass Sie die Schleifen ausrollen, um diesen Overhead zu sparen. Machen Sie so wenig Registerspeicherung wie nötig. Vielleicht hilft es, wenn Sie den ASM-Code hier veröffentlichen, damit wir ihn überprüfen können.
Karatsuba wird dir nicht helfen, da es erst ab etwa 20-40 32-Bit-Wörtern effizient zu werden beginnt.
Division ist immer viel teurer als Multiplikation. Wenn Sie viele Male durch eine Konstante oder durch denselben Wert teilen, kann es hilfreich sein, das Reziproke vorher zu berechnen und dann mit ihm zu multiplizieren.