Optimieren C- und C++-Compiler Vergleiche mit Funktionsaufrufen?

Lesezeit: 6 Minuten

Wander Nauta

Optimieren C- und C++-Compiler im Allgemeinen Vergleiche mit Funktionen?

Zum Beispiel, diese Seite schlägt vor, dass die size Funktion auf std::lists in C++ kann in einigen Standardbibliotheksimplementierungen eine lineare Komplexität O(N) haben (was für eine verkettete Liste sinnvoll ist).

Aber in diesem Fall, wenn myList ist eine riesige Liste, was würde so etwas bewirken?

    if (myList.size() < 5) return 1;
    else return 2;

Würde die Funktion size() alle N Listenmitglieder finden und zählen, oder wäre sie für einen Kurzschluss optimiert, nachdem 5 Mitglieder gefunden wurden?

Wenn ja size() Der lange Weg herauszufinden, dass das Stoppen nach 5 eine gute Idee ist, ist für einen Compiler unglaublich schwierig.

– Flexo
♦

11. Mai 2012 um 11:20 Uhr
Es gibt möglicherweise Spielraum dafür, wenn es inline ist size aber ich denke, es ist ein Weitschuss zu erkennen, dass es aus einer Schleife ausbrechen kann, die einen Zähler erhöht.

– Rup

11. Mai 2012 um 11:21 Uhr
Ich würde mir keine Sorgen machen. Während der C++03-Standard keine O(1)-Komplexität für erforderte size()das tat es empfehlen es, und es ist einfach zu implementieren. Ich wäre überrascht, wenn Ihre Implementierung die Anzahl der Elemente im Container nicht verfolgen würde (Sie können dies leicht überprüfen, indem Sie die <list> Header.

– David Rodríguez – Dribeas

11. Mai 2012 um 11:33 Uhr
@WanderNauta: Das Problem damit, eine allgemeine Frage stellen zu wollen und eine bestimmte Frage zu stellen, ist, dass Sie Antworten auf die bestimmte Frage erhalten. Wenn die Frage allgemein ist, lautet die Antwort, dass der Compiler dies in den meisten Fällen nicht kann. Der Fall a size() auf einer Liste ist ein Sonderfall in dem Sinne, dass der Compiler als Vorlage die Definition der Funktion hat und damit gibt es etwas entfernte Chance, dass es es herausfinden könnte. Im Allgemeinen hat der Compiler keinen Zugriff auf die Definition der Funktionen und die Optimierungsmöglichkeiten sind viel schwieriger.

– David Rodríguez – Dribeas

11. Mai 2012 um 11:43 Uhr
Ganz im Gegenteil, selbst mit Inlining gibt es nur sehr wenige Chancen, ohne es, vergessen Sie es, die Funktion muss vollständig ausgeführt werden, bevor der Vergleich durchgeführt werden kann

– David Rodríguez – Dribeas

11. Mai 2012 um 11:52 Uhr

Jon

Theoretisch besteht die Möglichkeit ggf size() war inline, aber um die Optimierung durchzuführen, müsste der Compiler dies tun

Erkennen Sie, dass Sie speziell eine „kleiner als“-Bedingung testen
Beweisen Sie, dass die Schleife (angenommen, eine existiert für die Zwecke dieser Diskussion) zu einer monoton steigenden Variablen führt

Beweisen Sie, dass es keine beobachtbaren Nebenwirkungen des Schleifenkörpers gibt

Das ist meiner Meinung nach eine Menge Dinge, auf die man sich verlassen kann, und es enthält Funktionen, die auch in anderen Zusammenhängen nicht “offensichtlich nützlich” sind. Denken Sie daran, dass Compiler-Anbieter nur begrenzte Ressourcen haben, also muss es wirklich gute Gründe dafür geben, diese Voraussetzungen zu implementieren und den Compiler alle Teile zusammenbringen zu lassen, um diesen Fall zu optimieren.

Auch wenn dies für jemanden ein Leistungsproblem ist Das Problem kann leicht im Code gelöst werden, Ich glaube nicht, dass es eine solche Rechtfertigung geben würde. Also nein, im Allgemeinen sollten Sie nicht erwarten, dass solche Fälle optimiert werden.

Ich bin verwirrt. Warum müsste der Wert monoton steigen?

– Wander Nauta

11. Mai 2012 um 11:26 Uhr
@WanderNauta: Denn wenn dies nicht der Fall wäre, bliebe keine andere Wahl, als alle Iterationen durchzuführen, um festzustellen, ob der Endwert kleiner als 5 ist.

– Oliver Charlesworth

11. Mai 2012 um 11:28 Uhr
Eigentlich ist es nicht so schlimm. Das Zählen der Listenlänge ist nicht so komplex. Und ich weiß, dass moderne Optimierer sogar UB beim Überlauf von vorzeichenbehafteten Ganzzahlen ausnutzen, um festzustellen, ob eine Reihe von Inkrementen zu einer monoton ansteigenden Variablen führt. (unsigned tut es seitdem nicht UINT_MAX+1 < UINT_MAX).

– MSalter

12. Mai 2012 um 12:56 Uhr

Eigentlich in C++11, std::list ist optimiert u size() wird in konstanter Zeit zurückgegeben.

Für C++03, size() arbeitet tatsächlich in linearer Zeit, da es jedes Mal die Elemente zählen muss.

Würde die Funktion size() alle N Listenmitglieder finden und zählen, oder wäre sie für einen Kurzschluss optimiert, nachdem 5 Mitglieder gefunden wurden?

Ich habe diese Art der Optimierung in der Praxis noch nie gesehen. Obwohl es sicherlich legal ist, bezweifle ich, dass es einen Compiler gibt, der so etwas tatsächlich implementiert.

Nur als Randbemerkung, ähnlicher Code in einer funktionalen Programmiersprache wie Haskell wird nur bis zur erforderlichen Tiefe erweitert.

– Jaywalker

11. Mai 2012 um 11:38 Uhr
@Jaywalker: Ich bin mir nicht so sicher wie du. Sie müssen eine erstellen longer-than Methode für diese mich denkt.

– Matthias M.

11. Mai 2012 um 11:49 Uhr
Ich halte mich da raus, bis ich das Etikett auf SO gesehen habe, wusste ich nicht, was Haskell ist. Ich habe StandardML im College gemacht.

– Luchian Grigore

11. Mai 2012 um 11:50 Uhr
In C++ könnte die Optimierung mit abscheulicher Operatorüberladung für die erfolgen < Operator…..

– R.. GitHub HÖR AUF, EIS ZU HELFEN

11. Mai 2012 um 13:23 Uhr
@Jaywalker Ab sofort length xs < k wird die gesamte Liste in GHC durchlaufen, und ich kenne keine Implementierung, die sie verkürzt. Sie würden Abkürzungen mit bekommen genericLength xs < k und einen geeigneten Lazy-Number-Typ. Oder mit einer Rewrite-Regel forall k xs. length xs < k = if k < 1 then False else null (drop (k-1) xs), aber das wäre Ihre eigene Sache, nicht die des Compilers. Und es würde das Verhalten für ändern length (1:2:undefined) < 2 Aus diesem Grund kann der Compiler sie beispielsweise nicht bereitstellen.

– Daniel Fischer

11. Mai 2012 um 14:04 Uhr

Die Funktion myList.size() selbst kann nicht für den Zweck kompiliert werden, für den Sie sie verwenden, daher bestimmt sie die gesamte Größe. Um die von Ihnen vorgeschlagene Optimierung zu erhalten, benötigen Sie anstelle der allgemeinen eine dedizierte Prädikatfunktion size()etwas wie bool sizeLessThan(int);.

Aber theoretisch ist dies eine Optimierung, die der Compiler beobachten könnte. Die Frage ist, kommt so etwas in der Praxis vor?

– Oliver Charlesworth

11. Mai 2012 um 11:23 Uhr
Wenn der Compiler beweisen kann, dass der Rest keine Rolle spielt, hat er das Recht, sich nicht darum zu kümmern, solange das beobachtbare Verhalten korrekt ist. Es ist theoretisch möglich, dass ein Compiler dies beweist, nur ein wenig knifflig in der Praxis.

– Flexo
♦

11. Mai 2012 um 11:23 Uhr
Sicher, es ist möglich, aber um dies zu bekommen, wäre etwas Nicht-Allgemeines erforderlich. Sie müssen damit rechnen, dass sich Code für solche Dinge (im allgemeinen Fall) entweder in einer Bibliothek oder zumindest in einem anderen Objekt befindet und daher auf generische Weise verknüpft ist (was die Wahrscheinlichkeit solcher spezialisierter Optimierungen eliminiert).

– mah

11. Mai 2012 um 11:25 Uhr

NEIN Sie fragen, ob der Compiler bewirken kann, dass sich eine Funktion je nach Verwendung ihrer Ergebnisse unterschiedlich verhält. Dies könnte möglicherweise nur für Inline-Funktionen durchgeführt werden, bei denen der Aufrufer und die Funktion gleichzeitig zusammen kompiliert werden. Es scheint eine ziemliche Strecke für alles darüber hinaus zu sein.

12055900cookie-checkOptimieren C- und C++-Compiler Vergleiche mit Funktionsaufrufen?

#c++ #Komplexitätstheorie #Optimierung