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

109

Ich bin nicht sicher, ob der folgende Code redundante Berechnungen verursachen kann oder ob er compilerspezifisch ist.

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

Wird strlen()jedes Mal berechnet, wenn ierhöht?

Gänseblümchen
quelle
14
Ich gehe davon aus, dass sich ohne eine ausgeklügelte Optimierung, die erkennen kann, dass sich 'ss' nie in der Schleife ändert, ja. Am besten kompilieren und die Baugruppe betrachten, um zu sehen.
MerickOWA
6
Dies hängt vom Compiler, von der Optimierungsstufe und davon ab, was Sie (möglicherweise) ssinnerhalb der Schleife tun .
Hristo Iliev
4
Wenn der Compiler nachweisen kann, dass er ssniemals geändert wird, kann er die Berechnung aus der Schleife heben.
Daniel Fischer
10
@Mike: "Analyse der Kompilierungszeit genau erforderlich, was strlen tut" - strlen ist wahrscheinlich eine intrinsische Analyse. In diesem Fall weiß der Optimierer, was es tut.
Steve Jessop
3
@ MikeSeymour: Es gibt kein vielleicht, vielleicht auch nicht. strlen wird durch den C-Sprachstandard definiert, und sein Name ist für die durch die Sprache definierte Verwendung reserviert, sodass ein Programm nicht frei ist, eine andere Definition bereitzustellen. Der Compiler und der Optimierer sind berechtigt anzunehmen, dass strlen ausschließlich von seiner Eingabe abhängt und es oder einen globalen Status nicht ändert. Die Herausforderung bei der Optimierung besteht darin, festzustellen, dass der Speicher, auf den ss zeigt, durch keinen Code in der Schleife geändert wird. Dies ist mit aktuellen Compilern je nach Code durchaus möglich.
Eric Postpischil

Antworten:

138

Ja, strlen()wird bei jeder Iteration ausgewertet. Unter idealen Umständen kann der Optimierer möglicherweise ableiten, dass sich der Wert nicht ändert, aber ich persönlich würde mich nicht darauf verlassen.

Ich würde so etwas tun

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

oder möglicherweise

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

Solange sich die Länge der Zeichenfolge während der Iteration nicht ändert. Wenn dies der Fall sein könnte, müssen Sie entweder strlen()jedes Mal aufrufen oder die kompliziertere Logik verwenden.

Mike Seymour
quelle
14
Wenn Sie wissen, dass Sie den String nicht manipulieren, ist der zweite weitaus vorzuziehen, da dies im Wesentlichen die Schleife ist, die strlenohnehin ausgeführt wird.
mlibby
26
@alk: Wenn die Zeichenfolge möglicherweise verkürzt wird, sind beide falsch.
Mike Seymour
3
@alk: Wenn Sie die Zeichenfolge ändern, ist eine for-Schleife wahrscheinlich nicht der beste Weg, um über jedes Zeichen zu iterieren. Ich würde denken, eine while-Schleife ist direkter und einfacher zu verwalten.
mlibby
2
Zu den idealen Umständen gehört das Kompilieren mit GCC unter Linux, wobei strlenmarkiert ist, __attribute__((pure))dass der Compiler mehrere Aufrufe vermeiden kann. GCC Attribute
David Rodríguez - Dribeas
6
Die zweite Version ist die ideale und idiomatischste Form. Sie können die Zeichenfolge nur einmal und nicht zweimal übergeben, was bei langen Zeichenfolgen eine viel bessere Leistung (insbesondere Cache-Kohärenz) bietet.
R .. GitHub STOP HELPING ICE
14

Ja, jedes Mal, wenn Sie die Schleife verwenden. Dann wird jedes Mal die Länge der Zeichenfolge berechnet. Verwenden Sie es also folgendermaßen:

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

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

Weitere Informationen finden Sie unter diesem Link .

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

char str[];
for ( int i = 0; i < strlen(str); i++)
{
//Something;
}
codeDEXTER
quelle
3
Ich kann "[es] ist effizienter" zustimmen, aber weniger Speicher verwenden? Der einzige Unterschied in der Speichernutzung, den ich mir strlenvorstellen kann, liegt im Aufrufstapel während des Aufrufs. Wenn Sie so knapp sind, sollten Sie wahrscheinlich darüber nachdenken, auch einige andere Funktionsaufrufe zu eliminieren ...
ein CVn
@ MichaelKjörling Nun, wenn Sie "strlen" verwenden, muss in einer Schleife jedes Mal, wenn die Schleife ausgeführt wird, die gesamte Zeichenfolge gescannt werden, während im obigen Code "str [ix]" nur ein Element während jedes Zyklus der Schleife, deren Position durch "ix" dargestellt wird. Somit benötigt es weniger Speicher als "strlen".
CodeDEXTER
1
Ich bin mir nicht sicher, ob das wirklich 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; }genau das, was Sie im Code in Ihrer Antwort tun. Ich behaupte nicht , dass die Zeichenfolge einmal iterieren anstatt zweimal mehr Zeit -effiziente, aber ich sehe nicht , der ein oder andere mehr oder weniger Speicher benötigt wird. Oder beziehen Sie sich auf die Variable, mit der die Zeichenfolgenlänge gespeichert wird?
Ein
@ MichaelKjörling Bitte beachten Sie den oben bearbeiteten Code und den Link. Und was den Speicher betrifft - jedes Mal, wenn die Schleife ausgeführt wird, wird jeder einzelne Wert, der iteriert, im Speicher gespeichert, und im Fall von 'strlen', da der gesamte String immer wieder gezählt wird, wird mehr Speicher zum Speichern benötigt. 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
1
@ 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 der Umfang und das Ende erreicht sind.
Ikke
9

Ein guter Compiler berechnet es möglicherweise nicht jedes Mal, aber ich glaube nicht, dass Sie sicher sein können, dass jeder Compiler es tut.

Darüber hinaus muss der Compiler wissen, dass sich strlen(ss)dies nicht ändert. Dies gilt nur, wenn ssdie forSchleife nicht geändert wird.

Wenn Sie beispielsweise eine schreibgeschützte Funktion ssin der forSchleife verwenden, aber den ssParameter- nicht als deklarieren const, kann der Compiler nicht einmal wissen, dass ssdies in der Schleife nicht geändert wird, und muss strlen(ss)in jeder Iteration berechnen .

Misch
quelle
3
+1: Nicht nur darf ssnicht in der forSchleife geändert werden ; Es darf von keiner in der Schleife aufgerufenen Funktion aus zugänglich sein und von dieser geändert werden (entweder weil es als Argument übergeben wird oder weil es eine globale Variable oder eine Dateibereichsvariable ist). Auch die Const-Qualifikation kann ein Faktor sein.
Jonathan Leffler
4
Ich halte es für sehr unwahrscheinlich, dass der Compiler weiß, dass sich 'ss' nicht ändert. Es könnte streunende Zeiger geben, die auf den Speicher in 'ss' verweisen, von dem der Compiler keine Ahnung hat, dass er 'ss' ändern könnte
MerickOWA
Jonathan hat recht, eine lokale const-Zeichenfolge könnte der einzige Weg für den Compiler sein, um sicherzugehen, dass sich 'ss' nicht ändern kann.
MerickOWA
2
@MerickOWA: In der Tat, das ist eines der Dinge, restrictfür die in C99.
Steve Jessop
4
In Bezug auf Ihre letzte para: Wenn Sie eine Nur - Lese-Funktion rufen ssin der for-Schleife, dann auch , wenn der Parameter deklariert wird const char*, der Compiler noch die Länge , es sei denn entweder neu berechnen muss (a) es , das weiß , sszeigt auf ein konstantes Objekt, im Gegensatz dazu, nur ein Zeiger auf const zu sein, oder (b) kann es die Funktion inline oder auf andere Weise sehen, dass sie schreibgeschützt ist. Das Übernehmen eines const char*Parameters ist kein Versprechen, die Daten, auf die verwiesen wird, nicht zu ändern, da das Umwandeln char*und Ändern gültig ist, vorausgesetzt, das geänderte Objekt ist nicht const und kein Zeichenfolgenliteral.
Steve Jessop
4

Wenn dies ssvom Typ ist const char *und Sie die constNess innerhalb der Schleife nicht wegwerfen, ruft der Compiler möglicherweise nur strleneinmal auf, wenn Optimierungen aktiviert sind. Dies ist aber sicherlich kein Verhalten, auf das man zählen kann.

Sie sollten das strlenErgebnis in einer Variablen speichern und diese Variable in der Schleife verwenden. Wenn Sie keine zusätzliche Variable erstellen möchten, je nachdem, was Sie tun, müssen Sie möglicherweise die Schleife umkehren, 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
}
Prätorianer
quelle
1
Es ist ein Fehler, überhaupt anzurufen strlen. Schleife einfach bis zum Ende.
R .. GitHub STOP HELPING ICE
i > 0? Sollte das nicht i >= 0hier sein? Persönlich würde ich auch anfangen, strlen(s) - 1wenn ich rückwärts über den String iteriere, dann \0braucht das Beenden keine besondere Überlegung.
ein CVn
2
@ MichaelKjörling i >= 0funktioniert nur, wenn Sie auf initialisieren strlen(s) - 1, aber wenn Sie eine Zeichenfolge auf Null Länge haben, läuft der Anfangswert unter
Praetorian
@ Prætorian, guter Punkt auf der Zeichenfolge mit der Länge Null. Ich habe diesen Fall nicht berücksichtigt, als ich meinen Kommentar schrieb. Wertet C ++ den i > 0Ausdruck beim ersten Schleifeneintrag aus? Wenn dies nicht der Fall ist, haben Sie Recht, der Fall mit der Länge Null wird die Schleife definitiv durchbrechen. Wenn dies der Fall ist, erhalten Sie "einfach" einen vorzeichenbehafteten i== -1 <0, also keinen Schleifeneintrag, wenn die Bedingung erfüllt ist i >= 0.
Ein Lebenslauf
@ MichaelKjörling Ja, die Exit-Bedingung wird vor dem ersten Ausführen der Schleife ausgewertet. strlenDer Rückgabetyp von 'ist vorzeichenlos und wird daher (strlen(s)-1) >= 0für Zeichenfolgen mit der Länge Null als wahr ausgewertet.
Prätorianer
3

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

Auf jeden Fall möchte ich die Möglichkeit einer cleveren Compiler-Optimierung nicht negieren, die jeden aufeinanderfolgenden Aufruf von strlen () nach dem ersten optimiert.

alk
quelle
3

Der gesamte Prädikatcode wird bei jeder Iteration der forSchleife ausgeführt. Um das Ergebnis des strlen(ss)Aufrufs zu speichern, müsste der Compiler dies zumindest wissen

  1. Die Funktion strlenwar nebenwirkungsfrei
  2. Der Speicher, auf den von sszeigt, ändert sich für die Dauer der Schleife nicht

Der Compiler kennt keines dieser Dinge und kann sich daher das Ergebnis des ersten Aufrufs nicht sicher merken

JaredPar
quelle
Nun, es könnte diese Dinge mit statischer Analyse wissen, aber ich denke, Ihr Punkt ist, dass eine solche Analyse derzeit in keinem C ++ - Compiler implementiert ist, ja?
GManNickG
@GManNickG es könnte definitiv # 1 beweisen, aber # 2 ist schwieriger. Für einen einzelnen Thread könnte es dies definitiv beweisen, aber nicht für eine Umgebung mit mehreren Threads.
JaredPar
1
Vielleicht bin ich stur, aber ich denke, Nummer zwei ist auch in Multithread-Umgebungen möglich, aber definitiv nicht ohne ein wild starkes Inferenzsystem. Ich denke nur hier nach. definitiv jenseits des Rahmens eines aktuellen C ++ - Compilers.
GManNickG
@ GManNickG Ich glaube nicht, dass es in C / C ++ möglich ist. Ich konnte sehr leicht verstauen die Adresse ssin ein size_toder teilen sie unter mehreren auf byteWerte. Mein hinterhältiger Thread könnte dann einfach Bytes in diese Adresse schreiben, und der Compiler hätte eine Art zu verstehen, auf die er sich bezieht ss.
JaredPar
1
@JaredPar: Tut mir leid, Sie könnten behaupten, dass int a = 0; do_something(); printf("%d",a);dies nicht optimiert werden kann, auf der Grundlage, dass do_something()Sie Ihre nicht initialisierte int-Sache ausführen oder den Stapel zurückkriechen und aabsichtlich ändern könnten . Tatsächlich optimiert gcc 4.5 es do_something(); printf("%d",0);mit -O3
Steve Jessop
2

Ja . strlen wird jedes Mal berechnet, wenn ich mich erhöhe.

Wenn Sie nicht ss änderte sich mit der Schleife Mittel es nicht Logik beeinflussen sonst wird es beeinflussen.

Es ist sicherer, folgenden Code zu verwenden.

int length = strlen(ss);

for ( int i = 0; i < length ; ++ i )
{
 // blabla
}
Kalai Selvan Ravi
quelle
2

Ja, der strlen(ss)berechnet die Länge bei jeder Iteration. Wenn Sie das ssauf irgendeine Weise erhöhen und auch das erhöhen i; es würde eine Endlosschleife geben.

Kumar Shorav
quelle
2

Ja, die strlen()Funktion wird jedes Mal aufgerufen, wenn die Schleife ausgewertet wird.

Wenn Sie die Effizienz verbessern möchten, denken Sie immer daran, alles in lokalen Variablen zu speichern ... Es wird einige Zeit dauern, aber es ist sehr nützlich.

Sie können den folgenden Code verwenden:

String str="ss";
int l = strlen(str);

for ( int i = 0; i < l ; i++ )
{
    // blablabla
}
Rajan
quelle
2

Ja, strlen(ss)wird jedes Mal berechnet, wenn der Code ausgeführt wird.

Hisham Muneer
quelle
2

Heutzutage nicht üblich, aber vor 20 Jahren auf 16-Bit-Plattformen würde ich Folgendes empfehlen:

for ( char* p = str; *p; p++ ) { /* ... */ }

Selbst wenn Ihr Compiler bei der Optimierung nicht sehr klug ist, kann der obige Code noch zu einem guten Assemblycode führen.

Luciano
quelle
1

Ja. Der Test weiß nicht, dass ss innerhalb der Schleife nicht geändert wird. Wenn Sie wissen, dass es sich nicht ändern wird, würde ich schreiben:

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

Arrgh, es wird auch unter idealen Umständen verdammt!

Ab heute (Januar 2018) und gcc 7.3 und clang 5.0, wenn Sie kompilieren:

#include <string.h>

void bar(char c);

void foo(const char* __restrict__ ss) 
{
    for (int i = 0; i < strlen(ss); ++i) 
    {
        bar(*ss);
    }
}    

Also haben wir:

  • ss ist ein konstanter Zeiger.
  • ss ist markiert __restrict__
  • Der Schleifenkörper kann den Speicher, auf den er zeigt, in keiner Weise berühren ss(naja, es sei denn, er verletzt den __restrict__).

und dennoch führen beide Compiler strlen() jede einzelne Iteration dieser Schleife aus . Tolle.

Dies bedeutet auch, dass die Anspielungen / Wunschdenken von @Praetorian und @JaredPar nicht auftauchen.

einpoklum
quelle
0

JA, in einfachen Worten. Und es gibt ein kleines Nein in seltenen Fällen, in dem der Compiler dies wünscht, als Optimierungsschritt, wenn er feststellt, dass überhaupt keine Änderungen vorgenommen wurden ss. Aber in sicherem Zustand sollten Sie es als JA betrachten. Es gibt Situationen wie in multithreadedund ereignisgesteuerte Programme, es kann fehlerhaft werden, wenn Sie es als NEIN betrachten. Gehen Sie auf Nummer sicher, da dies die Programmkomplexität nicht zu stark verbessern wird.

Pervez Alam
quelle
0

Ja.

strlen()wird jedes Mal berechnet, wenn ierhöht und nicht optimiert.

Der folgende Code zeigt, warum der Compiler nicht optimieren sollte strlen().

for ( int i = 0; i < strlen(ss); ++i )
{
   // Change ss string.
   ss[i] = 'a'; // Compiler should not optimize strlen().
}
Amir Saniyan
quelle
Ich denke, dass diese spezielle Modifikation niemals die Länge von ss ändert, sondern nur den Inhalt, sodass (ein wirklich, wirklich cleverer) Compiler immer noch optimieren kann strlen.
Darren Cook
0

Wir können es leicht testen:

char nums[] = "0123456789";
size_t end;
int i;
for( i=0, end=strlen(nums); i<strlen(nums); i++ ) {
    putchar( nums[i] );
    num[--end] = 0;
}

Die Schleifenbedingung wird nach jeder Wiederholung ausgewertet, bevor die Schleife neu gestartet wird.

Achten Sie auch auf den Typ, mit dem Sie die Länge der Zeichenfolgen verarbeiten. es sollte das sein, size_twas wie unsigned intin stdio definiert wurde. Das Vergleichen und Casting kann zu intschwerwiegenden Sicherheitslücken führen.

Rsh
quelle
0

Nun, ich habe bemerkt, dass jemand sagt, dass es standardmäßig von jedem "cleveren" modernen Compiler optimiert wird. Übrigens Ergebnisse ohne Optimierung betrachten. Ich habe versucht:
Minimaler C-Code:

#include <stdio.h>
#include <string.h>

int main()
{
 char *s="aaaa";

 for (int i=0; i<strlen(s);i++)
  printf ("a");
 return 0;
}

Mein Compiler: g ++ (Ubuntu / Linaro 4.6.3-1ubuntu5) 4.6.3
Befehl zur Generierung von Assembler-Code: g ++ -S -masm = intel test.cpp

Gotten assembly code at the output:
    ...
    L3:
mov DWORD PTR [esp], 97
call    putchar
add DWORD PTR [esp+40], 1
    .L2:
     THIS LOOP IS HERE
    **<b>mov    ebx, DWORD PTR [esp+40]
mov eax, DWORD PTR [esp+44]
mov DWORD PTR [esp+28], -1
mov edx, eax
mov eax, 0
mov ecx, DWORD PTR [esp+28]
mov edi, edx
repnz scasb</b>**
     AS YOU CAN SEE it's done every time
mov eax, ecx
not eax
sub eax, 1
cmp ebx, eax
setb    al
test    al, al
jne .L3
mov eax, 0
     .....
Tebe
quelle
Ich würde es ablehnen, jedem Compiler zu vertrauen, der versucht hat, ihn zu optimieren, es sei denn, die Adresse der Zeichenfolge wurde restrict-qualifiziert. Während es einige Fälle gibt, in denen eine solche Optimierung legitim wäre, würde der Aufwand, der erforderlich ist, um solche Fälle ohne solche zuverlässig zu identifizieren restrict, mit ziemlicher Sicherheit den Nutzen übersteigen. Wenn die Adresse der Zeichenfolge jedoch ein const restrictQualifikationsmerkmal hätte, würde dies an und für sich ausreichen, um die Optimierung zu rechtfertigen, ohne auf etwas anderes achten zu müssen.
Supercat
0

Ich gehe auf Prætorians Antwort ein und empfehle Folgendes:

for( auto i = strlen(s)-1; i > 0; --i ) {foo(s[i-1];}
  • autoweil Sie sich nicht darum kümmern möchten, welcher Typ strlen zurückgibt. Ein C ++ 11-Compiler (z. B. gcc -std=c++0xnicht vollständig C ++ 11, aber automatische Typen funktionieren) erledigt dies für Sie.
  • i = strlen(s)weil Sie mit vergleichen möchten 0(siehe unten)
  • i > 0 weil der Vergleich mit 0 (etwas) schneller ist als der Vergleich mit einer anderen Zahl.

Nachteil ist, dass Sie verwenden müssen, i-1um auf die Zeichenfolgen zuzugreifen.

steffen
quelle