Iteration schrecklich ineffizient?

[Erwin2777]

Hallo!

Konstrukte wie dieses sind ja normalerweise an der Tagesordnung:

for(std::vector<int>::const_iterator it = v.begin(); it != v.end(); ++it)
{
    // ...
}

Nun muss aber doch vor jedem Durchlauf der Ausdruck "it != v.end()" ausgewertet werden, d.h. jedes Mal muss die end()-Methode aufgerufen werden. Ein const_iterator muss konstruiert werden, wird kopiert, zerstört und anschließend nochmal zerstört (es sei denn: Return Value Optimization). Und das in jedem Durchlauf!

Darum meine Frage: Wenn ihr wisst, dass der Container sich während der Schleife nicht ändert, speichert ihr dann den Iterator schon vorher? Also so:

const std::vector<int>::const_iterator end(v.end()); for(std::vector<int>::const_iterator it = v.begin(); it != end; ++it)
{
    // ...
}

Bringt das viel, wenn man in der Schleife nicht viel macht?

Danke!

[drakon]

Das macht so gut, wie gar nichts aus. Ich hätte noch nie beobachtet, dass mir das irgendwas an effizienz (merkbar) gekostet hätte.
Wenn du irgendetwas an einer Schleife optimieren musst (wenn überhaupt), dann ist es innerhalb. Oder allgemein die Iterationen zu verringern.
Aber wie schon oft klingt das sehr nach Premature optimization.

[tipp]

compilier mal im release mode

[asc]

Erwin2777 schrieb:

Darum meine Frage: Wenn ihr wisst, dass der Container sich während der Schleife nicht ändert, speichert ihr dann den Iterator schon vorher?

Nein, aber ich werte end() dennoch nur einmal aus:

for(std::vector<int>::const_iterator it=v.begin(), end=v.end(); it!=end; ++it)
{
    // ...
}

[Erwin2777]

asc schrieb:

Erwin2777 schrieb:

Darum meine Frage: Wenn ihr wisst, dass der Container sich während der Schleife nicht ändert, speichert ihr dann den Iterator schon vorher?

Nein, aber ich werte end() dennoch nur einmal aus:

for(std::vector<int>::const_iterator it=v.begin(), end=v.end(); it!=end; ++it)
{
    // ...
}

Das ist gut, danke!
Da spart man sich viel Tipperei.

[Fellhuhn]

Nur doof wenn sich end() ändert und man sich diese "Optimierung" angewöhnt hat.

[hellihjb]

Wenn ihr wisst, dass der Container sich während der Schleife nicht ändert

Das weiss man dann, wenn man ausschliesslich const-Methoden aufruft und dann ist jeder Compiler schlau genug, end auch nur einmal auszuwerten; schliesslich kann es sich nicht aendern.

[hustbaer]

hellihjb schrieb:

Wenn ihr wisst, dass der Container sich während der Schleife nicht ändert

Das weiss man dann, wenn man ausschliesslich const-Methoden aufruft und dann ist jeder Compiler schlau genug, end auch nur einmal auszuwerten; schliesslich kann es sich nicht aendern.

Falsch. Eine const Methode kann ein Objekt auch ändern (seis über den pösen const_cast, oder einfach dadurch dass mutable Member geändert werden).
Es kann leicht sein dass ein Compiler durch Inlining und einen guten Optimizer in der Lage ist alles wegzuoptimieren, aber mit const oder nicht-const hat das garnix zu tun.

[phalanx-fanboy]

hellihjb schrieb:

Wenn ihr wisst, dass der Container sich während der Schleife nicht ändert

Das weiss man dann, wenn man ausschliesslich const-Methoden aufruft und dann ist jeder Compiler schlau genug, end auch nur einmal auszuwerten; schliesslich kann es sich nicht aendern.

Wie bereits gesagt wurde, ist das nicht richtig.
Aber was noch dazu kommt, ist Aliasing.

Ich könnte ja in meiner Schleife eine Funktion aufrufen, die meinen Container verändert. Das muss ja gar nicht "direkt" geschehen, sondern kann im Worst Case über einen gecasteten void*-Zeiger gehen.

Das heißt: der Compiler kann nicht wissen, ob sich der Container in der Schleife ändern wird oder nicht. Und daher darf er eigentlich auch nichts wegoptimieren. Oder sehe ich das falsch?

[pusher]

*push*

Darf der compiler das nun weg optimieren oder nicht?
würd mich mal interessiern

[Badestrand]

pusher schrieb:

Darf der compiler das nun weg optimieren oder nicht?

Der Compiler darf machen was er will, solange sich das Programm so verhält, wie du es im Quelltext angegeben hast. Wenn er zweifelsfrei feststellen kann, dass der end()-Aufruf während der Iterationen immer das selbe Objekt zurückgibt, kann er sich den Wert selbst in einer temporären Variable speichern.

[Bashar]

Das hängt davon ab, welche Informationen dem Compiler zur Verfügung stehen. Er kann den Code zur Berechnung des Ausdrucks v.end() aus der Schleife herausheben, wenn er beweisen kann, dass der Code innerhalb der Schleife den Wert nicht verändert. Dazu hat er prinzipiell zwei Ansatzpunkte: (1) std::vector ist Teil der Standardbibliothek, der Compiler kann also spezielles Wissen über das Verhalten haben. Er könnte z.B. wissen, welche Operationen den end-Iterator verändern können. (2) Er kennt die Implementierung von end und allen anderen Vector-Methoden, weil diese inline sind. Es dürfte in den meisten Fällen einen end-Zeiger in std::vector geben, der nur an bestimmten anderen Stellen verändert wird.
Insgesamt muss er dann noch nachweisen, dass es keine legale Möglichkeit gibt, auf anderem Wege den Vektor zu verändern, indem er verfolgt, welche Zeiger und Referenzen noch auf diesen Vektor zeigen können. Beispiel:

extern void f(vector<bla>*);
extern g(bla&);

vector<bla> v;
f(&v);
for (vector<bla>::iterator i = v.begin(); v != v.end(); ++v) {
  g(*i);
}

Er muss jetzt Worst-Case-Annahmen treffen, nämlich dass f die Referenz irgendwo global speichert, g darauf Zugriff hat und v Elemente hinzufügt oder entfernt. Es wäre natürlich denkbar, dass bei der Übersetzung von f und g analysiert wird, was die tun, und als Metainformation irgendwo gespeichert wird, so dass diese Resultate in der Schleife zur Verfügung stehen. Der Fantasie sind da keine Grenzen gesetzt.

[Badestrand]

Oh, und der Vollständigkeit halber (hab ich in meinem Post zwei drüber auch vergessen): Es dürfen auch keine Seiteneffekte unterschlagen werden, z.B. wenn im Container mitgezählt wird, wie oft "end()" aufgerufen wird, darf der Aufruf nicht "einfach so" weg-optimiert werden. Der Compiler könnte aber die Zählervariable selbst um den entsprechenden Wert erhöhen.