Performancefrage: Iteratoren

hustbaer

SeppJ schrieb:

hustbaer schrieb:

Und welche STL tut das nicht?

GNU? Und vermutlich auch die kommerziellen STLs

Äh.
2x nein

Mag sein dass die GNU Standard-Library keine Checked-Iterators verwendet. Trotzdem ist die an genug Stellen langsamer als vergleichbarer C-Code. Denk bloss mal an iostreams...

SeppJ

hustbaer schrieb:

Mag sein dass die GNU Standard-Library keine Checked-Iterators verwendet. Trotzdem ist die an genug Stellen langsamer als vergleichbarer C-Code. Denk bloss mal an iostreams...

Du willst doch wohl nicht ernsthaft die popeligen IO-Funktionen aus der C-Standardbibliothek mit den mächtigen IO-Streams vergleichen?

edit: Vergleichen darfst du sie natürlich . Aber wenn du dabei feststellst, dass sie vergleichbar sind, dann ist dir nicht mehr zu helfen

hustbaer

Du willst doch wohl nicht ernsthaft behaupten dass man mit der Standard C++ Library alles gleich schnell (oder schneller) machen kann als mit vergleichbaren C-Konstrukten, wo man alles zu Fuss programmiert (weil man es muss)?

EDIT: und natürlich sind die vergleichbar, was bist denn du für ein Vogel. OK, sie können mehr. Diese Feststellung ist das Resultat eines Vergleichs. Was impliziert dass sie vergleichbar sind, denn sonst ... alles klar? Mir ist schon klar was du meinst, nur mit vector+Iteratoren vs. nackte Arrays ist es nichts anderes.

SeppJ

hustbaer schrieb:

Du willst doch wohl nicht ernsthaft behaupten dass man mit der Standard C++ Library alles gleich schnell (oder schneller) machen kann als mit vergleichbaren C-Konstrukten, wo man alles zu Fuss programmiert (weil man es muss)?

Natürlich sind die Sachen genauso schnell wie C-Konstrukte die das gleiche tun. Zumindest wenn die STL-Bauer keine ungeforderten Checks einbauen. Ein gut programmierter Vector mit Iteratoren ist exakt so schnell wie ein dynamisches Array mit Zählvariable, weil sie genau das gleiche machen. Das gilt auch für die anderen Teile der C++-Bibliothek.

IO-Streams sind langsamer eben weil sie viel mehr können. Wenn man z.B. Zeichenfolgen in Zahlen umwandeln kann, kann man ein flottes atoi nehmen. Dann geht das aber nur mit ASCII-Dezimalzahlen. Will man alle möglichen Zahlenformate (eventuell sogar lokalisiert) als Quelle zulassen, muss man in C ordentlich dazu programmieren. Das Ergebnis dürfte in etwa so schnell sein wie ein ostream::operator>>(int). Da man dies nicht immer unbedingt braucht ist atoi auch nach wie vor ein Teil von C++.

edit: Und du hast damit angefangen die umgangssprachliche Bedeutung von "vergleichbar" zu benutzen und solltest daher ganz genau wissen, was damit gemeint ist.

brotbernd

int main() 
{
    const size_t size = 10000000;
    typedef std::vector<int> Vector;
    Vector a(size), b(size), c(size, 0);
    std::generate(a.begin(), a.end(), rand);
    std::generate(b.begin(), b.end(), rand);
    {
        HrTimer t;
        for(size_t n = 0; n < size; ++n)
            c[n] = a[n] * b[n];
    }
    {
        HrTimer t;
        for(Vector::iterator ia = a.begin(), ib = b.begin(), ic = c.begin(), ea = a.end();
            ia != ea; ++ia, ++ib, ++ic)
            *ic = *ia * *ib;
    }
    {
        HrTimer t;
        for(Vector::iterator ia = a.begin(), ib = b.begin(), ic = c.begin();
            ia != a.end(); ++ia, ++ib, ++ic)
            *ic = *ia * *ib;
    }
    {
        HrTimer t;
        std::transform(a.begin(), a.end(), b.begin(), c.begin(), std::multiplies<int>());
    }
    return 0;
}

// msvc10 #define _SECURE_SCL 0
47.0475 ms
45.8322 ms
45.9266 ms
46.7511 ms
// msvc10 #define _SECURE_SCL 1
49.4768 ms
105.436 ms
129.12 ms
46.0183 ms

Ich hab mir den Code nicht angeguckt, aber ich vermute mal das alle Versionen mehr oder weniger den gleichen Code generieren, wenn checked Iteratoren deaktiviert sind.
In diesem Fall ist es also performance technisch völlig wurst.
Ansonsten sind immer zunächst STL Algorithmen zu bevorzugen (dort gibt es oft für Spezialfälle effizientere Überladungen), wenn da nichst passt nehm ich die die Form for(Iter i = v.begin(), e = v.end(); i!=e; ++i) . Ich kann jetzt zwar keinen Fall konstruieren, wo der Aufruf von end() nicht wegoptimiert wird, aber diese Version gibt bei einfach ein besseres Gefühl;)

It0101

@HustBaer:

Deine Aussage widerspricht aber der landläufigen Meinung im C++-Forum dass absolut nichts aber auch garnichts schneller ist, als die STL ( in jeglicher Form der Implementierung ) und was man auf keinen Fall tun sollte, ist irgendwelche Dinge, auf keinen Fall Container, selber zu programmieren... Auf gar keinen Fall!!!

[Vorsicht, dieser Beitrag könnte ein gewisses Maß an Ironie enthalten]

SeppJ

It0101 schrieb:

( in jeglicher Form der Implementierung )

Nee, das ist bekannt das dies nicht so ist. Es kommt schließlich jeden Monat jemand daher der die MSVC-STL mit C vergleicht und sich wundert warum diese im Releasemodus so langsam ist.

krümelkacker

hustbaer schrieb:

Mag sein dass die GNU Standard-Library keine Checked-Iterators verwendet.

libstdc++ bietet beides. Den STL-Debug-Modus kann man per -D_GLIBCXX_DEBUG aktivieren.

hustbaer

Ja Blubb.

Die C++ Std.Lib. macht diverse Vorgaben, die es nahezu bis gänzlich unmöglich machen eine performante Implementierung zu schreiben. Iostreams ist ein gutes Beispiel - das ganze Streambuffer Interface, die Locales etc.

Die Behauptung dass eine C++ Std.Lib. Implementierung gleich schnell (oder schneller) sein kann, wie (als) "vergleichbarer" C-Code, ist daher mMn. sinnlos oder falsch.
Sinnlos wenn man eine sinnlose Definition von "vergleichbarem" C-Code verwendet (die z.B. keinen C-Code erlaubt, der Features die nicht benötigt werden einfach weglässt).
Und falsch wenn man eine sinnvolle Definition von "vergleichbarem" C-Code verwendet.

Wer das anders sieht soll es anders sehen, ich bin die Diskussion ziemlich leid.

Blubb.

Nexus

SeppJ schrieb:

Es kommt schließlich jeden Monat jemand daher der die MSVC-STL mit C vergleicht und sich wundert warum diese im Releasemodus so langsam ist.

Und bemerkenswert ist auch, dass nur 95% dieser Leute vergessen, die Debug-Laufzeitumgebung und _SECURE_SCL abzuschalten. Ja, im Release-Modus.

Aber trotzdem ein guter Grund für einen Microsoft-Flame.

camper

It0101 schrieb:

@HustBaer:

Deine Aussage widerspricht aber der landläufigen Meinung im C++-Forum dass absolut nichts aber auch garnichts schneller ist, als die STL ( in jeglicher Form der Implementierung ) und was man auf keinen Fall tun sollte, ist irgendwelche Dinge, auf keinen Fall Container, selber zu programmieren... Auf gar keinen Fall!!!

[Vorsicht, dieser Beitrag könnte ein gewisses Maß an Ironie enthalten]

Es ist tatsächlich schwer vorstellbar, dass das Programm schneller fertig wird, wenn zuerst grundlegende Datenstrukturen wie Container selbst entwickelt werden müssen.

Dobi

Hab gerade mal getestet, wie VC++ (2005 Express) Vektoren mit Iteratoren umsetzt, und mir die Assemblerausgabe angeguckt (release, mit Optimierungen, kein secure_sonstwas_Brei).

#include <vector>
#include <iostream>
using namespace std;
int main() {

    int csize = 10000;
    int* c = (int*) malloc (csize*sizeof(int));
    int* cend = c + csize;
    int sc = 0;
    for( int* ip = c; ip < cend; ++ip )
        sc += *ip;
    printf("%d", sc);
    free(c);

    typedef vector<int> TV;
    TV cpp(10000);
    int scpp(0);
    for( TV::const_iterator it( cpp.begin() ); it != cpp.end(); ++it )
        scpp += *it;
    cout << scpp << endl;

    return 0;
}

; Line 10
    cmp    esi, edx
    jae    SHORT $LN4@main
    npad    4
$LL6@main:
; Line 11
    add    ecx, DWORD PTR [eax]
    add    eax, 4
    cmp    eax, edx
    jb    SHORT $LL6@main
$LN4@main:

; Line 18
    mov    esi, DWORD PTR _cpp$[esp+52]
    mov    edx, DWORD PTR _cpp$[esp+56]
    xor    ecx, ecx
    cmp    esi, edx
    mov    eax, esi
    je    SHORT $LN1@main
    npad    4
$LL24@main:
; Line 19
    add    ecx, DWORD PTR [eax]
    add    eax, 4
    cmp    eax, edx
    jne    SHORT $LL24@main
$LN1@main:

Zumindest für die Schleife (ohne Initialisierung) ist hier komplett das selbe bei rausgekommen (Line 11 und Line 19).
Wie das bei komplexeren Geschichten aussieht, weiß ich nicht. Ich bin aber oft überrascht, was Compiler so für Optimierungen hinbekommen.
Zur Streamfrage kann ich leider nix beitragen.

SeppJ

Dobi schrieb:

Wie das bei komplexeren Geschichten aussieht, weiß ich nicht. Ich bin aber oft überrascht, was Compiler so für Optimierungen hinbekommen.

Abgesehen davon dass Compiler dabei wirklich gut sind, gibt's da auch nicht mehr viel zu tun. Wie schon gesagt, wenn man keine Laufzeitprüfungen mehr hat ist ein vector-Iterator effektiv ein Pointer mit Syntaxzucker. Und von Syntaxzucker bleibt beim Compileren nichts übrig.

krümelkacker

vector<T>::const_iterator könnte bei Dobis Test auch ein Alias für T const* gewesen sein. Das müsste man mal nachprüfen. In dem Fall wäre es nämlich gar keine besondere Optimierungsleistung.