Ist es für den Compiler legal, die zeitliche Komplexität eines Programms zu verringern? Wird dies als beobachtbares Verhalten betrachtet?

_{(Hinweis: Dies soll eine Sprachanwaltsfrage sein; Ich beziehe mich nicht auf bestimmte vorhandene Compiler.)}

Wann, wenn überhaupt, darf der Compiler die Zeitkomplexität eines Programms verringern?
Unter welchen Umständen (falls zutreffend) wird dies als „beobachtbares Verhalten“ betrachtet und warum?
(Kann der Compiler beispielsweise ein Programm in Polynomialzeit legal auf ein Programm in Exponentialzeit “reduzieren”?)

Wenn sich die Antwort in C und C++ oder in verschiedenen Versionen von beiden unterscheidet, erläutern Sie bitte die Unterschiede.

Der C-Standard hat eigentlich kein Zeitkomplexitätsmodell, weder für seine primitiven Operationen noch für seine Bibliotheksfunktionen, so dass Compiler so ziemlich alles tun dürfen, was die Programmsemantik (beobachtbares Verhalten) bewahrt.

Der C++-Standard gibt nur für einige seiner Bibliotheksfunktionen Komplexitätsgarantien und sagt (17.5.1.4 [structure.specifications]):

Die in den Bibliotheksklauseln angegebenen Komplexitätsanforderungen sind Obergrenzen, und Implementierungen, die bessere Komplexitätsgarantien bieten, erfüllen die Anforderungen.

Ein Compiler behält diese Grenzen besser bei (und da viele der Funktionen auf Vorlagen basieren/inline sein können, ist der Compiler beteiligt), aber die Grenzen beziehen sich auf die Anzahl der Elemente in Containern und beschränken die Anzahl der Aufrufe von Vergleichsoperatoren und die wie. Ansonsten ist der Compiler wieder frei zu tun, was er will.

Die Leistung des Codes wird nicht als beobachtbares Verhalten betrachtet und könnte möglicherweise vom Compiler in beide Richtungen geändert werden. In der Praxis sind z Qualität der Umsetzung (QoI) Gründe, warum Compiler Ihre Programme nicht verschlechtern, aber es gibt Fälle, in denen QoI nicht die Leistung ist.

Ein Compiler könnte mit den entsprechenden Flags dem Programm, das er zu Debugging-Zwecken erstellt, eine Instrumentierung hinzufügen (dies ist häufig bei Bibliotheksimplementierungen der Fall, z. B. bei geprüften Iteratoren).

Beachten Sie, dass die einfache Antwort auf Wenn Der Compiler würde Ihr Programm in zweierlei Hinsicht verschlechtern: Wenn der Client danach fragt oder wenn der Implementierer keine Benutzer für den Compiler haben möchte.

5.1.2.3 im C-Standard sagt

Die semantischen Beschreibungen in dieser Internationalen Norm beschreiben das Verhalten einer abstrakten Maschine, bei der Optimierungsfragen keine Rolle spielen.

Der C++-Standard hat in 1.9 einen ähnlichen Wortlaut [intro.execution]

Beide Standards haben die gleiche Definition von beobachtbarem Verhalten:

Die Mindestanforderungen an eine konforme Implementierung sind:
— Zugriffe auf flüchtige Objekte werden streng nach den Regeln der abstrakten Maschine ausgewertet.
— Bei Programmende müssen alle in Dateien geschriebenen Daten mit dem Ergebnis identisch sein, das die Ausführung des Programms gemäß der abstrakten Semantik hervorgebracht hätte.
— Die Eingangs- und Ausgangsdynamik von interaktiven Geräten muss wie in 7.21.3 spezifiziert erfolgen. Die Absicht dieser Anforderungen besteht darin, dass eine ungepufferte oder zeilengepufferte Ausgabe so schnell wie möglich erscheint, um sicherzustellen, dass Aufforderungsmeldungen tatsächlich erscheinen, bevor ein Programm auf eine Eingabe wartet.
Dies ist das beobachtbares Verhalten des Programms.

Also alles andere, zB Leistung von a for Schleife oder die Anzahl der Lese-/Schreibvorgänge für nichtflüchtige Variablen wird nicht als beobachtbar angesehen, und daher gibt es keine entsprechenden Leistungsanforderungen an den Compiler.

Wenn der Compiler einen Codeblock 100 Mal neu auswerten wollte (unter der Annahme, dass er keine beobachtbaren Nebenwirkungen hatte und nur den Zustand nichtflüchtiger Variablen änderte) und überprüfen wollte, dass jedes Mal dieselben Ergebnisse erzielt wurden (und nicht von kosmischen Strahlen oder fehlerhafte Hardware), die der Standard zulassen würde.

Andere haben darauf hingewiesen, dass der Standard nicht die Funktionsweise der C-Laufzeitumgebung einschränkt, sondern nur ihr beobachtbares Verhalten. Es gibt keinen Grund, warum Sie beispielsweise C nicht interpretiert oder JIT-kompiliert haben können.

Stellen Sie sich eine C-Implementierung vor, bei der alle Speicherzellen in einer verknüpften Liste auf einem zugrunde liegenden System gespeichert sind. Zeiger sind dann ein Index in diese verkettete Liste. Alle Zeigeroperationen würden normal funktionieren, außer dass die Laufzeit bei jedem Speicherzugriff über die verknüpfte Liste iterieren müsste. Allerlei gängige Algorithmen würden plötzlich einen zusätzlichen Faktor N in ihrer Komplexität gewinnen, zum Beispiel die gängigen nullterminierten String-Operationen.