benchmarking trig lookup tables leistungssteigerung gegenüber cpp-implementierung

Question

Wir entwickeln ein Echtzeitsystem, das während eines zeitkritischen Zeitraums sin/cos-Berechnungen durchführen soll. Wir erwägen die Verwendung einer Nachschlagetabelle, um die Leistung zu verbessern, und ich versuche, den Nutzen/Kosten der Implementierung einer Tabelle zu bewerten. Leider wissen wir noch nicht, welchen Genauigkeitsgrad wir benötigen, aber wahrscheinlich etwa 5-6 Dezimalpunkte.

Ich denke, dass ein umfassender Vergleich von C++ Trig-Funktionen mit Lookup-Ansätzen bereits früher durchgeführt wurde. Ich hatte gehofft, dass mir jemand einen Link zu einer Seite geben könnte, die einen solchen Vergleich dokumentiert. Wenn es solche Ergebnisse nicht gibt, wäre ich für Vorschläge dankbar, wie ich feststellen kann, wie viel Speicher für eine Nachschlagetabelle bei einer bestimmten Mindestgenauigkeit erforderlich ist und wie ich die potenziellen Geschwindigkeitsvorteile ermitteln kann.

Gracias.

Answer 1

Ich kann nicht alle Ihre Fragen beantworten, aber anstatt zu versuchen, theoretische Geschwindigkeitsvorteile zu ermitteln, wäre es mit Sicherheit besser, wenn Sie ein Profil in Ihrer tatsächlichen Anwendung erstellen würden. Dann erhalten Sie ein genaues Bild von der Art der Verbesserung, die Sie in Ihrem spezifischen Problembereich erzielen können, was die nützlichste Information für Ihre Bedürfnisse ist.

Answer 2

Wie genau ist Ihre Grad-Eingabe (lassen Sie uns Grad statt Bogenmaß verwenden, um die Diskussion "einfacher" zu halten). Zehntel eines Grades? Hundertstel eines Grades? Wenn Ihre Winkelgenauigkeit nicht groß ist, kann Ihr trigonometrisches Ergebnis auch nicht besser sein.

Ich habe gesehen, dies als ein Array indiziert durch Hundertstel eines Grades implementiert (halten den Winkel als eine ganze Zahl w/zwei implizite Dezimalpunkt hilft auch mit der Berechnung - keine Notwendigkeit, hochpräzise Float/Double Radian Winkel zu verwenden).

Die Speicherung von SIN-Werten von 0,00 bis 90,00 Grad würde 9001 32-Bit-Float-Ergebniswerte ergeben.

SIN[0] = 0,0 ... SIN[4500] = 0,7071068 ... SIN[9000] = 1,0

Bei SIN ist die trigonometrische Eigenschaft von COS(a) = SIN(90-a) bedeutet einfach, dass man SIN[9000-a] um COS(a) zu erhalten

Wenn Sie eine höhere Genauigkeit benötigen, aber keinen Speicher für mehr Tabellenplatz haben, können Sie eine lineare Interpolation zwischen den beiden Einträgen im Array durchführen, z. B. wäre SIN von 45,00123

SIN[4500] + 0,123 * (SIN[4501] - SIN[4500])

Answer 3

Die einzige Möglichkeit, die Leistungsmerkmale der beiden Ansätze zu ermitteln, besteht darin versuchen Sie es .

Ja, es gibt wahrscheinlich Benchmarks, die von anderen durchgeführt wurden, aber sie liefen nicht im Kontext Ihres Codes, und sie liefen nicht auf Ihrer Hardware, so dass sie nicht sehr gut auf Ihre Situation anwendbar sind.

Sie können jedoch die Befehlslatenzen in den Handbüchern für Ihre CPU nachschlagen. (Intel und AMD haben diese Informationen in PDF-Form auf ihren Websites verfügbar, und die meisten anderen CPU-Hersteller haben ähnliche Dokumente).

Dann können Sie zumindest herausfinden, wie schnell die tatsächlichen Trig-Befehle sind, was Ihnen einen Richtwert gibt, den die Nachschlagetabelle übertreffen muss, damit sie sich lohnt.

Aber das gibt Ihnen nur eine grobe Schätzung der einen Seite der Gleichung. Eine ähnliche grobe Schätzung der Kosten einer Nachschlagetabelle ist möglich, wenn Sie die Latenzzeiten der Caches der CPU kennen und eine ungefähre Vorstellung von der Latenzzeit der Speicherzugriffe haben.

Aber die einzige Möglichkeit, genaue Informationen zu erhalten, besteht darin, es zu versuchen. Implementieren Sie beides, und sehen Sie, was in votre Anwendung. Nur dann werden Sie wissen, was besser ist in votre Fall.