Wird strlen mehrfach berechnet, wenn es in einer Schleifenbedingung verwendet wird?

Lesezeit: 8 Minuten

Benutzeravatar von Daisy
Gänseblümchen

Ich bin mir nicht sicher, ob der folgende Code redundante Berechnungen verursachen kann, oder ist er Compiler-spezifisch?

for (int i = 0; i < strlen(ss); ++i)
{
    // blabla
}

Werden strlen() jedes Mal wenn berechnet werden i steigt?

  • Ich vermute, dass ohne eine ausgeklügelte Optimierung, die erkennen kann, dass sich ‘ss’ in der Schleife nie ändert, dann ja. Am besten kompilieren, und sich die Assembly anschauen.

    – MerickOWA

    6. Juli 2012 um 15:21 Uhr


  • Es hängt vom Compiler ab, von der Optimierungsstufe und davon, was Sie tun (könnten). ss innerhalb der Schleife.

    – Christo Iljew

    6. Juli 2012 um 15:21 Uhr

  • Wenn der Compiler das beweisen kann ss nie modifiziert wird, kann es die Berechnung aus der Schleife ziehen.

    – Daniel Fischer

    6. Juli 2012 um 15:22 Uhr

  • @Mike: “Kompilierzeitanalyse von genau dem, was strlen tut, erforderlich” – strlen ist wahrscheinlich intrinsisch, in diesem Fall weiß der Optimierer, was er tut.

    – Steve Jessop

    6. Juli 2012 um 15:33 Uhr


  • @MikeSeymour: Es gibt kein vielleicht, vielleicht nicht. strlen ist durch den C-Sprachstandard definiert, und sein Name ist für die von der Sprache definierte Verwendung reserviert, sodass es einem Programm nicht freisteht, eine andere Definition bereitzustellen. Der Compiler und der Optimierer sind berechtigt anzunehmen, dass strlen ausschließlich von seiner Eingabe abhängt und sie oder irgendeinen globalen Zustand nicht modifiziert. Die Herausforderung bei der Optimierung besteht hier darin, festzustellen, dass der Speicher, auf den ss zeigt, nicht durch Code innerhalb der Schleife verändert wird. Das ist mit aktuellen Compilern durchaus machbar, abhängig vom konkreten Code.

    – Eric Postpischil

    6. Juli 2012 um 15:41 Uhr

Benutzeravatar von Mike Seymour
Mike Seymour

Ja, strlen() wird bei jeder Iteration ausgewertet. Es ist möglich, dass der Optimierer im Idealfall daraus schließen kann, dass sich der Wert nicht ändert, aber ich persönlich würde mich nicht darauf verlassen.

Ich würde sowas machen

for (int i = 0, n = strlen(ss); i < n; ++i)

oder evtl

for (int i = 0; ss[i]; ++i)

solange sich die Länge der Zeichenfolge während der Iteration nicht ändert. Wenn ja, müssen Sie entweder anrufen strlen() jedes Mal, oder behandeln Sie es durch kompliziertere Logik.

  • Wenn Sie wissen, dass Sie die Saite nicht manipulieren, ist die zweite weitaus vorzuziehen, da dies im Wesentlichen die Schleife ist, die ausgeführt wird strlen ohnehin.

    – mlibby

    6. Juli 2012 um 15:35 Uhr

  • @alk: Wenn die Zeichenfolge möglicherweise gekürzt wird, sind beide falsch.

    – Mike Seymour

    6. Juli 2012 um 15:36 Uhr

  • @alk: Wenn Sie die Zeichenfolge ändern, ist eine for-Schleife wahrscheinlich nicht der beste Weg, um über jedes Zeichen zu iterieren. Ich denke, eine While-Schleife ist direkter und einfacher, den Indexzähler zu verwalten.

    – mlibby

    6. Juli 2012 um 15:40 Uhr

  • ideale Umstände umfassen das Kompilieren mit GCC unter Linux, wo strlen ist gekennzeichnet als __attribute__((pure)) ermöglicht dem Compiler, mehrere Aufrufe zu vermeiden. GCC-Attribute

    – David Rodríguez – Dribeas

    6. Juli 2012 um 15:42 Uhr

  • Die zweite Version ist die ideale und idiomatischste Form. Es ermöglicht Ihnen, die Zeichenfolge nur einmal statt zweimal zu übergeben, was eine viel bessere Leistung (insbesondere Cache-Kohärenz) für lange Zeichenfolgen bietet.

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

    6. Juli 2012 um 17:26 Uhr

Benutzeravatar von codeDEXTER
codeDEXTER

Ja, jedes Mal, wenn Sie die Schleife verwenden. Dann wird jedes Mal die Länge der Zeichenfolge berechnet. also benutze es so:

char str[30];
for ( int i = 0; str[i] != '\0'; i++)
{
//Something;
}

Im obigen Code str[i] überprüft nur ein bestimmtes Zeichen in der Zeichenfolge an der Position i Jedes Mal, wenn die Schleife einen Zyklus startet, benötigt sie weniger Speicher und ist effizienter.

Sieh dir das an Verknüpfung für mehr Informationen.

Im folgenden Code jedes Mal, wenn die Schleife ausgeführt wird strlen zählt die Länge der gesamten Zeichenfolge, was weniger effizient ist, mehr Zeit in Anspruch nimmt und mehr Speicher benötigt.

char str[];
for ( int i = 0; i < strlen(str); i++)
{
//Something;
}

  • kann ich zustimmen“[it] ist effizienter”, verbraucht aber weniger Speicher? Der einzige Unterschied in der Speichernutzung, den ich mir vorstellen kann, wäre in der Aufrufliste während der strlen aufrufen, und wenn Sie so knapp laufen, sollten Sie wahrscheinlich darüber nachdenken, auch ein paar andere Funktionsaufrufe zu eliminieren …

    – Benutzer

    6. Juli 2012 um 20:17 Uhr

  • @MichaelKjörling Nun, wenn Sie “strlen” verwenden, muss es in einer Schleife jedes Mal, wenn die Schleife ausgeführt wird, die gesamte Zeichenfolge scannen, während im obigen Code die “str[ix]”, scannt es während jedes Zyklus der Schleife nur ein Element, dessen Position durch “ix” dargestellt wird. Daher benötigt es weniger Speicher als “strlen”.

    – codeDEXTER

    6. Juli 2012 um 20:42 Uhr


  • Ich bin mir nicht sicher, ob das wirklich viel Sinn macht. Eine sehr naive Implementierung von strlen wäre so etwas wie int strlen(char *s) { int len = 0; while(s[len] != '\0') len++; return len; } Das ist ziemlich genau das, was Sie im Code in Ihrer Antwort tun. Ich behaupte nicht, dass es mehr ist, die Zeichenfolge einmal statt zweimal zu durchlaufen Zeit-effizient, aber ich sehe nicht, dass der eine oder andere mehr oder weniger Speicher verbraucht. Oder beziehen Sie sich auf die Variable, die zum Halten der Zeichenfolgenlänge verwendet wird?

    – Benutzer

    6. Juli 2012 um 20:49 Uhr

  • @MichaelKjörling Bitte sehen Sie sich den oben bearbeiteten Code und den Link an. Und was den Speicher betrifft – jedes Mal, wenn die Schleife ausgeführt wird, wird jeder Wert, der iteriert wird, im Speicher gespeichert, und im Falle von ‘strlen’, da die gesamte Zeichenfolge immer wieder gezählt wird, ist mehr Speicher zum Speichern erforderlich. und auch, weil C++ im Gegensatz zu Java keinen “Garbage Collector” hat. Dann kann ich mich auch irren. siehe Link zum Fehlen von “Garbage Collector” in C++.

    – codeDEXTER

    6. Juli 2012 um 21:55 Uhr

  • @aashis2s Das Fehlen eines Garbage Collectors spielt nur beim Erstellen von Objekten auf dem Heap eine Rolle. Objekte auf dem Stapel werden zerstört, sobald das Zielfernrohr und endet.

    – Ikke

    10. Juli 2012 um 19:32 Uhr

Benutzeravatar von Misch
Misch

Ein guter Compiler berechnet es vielleicht nicht jedes Mal, aber ich glaube nicht, dass man sicher sein kann, dass es jeder Compiler tut.

Außerdem muss der Compiler das wissen strlen(ss) ändert sich nicht. Dies gilt nur, wenn ss wird nicht eingewechselt for Schleife.

Zum Beispiel, wenn Sie eine Nur-Lese-Funktion verwenden ss in for Schleife aber nicht deklarieren ss-Parameter als constder Compiler kann das nicht einmal wissen ss wird in der Schleife nicht verändert und muss berechnet werden strlen(ss) in jeder Iteration.

  • +1: Nicht nur muss ss nicht geändert werden for Schleife; Es darf nicht von einer in der Schleife aufgerufenen Funktion zugänglich sein und von ihr geändert werden (entweder weil es als Argument übergeben wird oder weil es eine globale Variable oder eine Dateibereichsvariable ist). Const-Qualifikation kann auch ein Faktor sein.

    – Jonathan Leffler

    6. Juli 2012 um 15:25 Uhr


  • Ich halte es für höchst unwahrscheinlich, dass der Compiler wissen könnte, dass sich ‘ss’ nicht ändert. Es könnte streunende Zeiger geben, die auf Speicher innerhalb von ‘ss’ zeigen, von denen der Compiler keine Ahnung hat, die ‘ss’ ändern könnten.

    – MerickOWA

    6. Juli 2012 um 15:25 Uhr

  • Jonathan hat Recht, eine lokale Konstantenzeichenfolge könnte die einzige Möglichkeit für den Compiler sein, sicherzustellen, dass es keine Möglichkeit für ‘ss’ gibt, sich zu ändern.

    – MerickOWA

    6. Juli 2012 um 15:27 Uhr

  • @MerickOWA: in der Tat, das ist eines der Dinge, die restrict ist für in C99.

    – Steve Jessop

    6. Juli 2012 um 15:27 Uhr

  • Bezüglich deines letzten Absatzes: Rufst du eine Nur-Lese-Funktion auf ss in der for-Schleife, dann auch dann, wenn ihr Parameter deklariert ist const char*der Compiler still muss die Länge neu berechnen, es sei denn, (a) es weiß das ss auf ein const-Objekt zeigt, anstatt nur ein Zeiger auf const zu sein, oder (b) es kann die Funktion einbetten oder anderweitig sehen, dass es schreibgeschützt ist. Ein Nehmen const char* Parameter ist nicht ein Versprechen, die Daten, auf die verwiesen wird, nicht zu ändern, da es gültig ist, darauf umzuwandeln char* und modify vorausgesetzt, dass das geänderte Objekt nicht konstant und kein Zeichenfolgenliteral ist.

    – Steve Jessop

    6. Juli 2012 um 15:31 Uhr


Wenn ss ist vom Typ const char * und du wirfst das nicht weg constinnerhalb der Schleife, die der Compiler möglicherweise nur aufruft strlen einmal, wenn Optimierungen eingeschaltet sind. Aber das ist sicherlich kein Verhalten, auf das man sich verlassen kann.

Die solltest du dir sparen strlen ergeben eine Variable und verwenden diese Variable in der Schleife. Wenn Sie keine zusätzliche Variable erstellen möchten, können Sie, je nachdem, was Sie tun, möglicherweise damit durchkommen, die Schleife umzukehren, um rückwärts zu iterieren.

for( auto i = strlen(s); i > 0; --i ) {
  // do whatever
  // remember value of s[strlen(s)] is the terminating NULL character
}

Formal ja, strlen() wird voraussichtlich für jede Iteration aufgerufen.

Wie auch immer, ich möchte nicht die Möglichkeit der Existenz einer cleveren Compiler-Optimierung negieren, die jeden nachfolgenden Aufruf von strlen() nach dem ersten wegoptimiert.

Benutzeravatar von JaredPar
JaredPar

Der Prädikatcode in seiner Gesamtheit wird bei jeder Iteration von ausgeführt for Schleife. Um das Ergebnis der strlen(ss) Aufruf des Compilers müsste das zumindest wissen

  1. Die Funktion strlen war nebenwirkungsfrei
  2. Die Erinnerung zeigte auf von ss ändert sich für die Dauer der Schleife nicht

Der Compiler kennt beides nicht und kann sich daher das Ergebnis des ersten Aufrufs nicht sicher merken

Benutzeravatar von Kalai Selvan Ravi
Kalai Selvan Ravi

Ja. strlen wird jedes Mal berechnet, wenn ich zunehme.

Wenn du ss nicht geändert mit in der Schleife meint es wird die Logik nicht beeinflussen andernfalls wird es sich auswirken.

Es ist sicherer, den folgenden Code zu verwenden.

int length = strlen(ss);

for ( int i = 0; i < length ; ++ i )
{
 // blabla
}

1422100cookie-checkWird strlen mehrfach berechnet, wenn es in einer Schleifenbedingung verwendet wird?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy