Index oder Iterator?

Hallo,
welche der beiden Versionen ist schneller oder verbraucht weniger Speicher?

std::vector<std::unique_ptr<object> > objects;
// über iterator
for (auto it = objects.begin(); it != objects.end(); ++it) {
	(*it)->doSomething();
}

// über index
for (int i = 0; i < objects.size(); ++i) {
    objects[i]->doSomething();
}

object ist in diesem Fall eine abstrakte Basisklasse. Kann ich da eigentlich den Pointer irgendwie umgehen?

Oberon_0

Die mit Iteratoren ist schneller, und verbraucht gleich viel Speicher. Falls der Compiler optimiert könnte das Ganze im Binary aber wieder gleich aussehen.
Grund: Beim Zugriff via Index muss jedesmal eine Zeiger-Addition ausgeführt werden, etwa wie vec.begin() + index . Tatsächlich sieht das bei VS10 so aus:

reference operator[](size_type _Off)
{	// subscript mutable sequence
	return (*(begin() + _Off));
}

EDIT: Falscher Code, das vorher war (glaube ich) der Indexoperator eines Iterators.

EOutOfResources

Normalerweise sollte ein Indexoperator einem Iterator (was die Geschwindigkeit angeht) überlegen sein. Aber Datenstrukturen wie Listen lassen sich kaum über einen Indexoperator ansprechen (oder nur sehr langsam). Zudem erlaubt ein Iterator das Wechseln der Speicherklasse ohne den wesentlichen Code umzuschreiben.

EOutOfResources

Oberon_0 schrieb:

Zeiger-Addition

Der Indexoperator des Vektors ist ungeprüft. So sollte es doch beinahe nichts kosten, oder irre ich mich?

hustbaer

Oberon_0 schrieb:

Die mit Iteratoren ist schneller, und verbraucht gleich viel Speicher.

EOutOfResources schrieb:

Normalerweise sollte ein Indexoperator einem Iterator (was die Geschwindigkeit angeht) überlegen sein.

Wow. Beides falsch.

Richtige Antwort: kann so oder so ausgehen.

Eisflamme

Siehe dazu auch eine von mir angestoßene Diskussion: http://www.c-plusplus.net/forum/283008

Edit: Ok, hat nur peripher damit zu tun, aber egal... Assoziationen schaffen ist doch immer gut.

Werner Salomon

EOutOfResources schrieb:

Normalerweise sollte ein Indexoperator einem Iterator (was die Geschwindigkeit angeht) überlegen sein.

Theoretisch ist das falsch, da die Iteratoren eine Addition eines Offsets pro Schleifendurchlauf weniger machen müssen.
Praktisch hängt es aber von den Fähigkeiten des verwendeten Compilers ab.

Habe gerade den Visual-C++-Express-2008 zur Hand - da sieht das so aus: folgender Code

vector< int > v(10000,2);
    for( int n=1200; --n; ) // damit ich überhaupt eine Zeit messen kann 
    {
        for( int i=0; i<v.size(); ++i )
            ++v[i];
    }

braucht auf meine PC ca. 15ms

und mit Iterator

for( int n=1200; --n; )
    {
        for( vector< int >::iterator i = v.begin(); i != v.end(); ++i )
            ++*i;
    }

schafft es nur in 84ms - also deutlich langsamer. Sieht man sich den Maschinencode an, so ist der deutlich suboptimal.

Aber der Sieger ist:

struct inc
{
    void operator()( int& i ) const
    {
        ++i;
    }
};
// ...
    for( int n=1200; --n; )
    {
        for_each( v.begin(), v.end(), inc() );
    }

mit nur 8ms, also fast doppelt so schnell wie die Index-Variante. Wer hätte das gedacht!

Gruß
Werner

drakon

Werner Salomon schrieb:

mit nur 8ms, also fast doppelt so schnell wie die Index-Variante. Wer hätte das gedacht!

Hmm. Das dürfte aber lediglich von dem size() herrühren. for_each macht ansonsten genau das gleiche, wie die erste Variante.

Hast du das auch mit dem extrahiertem size Aufruf probiert? Sollte dann das gleiche Ergebnis geben.

volkard

Werner Salomon schrieb:

EOutOfResources schrieb:

Normalerweise sollte ein Indexoperator einem Iterator (was die Geschwindigkeit angeht) überlegen sein.

Theoretisch ist das falsch, da die Iteratoren eine Addition eines Offsets pro Schleifendurchlauf weniger machen müssen.

Nee, es ist theoretisch oft wahr, weil der Prozessor den Indexzugriff kostenlos schafft, und bei zwei beteiligten Arrays gleich ein Register weniger gebraucht wird, und das ist frei für weiter außen liegende Aufgaben. Oder überhaupt erst verwendbar. (Frei aus dem AMD Optimierungshandbuch, die sprachen von register pressure.)

Praktisch sollte hier kein Unterschied messbar sein. Falls doch, sind es die zusätzlichen Debug-Funktionen des MSVC, die schaltet man AFAIR nicht aus, wenn man auf Release umstellt, sondern muß noch komische Makros dazu setzen. Oder war das erst ab dem Visual Studio 2010?

hustbaers "Richtige Antwort: kann so oder so ausgehen." kann ich nur zustimmen, möchte es noch ergänzen mit "Und zwar aus Gründen, die außerhalb des zu messenden Codes liegen."

volkard

Das hier

for( int i=0; i!=v.size(); ++i )
            ++v[i];

ergibt bei mir mit
g++ -march=native -DNDEBUG --save-temps -O3 main.cpp
lediglich "normalen" assembler-code.

Aber

int s=v.size();
        for( int i=0; i!=s; ++i )
            ++v[i];

erzeugt MMX-Code.

Außerdem erzeugen die Iterator-Varianten MMX-Code, egal, ob ich mir end() vorher in einer Variablen merke.

???

brotbernd

Werner Salomon schrieb:

for( int n=1200; --n; )
    {
        for( vector< int >::iterator i = v.begin(); i != v.end(); ++i )
            ++*i;
    }
schafft es nur in 84ms - also deutlich langsamer. Sieht man sich den Maschinencode an, so ist der deutlich suboptimal.

Auch mit

#define _SECURE_SCL 0

probiert?.

Man kann zwar mal drüber nachdenken und zum Spaß auch mal nachmessen aber nach Optimierungen sind die Unterschiede so gering oder überhaupt nicht vorhanden, dass ich die Entscheidung bei sowas nie aufgrund von ein paar nanosekunden treffen würde. Iteratoren haben eigentlich immer Vorteile und den Index benutze ich bei Random Access Conatinern eigentlich nur, wenn ich ihn noch irgendwie anders benutze und beim Einsatz von Iteratoren einen zusätzlichen Zähler definieren müsste.
Sofern ohne große Umstände anwendbar finden man aber das Optimum (in Effektivität, Flexibilität, Lesbarkeit (ok, ist oft auch geschmacksache)) oft in <algorithm>

Ich habs mal so mit for_each() aus <algortithm> versucht:

std::for_each(objects.begin(), objects.end(), [](std::unique_ptr<object> ptr) {ptr->doSomething();});

Über Lesbarkeit lässt sich streiten, jedoch bekomm ich imemr folgende Fehlermeldung:

error C2248: "std::unique_ptr<_Ty>::unique_ptr": Kein Zugriff auf private Member, dessen Deklaration in der std::unique_ptr<_Ty>-Klasse erfolgte.

ipsec

Nimm den Pointer als const-Referenz.

Danke, so klappts, aber wieso muss ich hier eine Referenz verwenden?

ipsec

Weil unique_ptr noncopyable ist.

Eisflamme

Die Fehlermeldung bezieht sich übrigens auf den copy-ctor, der eben wegen noncopyableness private ist. Vielleicht hilft Dir das?