Berechnen Sie die theoretische Geschwindigkeit eines Programms?

Question

Ich habe zwei verschiedene Möglichkeiten geschrieben, das Gleiche zu tun. Ich würde gerne vergleichen, welches schneller ausgeführt wird. Natürlich ist es immer möglich zu benchmarken, aber wie ein Programm-Benchmark von Maschine zu Maschine verschieden sein kann und von vielen äußeren Faktoren beeinflusst werden kann. Wie kann ich berechnen, was schneller ist ohne Bankmarkierung? Mein Gedanke wäre, dass Sie die Zeiten aller im Programm ausgeführten Operationen summieren würden. Ist das eine normale Sache zu tun? Es scheint, als ob Sie beim Benchmark-Benchmark viel Platz für Fehler haben.

Answer 1

Mein Gedanke wäre, dass Sie die Zeiten aller Operationen im Programm summieren würden.

Ja, aber Sie können nicht einfach/zuverlässig diese Zeiten mit einer anderen Methode als Benchmarking herausfinden.

Das Problem besteht darin, dass diese Zeiten vom dynamischen Kontext dessen abhängen, was zuvor in Ihrem Programm (oder sogar im gesamten System) passiert ist. CPUs sind komplexe Biester, und Cache-Effekte (Daten-Cache und Befehls-Cache) sind oft ein wichtiger Faktor. So ist die Verzweigungsvorhersage. Why is it faster to process a sorted array than an unsorted array?

Statische Analyse einer kleinen Schleife in Assemblersprache ist möglich. z.B. Ich kann genau vorhersagen, wie viele Zyklen pro Iteration eine einfache Schleife auf Intel Haswell ausführen kann, unter der Annahme, dass kein Cache verpasst, basierend auf Agner Fog's microarchictecture pdf and instruction tables. Darüber hinaus geht es immer mehr um Vermutungen. Die Leistung in einer hochgradig interpretierten Sprache wie Ruby ist für Experten, die viel Zeit darauf verwenden, Code zu optimieren, etwas vorhersehbar, aber fast sicher nicht "das wird diese Anzahl von Mikrosekunden benötigen", nur "das ist wahrscheinlich ein bisschen oder viel schneller als das ".

Answer 2

Die algorithmische Komplexität gibt Ihnen einen theoretischen Geschwindigkeitsvergleich für einen Algorithmus.

Ihre Frage bezieht sich auf ein beliebiges Programm, aber ein Programm ist mehr als eine Sammlung von Algorithmen.

Die Ausführungsgeschwindigkeit eines Programms hängt von dem Kontext ab, in dem es ausgeführt wird (I/Os, Betriebssystem (Multitasking oder nicht), Hardware).

Also gibt es keine andere Methode als Statistiken über eine Reihe von Messungen, die eine Definition für die Benchmark ist.