Iteratoren langsam? Vorteile?



  • Hallo,

    ich habe ein Programm dass ich profile.
    Ich bemerke dass nahezu 80% meiner Zeit auf iteratoren drauf gehen.
    Jetzt würde ich gerne wissen ob iteratoren aus der stl von haus aus etwas langsamer sind und wenn ja - warum?

    Das würde bedeuten bei statischen konstrukten immer mit array und festen grössen zu arbeiten um möglichst shcnell zu bleiben - stimmt das?

    Worin liegen denn dann die vorteile in iteratoren? Dass sie nicht über die array-grenzen hinaus schießen?

    Danke euch 🙂



  • Zunächst mal die Frage: Langsamer als was?
    Zweite Frage: Du hast aber schon im Release-Modus kompiliert?

    Denn einige STL-Implementierungen haben im Debug-Modus tolle Sicherheitsüberprüfungen eingebaut, die im Release-Modus wegfallen. In vielen Implementierungen sind zum Beispiel die Iteratoren von vector<T> einfach T*, also genauso schnell wie normale Zeiger.

    Der wesentliche Vorteil von Iteratoren ist, daß sie eine Abstraktion vom Container schaffen und so Algorithmen auf ihnen unbekannten Containern arbeiten können. Die meisten Iteratoren bieten keine zusätzlichen Checks, obwohl das natürlich möglich wäre.



  • langsamer als statische arrays mein ich.

    Ich compiliere nicht im debug modus. ganz "normal" so wies dann im ergebnis laufen sollte...



  • Also eigentlich sollte ein std::vector nicht langsamer sein als ein statisches Array (es sei denn Du nutzt exzessiv, daß der vector wachsen kann, das bezahlt man natürlich). Bei ner std::list kann das natürlich ganz anders aussehen.

    Kannst Du vielleicht ein bißchen konkreter werden was Du tust, oder vielleicht nen kleinen Codeausschnitt posten?



  • Benutzt du Visual C++? Dort habe ich festgestellt das zum Beispiel

    std::string s = ...;
    std::vector<char> v(s.begin(), s.end());
    

    viel langsamer ist als

    std::vector<char> v(&s[0], &s[s.length()]);
    


  • mit dem iterator ein array duchgehen sollte schneller sein als mit [], da der iterator doch dem pointer entspricht.

    Halloween | ISBN: 3526520887



  • Naja, auf jeden Fall keine "checked" iteratoren verwenden, gelle 🙂
    Mach mal den hier in dein Programm rein wenn du MSVC 8 verwendest:

    #define HLP1(x) HLP2(x)
    #define HLP2(x) HLP3(#x)
    #define HLP3(x) x
    #pragma message("_SECURE_SCL: " HLP1(_SECURE_SCL))
    

    Wenn da was anderes als "_SECURE_SCL: 0" steht dann is klar was faul ist.

    MSDN schrieb:

    _SECURE_SCL
    If defined as 1, unsafe iterator use causes a runtime error. If defined as 0, checked iterators are disabled. The exact behavior of the runtime error depends on the value of _SECURE_SCL_THROWS. The default value for _SECURE_SCL is 1, meaning checked iterators are enabled by default.

    Die Schweine nämlich. Das is im Release auch defaultmässig 1 (habs grad noch extra ausprobiert). Hmpf. 😡



  • mit dem iterator ein array duchgehen sollte schneller sein als mit [], da der iterator doch dem pointer entspricht.

    Ja erstens geht hier eh niemand mit [] spazieren, und zweitens stimmt das nicht unbedingt weil Compiler gottseidank schli-schla-schlau sind und ganz gut optimieren können. Aus einem...

    int lala[100];
    // ...
    for(unsigned i = 0; i < 100; i++)
        lala[i] += 123;
    

    ...wird im generierten Code ganz schnell eine Schleife mit "walking pointer" und "pointer != end" als Abbruchbedingung. Selbst schon gesehen, kannste mir glauben 😉



  • also is es schneller als [], nur weil der compiler möglicher weise beim optimeren das gleiche draus macht is [] nicht genauso schnell



  • Nur so als Anmerkung am Rande: nur weil 80% deiner Zeit bei der Arbeit mit Iteratoren drauf gehen, heißt das nicht, dass da etwas faul ist, wenn dein Programm eben so ausschaut, dass viel mit Iteratoren (lies: Zeigern) arbeitet.
    Normal sollte der Unterschied zwischen einem Zeiger und einem Iterator kaum spürbar sein bis gar nicht spürbar sein.



  • @lolz: er schreibt aber schon dass es langsamer ist. Was soll dann der Hinweis dass es nicht langsamer sein muss?!? Keks 🙂
    Und z.B. checked iterator sind langsam, das sollte auch jedem klar sein. Genauso wie z.B. iterator von std::deque<T>.

    @dingens: Jajablabla. Aber sag mal, wo hier siehst du bitte jmd. der über nen array/vector mit [] drübergeht? (Meine Antwort auf dein Posting natürlich ausgenommen)
    Also ich finde das in dem Thread hier nicht.



  • hustbaer schrieb:

    Die Schweine nämlich. Das is im Release auch defaultmässig 1 (habs grad noch extra ausprobiert). Hmpf. 😡

    Die Release-Version beim VC 2005 ist generell nicht so sehr auf optimiale Performanz aus wie das früher der Fall war. Es werden z.B. trotzdem Debug-Symbol generiert und einige Sicherheitschecks bleiben auch an (z.B der Buffer-Security-Check). Man kann da also noch einiges rausholen. Auf der anderen Seite ist die Release-Konfiguration für die meisten Programme in meinen Augen ein guter Kompromiss zwischen Performanz und Sicherheit.



  • schon mal danke...vielleicht könnt ihr mir ja dann ein wenig helfen bei meinem optimierungsproblem...

    also vorweg: ich arbeite mit debian linux mit kdevelop3
    Compiler: gcc3.4.3 (ich weiß - net der neueste)

    Funktionsweise:
    Ich habe eine Matrix in einem vector gespeichert. Die werte sind von oben nach unten und nicht wie üblich von links nach rechts gespeichert - d.h. sie ist SPALTENWEISE gespeichert - d.h. zuerst die werte der ersten spalte, dann der zweiten usw.
    Jetzt möchte ich alle ZEILEN der matrix löschen in denen ALLE einträge Null sind. Dies ist schwieriger weil ich ja Spaltenweise gespeichert habe - daran ist leider nix zu ändern.

    Mein versuch im moment ist dieser:

    void 
     myClass::Lösche_alle_Nullzeilen(std::vector< double >& matrix, 
                           int& x_dim, 
                           int& y_dim, 
                           const int col, 
                           int& idx) 
     { 
         std::vector< bool >     mask( y_dim ); 
    
         for ( int y = 0; y < y_dim; ++y ) 
         { 
             mask[ y ] = true; 
             if(y == col) 
             { 
                 mask[ y ] = false; 
                 continue; 
             } 
             for ( int x = 0; x < x_dim; ++x ) 
             { 
                 if ( matrix[ x * y_dim + y ] != 0 ) 
                 { 
                     mask[ y ] = false; 
                     break; 
                 } 
             } 
         } 
    
         matrix.erase( std::remove_if( matrix.begin(), 
                       matrix.end(), 
                       IS_MASKED( matrix, mask ) ), 
         matrix.end() ); 
    
         y_dim = matrix.size() / x_dim;     
     } 
    
     //das struct sieht so aus: 
     struct IS_MASKED 
     { 
         std::vector< bool > mask_; 
         const std::vector< double >* erase_el_; 
    
         IS_MASKED(const std::vector< double >& erase_el, 
                   const std::vector< bool >& mask) : erase_el_( &erase_el ), 
                                                      mask_( mask ) 
         { 
         } 
    
         bool operator()(const double& f) const 
         { 
             return mask_[ ( &f - &*erase_el_->begin() ) % mask_.size() ]; 
         } 
     };
    

    leider wie gesagt dauert das zu lange. Laut meinem callgraphen fressen die iteratoren die meiste Zeit weg - und das aus dieser obigen funktion. Das bedeutet doch aber dass nur das hier:

    matrix.erase( std::remove_if( matrix.begin(), 
                       matrix.end(), 
                       IS_MASKED( matrix, mask ) ), 
         matrix.end() );
    

    für das löschen verantworlich sein kann da nirgendwo sonst iteratoren in dieser funktion verwendet werden....

    für änderungsvorschläge oder auch ideen wie man es besser realisieren könnte bin ich sehr dankbar!!!



  • Was passiert denn, wenn Du einfach mal pointer verwendest, zumindest für den remove-teil? Also statt v.begin() ein &*v.begin() und statt v.end() ein &*v.begin()+v.size() Oder sowas. Achtung, funktioniert so natürlich nicht, wenn der vector leer ist. Das ist aber bei ner Matrix sowieso nicht sinnvoll.


Log in to reply